Asortativitate

Sortativitatea , sau amestecarea asortativă , este preferința nodurilor de rețea de a se alătura altor noduri care sunt într-un fel similare cu acestea. Deși măsura specifică a similitudinii poate varia, teoreticienii rețelelor examinează adesea asortativitatea în ceea ce privește gradele nodurilor . [1] Adăugarea acestei caracteristici la modelele de rețea permite adesea aproximări mai precise ale comportamentului multor rețele reale.

Corelațiile dintre nodurile de grade similare se găsesc adesea în modelele de amestecare ale multor rețele observate. De exemplu, în rețelele sociale , nodurile tind să se conecteze la alte noduri cu valori similare. Această tendință este denumită amestecare asortativă sau asortativitate . Pe de altă parte, rețelele tehnologice și biologice prezintă în mod obișnuit amestecare dezasortată sau dezasortativitate , deoarece nodurile cu grade ridicate tind să se alăture nodurilor cu grade scăzute. [2]

Dimensiune

Sortitivitatea este adesea implementată în practică ca o corelație între două noduri. Cu toate acestea, există mai multe modalități de a evalua o astfel de corelație. Cele mai semnificative două măsuri sunt factorul de asortativitate și conectivitatea vecinilor . Aceste măsuri sunt discutate mai detaliat mai jos.

Factorul asortativ

Coeficientul de asortatibilitate este coeficientul de corelație Pearson al gradului dintre perechile de noduri conectate. [2] Valorile pozitive ale lui r denotă corelații între nodurile de grade similare, iar valorile negative denotă relații între nodurile de grade diferite. În general, r se află între −1 și 1. Când r = 1, se spune că rețeaua are modele de amestecare asortative perfecte, când r = 0 rețeaua nu este asortativă, iar când r = −1, rețeaua este complet dezasortativă. .

Coeficientul de asortativitate este dat de formula: , unde este distribuția gradelor reziduale (gradul rămas) . Fixează numărul de muchii care ies dintr-un nod, cu excepția unei muchii care conectează perechea. Această distribuție se obține din distribuția puterii ca . În cele din urmă, denotă distribuția comună a gradelor reziduale a două vârfuri. Acest număr este simetric pentru un grafic nedirecționat și urmează regulile de însumare: și . $r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k))}}{\sigma _{q}^{2)))$ $q_{k)$ $p_{{k}}$ $q_{k}={\frac {(k+1)p_{k+1)}{\sum _{j\geq 1}jp_{j))}$ $e_{jk)$ $\sum _{jk}{e_{jk}}=1\,$ $\sum _{j}{e_{jk}}=q_{k}\,$

Într-un grafic direcționat, in-asortativity ( ) și out-assortativity ( ) măsoară tendința nodurilor de a se conecta la alte noduri care au grade similare în interior și, respectiv, în exterior. [4] [5] Expandând acest lucru, pot fi luate în considerare patru tipuri de asortativitate (vezi [4] [6] ). Luând convențiile articolului respectiv, este posibil să definiți patru metrici: , , și . Fie una dintre perechile de cuvinte in / out (de exemplu, ). Fie acesta să fie numărul de margini din rețea. Să presupunem că am numerotat marginile rețelei ca . Având în vedere o muchie cu număr , fie - să fie gradul sursei (de exemplu, coada ) al vârfului nodal al muchiei și - să fie gradul nodului țintă (adică , capul ) al muchiei --a. Notăm mediile cu o bară, astfel încât și sunt mediile -gradul surselor și respectiv -gradul țintelor; mediile sunt luate de-a lungul marginilor rețelei. În sfârșit avem: $r({\text {in)),{\text {in}})$ $r({\text{out)),{\text{out}})$ $r({\text {in)),{\text {in}})$ $r({\text{in)),{\text{out}})$ $r({\text{out)),{\text{in}})$ $r({\text{out)),{\text{out}})$ $(\alpha,\beta)$ $(\alpha ,\beta )=({\text {out)),{\text {in}))$ $E$ $1,\ldots ,E$ $i$ $j_{i}^{\alpha }$ $\alfa$ $k_{i}^{\beta }$ $\beta$ $i$ ${\bar {j^{\alpha }))$ ${\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} }}}}.$

Conectivitate vecină

