Assortativitet

Assortativitet , eller assortativ blanding , er netværksknudernes præference for at slutte sig til andre noder, der på en eller anden måde ligner dem. Selvom det specifikke mål for lighed kan variere, undersøger netværksteoretikere ofte assortativitet i form af nodegrader . [1] Tilføjelse af denne egenskab til netværksmodeller tillader ofte mere nøjagtige tilnærmelser af adfærden for mange rigtige netværk.

Korrelationer mellem noder af lignende grader findes ofte i blandingsmønstrene i mange observerede netværk. For eksempel i sociale netværk har noder en tendens til at forbinde til andre noder med lignende gradværdier. Denne tendens omtales som assortativ blanding eller assortativitet . På den anden side udviser teknologiske og biologiske netværk typisk disassortativ blanding eller disassortativitet , da noder med høje grader har tendens til at slutte sig til noder med lave grader. [2]

Dimension

Assortativitet implementeres ofte i praksis som en sammenhæng mellem to noder. Der er dog flere måder at vurdere en sådan sammenhæng på. De to vigtigste mål er assortativitetsfaktoren og naboforbindelse . Disse tiltag diskuteres mere detaljeret nedenfor.

Assortativ faktor

Assortativitetskoefficienten er Pearson-korrelationskoefficienten for graden mellem par af forbundne noder. [2] Positive værdier af r angiver korrelationer mellem noder af lignende grader, og negative værdier angiver forhold mellem noder af forskellige grader. Generelt ligger r mellem −1 og 1. Når r = 1, siges netværket at have perfekte assortative blandingsmønstre, når r = 0 er netværket ikke-assortativt, og når r = −1 er netværket fuldstændig disassortativt .

Assortativitetskoefficienten er givet ved formlen: , hvor er fordelingen af restgrader (restgrad) . Det fastsætter antallet af kanter, der udgår fra en node, bortset fra en kant, der forbinder parret. Denne fordeling fås fra strømfordelingen som . Endelig betegner den fælles fordeling af de resterende grader af to hjørner. Dette tal er symmetrisk for en urettet graf og følger summeringsreglerne: og . ${\displaystyle r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k))}}{\sigma _{q}^{2))))$ ${\displaystyle q_{k))$ $p_{{k}}$ ${\displaystyle q_{k}={\frac {(k+1)p_{k+1)){\sum _{j\geq 1}jp_{j))))$ ${\displaystyle e_{jk))$ $\sum _{jk}{e_{jk}}=1\,$ $\sum _{j}{e_{jk}}=q_{k}\,$

I en rettet graf måler in-assortativitet ( ) og ud-assortativitet ( ) knudernes tendens til at forbinde til andre knudepunkter, der har tilsvarende ind- og ud-grader, henholdsvis. [4] [5] I forlængelse heraf kan fire typer assortativitet overvejes (se [4] [6] ). Med konventionerne i denne artikel er det muligt at definere fire metrics: , , , og . Lad det være et af ordparrene ind / ud (for eksempel ). Lad dette være antallet af kanter i netværket. Antag, at vi har nummereret netværkets kanter som . Givet en kant med tal , lad - være graden af kilden (for eksempel hale ) af kantens knudepunkt, og - være graden af målknuden (dvs. hovedet ) af den -te kant. Vi betegner gennemsnitsværdierne med en søjle, så og er gennemsnitsværdierne - henholdsvis kildernes grad og målene - graden af mål; gennemsnittet tages langs netværkets kanter. Endelig har vi: $r({\text{in)),{\text{in)))$ $r({\text{out)),{\text{out)))$ $r({\text{in)),{\text{in)))$ $r({\tekst{ind)),{\tekst{ud)))$ $r({\text{out)),{\text{in)))$ $r({\text{out)),{\text{out)))$ $(\alpha ,\beta )$ $(\alpha ,\beta )=({\tekst{ud)),{\tekst{ind)))$ $E$ $1,\ldots ,E$ $jeg$ $j_{i}^{\alpha }$ $\alfa$ $k_{i}^{\beta }$ $\beta$ $jeg$ ${\displaystyle {\bar {j^{\alpha ))))$ ${\displaystyle {\bar {k^{\beta ))))$ $\alfa$ $\beta$

$r(\alpha ,\beta )={\frac {\sum _{i}(j_{i}^{\alpha}-{\bar {j^{\alpha ))})(k_{i }^{\beta}-{\bar {k^{\beta }}})}{{\sqrt {\sum _{i}(j_{i}^{\alpha}-{\bar {j^{ \alpha ))})^{2))}{\sqrt {\sum _{i}(k_{i}^{\beta }-{\bar {k^{\beta ))})^{2} }}}}.$

