Centralitate

Indicatorul de centralitate sau proximitate față de centru în teoria grafurilor și analiza rețelelor determină cele mai importante vârfuri ale grafului. Aplicațiile indicatorului sunt utilizate pentru a identifica persoana (persoanele) cea mai influentă(e) dintr-o rețea socială , nodurile cheie ale infrastructurii de pe internet sau rețelele metropolitane și purtătorii bolii. Conceptele de centralitate dezvoltate inițial în analiza rețelelor sociale și mulți termeni de centralitate sunt utilizați pentru a măsura sursele primare sociologice [2] . Aceste metrici nu trebuie confundate cu metricile de influență a nodului , care caută caracteristici cantitative ale influenței fiecărui nod din rețea.

Definiția și descrierea indicilor de centralitate

Indicii de centralitate sunt răspunsuri la întrebarea „Ce caracterizează importanța unui vârf?” Răspunsul este dat în termenii unei funcții cu valoare reală pe vârfurile graficului, ale cărei valori (așteptată) oferă un clasament care determină cele mai importante noduri [3] [4] [5] .

Cuvântul „importanță” are o gamă largă de sensuri, ceea ce duce la multe definiții diferite ale centralității. Au fost propuse două scheme de clasificare. „Importanța” poate fi înțeleasă în raport cu tipul de flux prin rețea. Acest lucru permite clasificarea centralității după tipul de flux care este considerat important [4] . „Importanța” poate fi înțeleasă alternativ ca participare la integritatea rețelei. Acest lucru permite clasificarea centralităților în funcție de modul în care măsoară participarea [6] . Ambele abordări împart centralitățile în categorii diferite. O centralitate care este potrivită pentru o categorie va fi adesea nepotrivită atunci când este aplicată unei alte categorii [4] .

Dacă centralitățile sunt clasificate în funcție de participarea lor, devine clar că majoritatea centralităților aparțin aceleiași categorii. Numărul de rute care provin de la un nod dat diferă doar în modul în care sunt determinate și numărate rutele. Restricționarea acordurilor pentru acest grup permite descrierea centralităților pe spectrul rutelor de la lungimea unu ( grad de conectivitate ) la rute nerestricționate ( grad de influență ) [3] [7] . Observația că multe centralități împărtășesc aceste legături explică nivelul ridicat de corelație dintre acești indici.

Descrierea fluxurilor în rețea

O rețea poate fi gândită ca o descriere a căilor pe care curge ceva. Acest lucru permite descrierea bazată pe tipuri de flux și tipuri de căi codificate de centralitate. Fluxul se poate baza pe transferuri, în care fiecare element indivizibil trece de la un nod la altul, similar cu livrarea coletelor de la oficiul poștal la domiciliul clientului. În al doilea caz, există o reproducere a elementului care trece la următorul nod, astfel încât atât sursa, cât și ținta să aibă acest element. Un exemplu de astfel de caz este răspândirea zvonurilor, în care informațiile sunt partajate în mod privat, atât sursa cât și ținta informate la sfârșitul procesului. Ultimul caz este propagarea paralelă, în care un element este propagat prin mai multe legături în același timp, similar unei emisiuni radio, care oferă aceeași informație multor ascultători în același timp [4] .

În mod similar, tipul de cale poate fi limitat la: geodezice (cele mai scurte căi), căi (nici un vârf nu este vizitat de mai multe ori, căi (vârfurile pot fi vizitate de mai multe ori, dar nicio margine nu este parcursă de două ori) sau trasee (atât vârfuri, cât și margini). poate apărea de mai multe ori) [4] .

Descriere după structura mersului

O clasificare alternativă poate fi derivată din modul în care este construită centralitatea. Acest lucru duce din nou la o împărțire în două clase - Radial sau Median. Centralitățile radiale numără numărul de căi care încep/se termină la un punct dat. Gradele de conectivitate și gradele de influență sunt exemple de măsuri radiale de centralitate, numărând numărul de căi de lungime unu sau nelimitat. Centralitățile mediane numără căile care trec printr-un vârf dat. Exemplul canonic este gradul de mediere Freeman, numărul celor mai scurte căi care trec printr-un vârf dat [6] .

În mod similar, contorizarea poate capta fie volumul , fie lungimea traseului. Volumul este numărul total de rute de un anumit tip. Trei exemple din paragraful anterior se încadrează în această categorie. Lungimea este distanța de la un punct dat la celelalte vârfuri din grafic. Gradul de proximitate față de alte noduri Freeman, distanța geodezică totală de la un punct dat la toate celelalte vârfuri, este cel mai cunoscut exemplu [6] . Rețineți că această clasificare depinde de tipul de rute care sunt calculate (adică trasee, circuite, căi, geodezice).

