Kac knuten centralitet

Kac nod centralitet är ett mått på centralitet i ett nätverk . Begreppet centralitet introducerades av Leo Katz 1953; det har använts för att mäta den relativa graden av påverkan av en aktör (eller nod) inom ett socialt nätverk [1] . Till skillnad från typiska mått på centralitet, som endast tar hänsyn till de kortaste vägarna ( geodetik ) mellan ett par aktiva objekt, mäter Katz centralitet påverkan genom att ta hänsyn till det totala antalet rutter mellan ett par aktiva objekt [2] .

Indikatorn liknar Googles PageRank - länkrankning och graden av påverkan [3] .

Dimension

Katz centralitet beräknar det relativa inflytandet av en nod i ett nätverk genom att mäta antalet närmaste grannar (noder av första graden) såväl som alla andra noder i nätverket som är anslutna via de närmaste grannarna. Varje väg eller länk mellan ett par noder tilldelas en vikt som definieras av värdet och avståndet mellan noderna som . I detta fall reduceras vikten av anslutningar med avlägsna grannar med en faktor [4] . $\alfa$ ${\displaystyle \alpha ^{d))$ $\alfa$

Till exempel, i figuren till höger, föreställ dig att centraliteten för "John" mäts och att . Vikten som tilldelas varje länk som kopplar "John" till sina närmaste grannar "Jane" och "Bob" kommer att vara . Eftersom "Jose" är kopplad till "John" indirekt via "Bob", kommer vikten som tilldelas denna anslutning (bestående av två länkar) att vara . På samma sätt kommer vikten som tilldelas länken mellan "Agneta" och "John" via "Aziz" och "Jane" att vara , och vikten som tilldelas länken mellan "Agneta" och "John" via "Diego )", "Jose ” och ”Bob”, kommer att vara lika med . $\alpha =0.5$ $(0.5)^{1}=0.5$ $(0.5)^{2}=0.25$ $(0.5)^{3}=0.125$ $(0,5)^{4}=0,0625$

Matematisk formulering

Låt A vara närliggande matris för nätverket i fråga. Elementen i matrisen A är variabler som tar värdet 1 om nod i är kopplad till nod j och värdet 0 annars. Graderna av matrisen A visar närvaron (eller frånvaron) av länkar mellan två noder genom mellanhänder. Till exempel, i matrisen , om elementet är , betyder detta att noderna 2 och 12 är sammankopplade med någon väg av längd 3. Om betecknar Kac-centraliteten för nod i , då matematiskt $(a_{ij})$ $A^{3}$ $(a_{2,12})=1$ $C_{\mathrm {Katz} }(i)$

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

Observera att definitionen ovan använder det faktum att elementet vid matrispositionen återspeglar det totala antalet gradkopplingar mellan noderna och . Värdet på dämpningsfaktorn bör väljas så att det är mindre än det reciproka av det absoluta värdet av det största egenvärdet för matrisen A [5] . I det här fallet kan följande uttryck användas för att beräkna Kac-centraliteten: $(I j)$ $A^{k}$ $k$ $i$ $j$ $\alfa$

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

var:

$E$ är identitetsmatrisen;

${\overrightarrow {I}}$ är en vektor med storlek n ( n är lika med antalet noder) bestående av ettor;

$A^{T}$ är den transponerade matrisen av matris A;

${\displaystyle (E-\alpha A^{T})^{-1))$ är den inverterbara matrisen för matrisen [5] . $(E-\alpha A^{T})$

En förlängning av detta koncept tillåter beräkning av rutter under dynamiska förhållanden [6] [7] . Tidsriktningen bevaras så att bidraget är asymmetriskt i informationsutbredningsriktningen.

Nätverk ger data i formen:

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

för

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

representerar närliggande matris vid varje tidpunkt . Följaktligen, $t_k$

$\left(A^{[k]}\right)_{ij}=1$ om det finns en kant från nod till nod vid tidpunkten och 0 annars. $i$ $j$ $t_k$