Naboforbindelse

En anden måde at evaluere gradkorrelation på er at studere egenskaberne for eller den gennemsnitlige grad af en nodes naboer med grad k . [8] Formelt defineres dette som: , hvor er den betingede sandsynlighed for , at en kant af en node med grad k peger på en node med grad k' . Hvis denne funktion er stigende, så er netværket assortativt, da det viser, at højgradsknuder i gennemsnit forbinder højgradsknuder. Omvendt, hvis funktionen er faldende, så er netværket disassortativt, da højere grads noder har tendens til at forbinde til lavere grad noder. Funktionen kan tegnes på en graf (se figur 2) for at vise det generelle mønster af assortativitet i netværket. $\langle k_{nn}\rangle$ ${\displaystyle \langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k)))$ $P(k'|k)$

Lokal assortativitet

Assortative netværk kan have disassortative noder og omvendt. Et mål for lokal assortativitet [9] er påkrævet for at opdage sådanne anomalier i netværk. Lokal assortativitet er defineret som det bidrag, hver node yder til netværkets assortativitet. Lokal assortativitet i ikke-retningsbestemte netværk er defineret som:

$\rho ={\frac {j\ \left(j+1\right)\left({\overline {k))-\ {\mu }_{q}\right)}{2M{\sigma }_{q}^{2}}}$

Hvor er den overskydende grad af en bestemt knude, er den gennemsnitlige overskydende grad af dens naboer, og M er antallet af links i netværket. $j$ $\overline{k}$

Følgelig er lokal assortativitet i rettede netværk [5] nodens bidrag til netværkets rettede assortativitet. En nodes bidrag til et rettet netværks assortativitet er defineret som: $r_{d}$ ${\displaystyle {\rho }_{d}=\ {\frac {{j_{out}}^{2}\left({\overline {k}}_{in}-\ {\mu }_{q }^{in}\right)+\ {j_{in}}^{2}\left({\overline {k}}_{out}-\ {\mu }_{q}^{out}\right )}{2\ M{\sigma }_{q}^{in}{\sigma }_{q}^{out))))$

Hvor er ud-graden af den pågældende node, er in-graden, er den gennemsnitlige in-grad af dens naboer (til hvilke noder har den }-te node en kant), og er den gennemsnitlige ud-grad af dens naboer (hvoraf knudepunkter har den -te knude en kant). , . $j_{out}$ ${\displaystyle j_{in))$ ${\overline {k}}_{in}$ $v$ ${\overline {k}}_{out}$ $v$ ${\sigma }_{q}^{in}\ \neq 0$ $\ {\ \sigma }_{q}^{out}\ \neq 0$

Ved at inkludere skaleringsvilkårene og sikrer vi, at den lokale assortativitetsligning for det rettede netværk opfylder betingelsen . ${\displaystyle {\sigma }_{q}^{in))$ ${\ \sigma }_{q}^{out}$ $r_{d}=\ \sum _{i=1}^{N}({\rho }_{d))$

Ydermere, afhængigt af om man betragter en in-grad eller en ud-grad, er det muligt at definere lokal in-assortativitet og lokal ud-assortativitet som de tilsvarende mål for lokal assortativitet i et rettet netværk. [5]

Assortative blandingsmønstre i rigtige netværk

Assortative mønstre for en række af virkelige netværk er blevet undersøgt. For eksempel i fig. 3 lister r værdier for flere netværk. Bemærk, at sociale netværk (de første fem linjer) har indlysende assortativ blanding. På den anden side viser alle teknologiske og biologiske netværk (midterste seks rækker) sig at være disassortative. Dette antages at skyldes, at de fleste netværk har en tendens til at udvikle sig, hvis ikke på anden måde begrænses, hen imod en tilstand af maksimal entropi - hvilket normalt er disassortivt. [ti]

Tabellen viser også r-værdierne beregnet analytisk for to netværksmodeller:

tilfældig graf over Erdős - Renyi ;
Barabashi-Albert model .

I Erdős-Rényi-modellen, da kanterne er tilfældigt fordelt, uanset toppunktsgrader, er resultatet, at r = 0 i grænsen for stor grafstørrelse. Den skalaløse Barabashi-Albert-model bevarer også denne egenskab. For Barabashi-Albert-modellen, i det specielle tilfælde med m=1 (hvor hver ny node er knyttet til kun en af de eksisterende noder med en sandsynlighed proportional med graden), får vi begge i grænsen for stor . [2] $r\to 0$ $(\log ^{2}N)/N$ $N$

Ansøgninger