Borgatti și Everett au considerat că această tipologie dă o idee despre cum se compară măsurile de centralitate. Centralitățile care se încadrează în aceeași celulă în această clasificare 2x2 sunt suficient de similare pentru a fi alternative acceptabile și se poate compara în mod rezonabil care scor este cel mai bun pentru o anumită problemă. Măsurile de la diferite celule, însă, sunt complet diferite. Orice determinare a adecvării relative nu poate avea loc decât într-un context predeterminat, care categorie este mai potrivită [6] .

Centralități volumetrice radiale care există pe spectru

Descrierea prin structura traseului arată că aproape toate centralitățile utilizate sunt măsuri radial-volumerice. Acest lucru dă încredere că centralitatea vârfurilor este o funcție a centralității vârfurilor cu care este asociată. Centralitățile diferă prin modul în care sunt asociate.

Bonacic a arătat că dacă o asociere este definită în termeni de căi, atunci o familie de centralități poate fi definită în termeni de lungimi de căi luate în considerare [3] . Gradul de conectivitate contează numărul de rute de lungime unu, gradul de influență numără rutele de lungime nelimitată. Sunt posibile și definiții alternative ale asociațiilor. Alpha-centrality vă permite să aveți surse externe de influență pentru vârfuri. Centralitatea subgrafului lui Estrada numără numai căi închise (triunghiuri, patrulatere, ...).

Inima acestor măsuri este observația că gradele matricei de adiacență a unui grafic dau numărul de căi cu lungimea egală cu gradul. În mod similar, exponentul matricei este strâns legat de numărul de căi de o lungime dată. O transformare inițială a matricei de adiacență permite definirea unui număr de diferite tipuri de rute. În oricare dintre abordări, centralitatea vârfurilor poate fi exprimată ca o sumă infinită sau

\sum _{k=0}^{\infty}A_{R}^{k}\beta ^{k)

pentru puterile matricei, sau

\sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!)}}

pentru exponentul matricei, unde

$k$ egal cu lungimea traseului,
$A_{R}$ este matricea de adiacență transformată și
$\beta$ este un parametru compensator care asigură convergenţa sumei.

Familia de măsuri Bonacic nu transformă matricea de adiacență. Centralitatea alfa înlocuiește matricea de adiacență cu rezoluția sa . Centralitatea subgrafului înlocuiește matricea de adiacență cu urma sa. Indiferent de transformarea inițială a matricei de adiacență, toate aceste abordări au un comportament limitator comun. Pe măsură ce tinde spre zero, indicele converge către gradul de conectivitate . Când se urmărește valoarea maximă, indicele converge către gradul de influență [7] . $\beta$ $\beta$

Centralitatea teoretică a jocului

O caracteristică comună a majorității măsurilor standard de mai sus este că evaluează importanța unui nod, concentrându-se doar pe rolul pe care nodul îl joacă singur. Cu toate acestea, în multe aplicații, această abordare nu va fi adecvată, deoarece interacțiunea nodurilor poate fi detectată dacă măsurile sunt aplicate nodurilor de grup.

De exemplu, luați în considerare problema opririi unei epidemii. Privind imaginea de rețea de mai sus, ce noduri ar trebui vaccinate? Pe baza măsurilor descrise mai sus, dorim să recunoaștem nodurile care sunt cele mai importante în răspândirea bolii. Folosirea abordărilor de centralitate care se concentrează pe proprietățile individuale ale nodurilor poate să nu fie o idee bună. Nodurile din caseta roșie singure nu pot opri răspândirea bolii, dar când sunt privite ca un grup, vedem clar că pot opri boala dacă începe în nodurile , , . Centralitățile teoriei jocurilor încearcă să țină cont de problemele și oportunitățile descrise folosind instrumentele teoriei jocurilor. Abordarea propusă de Michalak (et al.) [8] folosește vectorul Shapley . Datorită complexității (în timp) a calculării vectorului Shapley, cea mai mare parte a efortului în acest domeniu este investit în dezvoltarea de noi algoritmi și metode care se bazează pe topologia specifică a rețelei și natura specială a problemei. Această abordare poate reduce complexitatea temporală a algoritmului de la exponențial la polinom. $v_{1}$ $v_{4)$ $v_{5}$

Restricții importante

Indicii de centralitate au două limitări importante, una este evidentă, cealaltă este subtilă. O limitare evidentă este aceea că centralitatea care este optimă pentru o aplicație nu este adesea optimă pentru alta. Mai mult, dacă nu ar fi așa, nu ar fi nevoie de atât de multe centralități diferite. O ilustrare a acestui fenomen este dată de zmeul lui Crackhard , pentru care trei noțiuni diferite de centralitate dau trei vârfuri diferite cele mai centrale [9] .

