Centralitatea nodului Kac

Centralitatea nodului Kac este o măsură a centralității într- o rețea . Conceptul de centralitate a fost introdus de Leo Katz în 1953; a fost folosit pentru a măsura gradul relativ de influență al unui actor (sau nod) în cadrul unei rețele sociale [1] . Spre deosebire de măsurile tipice de centralitate, care iau în considerare doar cele mai scurte căi ( geodezice ) între o pereche de obiecte active, centralitatea Katz măsoară impactul luând în considerare numărul total de rute între o pereche de obiecte active [2] .

Indicatorul este asemănător cu clasarea link -urilor PageRank de la Google și cu gradul de influență [3] .

Dimensiune

Centralitatea Katz calculează influența relativă a unui nod dintr-o rețea prin măsurarea numărului de vecini cei mai apropiați (noduri de gradul I), precum și a tuturor celorlalte noduri din rețea care sunt conectate prin cei mai apropiați vecini. Orice cale sau legătură între o pereche de noduri i se atribuie o pondere definită de valoarea și distanța dintre noduri ca . În acest caz, ponderea conexiunilor cu vecinii la distanță este redusă cu un factor [4] . $\alfa$ $\alpha ^{d)$ $\alfa$

De exemplu, în figura din dreapta, imaginați-vă că centralitatea lui „Ioan” este măsurată și că . Greutatea atribuită fiecărei legături care leagă „John” de vecinii săi imediati „Jane” și „Bob” va fi . Deoarece „Jose” este conectat la „John” indirect prin „Bob”, ponderea atribuită acestei conexiuni (formată din două legături) va fi . În mod similar, ponderea atribuită legăturii dintre „Agneta” și „John” prin „Aziz” și „Jane” va fi , iar ponderea atribuită legăturii dintre „Agneta” și „John” prin „Diego )”, „Jose ” și „Bob”, vor fi egale cu . $\alpha =0,5$ $(0,5)^{1}=0,5$ $(0,5)^{2}=0,25$ $(0,5)^{3}=0,125$ $(0,5)^{4}=0,0625$

Formulare matematică

Fie A matricea de adiacență a rețelei luate în considerare. Elementele matricei A sunt variabile care iau valoarea 1 dacă nodul i este conectat la nodul j , iar valoarea 0 în caz contrar. Gradele matricei A arată prezența (sau absența) legăturilor între două noduri prin intermediari. De exemplu, în matrice , dacă elementul este , atunci aceasta înseamnă că nodurile 2 și 12 sunt conectate printr-o cale de lungime 3. Dacă denotă centralitatea Kac a nodului i , atunci matematic $(a_{ij})$ $A^{3}$ $(a_{2,12})=1$ $C_{\mathrm {Katz} }(i)$

C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{ k})_{ji}~.

Rețineți că definiția de mai sus folosește faptul că elementul din poziția matricei reflectă numărul total de îmbinări de grade dintre noduri și . Valoarea factorului de amortizare trebuie aleasă astfel încât să fie mai mică decât inversul valorii absolute a celei mai mari valori proprii a matricei A [5] . În acest caz, următoarea expresie poate fi utilizată pentru a calcula centralitatea Kac: $(i,j)$ $A^{k}$ $k$ $i$ $j$ $\alfa$

{\overrightarrow {C}}_{\mathrm {Katz} }=((E-\alpha A^{T})^{-1}-E){\overrightarrow {I}}~,

Unde:

$E$ este matricea identitară;

${\overrightarrow {I}}$ este un vector de dimensiune n ( n este egal cu numărul de noduri) format din unii;

$A^{T}$ este matricea transpusă a matricei A;

$(E-\alpha A^{T})^{-1)$ este matricea inversabilă a matricei [5] . $(E-\alpha A^{T})$

O extensie a acestui concept permite calcularea rutelor în condiții dinamice [6] [7] . Direcția timpului este conservată astfel încât contribuția este asimetrică în direcția de propagare a informațiilor.

Rețelele oferă date de forma:

\left\{A^{[k]}\in \mathbb {R} ^{N\times N}\right\}\qquad

pentru

\quad k=0,1,2,\ldots, M~,

reprezentand matricea de adiacenta in fiecare moment . Prin urmare, $t_k$

$\left(A^{[k]}\right)_{ij}=1$ dacă există o margine de la nod la nod la momentul , și 0 în caz contrar. $i$ $j$ $t_k$

Orele sunt ordonate, dar nu neapărat distribuite uniform. pentru fiecare este un număr ponderat al numărului de rute dinamice de lungime de la nod la nod . Tip de comunicare dinamică între noduri: $t_{0}<t_{1}<\cdots <t_{M)$ $Q\in \mathbb {R} ^{N\times N}$ $(Q)_{ij)$ $w$ $i$ $j$

