Modülerlik (ağlar) - Modularity (networks)

Ağ bilimi
Teori
Grafik Karmaşık ağ Bulaşma Küçük dünya Ölçeksiz Topluluk yapısı Süzülme Evrim Kontrol edilebilirlik Grafik çizimi Sosyal sermaye Bağlantı analizi Optimizasyon Mütekabiliyet Kapanış Homofilik Geçişlilik Tercihli ek Denge teorisi Ağ etkisi Sosyal etki
Ağ türleri
Bilgilendirici (bilgi işlem) Telekomünikasyon Ulaşım Sosyal Bilimsel işbirliği Biyolojik Yapay sinir Birbirine bağımlı Anlamsal Mekansal Bağımlılık Akış Çip üzerinde
Grafikler
Özellikleri Clique Bileşen Kesmek Döngü Veri yapısı Kenar Döngü Semt Yol Köşe Komşuluk listesi  / matris Olay listesi  / matris Türler Bipartit Tamamlayınız Yönetmen Aşırı Çok Rastgele Ağırlıklı
Metrikler Algoritmalar
Merkeziyet Derece Arasılık Yakınlık PageRank Motif Kümeleme Derece dağılımı Çeşitlilik Mesafe Modülerlik Verimlilik
Modeller
Topoloji Rastgele grafik Erdős – Rényi Barabási-Albert Spor modeli Watt-Strogatz Üstel rastgele (ERGM) Rastgele geometrik (RGG) Hiperbolik (HGN) Hiyerarşik Stokastik blok Maksimum entropi Yumuşak konfigürasyon LFR Benchmark Dinamikler Boole ağı ajan tabanlı Epidemi /BAYIM
Listeler Kategoriler
Konular Yazılım Ağ bilimcileri Kategori: Ağ teorisi Kategori: Grafik teorisi

Modülerlik ölçümü ve renklendirme örneği ölçeksiz ağ.

Modülerlik yapısının bir ölçüsüdür ağlar veya grafikler. Bir ağın modüllere (ayrıca gruplar, kümeler veya topluluklar olarak da adlandırılır) bölünmesinin gücünü ölçmek için tasarlanmıştır. Modülerliği yüksek ağlar, modüller içindeki düğümler arasında yoğun bağlantılara sahiptir, ancak farklı modüllerdeki düğümler arasında seyrek bağlantılar vardır. Modülerlik, genellikle algılama için optimizasyon yöntemlerinde kullanılır topluluk yapısı ağlarda. Bununla birlikte, modülerliğin bir çözünürlük sınırına sahip olduğu ve bu nedenle küçük toplulukları tespit edemediği gösterilmiştir. Hayvan beyinleri dahil biyolojik ağlar, yüksek derecede modülerlik sergiler.

Motivasyon

Bilimsel olarak önemli birçok sorun, ağlar kullanılarak temsil edilebilir ve deneysel olarak incelenebilir. Örneğin, biyolojik ve sosyal modeller, World Wide Web, metabolik ağlar, besin ağları, sinir ağları ve patolojik ağlar, bazı beklenmedik yapısal özellikleri ortaya çıkarmak için matematiksel olarak temsil edilebilen ve topolojik olarak çalışılabilen gerçek dünya problemleridir.^[1] Bu ağların çoğu, ağın dinamiklerine ilişkin bir anlayış oluşturmada önemli bir öneme sahip belirli bir topluluk yapısına sahiptir. Örneğin, yakından bağlantılı bir sosyal topluluk, gevşek bir şekilde bağlı bir topluluktan daha hızlı bir bilgi aktarımı veya söylenti aktarımı anlamına gelecektir. Bu nedenle, bir ağ, düğümler arasında belirli bir etkileşim derecesini ifade eden bağlantılarla bağlanan bir dizi ayrı düğümle temsil ediliyorsa, topluluklar, ağın geri kalanıyla yalnızca seyrek olarak bağlanan yoğun şekilde birbirine bağlı düğüm grupları olarak tanımlanır. Bu nedenle, topluluklar düğüm derecesi, kümeleme katsayısı, aralık, merkezilik gibi oldukça farklı özelliklere sahip olabileceğinden, ağlardaki toplulukları tanımlamak zorunlu olabilir.^[2] vb., ortalama ağınkinden. Modülerlik, maksimize edildiğinde belirli bir ağdaki toplulukların ortaya çıkmasına yol açan böyle bir ölçüdür.