O limitare subtilă este că există o concepție greșită generalizată că centralitatea vârfurilor reflectă importanța relativă a vârfurilor. Indicii de centralitate au fost dezvoltați în mod explicit pentru clasare, ceea ce permite selectarea celor mai importante vârfuri [3] [4] . O fac bine sub limitările menționate. Nu au fost concepute pentru a măsura nodurile într-un mod general. Recent, fizicienii de rețea au început să dezvolte metrici de influență a nodurilor pentru a rezolva această problemă.

Eroarea este dubla. În primul rând, clasarea numai în ordinea vârfurilor, deoarece importanța lor nu reflectă diferența de importanță dintre diferitele niveluri de clasare. Acest fapt poate fi atenuat prin aplicarea centralității lui Freeman la măsura centralității în cauză, ceea ce oferă o perspectivă asupra importanței nodurilor prin diferitele lor scoruri de centralitate. Mai mult, centralitatea Freeman vă permite să comparați unele rețele din punct de vedere al indicatorilor de la nodurile cu cea mai mare valoare [10] .

În al doilea rând, proprietățile care reflectă (corect) cele mai importante vârfuri dintr-o anumită rețea/aplicație nu se generalizează neapărat la restul vârfurilor. Pentru majoritatea celorlalte noduri din rețea, clasarea poate fi lipsită de sens [11] [12] [13] [14] . Aceasta explică, de exemplu, de ce doar primele câteva rezultate ale unei căutări de imagini Google apar într-o ordine adecvată. PageRank este o măsură extrem de instabilă, care arată adesea rangul opus după o mică modificare a parametrului de căutare [15] .

Deși imposibilitatea generalizării indicelui de centralitate la restul rețelei poate să nu pară evidentă la prima vedere, ea rezultă direct din definițiile de mai sus. Rețelele complexe au o topologie eterogenă. În ce măsură măsura optimă depinde de structura rețelei a celor mai importante vârfuri, în măsura în care măsura care este optimă pentru astfel de vârfuri nu este optimă pentru restul rețelei [11] .

Conectivitate

Din punct de vedere istoric, primul și cel mai simplu concept conceptual este gradul de conectivitate , care este definit ca numărul de legături incidente la un nod (adică numărul de legături pe care le are un nod). Gradul poate fi interpretat în funcție de riscul direct al nodului de a prinde ceva care trece prin rețea (cum ar fi un virus sau unele informații). În cazul unei rețele direcționate (unde sunt direcționate legăturile), definim de obicei două măsuri diferite ale gradului de conectivitate, și anume în -degree și out -degree . În consecință, gradul în interior este numărul de conexiuni cu nodul, iar gradul în afara este numărul de conexiuni ale nodului cu alte noduri. Atunci când conexiunea este asociată cu un aspect pozitiv, cum ar fi prietenia sau cooperarea, gradul de intrare este adesea interpretat ca un fel de popularitate, iar gradul de exterior ca sociabilitate.

Gradul de conectivitate a unui vârf pentru un graf dat cu vârfuri și muchii este definit ca $v$ $G:=(V,E)$ $|V|$ $|E|$

C_{D}(v)=\deg(v)

Calcularea gradului de conectivitate pentru toate nodurile dintr-un graf necesită timp în reprezentarea matricei densă de adiacență a graficului și timp în reprezentarea matriceală rară pentru muchii . $\Theta (V^{2})$ $\Theta (E)$

Definiția centralității la nivel de nod poate fi extinsă la întregul graf, iar în acest caz vorbim despre centralitatea grafului [10] . Fie nodul cu cel mai înalt grad de conectivitate în . Fie un grafic conectat cu noduri care maximizează următoarea valoare (cu ca nodul cu cel mai mare grad de conectivitate în ): $v*$ $G$ $X:=(Y,Z)$ $|Y|$ $y*$ $X$

H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]

În consecință, gradul de centralitate a graficului este egal cu: $G$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})] {H}}

Valoarea este maximă atunci când graficul conține un nod central la care sunt conectate toate celelalte noduri ( graficul stea ), caz în care $H$ $X$

H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2.

Astfel, pentru orice grafic $G:=(V,E),$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})] }{|V|^{2}-3|V|+2}}

Apropierea de alte noduri

Într -un graf conectat , gradul normalizat de proximitate a unui nod este egal cu lungimea medie a căii celei mai scurte dintre nod și toate celelalte noduri din graf. Apoi, cu cât nodul este mai central, cu atât este mai aproape de toate celelalte noduri.

Gradul de proximitate a fost definit de Alex Bavelas (1950) ca reciproca distantei [16] [17] , i.e.

C(x)={\frac {1}{\sum _{y}d(y,x)))

