Gradul de mediere

Gradul de mediere este o măsură a centralității într-un grafic bazat pe cele mai scurte căi . Pentru orice pereche de vârfuri dintr-un graf conectat, există cel puțin o cale (cea mai scurtă) între vârfuri pentru care fie numărul de muchii de-a lungul căreia merge calea (pentru graficele neponderate) fie suma greutăților acestor muchii (pentru ponderate). grafice) este minimă. Gradul de mediere pentru fiecare vârf este egal cu numărul acestor cele mai scurte căi prin vârf.

Gradul de mediere este utilizat pe scară largă în teoria rețelelor - reflectă gradul în care sunt vârfuri între alte vârfuri. De exemplu, într-o rețea de telecomunicații , nodul cu cel mai înalt grad de intermediere ar avea mai mult control asupra rețelei pe măsură ce mai multe informații trec prin acel nod. Gradul de mediere a fost dezvoltat ca măsură generală a centralității - poate fi aplicat unei game largi de probleme din teoria rețelelor, inclusiv probleme legate de rețelele sociale , biologice, de transport și cooperarea științifică [1] .

Deși autorii anteriori au descris intuitiv centralitatea în termeni de grad de intermediere, Freeman [2] a oferit prima definiție formală a gradului de intermediere.

Definiție

Gradul de mediere a nodului este dat de: $v$

g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st)))

unde este egal cu numărul total de căi cele mai scurte de la nod la nod și este egal cu numărul acestor căi care trec prin . $\sigma _{st)$ $s$ $t$ $\sigma _{st}(v)$ $v$

Rețineți că gradul de mediere este egal cu fracția de perechi de noduri cu condiția definită de condiția de însumare. Prin urmare, există perechi de noduri ale căror cele mai scurte căi nu includ , astfel încât . Împărțirea este prin pentru graficele direcționate și prin pentru graficele nedirecționate, unde este egal cu numărul de noduri din componenta cea mai mare. Rețineți că această valoare este cea mai mare atunci când un vârf este conținut în orice cale mai scurtă. Adesea, acest lucru nu se face și normalizarea se poate face fără pierderea preciziei. $v$ $g\in [0,1]$ $(N-1)(N-2)$ $(N-1)(N-2)/2$ $N$

{\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)))

care duce la

\max(normal)=1

\min(normal)=0

Rețele ponderate

Într-o rețea ponderată, legăturile care conectează nodurile nu mai sunt tratate ca interacțiuni separate, ci sunt ponderate proporțional cu capacitatea, influența, frecvența lor etc., ceea ce adaugă o altă dimensiune eterogenității rețelei pe lângă efectele topologice. Gradul de mediere a unui nod într-o rețea ponderată este dat de suma greutăților marginilor sale adiacente.

s_{i}=\sum _{j=1}^{N}a_{ij}w_{ij)

Când și sunt matricele de adiacență și greutate între noduri și respectiv. Similar cu legea puterii a distribuției gradelor găsită în rețelele invariante la scară, gradul unui nod dat respectă, de asemenea, o lege a puterii. $a_{{ij}}$ $w_{ij}$ $i$ $j$

s(k)\aprox k^{\beta )

Studiul valorii medii a rezistenței vârfurilor cu gradul de mediere arată că comportamentul funcțional poate fi aproximat prin expresia [3] $s(b)$ $b$

s(b)\aprox b^{\alpha )

Centralitatea percolației

Centralitatea de percolare este o versiune a gradului ponderat de mediere, dar ia în considerare „starea” nodurilor sursă și țintă ale fiecărei căi cele mai scurte atunci când se calculează greutatea. Scurgerile au loc în rețele complexe într-o mare varietate de scenarii. De exemplu, o infecție virală sau bacteriană se poate răspândi prin rețelele sociale ale oamenilor, cunoscute sub numele de rețele de contact. Răspândirea bolii poate fi considerată și la un nivel ridicat de abstractizare, luând în considerare o rețea de orașe sau centre de populație conectate prin drumuri, căi ferate sau linii aeriene. Virușii informatici se pot răspândi în rețelele de computere. Zvonurile și știrile despre oferte și oferte de afaceri se pot răspândi și prin rețelele sociale ale oamenilor. În toate aceste scenarii, „contagiunea” se răspândește prin legăturile unei rețele complexe, schimbând „stările” nodurilor în mod reversibil sau ireversibil. De exemplu, într-un scenariu epidemiologic, indivizii trec de la starea „susceptibilă” la starea „infectată”. Stările nodurilor specifice pe măsură ce se răspândește „contagiune” pot lua valori binare (cum ar fi „o știre primită/neprimită”), valori discrete (susceptibil/infectat/vindecat) sau chiar valori continue (cum ar fi proporția de persoane infectate din oraș). Lucrul comun în toate aceste scenarii este că răspândirea „infecției” duce la o schimbare a stării nodurilor rețelei. Având în vedere acest lucru, a fost propusă centralitatea percolației (PC) , care măsoară importanța unui nod în ceea ce privește contribuția la percolarea prin rețea. Această măsură a fost propusă de Payravinan și colab .[4] .