O altă modalitate de a evalua corelația de grad este de a studia proprietățile lui , sau gradul mediu al vecinilor unui nod cu gradul k . [8] În mod formal, aceasta este definită ca: , unde este probabilitatea condiționată ca o muchie a unui nod cu gradul k să indice un nod cu gradul k' . Dacă această funcție este în creștere, atunci rețeaua este asortativă, deoarece arată că nodurile de grad înalt se conectează, în medie, la noduri de grad înalt. În schimb, dacă funcția este în scădere, atunci rețeaua este dezasortată, deoarece nodurile de grad superior tind să se conecteze la noduri de gradul inferior. Funcția poate fi desenată pe un grafic (vezi Figura 2) pentru a arăta modelul general de asortativitate în rețea. $\langle k_{nn}\rangle$ $\langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k))$ $P(k'|k)$

Sortitivitate locală

Rețelele asortative pot avea noduri dezasortative și invers. Este necesară o măsură de asortativitate locală [9] pentru a detecta astfel de anomalii în rețele. Sortitivitatea locală este definită ca contribuția pe care fiecare nod o face la sortitivitatea rețelei. Sortitivitatea locală în rețelele nedirecționale este definită ca:

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

Unde este gradul de exces al unui anumit nod, este gradul de exces mediu al vecinilor săi și M este numărul de legături din rețea. $j$ $\overline{k}$

În consecință, asortativitatea locală în rețelele direcționate [5] este contribuția nodului la asortativitatea dirijată a rețelei. Contribuția unui nod la asortativitatea unei rețele direcționate este definită astfel: $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))))$

Unde este gradul de exterior al nodului în cauză, este gradul de intrare, este gradul de intrare mediu al vecinilor săi (la care noduri are marginea }-lea nod) și este gradul de exterior mediu al vecinii săi (din care noduri nodul --lea are o margine). , . $j_{out}$ $j_{in)$ ${\overline {k}}_{in}$ $v$ ${\overline {k}}_{out}$ $v$ ${\sigma }_{q}^{in}\ \neq 0$ $\ {\ \sigma }_{q}^{out}\ \neq 0$

Prin includerea termenilor de scalare și , ne asigurăm că ecuația de asortativitate locală pentru rețeaua direcționată satisface condiția . ${\sigma }_{q}^{in)$ ${\ \sigma }_{q}^{out}$ $r_{d}=\\sum _{i=1}^{N}({\rho }_{d))$

Mai mult, în funcție de faptul că se consideră un grad înalt sau unul în afara gradului, este posibil să se definească in-asortativitate locală și extra-asortativitate locală ca măsuri corespunzătoare de asortativitate locală într-o rețea direcționată. [5]

Modele asortative de amestecare în rețele reale

Au fost explorate modele asortative pentru o varietate de rețele din lumea reală. De exemplu, în Fig. 3 listează valorile r pentru mai multe rețele. Rețineți că rețelele sociale (primele cinci rânduri) au o amestecare asortativă evidentă. Pe de altă parte, toate rețelele tehnologice și biologice (în mijlocul șase rânduri) se dovedesc a fi dezasortitive. Se speculează că acest lucru se datorează faptului că majoritatea rețelelor tind să evolueze, dacă nu sunt altfel constrânse, către o stare de entropie maximă - care este de obicei dezasortivă. [zece]

Tabelul prezintă, de asemenea, valorile r calculate analitic pentru două modele de rețea:

grafic aleatoriu Erdős - Renyi ;
Modelul Barabashi-Albert .

În modelul Erdős-Rényi, deoarece muchiile sunt distribuite aleator, indiferent de gradele vârfurilor, rezultatul este că r = 0 în limita de dimensiune mare a graficului. Modelul fără scară Barabashi-Albert păstrează și el această proprietate. Pentru modelul Barabashi-Albert, în cazul special cu m=1 (unde fiecare nod nou este atașat doar unuia dintre nodurile existente cu o probabilitate proporțională cu gradul), obținem ambele în limita lui mare . [2] $r\la 0$ $(\log ^{2}N)/N$ $N$

Aplicații