unde este egală cu distanța dintre vârfuri și . Cu toate acestea, când se vorbește despre gradul de proximitate față de alte noduri, oamenii se referă de obicei la forma sa normalizată, obținută de obicei din formula anterioară prin înmulțirea cu , unde este egal cu numărul de noduri din grafic. Dimensionarea permite compararea între nodurile graficelor de diferite dimensiuni. $d(y,x)$ $X$ $y$ $N-1$ $N$

Luarea în considerare a distanței de la sau față de toate celelalte noduri nu este aplicabilă graficelor nedirecționate, în timp ce în graficele direcționate acestea dau rezultate destul de diferite. De exemplu, un site web poate avea o proximitate de ieșire mare, dar o proximitate de intrare scăzută).

Centralitate armonică

Într-un grafic (nu neapărat conectat), centralitatea armonică inversează operațiile de însumare și inversare în determinarea gradului de apropiere:

H(x)=\sum _{y\neq x}{\frac {1}{d(y,x))}

unde , dacă nu există cale de la la . Centralitatea armonică poate fi normalizată prin împărțirea la , unde este egal cu numărul de noduri din grafic. $1/d(y,x)=0$ $y$ $X$ $N-1$ $N$

Centralitatea armonică a fost propusă de Marchiori și Lathora (2000) [18] , apoi independent de Dekker (2005) sub denumirea de centralitate evaluată [19] , și Rochat (2009) [ 20] .

Gradul de mediere

Gradul de mediere este o măsură a centralității unui vârf într-un grafic (există și un grad de mediere a muchiei , care nu este discutat aici). Gradul de mediere cuantifică de câte ori un nod realizează o punte pe cea mai scurtă cale între alte două noduri. Gradul de mediere a fost introdus de Linton Freeman ca măsură a expresiei cantitative a interacțiunii unei persoane cu alte persoane într-o rețea socială [21] . În acest concept, vârfurile care au cea mai mare probabilitate de a se afla pe calea cea mai scurtă aleasă aleatoriu între două vârfuri alese aleatoriu au un grad ridicat de mediere.

Gradul de mediere al unui vârf într-un grafic cu vârfuri se calculează după cum urmează: $v$ $G:=(V,E)$ $V$

Pentru fiecare pereche de vârfuri ( s , t ) se calculează cele mai scurte căi dintre ele .
Pentru fiecare pereche de vârfuri ( s , t ) se determină fracțiunea celor mai scurte căi care trec prin vârful în cauză (aici, vârful v ).
Rezumam aceste cote pentru toate perechile de vârfuri ( s , t ).

Mai compact, gradul de mediere poate fi reprezentat ca [22] :

