Modele de amestecare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 11 mai 2021; verificările necesită 4 modificări .

Tiparele de amestecare se referă la tendințele sistematice ale unui tip de nod dintr-o rețea de a se conecta la un alt tip. De exemplu, nodurile pot avea tendința de a se conecta cu alte noduri care sunt foarte asemănătoare sau foarte diferite. Această caracteristică este destul de comună în multe rețele sociale , deși este observată uneori și în rețelele non-sociale. Tiparele de amestecare sunt strâns legate de asortativitatea ; totuși, în sensul acestui articol, termenul este folosit pentru a se referi la amestecarea asortativă sau dezasortativă, în funcție de factorii din lumea reală, topologici sau sociologici.

Tipuri de modele de amestecare

Tiparele de amestecare sunt o caracteristică la nivel de rețea care indică tendința nodurilor de a se conecta cu alte noduri similare sau diferite. Amestecarea poate fi astfel clasificată ca asortativă sau dezasortată. Amestecarea asortativă este tendința nodurilor de a se conecta cu noduri similare, în timp ce amestecarea dissortative se referă la cazul opus, în care sunt conectate noduri foarte diferite.

Caracteristicile specifice ale nodurilor implicate în formarea legăturilor între perechi formează modelele de amestecare ale rețelei. De exemplu, o rețea de relații sexuale este probabil dominată de legăturile bărbați-femei, în timp ce o rețea de prietenii poate fi dominată de legăturile bărbat-bărbați și femeie-feminin. Examinarea diferitelor seturi de caracteristici ale nodurilor poate dezvălui astfel comunități sau alte proprietăți structurale ale rețelei. În general, există două tipuri de metode de utilizare a acestor proprietăți. Una dintre ele se bazează pe calcule analitice folosind funcții de generare . Celălalt este numeric și se bazează pe simulări Monte Carlo pentru generarea de grafice. [unu]

Când studiază modelele de amestecare în rețele , MEJ Newman începe prin a clasifica caracteristicile nodurilor în două categorii. În timp ce numărul de caracteristici ale nodurilor din lumea reală este practic nelimitat, ele pot fi împărțite în două tipuri: discrete și scalare/topologice. Următoarele secțiuni definesc diferențele dintre aceste categorii și oferă exemple pentru fiecare. Pentru fiecare categorie, Newman a introdus și a descris pe scurt modele de rețele cu amestecare asortativă.

Amestecare bazată pe caracteristici discrete

Caracteristicile discrete ale unui nod sunt categorice, nominale sau enumerative și adesea calitative. De exemplu, rasa, genul și orientarea sexuală sunt caracteristici discrete studiate frecvent.

Pentru a măsura amestecarea într-o rețea pe baza caracteristicilor discrete, Newman [1] definește cantitatea ca proporția de margini dintr-o rețea care conectează nodurile de tip cu tipul (vezi Fig. 1) $e_{ij}$ $i$ $j$ [ unde? ] . Într-o rețea nedirecționată, acest număr este simetric față de indicii săi , în timp ce într-o rețea direcționată, poate fi asimetric. Îndeplinește regulile de însumare: $e_{ij}=e_{ji)$

\sum _{ij}{e_{ij}=1},\quad \sum _{j}{e_{ij}=a_{i}},\quad \sum _{i}{e_{ij }=b_{j}}~,

unde și sunt fracțiile fiecărui tip de capăt al muchiei atașate la nodurile de tip . $a_{{i}}$ $b_{{i}}$ $i$

În graficele nedirecționate, unde nu există nicio distincție fizică între capetele unei legături, de ex. capetele marginilor sunt toate de același tip, . $a_{i}=b_{i}$

Atunci coeficientul de asortativitate este o măsură a puterii asemănării sau a disimilarității dintre două noduri dintr-un set de caracteristici discrete, care poate fi definită ca:

r={\frac {\sum _{i}{e_{ii}}-\sum _{i}{a_{i}b_{i}}}{1-\sum _{i}{a_ {i}b_{i}}}}}

r_{min}=-{\frac {\sum _{i}{a_{i}b_{i)}}{1-\sum _{i}{a_{i}b_{i)}} }~.