Assortativitetsegenskaber er nyttige inden for epidemiologi, fordi de hjælper med at forstå spredningen af sygdomme eller lægemidler. For eksempel kan fjernelsen af en del af netværkets knudepunkter svare til helbredelse, vaccination eller karantæne af individer eller celler. Fordi assortativ blanding forekommer i sociale netværk, er sygdomme, der påvirker højkvalitetsindivider, mere tilbøjelige til at sprede sig til andre højkvalitetsknuder. I modsætning hertil kan vaccinationsstrategier, der specifikt retter sig mod høje graders hjørner, hurtigt ødelægge et epidemisk netværk i cellulære netværk - der ligesom biologiske netværk sandsynligvis vil være disassortive.

Strukturel disassortativitet

Den underliggende struktur af netværket kan få disse målinger til at indikere disassortativitet, der ikke svarer til faktisk assortativ eller disassortativ blanding. Der skal udvises særlig omhu for at undgå strukturel disassortering.

Se også

Assortativ blanding
Fortrinsret tilknytning
Homofili
Strukturel afskæring
Rig klubkoefficient

Links

↑ Newman, MEJ (27. februar 2003). "Blanding af mønstre i netværk". Fysisk gennemgang E. American Physical Society (APS). 67 (2): 026126. arXiv : cond-mat/0209450 . Bibcode : 2003PhRvE..67b6126N . DOI : 10.1103/physreve.67.026126 . ISSN 1063-651X .
↑ 1 2 3 4 Newman, MEJ (28. oktober 2002). "Assortativ blanding i netværk". Fysiske anmeldelsesbreve . American Physical Society (APS). 89 (20): 208701. arXiv : cond-mat/0205405 . Bibcode : 2002PhRvL..89t8701N . DOI : 10.1103/physrevlett.89.208701 . ISSN 0031-9007 . PMID 12443515 .
↑ Xulvi-Brunet, R.; Sokolov, I. M. (2005). "Ændring af sammenhænge i netværk: assortativitet og dissortativitet" . Acta Physica Polonica B. 36 (5): 1431. Arkiveret fra originalen 2021-05-09 . Hentet 2021-05-09 . Forældet parameter brugt |deadlink=( hjælp )
↑ 1 2 Braha, D.; Bar-Yam, Y. (2007). "Den statistiske mekanik ved kompleks produktudvikling: Empiriske og analytiske resultater" Arkiveret 14. februar 2021 på Wayback Machine . ledelsesvidenskab. 53(7): 1127-1145.
↑ 1 2 3 Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). "Assortativ blanding i rettede biologiske netværk". IEEE/ACM-transaktioner om beregningsbiologi og bioinformatik . 9 (1): 66-78. DOI : 10.1109/TCBB.2010.80 . PMID 20733240 .
↑ Foster, Jacob; David V. Foster; Peter Grassberger; Maya Paczuski (juni 2010). "Kantretning og netværks struktur" . Proceedings of the National Academy of Sciences . 107 (24): 10815-20. arXiv : 0908.4288 . Bibcode : 2010PNAS..10710815F . DOI : 10.1073/pnas.0912671107 . PMC2890716 . _ PMID20505119 . _
↑ Lee, Sang Hoon; Kim, Pan-Jun; Jeong, Hawoong (4. januar 2006). "Statistiske egenskaber for stikprøvenetværk" . Fysisk gennemgang E. American Physical Society (APS). 73 (1): 016102. arXiv : cond-mat/0505232 . DOI : 10.1103/physreve.73.016102 . ISSN 1539-3755 . Arkiveret fra originalen 2017-09-21 . Hentet 2021-05-09 . Forældet parameter brugt |deadlink=( hjælp )
↑ Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). "Internettets dynamiske og korrelationsegenskaber". Fysiske anmeldelsesbreve . American Physical Society (APS). 87 (25): 258701. arXiv : cond-mat/0105161 . Bibcode : 2001PhRvL..87y8701P . DOI : 10.1103/physrevlett.87.258701 . ISSN 0031-9007 . PMID 11736611 .
↑ Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). "Lokal assortativitet i skalafrie netværk". EPL (Europhysics Letters) . 84 (2): 28002. Bibcode : 2008EL.....8428002P . DOI : 10.1209/0295-5075/84/28002 .
↑ Johnson, Samuel; Torres, Joaquin J.; Marro, J.; Muñoz, Miguel A. (11. marts 2010). "Entropisk oprindelse af disassortativitet i komplekse netværk". Fysiske anmeldelsesbreve . American Physical Society (APS). 104 (10): 108702. arXiv : 1002.3286 . Bibcode : 2010PhRvL.104j8702J . DOI : 10.1103/physrevlett.104.108702 . ISSN 0031-9007 . PMID 20366458 .