C_{B}(v)=\sum _{s\neq v\neq t\in V}{\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 de astfel de căi care trec prin . Gradul de mediere poate fi normalizat prin împărțirea la numărul de perechi de vârfuri fără v , care este egal cu pentru graficele direcționate și egal cu pentru graficele nedirecționate . De exemplu, într-o stea nedirecționată , vârful central (care este conținut în orice cale cea mai scurtă posibilă) are grad de mediere (1 dacă este normalizat), în timp ce frunzele (care nu sunt conținute în nicio cale cea mai scurtă) au gradul de mediere 0. $\sigma _{st)$ $s$ $t$ $\sigma _{st}(v)$ $v$ $(n-1)(n-2)$ $(n-1)(n-2)/2$ $(n-1)(n-2)/2$

Din punct de vedere computațional, atât gradul de mediere, cât și gradul de proximitate al tuturor nodurilor dintr-un grafic implică calcularea celor mai scurte căi între toate perechile de vârfuri din grafic, ceea ce necesită timp atunci când se folosește algoritmul Floyd-Warshall . Cu toate acestea, pe grafice rare , algoritmul lui Johnson poate fi mai eficient, rulând în timp . În cazul graficelor neponderate, calculele pot fi efectuate folosind algoritmul Brandes [22] , care necesită timp . De obicei, acești algoritmi presupun că graficele sunt nedirecționate și conectate cu rezoluția buclelor și a mai multor margini. Când lucrați cu grafice de rețea care reprezintă conexiuni simple care adesea nu au bucle sau margini multiple (unde marginile reprezintă conexiuni între oameni). În acest caz, folosind algoritmul lui Brandes, indicele de centralitate final este împărțit la 2 pentru a ține seama de faptul că fiecare cale cea mai scurtă este numărată de două ori [22] . $O(V^{3})$ $O(V^{2}\log V+VE)$ $O(VE)$

Gradul de influență

Gradul de influență este o măsură a influenței unui nod în rețea . Acesta atribuie scoruri relative tuturor nodurilor din rețea pe baza conceptului că legăturile la nodurile cu scoruri mari contribuie mai mult la scorul nodului în cauză decât aceeași legătură către un nod cu scoruri scăzute [23] [5] [5] . PageRank -ul Google și centralitatea nodului lui Katz sunt variante ale gradului de influență [24] .

Folosind matricea de adiacență pentru a găsi gradul de influență

Pentru un graf dat cu vârfuri, fie matricea de adiacență , adică , dacă vârful este conectat la vârf , și altfel. Indicele de centralitate relativă a vârfurilor poate fi definit ca $G:=(V,E)$ $|V|$ $A=(a_{v,t})$ $a_{v,t}=1$ $v$ $t$ $a_{v,t}=0$ $v$

x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _ {t\în G}a_{v,t}x_{t}

unde este mulțimea vecinilor vârfului și este o constantă. După transformări minore, această expresie poate fi rescrisă în notație vectorială ca o ecuație pentru un vector propriu $M(v)$ $v$ $\lambda$

\mathbf {Ax} = {\lambda }\mathbf {x}

În general, există multe valori proprii diferite pentru care există un vector propriu diferit de zero. Deoarece elementele matricei de adiacență sunt nenegative, există o singură valoare proprie cea mai mare care este reală și pozitivă, după teorema Frobenius–Perron . Această valoare proprie cea mai mare oferă măsura dorită a centralității [23] . Componenta vectorului propriu asociat oferă centralitatea relativă a unui vârf în rețea. Vectorul propriu este definit până la un factor, astfel încât doar relația dintre centralitățile vârfurilor este complet definită. Pentru a determina valoarea absolută a exponentului, este necesar să se normalizeze vectorul propriu, de exemplu, astfel încât suma tuturor vârfurilor să fie egală cu 1 sau să se normalizeze cu numărul total de vârfuri n . Metoda puterii este unul dintre mulți algoritmi de derivare a valorilor proprii care pot fi utilizați pentru a găsi acest vector propriu dominant [24] . Mai mult, aceasta poate fi generalizată astfel încât elementele matricei A pot fi numere reale reprezentând puterea legăturii, ca într-o matrice stocastică . $\lambda$ $v^{th}$ $v$

Centralitate după Katz

Centralitatea conform lui Kac [25] este o generalizare a gradului de conexiune. Conectivitatea măsoară numărul de vecini direcți, iar centralitatea Kac măsoară numărul tuturor nodurilor care pot fi conectate prin căi în timp ce penalizează nodurile îndepărtate. Matematic, această centralitate este definită ca

x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}

unde este un multiplicator de atenuare din intervalul . $\alfa$ $(0,1)$

Potrivit lui Katz, centralitatea poate fi privită ca o variantă a gradului de influență. O altă formă de centralitate conform lui Kac este

x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).

În comparație cu gradul de influență , acesta este înlocuit cu $x_{j}$ $x_{j}+1.$

Sa arătat [26] că vectorul propriu principal (corespunzând celei mai mari valori proprii a matricei de adiacență ) este limita de centralitate Kac pe măsură ce k se apropie de jos. $A$ $\alfa$ ${\tfrac {1}{\lambda ))$

PageRank

PageRank satisface următoarea egalitate

x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)))+{\frac {1-\alpha }{N}} ,

Unde

L(j)=\sum _{i}a_{ji)

este egal cu numărul de vecini ai nodului (sau numărul de conexiuni de ieșire ale graficului direcționat). În comparație cu gradul de influență și centralitate al lui Katz, factorul de scalare este o diferență importantă . Diferența dintre PageRank și gradul de influență constă în faptul că vectorul PageRank este un vector propriu stânga (adică un vector propriu al matricei transpuse, rețineți că multiplicatorul are ordinea inversă a indicilor) [27] . $j$ $L(j)$ $a_{ji)$

Centralitatea percolației

Există o grămadă de măsuri de centralitate pentru a determina „importanța” unui singur nod într-o rețea complexă. Cu toate acestea, ele reflectă importanța unui nod pur în termeni topologici, iar valoarea unui nod nu depinde în niciun fel de „starea” nodului. Valoarea rămâne constantă indiferent de dinamica rețelei. Acest lucru este valabil chiar și pentru măsurile de mediere măsurate. Cu toate acestea, un nod poate fi, de asemenea, situat central în ceea ce privește gradul de intermediere sau altă măsură de centralitate, dar să nu fie „localizat central” în contextul unei rețele în care există o scurgere. Scurgerea „infecției” are loc în rețelele complexe într-un număr mare de scenarii. O infecție virală sau bacteriană se poate răspândi prin rețelele de socializare ale oamenilor, cunoscute sub numele de rețele de contact. Răspândirea bolii poate fi privită ș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 sau știrile despre oferte și oferte de afaceri se pot răspândi și prin rețelele sociale ale oamenilor. În toate aceste scenarii, „infecția” 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 Pairavinan și colab .[28] .

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 numărul total de căi cele mai scurte de la nod la nod și este 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ă o stare strânsă la momentul , și când , care indică o scurgere completă la timp . Valorile dintre aceste valori înseamnă 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 terminale, cel mai rău caz de timp este . $O(NM)$ $O(N^{3})$