{\mathcal {Q}}=\left(E-\alpha A^{[0]}\right)^{-1}\cdots \left(E-\alpha A^{[M]}\ dreapta)^{-1}~.

În formă normalizată:

{\hat {\mathcal {Q}}}^{[k]}={\frac ({\hat {\mathcal {Q}}}^{[k-1]}\left(E-\ alfa A^{[k]}\right)^{-1}}{\left\|{\hat {\mathcal {Q}}}^{[k-1]}\left(E-\alpha A^ {[k]}\dreapta)^{-1}\dreapta\|}}~.

Astfel, centralitatea arată cât de eficient un nod poate „trimite” și „primi” mesaje dinamice prin rețea: $n$

C_{n}^{\mathrm {difuzare} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{nk}\quad

și

\quad C_{n}^{\mathrm {primire} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{kn}~.

Aplicații

Centralitatea Katz poate fi folosită pentru a calcula centralitatea în rețele direcționate, cum ar fi rețelele de cotații și World Wide Web [8] . Este cel mai util în analiza graficelor aciclice direcționate, în care măsurile utilizate în mod tradițional, cum ar fi gradul de influență , devin lipsite de sens [8] .

Centralitatea Katz poate fi folosită și în evaluarea stării relative sau a influenței obiectelor dintr-o rețea socială. Un articol al lui Laughlin et al [9] demonstrează analiza aplicării versiunii dinamice a centralității Katz la datele Twitter, identificând obiecte care au statutul de lideri de discuții stabili. Aplicarea conceptului Katz de centralitate permite compararea metodologiilor care implică experți umani și evaluarea concordanței rezultatelor acestora cu un grup de experți în rețelele sociale.

În neuroștiințe , s-a descoperit că centralitatea Kac se corelează cu rata relativă de declanșare a neuronilor într-o rețea neuronală [10] . Expansiunea temporală a centralității lui Katz a fost aplicată datelor fMRI obținute din experimente de învățare muzicală [11] în care datele sunt colectate înainte și după procesul de învățare. Rezultatele au arătat că modificările în structura rețelei au creat în fiecare sesiune conexiuni cantitative care formează clustere pe așa-numita linie a învățării de succes.

Note

↑ Katz, 1953 , p. 39–43.
↑ Hanneman, Riddle, 2005 .
↑ Vigna, 2016 , p. 433-445.
↑ Aggarwal, 2011 .
↑ 12 Junker , Schreiber, 2008 .
↑ Grindrod, Parsons, Higham, Estrada, 2011 .
↑ Grindrod, Higham, 2010 , p. 753–770.
↑ 12 Newman , 2010 .
↑ Laflin, Mantzaris et al., 2013 .
↑ Fletcher și Wennekers 2017 , p. 1750013.
↑ Mantzaris, Bassett et al., 2013 , p. 83–92.

Literatură

Katz L. A New Status Index Derived from Sociometric Index // Psychometrics. — 1953.
Hanneman RA, Riddle M. Introducere în metodele rețelelor sociale. — Riverside, CA: Universitatea din California, Riverside, 2005.
Analiza datelor rețelei sociale Aggarwal CC . — New York, NY: Springer, 2011.
Junker BH, Schreiber F. Analiza rețelelor biologice. - Hoboken, NJ: John Wiley & Sons, 2008. - ISBN 978-0-470-04144-4 .
Newman MEJ Networks: o introducere. — Oxford, Marea Britanie: Oxford University Press, 2010.
Vigna S. Clasament spectral // Network Science. - 2016. - Vol. 4 , nr. 4 . - doi : 10.1017/nws.2016.21 .
Alexander V. Mantzaris, Danielle S. Bassett, Nicholas F. Wymbs, Ernesto Estrada, Mason A. Porter, Peter J. Mucha, Scott T. Grafton, Desmond J. Higham. Centralitatea dinamică a rețelei rezumă învățarea în creierul uman // Journal of Complex Networks. - 2013. - Vol. 1 , numărul. 1 .
Peter Grindrod, Desmond J. Higham. Grafice evolutive: Modele dinamice, probleme inverse și propagare // Proc. Roy. soc. A. - 2010. - T. 466 .
Peter Grindrod, Mark C. Parsons, Desmond J. Higham, Ernesto Estrada. Comunicabilitate prin rețele în evoluție // Physical Review E. - APS, 2011. - T. 83 .
Peter Laflin, Alexander V. Mantzaris, Fiona Ainley, Amanda Otley, Peter Grindrod, Desmond J. Higham. Descoperirea și validarea influenței într-o rețea socială online dinamică // Analiza rețelelor sociale și minerit. - Springer, 2013. - V. 3 , nr. 4 .
Jack McKay Fletcher, Thomas Wennekers. De la structură la activitate: utilizarea măsurilor de centralitate pentru a prezice activitatea neuronală // International Journal of Neural Systems. - 2017. - T. 0 , Nr. 0 . - doi : 10.1142/S0129065717500137 .