Modulaarisuus (verkkotiede)

Modulaarisuus on yksi verkkojen tai graafien rakenteen mitta . Mittaus on kehitetty mittaamaan verkon moduuleihin (ryhmiksi, klustereiksi tai yhteisöiksi) jakautumisen vahvuutta. Verkoissa, joissa on korkea modulaarisuus, on tiiviit linkit moduulien sisällä olevien solmujen välillä, mutta heikkoja linkkejä eri moduulien solmujen välillä. Modulaarisuutta käytetään usein optimoitaessa menetelmiä yhteisörakenteen verkostoissa. Modulaarisuuden on kuitenkin osoitettu olevan resoluutioraja-ongelma, joten tämä mittaus ei pysty erottamaan pieniä yhteisöjä. Biologiset verkot, mukaan lukien eläinten aivot, osoittavat suurta modulaarisuutta.

Motivaatio

Monia tärkeitä tieteellisiä ongelmia voidaan esittää ja kokeellisesti tutkia verkostojen avulla. Esimerkiksi biologiset ja sosiaaliset rakenteet, World Wide Web , metaboliset verkot , ravintoverkot , hermoverkot ja patologiset verkostot ovat todellisen maailman ongelmia, jotka voidaan matemaattisesti esittää ja tutkia topologisesti joidenkin odottamattomien rakenteellisten ominaisuuksien paljastamiseksi [1] . Useimmilla näistä verkoista on tietty rakenne, jolla on suuri merkitys verkkodynamiikan rakentamiselle ja ymmärtämiselle. Esimerkiksi tiiviisti yhdistetty sosiaalinen yhteisö johtaa nopeampaan tiedon tai huhujen välittämiseen kuin löyhästi kytketty yhteisö. Sitten, jos verkkoa edustaa joukko yksittäisiä solmuja, jotka on yhdistetty linkeillä, jotka ilmaisevat solmujen tietyn tason, yhteisöt määritellään tiiviisti vuorovaikutteisten solmujen ryhmiksi, jotka ovat löyhästi yhteydessä muuhun verkkoon. Siksi voi olla äärimmäisen tärkeä tehtävä määrittää yhteisöjä verkossa, koska yhteisöillä voi olla täysin erilaisia ominaisuuksia kuin keskiverkolla, kuten solmuaste , klusterointikerroin , välitysaste , keskeisyys [2] , jne. Modulaarisuus on yksi tällainen toimenpide, jonka maksimointi johtaa yhteisöjen syntymiseen tiettyyn verkkoon.

Määritelmä

Modulaarisuus on yhtä suuri kuin niiden reunojen osuus reunojen kokonaismäärästä, jotka kuuluvat annettuihin ryhmiin, miinus niiden reunojen odotettu osuus, jotka kuuluisivat samoihin ryhmiin, jos ne jakautuisivat satunnaisesti. Modulaarisuuden arvo on välissä [3] . Modulaarisuus on positiivinen, jos ryhmien reunojen määrä saavuttaa odotetun määrän. Tietyllä verkkosolmujen osiolla joihinkin moduuleihin modulaarisuus heijastaa linkkien keskittymistä moduuleissa verrattuna linkkien satunnaiseen jakautumiseen kaikkien solmujen välillä kiinnittämättä huomiota moduuleihin. $[-1,1]$

Modulaarisuuden laskemiseen on useita menetelmiä [1] . Yleisimmin hyväksytyssä käsitteen versiossa reunat satunnaistetaan siten, että kunkin kärjen aste säilyy. Tarkastellaan graafia, jossa on solmuja , linkkejä ja ( reunat ) siten, että se voidaan jakaa kahdeksi yhteisöksi yhteisön jäsenyysmuuttujan avulla. Jos solmu kuuluu yhteisöön 1, ja jos se kuuluu yhteisöön 2, . Esitetään verkon viereisyysmatriisi matriisilla , jossa tarkoittaa, että solmujen ja välillä ei ole reunaa (ei yhteyttä) , ja tarkoittaa, että reuna on olemassa. Lisäksi pidämme verkkoa yksinkertaisuuden vuoksi ohjaamattomana. Sitten . (On tärkeää huomata, että yleisessä tapauksessa kahden solmun välillä voi olla useita reunoja, mutta otamme yksinkertaisin tapauksen). $n$ $m$ $s$ $v$ $s_{v}=1$ $v$ $s_{v}=-1$ $A$ $A_{vw}=0$ $v$ $w$ $A_{vw}=1$ $A_{vw}=A_{wv}$