Centralitatea clicului încrucișat

Centralitatea încrucișată a unui nod individual într-un grafic complex determină conexiunile nodului la diferite clicuri . Un nod cu centralitate ridicată a clicurilor încrucișate promovează răspândirea informațiilor sau a bolii în grafic. Clicile sunt subgrafe în care fiecare nod este conectat la toate celelalte noduri de clică. Centralitatea clicului încrucișat a unui nod pentru un graf dat cu vârfuri și muchii este notat ca și egal cu numărul de clicuri căruia îi aparține vârful . Această măsură a fost folosită în lucrarea lui Fagani [29] , dar a fost propusă pentru prima dată de Everett și Borgatti în 1998 sub denumirea de „clique overlap centrality”. $v$ $G:=(V,E)$ $|V|$ $|E|$ $X(v)$ $v$

Centralitatea Freeman

Centralitatea oricărei rețele este o măsură a cât de central este nodul său cel mai central în comparație cu alte noduri [10] . Măsura centralității este apoi (a) calculată ca sumă a diferențelor de centralitate dintre cel mai central nod din rețea și toate celelalte noduri și (b) împărțind această valoare la cea mai mare sumă teoretică a diferențelor oricărei rețele din rețea. aceeași dimensiune [10] . Atunci orice măsură de centralitate poate avea propria sa măsură de centralitate. Din punct de vedere formal, dacă este măsura centralității punctului , dacă este cea mai mare astfel de măsură din rețea și dacă $C_{x}(p_{i})$ $i$ $C_{x}(p_{*})$

\max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})

este cea mai mare sumă de diferențe în centralitatea punctului pentru orice graf cu același număr de noduri, atunci centralitatea rețelei este [10] $C_{x}$

C_{x}={\frac {\sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}{\max \ suma _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}}.

Măsuri ale centralității bazate pe diferențe

Pentru a obține rezultate mai bune în clasarea nodurilor unei rețele date, Alvarez-Socorro (et al.) [30] folosește o măsură a disimilarității (caracteristică teoriei clasificării și analizei datelor) pentru a îmbunătăți măsura centralității în rețelele complexe. Acest lucru este ilustrat de gradul de influență prin calcularea centralității fiecărui nod prin rezolvarea problemei cu valori proprii

W\mathbf {c} =\lambda \mathbf {c}

unde (produs în funcție de coordonate) și este o matrice de disimilaritate arbitrară , definită în termeni de măsurare a disimilarității. De exemplu, prin diferența lui Jaccard dată de formulă $W_{ij}=A_{ij}D_{ij}$ $D_{ij}$

D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{ +}(j)|}}

Această măsură ne permite să cuantificăm contribuția topologică (deci numită centralitate de contribuție) a fiecărui nod la centralitatea unui anumit nod, obținând un raport mai mare greutate/importanță a acelor noduri cu o diferență mai mare, deoarece acest lucru permite unui nod dat să ajungă la noduri care nu poate fi contactat direct.

Rețineți că este nenegativ, deoarece și sunt matrici nenegative, deci putem folosi teorema Frobenius-Perron pentru a ne asigura că soluția problemei de mai sus este unică pentru cu c nenegativ , ceea ce ne permite să obținem centralitatea lui fiecare nod din rețea. Astfel, centralitatea nodului i este egală cu $W$ $A$ $D$ $\lambda =\lambda _{max}$

c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\ ,j=1,\cdots ,n

unde este egal cu numărul de noduri de rețea. Unele rețele și măsuri de disimilaritate au fost testate de Alvarez-Socorro (et al.) [31] și s-au obținut rezultate îmbunătățite în cazurile studiate. $n$

Generalizări

Studiile empirice și teoretice generalizează conceptul de centralitate în contextul rețelelor statice la centralități dinamice [32] în contextul rețelelor dependente de timp și de scurtă durată [33] [34] [35] .

Pentru o generalizare a rețelelor ponderate, vezi Opsal și colab .[36] .

Conceptul de centralitate a fost, de asemenea, generalizat la nivel de grup. De exemplu, gradul de mediere a grupului arată proporția legăturilor geodezice de perechi (adică căi de lungime minimă) de noduri care nu aparțin grupului care trec prin grup [37] [38] .

Vezi și

Note