Tanım

Modülerlik, verilen gruplara düşen kenarların, kenarların rastgele dağıtılması durumunda beklenen kesirden çıkarılmasıdır. Ağırlıksız ve yönsüz grafikler için modülerliğin değeri aralıkta yatmaktadır ${displaystyle [-1 / 2,1]}$.^[3] Gruplardaki kenar sayısının şans esasına göre beklenen sayıyı aşması olumludur. Ağın köşelerinin belirli modüllere bölünmesi için modülerlik, modüllerden bağımsız olarak tüm düğümler arasındaki rastgele bağlantı dağılımına kıyasla modüller içindeki kenarların yoğunluğunu yansıtır.

Modülerliği hesaplamanın farklı yöntemleri vardır.^[1] Kavramın en yaygın versiyonunda, kenarların rasgele seçilmesi, derece her köşe için. İle bir grafik düşünün ${displaystyle n}$ düğümler ve ${displaystyle m}$ bağlantılar (kenarlar ) öyle ki grafik bir üyelik değişkeni kullanılarak iki topluluğa bölünebilir ${displaystyle s}$. Eğer bir düğüm ${displaystyle v}$ 1. topluluğa ait, ${displaystyle s_ {v} = 1}$, ya da eğer ${displaystyle v}$ 2. topluluğa ait, ${displaystyle s_ {v} = - 1}$. Bırak bitişik matris ağ için temsil edilecek ${displaystyle A}$, nerede ${displaystyle A_ {vw} = 0}$ düğümler arasında kenar (etkileşim yok) olmadığı anlamına gelir ${displaystyle v}$ ve ${displaystyle w}$ ve ${displaystyle A_ {vw} = 1}$ ikisi arasında bir kenar olduğu anlamına gelir. Ayrıca basitlik için, yönlendirilmemiş bir ağı düşünüyoruz. Böylece ${displaystyle A_ {vw} = A_ {wv}}$. (İki düğüm arasında birden çok kenarın olabileceğine dikkat etmek önemlidir, ancak burada en basit durumu değerlendiriyoruz).

Modülerlik ${displaystyle Q}$ daha sonra, verilen ağ ile aynı düğüm derece dağılımına sahip rastgele bir grafik için grup 1 veya 2'ye düşen kenarların fraksiyonu eksi grup 1 ve 2'deki beklenen kenar sayısı olarak tanımlanır.

Beklenen kenar sayısı, bir kavram kullanılarak hesaplanacaktır. konfigürasyon modeli.^[4] Yapılandırma modeli, belirli bir ağın rastgele bir şekilde gerçekleştirilmesidir. İle bir ağ verildiğinde ${displaystyle n}$ düğümler, burada her düğüm ${displaystyle v}$ düğüm derecesine sahip ${displaystyle k_ {v}}$, konfigürasyon modeli her kenarı ikiye böler ve ardından her yarım kenarı a Taslak, ağdaki diğer herhangi bir saplama ile rastgele yeniden bağlanır (kendisi dışında), hatta kendi kendine döngülere (bir saplama aynı düğümden başka bir saplamaya yeniden bağlandığında meydana gelir) ve aynı iki düğüm arasında birden çok kenara izin verir. Bu nedenle, grafiğin düğüm derecesi dağılımı bozulmadan kalsa bile, konfigürasyon modeli tamamen rastgele bir ağ ile sonuçlanır.

Düğümler Arasında Beklenen Kenar Sayısı

Şimdi iki düğümü düşünün v ve w, düğüm dereceleriyle ${displaystyle k_ {v}}$ ve ${displaystyle k_ {w}}$ sırasıyla, yukarıda açıklandığı gibi rasgele yeniden bağlanmış bir ağdan. Bu düğümler arasında beklenen tam kenar sayısını hesaplıyoruz.