Q:n modulaarisuus määritellään ryhmiin 1 tai 2 kuuluvien reunojen osuutena miinus ryhmien 1 ja 2 reunojen odotettu määrä satunnaisessa graafissa, jolla on sama solmuastejakauma kuin tietyssä verkossa.

Odotettu reunojen lukumäärä voidaan laskea käyttämällä konfiguraatiomallikonseptia [4] . Konfigurointimalli on tietyn verkon satunnaistettu toteutus. Kun otetaan huomioon solmuverkko, jossa jokaisella solmulla on aste , konfigurointimalli leikkaa jokaisen reunan kahteen puolikkaaseen, ja sitten jokainen reunan puolisko, jota kutsutaan tyngiksi , liittyy satunnaisesti jokaiseen toiseen verkon osaan (paitsi itseensä), jopa sallien silmukat. (mikä tapahtuu, kun tynkä muodostaa yhteyden toiseen tynkään samassa solmussa) ja useita reunoja saman solmuparin välillä. Silloin, vaikka graafin solmuaste säilyisikin, konfiguraatiomalli johtaa täysin satunnaiseen verkkoon. $n$ $v$ ${\displaystyle k_{v))$

Odotettu reunojen lukumäärä solmujen välillä

Tarkastellaan nyt kahta solmua v ja w asteilla ja vastaavasti satunnaisesti siirretyistä linkeistä, kuten yllä on kuvattu. Laskemme näiden solmujen välisten kokonaisten reunojen odotetun määrän. ${\displaystyle k_{v))$ ${\displaystyle k_{w))$

Olkoon kantojen kokonaismäärä verkossa : $l$

l=\sum _{u}k_{u}=2m

(yksi)

Tarkastellaan kutakin solmun v tyngiä ja luo niille assosiatiiviset indikaattorimuuttujat , , c , jos i:s tynkä liittyy johonkin solmun w tyngystä tässä satunnaisessa graafissa. Jos ei, arvo on 0. Koska v :n i:s tynkä voidaan yhdistää mihin tahansa jäljellä olevista tyngistä yhtä suurella todennäköisyydellä ja koska on tyngejä, jotka liittyvät w :ään , on selvää, että ${\displaystyle k_{v))$ $I_i$ ${\displaystyle i=1,\ldots ,k_{v))$ $I_{i}=1$ ${\displaystyle k_{w))$ $2m-1$ ${\displaystyle k_{w))$

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

Solmujen v ja w välisten täydellisten reunojen kokonaismäärä on silloin , joten odotusarvo on ${\displaystyle J_{vw))$ $J_{vw}=\sum _{i}^{k_{v}}I_{i}$

E[J_{vw}]=E[\sum _{i}I_{i}]=\sum _{i}^{k_{v}}E[I_{i}]={\frac { k_{v}k_{w}}{2m-1}}

Monissa artikkeleissa seuraava likiarvo on tehty satunnaisille verkoille, joissa on suuri määrä reunoja. Jos m on suuri, pudota yhden vähennys edellä olevan kaavan nimittäjästä ja käytä yksinkertaisesti yksinkertaisempaa approksimaatiota kahden solmun välisten reunojen odotettuun lukumäärään. Lisäksi suuressa satunnaisessa verkossa silmukoiden ja useiden reunojen määrä on häviävän pieni. Silmukoiden ja useiden reunojen huomioimatta jättäminen viittaa siihen, että kahden solmun välillä on enintään yksi reuna. Tässä tapauksessa siitä tulee binäärinen indikaattorimuuttuja, jolloin sen odotusarvo on yhtä suuri kuin todennäköisyys, että muuttuja saa arvon 1, mikä tarkoittaa, että solmujen v ja w välisen reunan todennäköisyyden voidaan katsoa olevan likimäärin yhtä suuri kuin . ${\frac {k_{v}k_{w}}{2m}}$ ${\displaystyle J_{vw))$ ${\frac {k_{v}k_{w}}{2m}}$