↑ O parte a terminologiei este preluată din articolul lui A. S. Semenov și M. V. Bartosh „ESTIMAREA STABILITĂȚII REȚELEI INTERNETUL LUCRURILOR UTILIZAREA INDICATORILOR DE CENTRALITATE A RELATIILOR” . Termenii din literatura rusă nu s-au stabilit. Deci, în articolul lui Evin I. A. Rețele complexe: o introducere în teorie , în locul termenului „grad de mediere”, sunt folosiți termenii „încărcare nod”, „conexiuni cu importanță maximă”. Pe pagina Network Metrics , în loc de termenul „grad de conectivitate”, este folosită traducerea literală „centralitate după grad”, în locul termenilor „grad de …” - „centralitate de …”. Uneori se folosește termenul „centralitate” în locul termenului „centralitate”.
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , p. 1170–1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , p. 55–71.
↑ 1 2 3 Negre, Morzan, Hendrickson et al., 2018 , p. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , p. 466–484.
↑ 1 2 Benzi, Klymko, 2013 , p. 686–706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , p. 607-650.
↑ Krackhardt, 1990 , p. 342–369.
↑ 1 2 3 4 5 Freeman, 1979 , p. 215–239.
↑ 12 Avocat , 2015 , p. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , p. P07005.
↑ Bauer și Lizier, 2012 , p. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , p. 1–13.
↑ Ghoshal, Barabsi, 2011 , p. 394.
↑ Bavelas, 1950 , p. 725–730.
↑ Sabidussi, 1966 , p. 581–603.
↑ Marchiori, Latora, 2000 , p. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , p. 35–41.
↑ 1 2 3 Brandes, 2001 , p. 163–177.
↑ 12 Newman , 2007 , p. 1-12.
↑ 12 Societatea Americană de Matematică . (nedefinit)
↑ Katz, 1953 , p. 39–43.
↑ Bonacich, 1991 , p. 155–168.
↑ Cum clasează Google paginile web? Arhivat din original la 31 ianuarie 2012. 20Î: Despre viața în rețea
↑ Piraveenan, Prokopenko, Hossain, 2013 , p. e53095.
↑ Faghani, 2013 , p. 1815–1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , p. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. Informații suplimentare pentru Eigencentrality bazate pe măsuri de diferență dezvăluie noduri centrale în rețele complexe . Nature Publishing Group. (nedefinit)
↑ Braha, Bar-Yam, 2006 , p. 59–63.
↑ Hill, Braha, 2010 , p. 046105.
↑ Gross, Sayama, 2009 .
↑ Holme, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , p. 245–251.
↑ Everett, Borgatti, 2005 , p. 57–76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Literatură

Newman MEJ Networks: o introducere. — Oxford, Marea Britanie: Oxford University Press, 2010.
Newman MEJ Matematica rețelelor, // The New Palgrave Encyclopedia of Economics . — Basingstoke, Palgrave Macmillan, 2007.