Centralitatea infiltrațiilor este definită pentru un nod dat și la un moment dat ca proporție de „căi de infiltrație” care trec prin nod. O „cale de scurgere” este cea mai scurtă cale dintre o pereche de noduri în care nodul sursă este într-o stare de scurgere (de exemplu, infectat). Nodul țintă poate fi într-o stare de percolare, o stare de non-percolare sau o stare de percolare parțială.

PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)} {\sigma _{sr))}{\frac {{x^{t}}_{s}}({\sum {[{x^{t}}_{i}}]}-{x^{ televizor}}}

unde este egal cu numărul total de căi cele mai scurte de la nod la nod și este egal cu numărul de astfel de căi care trec prin . Starea de scurgere a unui nod la un moment dat este desemnată ca și există două cazuri speciale când , care indică starea de etanșeitate la timp , și când , care indică o scurgere completă la timp . Valorile dintre aceste valori indică stări de infiltrație parțială (de exemplu, într-o rețea de orașe, acesta ar putea fi procentul de persoane infectate din oraș). $\sigma _{sr)$ $s$ $r$ $\sigma _{sr}(v)$ $v$ $i$ $t$ ${x^{t}}_{i}$ ${x^{t}}_{i}=0$ $t$ ${x^{t}}_{i}=1$ $t$

Greutățile căilor de scurgere depind de nivelurile de scurgere atribuite nodurilor sursă, pe baza postulatului că, cu cât nivelul de scurgere al nodului sursă este mai mare, cu atât sunt mai importante căile care ies din acel nod. Nodurile care se află pe cele mai scurte căi pornind de la nodurile cu percolație mare sunt, prin urmare, potențial mai importante pentru percolare. Definiția PC poate fi, de asemenea, extinsă pentru a include și greutățile nodurilor țintă. Calculul centralității scurgerilor se realizează în timp cu o implementare eficientă împrumutată de la algoritmul rapid Brandes, iar dacă calculele necesită luarea în considerare a ponderilor nodurilor finale, timpul cel mai rău caz este egal cu . $O(NM)$ $O(N^{3})$

Algoritmi

Calcularea gradelor de mediere și a gradelor de proximitate ale tuturor nodurilor dintr-un grafic necesită calcularea celor mai scurte căi între toate perechile de vârfuri din grafic, ceea ce necesită timp atunci când se utilizează algoritmul Floyd-Warshall modificat pentru a găsi toate căile, mai degrabă decât una pentru două. nodurile selectate. Pe grafice rare , algoritmul lui Johnson sau algoritmul lui Brandeis poate fi mai eficient, ambii algoritmi rulând în timp . Pe graficele neponderate, calcularea gradului de mediere folosind algoritmul Brandes durează [5] . $\Theta (|V|^{3})$ $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$

Când se calculează gradele de mediere și gradele de proximitate ale tuturor vârfurilor graficului, se presupune că graficele sunt nedirecționate, conectate și sunt permise mai multe muchii. Când se lucrează cu grafice de rețea, graficele de multe ori nu au cicluri sau margini multiple, reflectând conexiuni simple (aici marginile reprezintă conexiunea dintre oameni). În acest caz, când se folosește algoritmul Brandes, valoarea centralității finale este împărțită la 2 pentru a se ține cont de faptul că fiecare cale cea mai scurtă este numărată de două ori [6] .

Un alt algoritm generalizează gradul de mediere a lui Freeman la geodezice și gradul de mediere a lui Newman la toate căile prin introducerea unui parametru care controlează schimbul dintre explorare și utilizare. Complexitatea timpului este egală cu numărul de muchii pe număr de noduri din graficul [7] .

Conceptul de centralitate a fost extins și la nivelul grupului [8] . Gradul de mediere a grupului indică proporția de geodezice care conectează perechi de membri non-grup care trec printr-un grup de noduri. Algoritmul lui Brandes pentru calcularea gradului de mediere a tuturor nodurilor a fost modificat pentru a calcula gradul de mediere de grup al unui grup de noduri cu același timp de rulare asimptotic [8] .

Concepte înrudite

Gradul de mediere este legat de conectivitatea rețelei prin aceea că vârfurile cu un grad ridicat de mediere pot rupe graficul dacă sunt îndepărtate (vezi setul de tăiere ).

Gradul de mediere al traseului generalizează gradul de mediere atunci când se aplică oricărei scheme de determinare a traseelor simple fără cicluri pe baza doar criteriului drumului cel mai scurt [9] .

Vezi și

Centralitate

Note

↑ Freeman, 1977 , p. 39.
↑ Freeman, 1977 .
↑ Barrat, Barthelemy, Pastor-Satorras, Vespignani, 2004 .
↑ Piraveenan, 2013 , p. e53095.
↑ Brandes, 2001 , p. unu.
↑ Brandes, 2001 , p. 9.
↑ Mantrach, 2010 .
↑ 1 2 Puzis, Yagil, Elovici, Braha, 2009 .
↑ Dolev, Elovici, Puzis, 2010 , p. 25:1-25:27.

Literatură

Ulrik Brandes. Un algoritm mai rapid pentru centralitatea interness // Journal of Mathematical Sociology. - 2001. - T. 25 , nr. 2 . — S. 163–177 . - doi : 10.1080/0022250x.2001.9990249 . Arhivat din original pe 13 octombrie 2017.
Linton Freeman. Un set de măsuri de centralitate bazate pe interness // Sociometrie. - 1977. - T. 40 , nr. 1 . — p. 35–41 . - doi : 10.2307/3033543 . — .
Goh KI, Kahng B., Kim D. Universal Behavior of Load Distribution in Scale-Free Networks // Physical Review Letters. - 2001. - T. 87 , nr. 27 . - S. 278701 . - doi : 10.1103/physrevlett.87.278701 . - Cod . - arXiv : cond-mat/0106565 .
Amin Mantrach. Nucleul de covarianță sum-over-paths: o nouă măsură de covarianță între nodurile unui grafic direcționat // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2010. - T. 32 , nr. 6 . - S. 1112-1126 . - doi : 10.1109/tpami.2009.78 .
Robert L. Moxley, Nancy F. Moxley. Determinarea punctului-centralității în rețelele sociale necontrivate // Sociometrie. - 1974. - T. 37 , nr. 1 . — S. 122–130 . - doi : 10.2307/2786472 . — .
Newman MEJ Networks: o introducere. - Oxford, Marea Britanie: Oxford University Press, 2010. - ISBN 978-0199206650 .
Shlomi Dolev, Yuval Elovici, Rami Puzis. Centralitatea de rutare între intermediari // J. ACM. - 2010. - T. 57 , nr. 4 . — S. 25:1–25:27 . - doi : 10.1145/1734213.1734219 .
Mahendra Piraveenan. Centralitatea percolației: cuantificarea impactului teoretic grafic al nodurilor în timpul percolării în rețele // PLOS ONE. - 2013. - T. 8 , nr. 1 . — S. e53095 . - doi : 10.1371/journal.pone.0053095 . - Cod biblic . — PMID 23349699 .
Barrat A., Barthelemy M., Pastor-Satorras R., Vespignani A. Arhitectura rețelelor complexe ponderate // PNAS. - 2004. - T. 101 , nr. 11 .
Puzis R., Yagil D., Elovici Y., Braha D. Collaborative attack on Internet users' anonymity // Internet Research. - 2009. - T. 19 , nr. 1 . Arhivat din original pe 7 decembrie 2013.
Shlomi Dolev, Yuval Elovici, Rami Puzis. Centralitatea de rutare între intermediari // J. ACM. - T. 57 , nr. 4 . - doi : 10.1145/1734213.1734219 .