Modulaarisuus

Siten ero solmujen välisten reunojen todellisen lukumäärän ja niiden välisten reunojen odotetun määrän välillä on $v$ $w$

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

Kaikkien parien summaaminen antaa modulaarisuuden yhtälön [1] . $K$

Q={\frac {1}{2m}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]{ \frac {s_{v}s_{w}+1}{2}}

(3)

On tärkeää huomata, että Ur. 3 toimii hyvin vain jakamiseen kahdeksi yhteisöksi. Käyttämällä hierarkkista osiointia (esimerkiksi jakamalla kahdeksi yhteisöksi ja jakamalla sitten kaksi aliyhteisöä kahdeksi pienemmäksi aliyhteisöksi Q :n maksimoimiseksi ) voidaan päästä lähelle minkä tahansa määrän yhteisöjä verkossa tunnistamista. Lisäksi (3) voidaan yleistää verkon osiointiin c yhteisöihin [5] .

Q={\frac {1}{(2m)))\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{(2m))) \right]\delta (c_{v},c_{w})=\sum _{i=1}^{c}(e_{ii}-a_{i}^{2})

(neljä)

missä e ij on niiden reunojen osuus, joiden toinen pää on yhteisössä i ja toinen yhteisössä j :

e_{ij}=\sum _{vw}{\frac {A_{vw}}{2m}}1_{v\in c_{i}}1_{w\in c_{j}}

ja a i on niiden reunan päiden osuus, jotka on yhdistetty yhteisön i kärkipisteisiin :

a_{i}={\frac {k_{i}}{2m}}=\sum _{j}e_{ij}

Esimerkki useiden yhteisöjen tunnistamisesta

Tarkastellaan suuntaamatonta verkkoa, jossa on 10 solmua ja 12 reunaa ja seuraava vierekkäisyysmatriisi.

Solmun tunnus	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen
yksi	0	yksi	yksi	0	0	0	0	0	0	yksi
2	yksi	0	yksi	0	0	0	0	0	0	0
3	yksi	yksi	0	0	0	0	0	0	0	0
neljä	0	0	0	0	yksi	yksi	0	0	0	yksi
5	0	0	0	yksi	0	yksi	0	0	0	0
6	0	0	0	yksi	yksi	0	0	0	0	0
7	0	0	0	0	0	0	0	yksi	yksi	yksi
kahdeksan	0	0	0	0	0	0	yksi	0	yksi	0
9	0	0	0	0	0	0	yksi	yksi	0	0
kymmenen	yksi	0	0	yksi	0	0	yksi	0	0	0

Kaavion yhteisöjä edustavat punaiset, vihreät ja siniset klusterin solmut kuvassa. Kuva 1. Optimaalinen jako yhteisöihin on esitetty kuvassa. 2.

Matriisiformulaatio

Vaihtoehtoinen modulaarisuuden muotoilu, joka on hyödyllinen erityisesti spektrin optimointialgoritmeissa, on seuraava [1] . Määrittele yhtä kuin 1, jos kärki v kuuluu ryhmään r , ja nolla muussa tapauksessa. Sitten ${\displaystyle S_{vr))$

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

ja näin ollen,

Q={\frac {1}{2m}}\sum _{vw}\sum _{r}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m }}\right]S_{vr}S_{wr}={\frac {1}{2m}}\mathrm {Tr} (\mathbf {S} ^{\mathrm {T} }\mathbf {BS} ),

missä S on (ei-neliö) matriisi, jossa on merkintöjä ja B on niin kutsuttu modulaarisuusmatriisi, jossa on merkintöjä ${\displaystyle S_{vr))$

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

Kaikki modulaarisuusmatriisin rivit ja sarakkeet laskevat yhteen nollaksi, mikä tarkoittaa, että jakamattoman verkon modulaarisuus on aina nolla.