Filip Bonacich. Putere și centralitate: o familie de măsuri // American Journal of Sociology. - 1987. - T. 92 , nr. 5 . - doi : 10.1086/228631 .
Bonacich P. Centralități simultane de grup și individuale // Rețele sociale. - 1991. - T. 13 , nr. 2 . - doi : 10.1016/0378-8733(91)90018-o .
Stephen P. Borgatti. Centralitate și flux de rețea // Rețele sociale. - 2005. - T. 27 . - doi : 10.1016/j.socnet.2004.11.008 .
Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. Centralitatea vectorului propriu pentru caracterizarea căilor alosterice ale proteinelor // Proceedings of the National Academy of Sciences. - 2018. - T. 115 . - doi : 10.1073/pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. O perspectivă teoretică grafică asupra centralității // Rețelele sociale. - 2006. - T. 28 , nr. 4 . - doi : 10.1016/j.socnet.2005.11.005 .
Michele Benzi, Christine Klymko. O analiză matriceală a diferitelor măsuri de centralitate // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , nr. 2 . - doi : 10.1137/130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Calcul eficient al valorii Shapley pentru centralitatea rețelei teoretice de joc // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Evaluarea peisajului politic: structură, cunoaștere și putere în organizații // Administrative Science Quarterly. - 1990. - Iunie ( vol. 35 , numărul 2 ). - doi : 10.2307/2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. Prezicerea epidemiei din caracteristicile individuale ale împrăștiatorilor // J. Stat. Mec.: Teorie Exp.. - 2012. - T. 2012 . - doi : 10.1088/1742-5468/2012/07/p07005 . - Cod . - arXiv : 1202.0024 .
Frank Bauer, Joseph Lizier. Identificarea răspânditorilor care afectează și estimarea eficientă a numărului de infecții în modelele epidemice: O abordare de numărare a plimbărilor // Europhys Lett. - 2012. - T. 99 . - S. 68007 . - doi : 10.1209/0295-5075/99/68007 . - Cod biblic . - arXiv : 1203.0502 .
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Centralitatea epidemiei -- există un impact epidemic subestimat al nodurilor periferice ale rețelei? // The European Physical Journal B. - 2013. - T. 86 , Nr. 10 . - doi : 10.1140/epjb/e2013-31025-5 . - arXiv : 1110.2558 .
Ghoshal G., Barabsi AL Clasificarea stabilității și a nodurilor super-stabile în rețele complexe. // NatCommun. - 2011. - T. 2 . - doi : 10.1038/ncomms1396 . — Cod biblic .
Avocatul Glenn. Înțelegerea puterii de răspândire a tuturor nodurilor dintr-o rețea: o perspectivă în timp continuu // Sci Rep. - 2015. - or. 5 . - doi : 10.1038/srep08665 . - Cod biblic . - arXiv : 1405.6707 . — PMID 25727453 .
Linton C. Freeman. Centralitatea în rețelele sociale: Clarificare conceptuală // Rețelele sociale. - 1979. - Vol. 1 , număr. 3 . — S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Arhivat din original pe 22 februarie 2016.
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 . — .
Alex Bavelas. Modele de comunicare în grupuri orientate spre sarcini // J. Acoust. soc. A.m. - 1950. - T. 22 , nr. 6 .
Sabidussi G. Sabidussi. Indicele de centralitate al unui grafic // Psihometrie. - 1966. - T. 31 , nr. 4 . - doi : 10.1007/bf02289527 . — PMID 5232444 .
Massimo Marchiori, Vito Latora. Armonia în lumea mică // Fizica A: Mecanica statistică și aplicațiile sale. - 2000. - T. 285 , nr. 3–4 . - doi : 10.1016/s0378-4371(00)00311-3 . - Cod . - arXiv : cond-mat/0008357 .
Anthony Decker. Distanța conceptuală în analiza rețelelor sociale // Journal of Social Structure. - 2005. - T. 6 , nr. 3 .
Yannick Rochat. Centralitatea de apropiere extinsă la graficele neconectate: Indicele de centralitate armonică // Aplicații ale analizei rețelelor sociale, ASNA 2009 . — 2009.
Ulrik Brandes. Un algoritm mai rapid pentru centralitatea interness // Journal of Mathematical Sociology. - 2001. - T. 25 , nr. 2 . - doi : 10.1080/0022250x.2001.9990249 .
Newman MEJ Matematica rețelelor .
Katz L. A New Status Index Derived from Sociometric Index // Psychometrics. - 1953. - S. 39-43 .
Piraveenan M., Prokopenko M., Hossain L. Centralitatea percolației: cuantificarea impactului teoretic grafic al nodurilor în timpul percolației în rețele // PLOS ONE. - 2013. - T. 8 , nr. 1 . - doi : 10.1371/journal.pone.0053095 . - Cod biblic . — PMID 23349699 .
Mohamamd Reza Faghani. Un studiu al mecanismelor de propagare și detectare a viermilor XSS în rețelele sociale online // Tranzacții IEEE privind criminalistica și securitatea informațiilor. - 2013. - T. 8 , nr. 11 . - doi : 10.1109/TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA Eigencentralitatea bazată pe măsuri de disimilaritate dezvăluie noduri centrale în rețele complexe // Rapoarte științifice. - 2015. - noiembrie ( vol. 5 ). - doi : 10.1038/srep17095 . - Cod biblic . — PMID 26603652 .
Braha D., Bar-Yam Y. From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks // Complexitate. - 2006. - T. 12 , nr. 2 . - doi : 10.1002/cplx.20156 . - Cod . - arXiv : fizica/0611295 .
Hill SA, Braha D. Dynamic Model of Time-Dependent Complex Networks // Physical Review E. - 2010. - Vol. 82 , nr. 4 . - doi : 10.1103/physreve.82.046105 . - Cod . - arXiv : 0901.4407 . — PMID 21230343 .
Rețele adaptive: teorie, modele și aplicații / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Temporal Networks. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Centralitatea nodului în rețelele ponderate: grad de generalizare și cele mai scurte căi // Rețele sociale. - 2010. - T. 32 , nr. 3 . - doi : 10.1016/j.socnet.2010.03.006 . Arhivat din original pe 26 februarie 2018.
Everett MG, Borgatti SP Extinderea centralității. În PJ Carrington, J. Scott și S. Wasserman (eds.) // Modele și metode în analiza rețelelor sociale. - New York: Cambridge University Press, 2005. - S. 57-76.
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.

Lectură pentru lecturi suplimentare

Koschützki, D.; Lehmann, K.A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. și Zlotowski, O. (2005) Indici de centralitate. În Brandes, U. și Erlebach, T. (Eds.) Network Analysis: Methodological Foundations , pp. 16-61, LNCS 3418, Springer-Verlag.