În această formulă , dacă nu există amestecare asortativă, deoarece în acest caz , și dacă rețeaua este complet asortativă. Dacă rețeaua este complet dezasortată, de exemplu. fiecare legătură conectează două noduri de tipuri diferite, apoi , care, în general, aparține intervalului . Acest interval pentru indică faptul că o rețea complet dezasortată este, în general, mai aproape de o rețea de amestecare aleatorie decât o rețea complet asortativă. Atunci când există mai multe tipuri diferite de noduri, amestecarea aleatorie va îmbina în cele mai multe cazuri noduri diferite, rezultând ca o astfel de rețea să pară predominant dezasorțioasă. Prin urmare, este firesc ca valoarea pentru o rețea aleatorie să fie mai apropiată de valoarea pentru o rețea complet dezasortată decât pentru o rețea complet asortativă. $r=0$ $e_{ij}=a_{i}b_{j)$ $r=1$ $r=r_{min}$ $-1\leq r<0$ $r_{min}$ $r=0$

Metoda funcției de generare se bazează pe ideea de a calcula de fiecare dată o funcție generatoare adecvată pentru distribuțiile de interes și vă permite să extrageți date legate de structura rețelei prin diferențierea acestora. Presupunând că distribuția gradelor pentru nodurile de tip și valoarea matricei (și, prin urmare, valorile lui și ) sunt cunoscute. Din ansamblul graficelor se obțin caracteristicile indicate și colective (macroscopice) ale rețelei. În general, funcțiile generatoare pentru și primul lor moment sunt date ca $p_{k}^{(i))$ $i$ $e_{ij}$ $a_{{i}}$ $b_{{i}}$ $p_{k}^{(i))$ $e_{ij}$ $p_{k}^{(i))$

G_{0}^{(i)}(x_{1},...,x_{n})=\sum _{k}p_{k}^{(i)}x^{k}

și

G_{1}^{(i)}={\frac {1}{z_{i)}}{\frac {dG_{0}^{(i))){dx)}{\Bigg | }_{x=1}~,

Unde:

x_{i}={\frac {\sum _{j}e_{ij}x_{j}}{\sum _{j}e_{ij}}}

– nod de tip ( în număr);

i

r_{i)

z_{i)

este gradul mediu al nodurilor de acest tip.

Următoarele distribuții prezintă un interes deosebit.

Distribuția numărului total de noduri accesibile la urmărirea unei muchii care intră într-un nod de tip are o funcție generatoare . În mod similar, distribuția numărului de noduri accesibile de la un nod de tip ales aleatoriu are o funcție generatoare . Din aceasta se pot obține unele caracteristici ale rețelei. Numărul mediu de noduri accesibile de la un nod tip este $i$ $H_{1}^{(i)}(x)=xG_{1}^{(i)}[H_{1}^{(1)}(x),...,H_{1} ^{(n)}(x)]$ $i$ $H_{0}^{(i)}(x)=xG_{0}^{(i)}[H_{1}^{(1)}(x),...,H_{1} ^{(n)}(x)]$ $s_{i)$ $i$

s_{i}={\frac {dH_{0}^{(i)}}{dx}}{\Bigg |}_{x=1}=1+G_{0}^{(i) '}(1){\frac {\sum _{j}e_{ij}H_{1}^{(i)'}(1)}{\sum _{j}e_{ij}}}~.

În plus, dacă este probabilitatea ca un nod de tip (selectat urmând o legătură aleasă aleatoriu în grafic) să nu aparțină unui cluster gigant , atunci fracția totală de noduri care alcătuiesc acest cluster este dată de $u_{{i}}$ $i$ $S$

S=1-\sum _{i}{\frac {a_{i}}{z_{i}}}G_{0}^{(i)}(u_{1},...,u_ {n})~.

Calculele numerice bazate pe metoda Monte Carlo par a fi în acord cu rezultatele analitice obținute folosind formulele descrise mai sus.

Amestecare bazată pe caracteristici scalare sau topologice

Caracteristicile scalare ale unui nod sunt caracteristici numerice. Ele pot fi variabile ordinale continue sau discrete, cum ar fi count. Vârsta este probabil cel mai simplu exemplu, deși inteligența și veniturile din mărfuri sunt alte exemple evidente posibile. Unele caracteristici topologice ale rețelei pot fi utilizate și pentru a studia amestecarea pe baza proprietăților scalare. În special, gradul de nod este adesea o caracteristică foarte importantă în amestecarea tiparelor în rețele. [2] Singularitățile scalare topologice sunt foarte utile deoarece, spre deosebire de alți exponenți, sunt întotdeauna disponibili. Uneori sunt folosite ca un indicator grosier al „sociabilității” reale (sociabilitatea, tendința de a stabili legături sociale). [unu]