Ağdaki toplam saplama sayısının ${displaystyle l}$:

${displaystyle l = toplam _ {u} k_ {u} = 2m}$

(1)

Her birini ele alalım ${displaystyle k_ {v}}$ düğüm noktaları v ve ilişkili gösterge değişkenleri oluşturun ${displaystyle I_ {i}}$ onlar için, ${displaystyle i = 1, ldots, k_ {v}}$, ile ${displaystyle I_ {i} = 1}$ i-inci saplama aşağıdakilerden birine bağlanırsa ${displaystyle k_ {w}}$ düğüm noktaları w bu belirli rastgele grafikte. Değilse, değeri 0'dır. Düğümün i-inci saplaması v herhangi birine bağlanabilir ${displaystyle 2m-1}$ eşit olasılığa sahip kalan saplamalar ve olduğu için ${displaystyle k_ {w}}$ düğüm ile ilişkili bağlanabileceği saplamalar w, belli ki

${displaystyle p (I_ {i} = 1) = E [I_ {i}] = {frac {k_ {w}} {2m-1}}}$

Toplam tam kenar sayısı ${displaystyle J_ {vw}}$ arasında v ve w sadece ${displaystyle J_ {vw} = toplam _ {i} ^ {k_ {v}} I_ {i}}$, dolayısıyla bu miktarın beklenen değeri

${displaystyle E [J_ {vw}] = E [toplam _ {i} I_ {i}] = toplam _ {i} ^ {k_ {v}} E [I_ {i}] = {frac {k_ {v} k_ {w}} {2a-1}}}$

Daha sonra birçok metin, çok sayıda kenarı olan rastgele ağlar için aşağıdaki tahminlerde bulunur. Ne zaman m büyükse, yukarıdaki paydada 1 çıkarma işlemini bırakırlar ve sadece yaklaşık ifadeyi kullanırlar ${displaystyle {frac {k_ {v} k_ {w}} {2m}}}$ iki düğüm arasındaki beklenen kenar sayısı için. Ek olarak, büyük bir rastgele ağda, kendi kendine döngülerin ve çoklu kenarların sayısı kaybolacak kadar azdır.^[5] Kendi kendine döngüleri ve çoklu kenarları göz ardı etmek, kişinin herhangi iki düğüm arasında en fazla bir kenar olduğunu varsaymasına izin verir. Bu durumda, ${displaystyle J_ {vw}}$ ikili bir gösterge değişkeni haline gelir, bu nedenle beklenen değeri aynı zamanda 1'e eşit olma olasılığıdır, bu da düğümler arasında bir kenarın var olma olasılığının yaklaşık olarak tahmin edilebileceği anlamına gelir v ve w gibi ${displaystyle {frac {k_ {v} k_ {w}} {2m}}}$.

Modülerlik

Bu nedenle, düğümler arasındaki gerçek kenar sayısı arasındaki fark ${displaystyle v}$ ve ${displaystyle w}$ ve aralarında beklenen kenar sayısı

${displaystyle A_ {vw} - {frac {k_ {v} k_ {w}} {2m}}}$

Tüm düğüm çiftlerinin toplanması, modülerlik denklemini verir, ${displaystyle Q}$.^[1]

${displaystyle Q = {frac {1} {2m}} toplam _ {vw} sol [A_ {vw} - {frac {k_ {v} k_ {w}} {2m}} ight] {frac {s_ {v} s_ {w} +1} {2}}}$

(3)

Şunu vurgulamakta yarar var Eq. 3 yalnızca iki topluluğa bölünmek için uygundur. Hiyerarşik bölümleme (yani iki topluluğa bölümleme, daha sonra iki alt topluluk, yalnızca maksimize etmek için daha küçük iki alt topluluğa bölündü. Q), bir ağdaki birden çok topluluğu tanımlamak için olası bir yaklaşımdır. Ek olarak, (3) bir ağı içine bölümlemek için genelleştirilebilir. c topluluklar.^[6]