Verkoille, jotka on jaettu kahteen yhteisöön, voidaan määrittää , mihin yhteisöön solmu v kuuluu , mikä johtaa $s_{v}=\pm 1$

Q={1 \over 4m}\sum _{vw}B_{vw}s_{v}s_{w}={1 \over 4m}\mathbf {s} ^{\mathrm {T} }\ mathbf {Bs} ,

missä s on sarakevektori, jossa on elementtejä [1] . ${\displaystyle s_{v))$

Tällä toiminnolla on sama muoto kuin Ising- spin glass Hamiltonin , jota käytetään luomaan yksinkertaisia tietokonealgoritmeja, kuten käyttämällä simuloitua hehkutusta modulaarisuuden maksimoimiseksi. Yleinen modulaarisuuden muoto mielivaltaiselle määrälle yhteisöjä vastaa Potts-spin-laseja ja samanlaisia algoritmeja voidaan kehittää myös tässä tapauksessa [6] .

Resoluutiorajoitus

Modulaarisuus vertaa klusterin sisällä olevien reunojen määrää odotettuun reunojen määrään, joka olisi klusterissa, jos verkko olisi satunnainen verkko, jossa on sama määrä solmuja ja jossa jokainen solmu säilyttää asteensa, mutta reunat yhdistävät solmut satunnaisesti. Tämä satunnainen graafimalli (nollamalli) olettaa eksplisiittisesti, että jokainen solmu voidaan yhdistää mihin tahansa verkon muihin solmuihin. Tämä oletus ei kuitenkaan ole käytännöllinen, jos verkko on erittäin suuri, koska solmun horisontti sisältää pienen osan verkosta jättäen huomioimatta suurimman osan verkosta. Tästä seuraa kuitenkin, että kahden solmuryhmän välisten reunojen odotettu määrä pienenee verkon koon kasvaessa. Näin ollen, jos verkko on riittävän suuri, kahden solmuryhmän välisten reunojen odotettu määrä satunnaisgraafimallin modulaarisuuden mukaan voi olla pienempi kuin yksi. Jos näin tapahtuu, yksi reuna kahden klusterin välillä voidaan tulkita modulaarisuuden kannalta merkkinä vahvasta korrelaatiosta kahden klusterin välillä, ja modulaarisuuden optimointi johtaisi kahden klusterin yhdistämiseen klustereiden ominaisuuksista riippumatta. . Siten jopa heikosti kytketyt kokonaiset graafit, joilla on suuri mahdollinen sisäreunojen tiheys ja jotka edustavat hyvin tunnistettuja yhteisöjä, voitaisiin yhdistää optimoimalla modulaarisuus, jos verkko olisi riittävän suuri [7] . Tästä syystä modulaarisuuden optimointi suurissa verkoissa ei tunnistaisi pieniä yhteisöjä, vaikka ne olisivat hyvin määriteltyjä. Tämä suuntaus on väistämätön menetelmissä, kuten modulaarisuuden optimoinnissa, jotka perustuvat globaaliin satunnaiskuvaajamalliin [8] .

Moniresoluutioiset menetelmät

On olemassa kaksi päälähestymistapaa, jotka yrittävät ratkaista ratkaisuongelman modulaarisuuden kontekstissa - lisäämällä vastus r jokaiseen solmuun silmukan muodossa , mikä lisää ( ) tai vähentää ( ) solmujen halua muodostaa yhteisöjä [9] , tai lisäämällä satunnaisen graafisen jäsenen eteen määrittelymodulaarisuuteen parametri, joka määrittää yhteisöjen sisäisten yhteyksien ja satunnaisgraafimallin välisen suhteellisen tärkeyden [6] . Modulaarisuuden optimointi näiden parametrien arvoille niiden vastaavilla aikaväleillä mahdollistaa verkon täyden mesoskaalan havaitsemisen mesoskaalalta, jossa kaikki solmut kuuluvat samaan yhteisöön, mikromittakaavaan, jossa mikä tahansa solmu muodostaa omansa. oma yhteisö, mistä johtuu moniresoluutiomenetelmien nimi . Näillä menetelmillä on kuitenkin osoitettu olevan rajoituksia, kun yhteisöt vaihtelevat suuresti [10] . $r>0$ $r<0$ $\gamma > 0$