Pentru a măsura asortativitatea variabilelor scalare, în mod similar cu cazul discret (vezi mai sus), se poate determina coeficientul de asortativitate. Poate fi măsurat folosind corelația standard Pearson , așa cum arată Newman. [1] În fig. 2[ unde? ] , de exemplu, calculul coeficientului de corelație Pearson dă r = 0,574. Acest lucru indică o asociere destul de puternică între vârstele soților și soțiilor la momentul căsătoriei.

Un factor alternativ poate fi calculat prin măsurarea amestecării peste puterile vârfurilor. Newman [1] a derivat următoarea expresie

r={\frac {\sum _{jk}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2)))

pentru o rețea nedirecțională. În această formulă, dacă se referă la distribuția de grade a unui grafic (adică, probabilitatea ca un nod să aibă gradul ), atunci . Aceasta se referă la excesul de grad al unui nod sau la numărul de muchii, altele decât cea studiată în prezent. denotă puterea medie în rețea și denota abaterea standard a distribuției . Pentru o rețea direcționată, expresia echivalentă este $p_{k}$ $k$ $\textstyle q_{k}={\frac {(k+1)p_{k+1}}{z}}$ $z$ $\sigma _{q)$ $q_{k}$

r={\frac {\sum _{jk}jk(e_{jk}-q_{j}^{in}q_{k}^{out})}{\sigma _{in}\sigma _ {out}}}~.

Această corelație este pozitivă atunci când nodurile sunt asortative în grade și negativă atunci când rețeaua este dezasortată. Astfel, această măsură oferă o idee generală a modelelor de amestecare în rețea. O analiză mai profundă este dată în articolul Assortativity .

Metoda de generare a funcțiilor este încă aplicabilă în acest caz, dar funcțiile care trebuie găsite pot fi rareori determinate analitic. Astfel, calculele numerice par a fi singura modalitate de a obține rezultatul final. În acest caz, se folosește din nou metoda Monte Carlo. Pentru cazul rețelelor cu o distribuție a legii puterii de grade , , are o medie divergentă, cu excepția cazului , care este rar. [3] În schimb, distribuția legii puterii trunchiată exponențial dă o distribuție pentru o putere în exces de tipul . Rezultatele pentru acest caz sunt descrise mai jos. $p_{k}\sim k^{-\tau }$ $q_{k)$ $\tau >3$ $\textstyle p_{k}={\frac {k^{-\tau }\mathrm {e} ^{-k/\kappa }}{\mathrm {Li} _{\tau }(\mathrm { e} ^{-1/\kappa })}}\ \mathrm {pentru} \k\geq 1$ $q_{k}\sim (k+1)^{1-\tau }\mathrm {e} ^{-(k+1)/\kappa )$

1) Poziția pe tranziția de fază la care clusterul gigant trece la valori mai mari de , în timp ce valoarea scade $\kappa$ $r$ . Cu alte cuvinte, cu cât rețeaua este mai asortativă, cu atât pragul de densitate a marginilor este mai scăzut pentru apariția unui cluster gigant.

2) Mărimea unui cluster gigant în limita mare este mai mică pentru un grafic cu amestecare asortativă decât pentru graficele neutre și dezasortative $\kappa$ .

3) Amestecarea asortativă în rețea afectează stabilitatea rețelei atunci când nodurile sunt îndepărtate . Rețelele asortative trebuie să elimine de aproximativ zece ori mai multe noduri cu grade înalte pentru a distruge un cluster gigant decât într-o rețea normală (prin obișnuit înțelegem o rețea neutră), în timp ce opusul este valabil pentru rețelele dezasortate, adică. sunt mai sensibile decât cele neutre la îndepărtarea nodurilor de grad înalt.