${displaystyle Q = {frac {1} {(2m)}} toplam _ {vw} sol [A_ {vw} - {frac {k_ {v} k_ {w}} {(2m)}} ight] delta (c_ {v}, c_ {w}) = toplam _ {i = 1} ^ {c} (e_ {ii} -a_ {i} ^ {2})}$

(4)

nerede e_ij toplulukta bir uç köşesi olan kenarların kesri ben ve topluluktaki diğeri j:

${displaystyle e_ {ij} = sum _ {vw} {frac {A_ {vw}} {2m}} 1_ {vin c_ {i}} 1_ {win c_ {j}}}$

ve a_ben topluluktaki köşelere eklenen kenar uçlarının kesri ben:

${displaystyle a_ {i} = {frac {k_ {i}} {2m}} = toplam _ {j} e_ {ij}}$

Birden çok topluluk algılama örneği

10 düğümü ve 12 kenarı ve aşağıdaki bitişik matrisi olan yönlendirilmemiş bir ağı ele alıyoruz.

Şekil 1. 10 düğümlü, 12 kenarlı Bitişik matrisine karşılık gelen Örnek Ağ.

Şekil 2. Q. Maksimum Q = 0.4896'yı maksimize eden ağ bölümleri

Grafikteki topluluklar, Şekil 1'de kırmızı, yeşil ve mavi düğüm kümeleri ile temsil edilmektedir. Optimal topluluk bölümleri Şekil 2'de gösterilmektedir.

Matris formülasyonu

Özellikle spektral optimizasyon algoritmalarında faydalı olan alternatif bir modülerlik formülasyonu aşağıdaki gibidir.^[1] Tanımlamak S_vr köşe ise 1 olmak v gruba ait r ve aksi takdirde sıfır. Sonra

${displaystyle delta (c_ {v}, c_ {w}) = toplam _ {r} S_ {vr} S_ {wr}}$

ve dolayısıyla

${displaystyle Q = {frac {1} {2m}} toplam _ {vw} toplam _ {r} sol [A_ {vw} - {frac {k_ {v} k_ {w}} {2m}} ight] S_ { vr} S_ {wr} = {frac {1} {2m}} mathrm {Tr} (mathbf {S} ^ {mathrm {T}} mathbf {BS}),}$

nerede S elemanlara sahip (kare olmayan) matristir S_vr ve B modülerlik matrisi olarak adlandırılan, elemanlara sahip

${displaystyle B_ {vw} = A_ {vw} - {frac {k_ {v} k_ {w}} {2m}}.}$

Modülerlik matrisinin tüm satırları ve sütunları toplamı sıfırdır; bu, bölünmemiş bir ağın modülerliğinin de her zaman sıfır olduğu anlamına gelir.

Yalnızca iki topluluğa bölünmüş ağlar için alternatif olarak tanımlanabilir s_v = ± 1 topluluğu hangi düğüme bağladığını belirtmek için v aittir, sonra yol açar

${displaystyle Q = {1 4 milyondan fazla} toplam _ {vw} B_ {vw} s_ {v} s_ {w} = {1 4 milyondan fazla} mathbf {s} ^ {mathrm {T}} mathbf {Bs},}$

nerede s elemanlı sütun vektörü s_v.^[1]

Bu işlev, aynı biçime sahiptir. Hamiltoniyen Ising'in döner cam basit bilgisayar algoritmaları oluşturmak için kötüye kullanılmış bir bağlantı, örneğin benzetimli tavlama, modülerliği en üst düzeye çıkarmak için. Keyfi sayıda topluluk için modülerliğin genel biçimi, bir Potts döner camına eşdeğerdir ve bu durum için de benzer algoritmalar geliştirilebilir.^[7]

Çözünürlük sınırı