Tiderna är ordnade, men inte nödvändigtvis jämnt fördelade. för varje är en viktad räkning av antalet dynamiska längdrutter från nod till nod . Typ av dynamisk kommunikation mellan noder: ${\displaystyle t_{0}<t_{1}<\cdots <t_{M))$ $Q\in \mathbb {R} ^{N\ gånger N}$ ${\displaystyle (Q)_{ij))$ $w$ $i$ $j$

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

I normaliserad form:

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

Således visar centralitet hur effektivt en nod kan "skicka" och "ta emot" dynamiska meddelanden över nätverket: $n$

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

och

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

Applikationer

Katz centralitet kan användas för att beräkna centralitet i riktade nätverk som offertnätverk och World Wide Web [8] . Det är mest användbart i analysen av riktade acykliska grafer, där traditionellt använda mått, såsom grad av påverkan , blir meningslösa [8] .

Katz-centralitet kan också användas för att utvärdera den relativa statusen eller inflytandet för objekt i ett socialt nätverk. En artikel av Laughlin et al [9] visar analysen av att tillämpa den dynamiska versionen av Katz centralitet på Twitter-data, identifiera objekt som har status som stabila diskussionsledare. Tillämpningen av Katz-konceptet med centralitet gör att man kan jämföra metoder som involverar mänskliga experter och utvärdera överensstämmelsen mellan deras resultat med en panel av experter på sociala nätverk.

Inom neurovetenskapen har det visat sig att Kac-centraliteten korrelerar med den relativa avfyringshastigheten för neuroner i ett neuralt nätverk [10] . Katz centralitet tidsmässiga expansion har tillämpats på fMRI -data som erhållits från musikinlärningsexperiment [11] där data samlas in före och efter inlärningsprocessen. Resultaten visade att förändringar i nätverkets struktur skapade i varje session kvantitativa kopplingar som bildar kluster på den så kallade linjen för framgångsrikt lärande.

Anteckningar

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

Litteratur

Katz L. Ett nytt statusindex härlett från Sociometric Index // Psychometrics. — 1953.
Hanneman RA, Riddle M. Introduktion till sociala nätverksmetoder. — Riverside, CA: University of California, Riverside, 2005.
Aggarwal CC Social Network Data Analysis. — New York, NY: Springer, 2011.
Junker BH, Schreiber F. Analys av biologiska nätverk. - Hoboken, NJ: John Wiley & Sons, 2008. - ISBN 978-0-470-04144-4 .
Newman MEJ Networks: En introduktion. — Oxford, Storbritannien: Oxford University Press, 2010.
Vigna S. Spectral ranking // Nätverksvetenskap. - 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. Dynamisk nätverkscentralitet sammanfattar lärande i den mänskliga hjärnan // Journal of Complex Networks. - 2013. - Vol. 1 , nummer. 1 .
Peter Grindrod, Desmond J. Higham. Evolverande grafer: Dynamiska modeller, omvända problem och fortplantning // Proc. Roy. soc. A. - 2010. - T. 466 .
Peter Grindrod, Mark C. Parsons, Desmond J. Higham, Ernesto Estrada. Kommunicerbarhet över nätverk under utveckling // Fysisk granskning E. - APS, 2011. - T. 83 .
Peter Laflin, Alexander V. Mantzaris, Fiona Ainley, Amanda Otley, Peter Grindrod, Desmond J. Higham. Upptäcka och validera inflytande i ett dynamiskt socialt nätverk online // Social Network Analysis and Mining. - Springer, 2013. - V. 3 , nr 4 .
Jack McKay Fletcher, Thomas Wennekers. Från struktur till aktivitet: Använda centralitetsmått för att förutsäga neuronaktivitet // International Journal of Neural Systems. - 2017. - T. 0 , nr 0 . - doi : 10.1142/S0129065717500137 .