Proprietățile de asortativitate sunt utile în domeniul epidemiologiei deoarece ajută la înțelegerea răspândirii bolilor sau a medicamentelor. De exemplu, îndepărtarea unei porțiuni din nodurile rețelei poate corespunde vindecării, vaccinării sau carantinei indivizilor sau celulelor. Deoarece amestecarea asortativă are loc în rețelele sociale, bolile care afectează indivizii de grad înalt au mai multe șanse să se răspândească la alte noduri de grad înalt. În schimb, în rețelele celulare – care, la fel ca și rețelele biologice, pot fi dezasortate – strategiile de vaccinare care vizează în mod specific vârfurile de grad înalt pot distruge rapid o rețea epidemică.

Dezasortativitate structurală

Structura de bază a rețelei poate face ca aceste metrici să indice caracterul dezasortat care nu corespunde amestecării efective asortitive sau dezasortative. Trebuie acordată o atenție deosebită pentru a evita dezasortarea structurală.

Vezi și

Amestecare asortativă
Atașament preferențial
Homofilie
Decupare structurală
Coeficient de club bogat

Link -uri

↑ Newman, MEJ (27 februarie 2003). „Amestecarea modelelor în rețele”. Analiza fizică E. Societatea Americană de Fizică (APS). 67 (2): 026126. arXiv : cond-mat/0209450 . Cod biblic : 2003PhRvE..67b6126N . DOI : 10.1103/physreve.67.026126 . ISSN 1063-651X .
↑ 1 2 3 4 Newman, MEJ (28 octombrie 2002). „Amestecare asortativă în rețele”. Scrisori de revizuire fizică . Societatea Americană de Fizică (APS). 89 (20): 208701. arXiv : cond-mat/0205405 . Cod biblic : 2002PhRvL..89t8701N . DOI : 10.1103/physrevlett.89.208701 . ISSN 0031-9007 . PMID 12443515 .
↑ Xulvi-Brunet, R.; Sokolov, I. M. (2005). „Schimbarea corelațiilor în rețele: asortativitate și disortativitate” . Acta Physica Polonica B. 36 (5): 1431. Arhivat din original la 09-05-2021 . Extras 2021-05-09 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ 1 2 Braha, D.; Bar-Yam, Y. (2007). „Mecanica statistică a dezvoltării de produse complexe: rezultate empirice și analitice” Arhivat 14 februarie 2021 la Wayback Machine . stiinta managementului. 53(7): 1127-1145.
↑ 1 2 3 Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). „Amestecare asortativă în rețele biologice direcționate”. Tranzacții IEEE/ACM despre biologie computațională și bioinformatică . 9 (1): 66-78. DOI : 10.1109/TCBB.2010.80 . PMID 20733240 .
↑ Foster, Iacob; David V. Foster; Peter Grassberger; Maya Paczuski (iunie 2010). „Direcția marginii și structura rețelelor” . Proceedings of the National Academy of Sciences . 107 (24): 10815-20. arXiv : 0908.4288 . Cod biblic : 2010PNAS..10710815F . DOI : 10.1073/pnas.0912671107 . PMC2890716 . _ PMID20505119 . _
↑ Lee, Sang Hoon; Kim, Pan-Jun; Jeong, Hawoong (4 ianuarie 2006). „Proprietățile statistice ale rețelelor eșantionate” . Analiza fizică E. Societatea Americană de Fizică (APS). 73 (1): 016102. arXiv : cond-mat/0505232 . DOI : 10.1103/physreve.73.016102 . ISSN 1539-3755 . Arhivat din original pe 21.09.2017 . Extras 2021-05-09 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). „Proprietăți dinamice și de corelare ale internetului”. Scrisori de revizuire fizică . Societatea Americană de Fizică (APS). 87 (25): 258701. arXiv : cond-mat/0105161 . Cod biblic : 2001PhRvL..87y8701P . DOI : 10.1103/physrevlett.87.258701 . ISSN 0031-9007 . PMID 11736611 .
↑ Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). „Asortativitatea locală în rețele fără scară”. EPL (Scrisori Eurofizice) . 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 martie 2010). „Originea entropică a dezasortativității în rețele complexe”. Scrisori de revizuire fizică . Societatea Americană de Fizică (APS). 104 (10): 108702. arXiv : 1002,3286 . Cod biblic : 2010PhRvL.104j8702J . DOI : 10.1103/physrevlett.104.108702 . ISSN 0031-9007 . PMID 20366458 .