Katso myös

Monimutkaiset verkot
Yhteisön rakenne

Muistiinpanot

↑ 1 2 3 4 5 Newman, 2006 , s. 8577–8696.
↑ Newman, 2007 .
↑ Li, Schuurmans, 2011 , s. 2.
↑ van der Hofstad, 2013 , s. 149.
↑ Clauset, Newman, Moore, 2004 , s. 066111.
↑ 1 2 Reichardt, Bornholdt, 2006 , s. 016110.
↑ Fortunato, Barthelemy, 2007 , s. 36–41.
↑ Kumpula, Saramäki, Kaski, Kertész, 2007 , s. 41–45.
↑ Arenas, Fernández, Gomez, 2008 , s. 053039.
↑ Lancichinetti, Fortunato, 2011 , s. 066122.

Kirjallisuus

Newman MEJ Modulaarisuus ja yhteisörakenne verkostoissa (englanniksi) // Proceedings of the National Academy of Sciences . - United States National Academy of Sciences , 2006. - Voi. 103 , iss. 23 . - P. 8577-8696 . - doi : 10.1073/pnas.0601602103 . - . - arXiv : fysiikka/0602124 . — PMID 16723398 .
Newman MEJ Verkostojen matematiikka // The New Palgrave Encyclopedia of Economics / Basingstoke Palgrave Macmillan. - 2007. - Ongelma. 2 .
Wenye Li, Dale Schuurmans. Modulaarinen yhteisön havaitseminen verkoissa // IJCAI Proceedings-International Joint Conference on Artificial Intelligence. - 2011. - T. 22 , no. 1 . - doi : 10.5591/978-1-57735-516-8/IJCAI11-231 .
Remco van der Hofstad. Luku 7 // Satunnaiset kuvaajat ja monimutkaiset verkot (uuspr.) . – 2013.
Aaron Clauset, Newman MEJ, Cris Moore. Yhteisörakenteen löytäminen erittäin suurissa verkostoissa // Phys. Rev. E. - 2004. - T. 70 , no. 6 . - S. 066111 . - doi : 10.1103/PhysRevE.70.066111 . - . - arXiv : cond-mat/0408187 .

Joerg Reichardt, Stefan Bornholdt. Yhteisön havaitsemisen tilastollinen mekaniikka // Physical Review E. - 2006. - Vol. 74 , no. 1 . - S. 016110 . - doi : 10.1103/PhysRevE.74.016110 . - . - arXiv : cond-mat/0603718 .
Santo Fortunato, Marc Barthelemy. Yhteisön havaitsemisen resoluutioraja (englanti) // Proceedings of the National Academy of Sciences . - United States National Academy of Sciences , 2007. - Voi. 104 , iss. 1 . - s. 36-41 . - doi : 10.1073/pnas.0605965104 . - . - arXiv : physics/0607100 . — PMID 17190818 .
Kumpula JM, Saramäki J., Kaski K., Kertész J. Rajoitettu resoluutio monimutkaisen verkkoyhteisön ilmaisussa Potts-mallilähestymistavalla // European Physical Journal B. - 2007. - V. 56 , no. 1 . - S. 41-45 . - doi : 10.1140/epjb/e2007-00088-4 . - . - arXiv : cond-mat/0610370 .
Alex Arenas, Alberto Fernández, Sergio Gomez. Monimutkaisten verkkojen rakenteen analyysi eri resoluutiotasoilla // New Journal of Physics. - 2008. - T. 10 , no. 5 . - S. 053039 . - doi : 10.1088/1367-2630/10/5/053039 . - . - arXiv : fysiikka/0703218 .
Andrea Lancichinetti, Santo Fortunato. Modulaarisuuden maksimoimisen rajat yhteisön havaitsemisessa // Physical Review E. - 2011. - T. 84 . - S. 066122 . - doi : 10.1103/PhysRevE.84.066122 . - . - arXiv : 1107.1155 .