Acest rezultat al dependenței stabilității rețelei de amestecarea nodurilor poate fi explicat după cum urmează. Prin definiție, nodurile de grad înalt din rețelele asortative tind să formeze un grup de bază între ele. Un astfel de grup de nucleu oferă stabilitate rețelei prin concentrarea tuturor nodurilor țintă aparente împreună într-o singură parte a graficului. Îndepărtarea acestor noduri de grad înalt este încă una dintre cele mai eficiente modalități de a distruge conectivitatea rețelei, dar mai puțin eficientă (comparativ cu o rețea neutră), deoarece prin eliminarea lor pe toate din aceeași parte a graficului, nu atacăm alte părți ale rețelei. grafic. Dacă aceste alte părți sunt stabile singure, atunci clusterul gigant va rămâne chiar dacă nodurile de grad înalt dispar. Pe de altă parte, rețelele cu amestecare dezasortativă sunt deosebit de sensibile la eliminarea nodurilor cu grade ridicate, deoarece aceste noduri sunt împrăștiate departe unul de celălalt în întreaga rețea, astfel încât atacarea lor este ca și cum ați ataca toate părțile rețelei în același timp.

Exemple și aplicații

O aplicație tipică a tiparelor de amestecare este studiul transmiterii bolii. De exemplu, multe studii folosesc amestecarea pentru a studia răspândirea SIDA și a altor boli contagioase. [4] [5] [6] Aceste articole găsesc o relație puternică între tiparele de amestecare și rata de răspândire a bolii. Rezultatele pot fi utile și pentru modelarea creșterii rețelelor din lumea reală, ca în [7] , de exemplu , sau descoperirea comunităților în rețele.

Note

↑ 1 2 3 4 5 Newman, MEJ (27.02.2003). „Amestecarea modelelor în rețele”. Analiza fizică E. 67 (2): 026126. arXiv : cond-mat/0209450 . Cod biblic : 2003PhRvE..67b6126N . DOI : 10.1103/physreve.67.026126 . ISSN 1063-651X . PMID 12636767 .
^ Newman, MEJ (28.10.2002) . „Amestecare asortativă în rețele”. Scrisori de revizuire fizică . 89 (20): 208701. arXiv : cond-mat/0205405 . Cod biblic : 2002PhRvL..89t8701N . DOI : 10.1103/physrevlett.89.208701 . ISSN 0031-9007 . PMID 12443515 .
↑ Albert, Reka; Barabasi, Albert-Lászlo (30-01-2002). „Mecanica statistică a rețelelor complexe”. Recenzii despre fizica modernă . 74 (1): 47-97. arXiv : cond-mat/0106096 . Cod biblic : 2002RvMP ...74...47A . DOI : 10.1103/revmodphys.74.47 . ISSN 0034-6861 .
↑ Aral, SO; Hughes, JP; Stoner, B; Whittington, W; Handsfield, HH; Anderson, R.M.; Holmes, KK (1999). „Modele de amestecare sexuală în răspândirea infecțiilor gonococice și cu chlamydia” . Jurnalul American de Sănătate Publică . Asociația Americană de Sănătate Publică. 89 (6): 825-833. DOI : 10.2105/ajph.89.6.825 . ISSN 0090-0036 . PMC 1508665 . PMID 10358670 .
↑ Garnett, Geoffrey P.; HUGHES, James P.; Anderson, Roy M.; Stoner, Bradley P.; Aral, Sevgi O.; et al. (1996). „Modele de amestecare sexuală ale pacienților care frecventează clinicile de boli cu transmitere sexuală.” Boli cu transmitere sexuală . Ovid Technologies (Wolters Kluwer Health). 23 (3): 248-257. DOI : 10.1097/00007435-199605000-00015 . ISSN 0148-5717 . PMID 8724517 .
↑ Ford, Kathleen; Sohn, Woosung; Lepkowski, James (2002). „Adolescenții americani: modele de amestecare sexuală, parteneri de legătură și concurență” . Boli cu transmitere sexuală . Ovid Technologies (Wolters Kluwer Health). 29 (1): 13-19. DOI : 10.1097/00007435-200201000-00003 . ISSN 0148-5717 . PMID 11773873 .
↑ Catanzaro, Michele; Caldarelli, Guido; Pietronero, Luciano (2004). „Creșterea rețelei sociale cu amestecare asortativă”. Fizica A: Mecanica statistică și aplicațiile sale . Elsevier BV. 338 (1-2): 119-124. Cod biblic : 2004PhyA..338..119C . DOI : 10.1016/j.physa.2004.02.033 . ISSN 0378-4371 .