Modülerlik, bir küme içindeki kenarların sayısını, ağın aynı sayıda düğüme sahip rastgele bir ağ olması ve her düğümün derecesini koruduğu, ancak kenarların başka türlü rasgele eklenmiş olması durumunda kümede bulacağı beklenen kenar sayısını karşılaştırır. Bu rastgele boş model, örtük olarak her düğümün ağın diğer herhangi bir düğümüne bağlanabileceğini varsayar. Ancak bu varsayım, ağ çok büyükse mantıksızdır, çünkü bir düğümün ufku, ağın küçük bir bölümünü içerir ve çoğunu yok sayar. Üstelik, bu, iki düğüm grubu arasındaki beklenen kenar sayısının, boyutun azalması durumunda azaldığı anlamına gelir. ağ artar. Dolayısıyla, bir ağ yeterince büyükse, modülerliğin sıfır modelinde iki düğüm grubu arasında beklenen kenar sayısı birden küçük olabilir. Böyle bir durumda, iki küme arasındaki tek bir kenar, modülerlik tarafından iki küme arasındaki güçlü bir korelasyonun bir işareti olarak yorumlanacak ve modülerliğin optimize edilmesi, kümelerin özelliklerinden bağımsız olarak iki kümenin birleşmesine yol açacaktır. Dolayısıyla, iç kenarların mümkün olan en yüksek yoğunluğuna sahip olan ve en iyi tanımlanabilir toplulukları temsil eden zayıf birbirine bağlı tam grafikler bile, ağ yeterince büyük olsaydı, modülerlik optimizasyonu ile birleştirilebilirdi.^[8]Bu nedenle, büyük ağlarda modülerliği optimize etmek, iyi tanımlanmış olsalar bile küçük toplulukları çözmede başarısız olacaktır. Bu önyargı, küresel bir boş modele dayanan modülerlik optimizasyonu gibi yöntemler için kaçınılmazdır.^[9]

Çoklu çözünürlük yöntemleri

Modülerlik bağlamında çözünürlük sınırını çözmeye çalışan iki ana yaklaşım vardır: bir direncin eklenmesi r şeklinde her düğüme öz döngü, artar (r> 0) veya azalır (r <0) topluluklar oluşturmak için düğümlerden kaçınma;^[10] veya bir parametrenin eklenmesi γ> 0 toplulukların iç bağlantıları ile boş model arasındaki göreceli önemi kontrol eden modülerlik tanımındaki boş durum teriminin önünde.^[7] Bu parametrelerin değerleri için modülerliği ilgili uygun aralıklarda optimize ederek, tüm düğümlerin aynı topluluğa ait olduğu makro ölçeğinden, her düğümün kendi topluluğunu oluşturduğu mikro ölçeğe kadar ağın tüm orta ölçeğini kurtarmak mümkündür. dolayısıyla adı çoklu çözünürlük yöntemleri. Bununla birlikte, topluluklar boyut olarak çok heterojen olduğunda bu yöntemlerin sınırlamaları olduğu gösterilmiştir.^[11]

Modüler ağların süzülmesi

Modüler ağlar üzerinde süzülme teorisi birkaç yazar tarafından incelenmiştir.^[12][13]

Modüler ağlarda salgın yayılıyor

Salgının yayılması son zamanlarda modüler ağlarda (topluluklarla ağlar) incelenmiştir.^[14]Bir ülkede yayılan bir hastalık, dünya çapında potansiyel bir insani ve ekonomik etkiye sahip bir pandemi haline gelebileceğinden, dünya çapında bir pandemi olasılığını tahmin etmek için modeller geliştirmek önemlidir. Çok yeni bir örnek, Çin'de (2019'un sonunda) başlayan ve küresel olarak yayılan koronavirüstür. Bu sayfada,^[14] yapısal modüler karmaşık bir ağda (topluluklara sahip) hastalık yayılması için bir model önerildi ve toplulukları birbirine bağlayan köprü düğümlerinin sayısının hastalığın yayılmasını nasıl etkilediğini ve pandemiyi duyurmak için kriterleri incelemek.

Ayrıca bakınız

• Karmaşık ağ
• Topluluk yapısı
• Boş model
• Süzülme teorisi

Referanslar