Kac csomó központi

A Kac csomópont központossága a hálózat központiságának mértéke . A centralitás fogalmát Leo Katz vezette be 1953-ban; a közösségi hálózaton belüli szereplő (vagy csomópont) befolyásának relatív mértékének mérésére használták [1] . Ellentétben a tipikus centralitás mérésekkel, amelyek csak a legrövidebb utakat ( geodéziákat ) veszik figyelembe egy pár aktív objektum között, a Katz-centralitás úgy méri a hatást, hogy figyelembe veszi az aktív objektumok párja közötti útvonalak teljes számát [2] .

A mutató hasonló a Google PageRank link rangsorához és a befolyás mértékéhez [3] .

Méret

A Katz-központúság kiszámítja egy csomópont relatív befolyását a hálózatban a legközelebbi szomszédok (első fokú csomópontok), valamint a hálózat összes többi csomópontjának a számának mérésével, amelyek a legközelebbi szomszédokon keresztül csatlakoznak. A csomópontpárok közötti bármely útvonalhoz vagy kapcsolathoz az érték és a csomópontok közötti távolság határozza meg a súlyt . Ebben az esetben a távoli szomszédokkal létesített kapcsolatok súlya egy faktorral csökken [4] . $\alpha$ ${\displaystyle \alpha ^{d))$ $\alpha$

Például képzelje el a jobb oldali ábrán, hogy "John" központi szerepét mérik, és hogy . A „John”-t közvetlen szomszédaival „Jane”-nel és „Bobbal” összekötő linkekhez rendelt súly . Mivel "Jose" közvetve "Bobon" keresztül kapcsolódik "Johnhoz", a (két linkből álló) kapcsolathoz rendelt súly a következő lesz . Hasonlóképpen az „Agneta” és „John” közötti kapcsolathoz „Aziz” és „Jane” keresztül rendelt súly a következő lesz , és az „Agneta” és „John” közötti kapcsolathoz „Diego )”, „Jose” rendelt súly ” és „Bob”, egyenlő lesz a -val . $\alpha =0,5$ $(0,5)^{1}=0,5$ $(0,5)^{2}=0,25$ $(0,5)^{3}=0,125$ $(0,5)^{4}=0,0625$

Matematikai megfogalmazás

Legyen A a vizsgált hálózat szomszédsági mátrixa . Az A mátrix elemei olyan változók, amelyek 1 értéket vesznek fel, ha az i csomópont a j csomóponthoz kapcsolódik, egyébként pedig 0 értéket. Az A mátrix fokai a két csomópont közötti kapcsolatok meglétét (vagy hiányát) mutatják közvetítőkön keresztül. Például a mátrixban , ha az elem , akkor ez azt jelenti, hogy a 2. és 12. csomópontot valamilyen 3 hosszúságú út köti össze. If jelöli az i csomópont Kac-centralitását , akkor matematikailag $(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}~.

Vegye figyelembe, hogy a fenti definíció azt a tényt használja, hogy a mátrix pozíciójában lévő elem tükrözi a csomópontok és a csomópontok közötti fokú csatlakozások teljes számát . A csillapítási tényező értékét úgy kell megválasztani, hogy az kisebb legyen, mint az A mátrix legnagyobb sajátértéke abszolút értékének reciproka [5] . Ebben az esetben a következő kifejezés használható a Kac-centralitás kiszámításához: $(i,j)$ $A^{k}$ $k$ $én$ $j$ $\alpha$

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

ahol:

$E$ az identitásmátrix;

${\overrightarrow {I}}$ egy n méretű vektor ( n egyenlő a csomópontok számával), amely egyesekből áll;

$A^{T}$ az A mátrix transzponált mátrixa ;

${\displaystyle (E-\alpha A^{T})^{-1))$ a mátrix invertálható mátrixa [ 5] . $(E-\alpha A^{T})$

Ennek a koncepciónak a kiterjesztése lehetővé teszi az útvonalak kiszámítását dinamikus körülmények között [6] [7] . Az idő iránya megmarad, így a hozzájárulás aszimmetrikus az információ terjedésének irányában.

A hálózatok a következő formában adják meg az adatokat:

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

számára

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

minden időpontban a szomszédsági mátrixot reprezentálja . Következésképpen, $t_k$

$\left(A^{[k]}\right)_{ij}=1$ ha van él a csomóponttól a csomópontig időben , és 0 egyébként. $én$ $j$ $t_k$

Az időpontok sorrendben vannak, de nem feltétlenül egyenletesen oszlanak el. mindegyik a csomóponttól a csomópontig terjedő dinamikus útvonalak számának súlyozott száma . A csomópontok közötti dinamikus kommunikáció típusa: ${\displaystyle t_{0}<t_{1}<\cdots <t_{M))$ $Q\in \mathbb {R} ^{N\times N}$ ${\displaystyle (Q)_{ij))$ $w$ $én$ $j$

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

Normalizált formában:

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

Így a központosítás megmutatja, hogy egy csomópont milyen hatékonyan képes dinamikus üzeneteket "küldeni" és "fogadni" a hálózaton keresztül: $n$

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

és

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

Alkalmazások

A Katz-centralitás felhasználható irányított hálózatokban, például árajánlati hálózatokban és a World Wide Web-ben [8] . Leginkább az irányított aciklikus gráfok elemzésénél hasznos, ahol a hagyományosan használt mértékek, például a befolyás mértéke értelmetlenné válnak [8] .

A Katz-centralitás a közösségi hálózatban lévő objektumok relatív állapotának vagy befolyásának értékelésére is használható. Laughlin és munkatársai [9] egy cikke bemutatja a Katz-centralitás dinamikus változatának Twitter-adatokra történő alkalmazásának elemzését, azonosítva azokat az objektumokat, amelyek stabil vitavezetői státusszal rendelkeznek. A Katz-féle centralitás-koncepció alkalmazása lehetővé teszi a humán szakértőket bevonó módszertanok összehasonlítását, és az eredmények egyezését a közösségi hálózatok szakértőiből álló testülettel.

Az idegtudományokban azt találták, hogy a Kac-centralitás korrelál a neuronok relatív tüzelési sebességével egy neurális hálózatban [10] . Katz centralitási időbeli kiterjesztését alkalmazták a zenetanulási kísérletekből [11] nyert fMRI adatokra , amelyek során a tanulási folyamat előtt és után gyűjtenek adatokat. Az eredmények azt mutatták, hogy a hálózat szerkezetének változása minden foglalkozáson kvantitatív kapcsolatokat hoz létre, amelyek klasztereket alkotnak az ún. sikeres tanulás vonalán.

Jegyzetek

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

Irodalom

Katz L. A szociometriai indexből származó új állapotindex // Pszichometria. – 1953.
Hanneman RA, Riddle M. Bevezetés a közösségi hálózatok módszereibe. – Riverside, CA: University of California, Riverside, 2005.
Aggarwal CC közösségi hálózat adatelemzése. – New York, NY: Springer, 2011.
Junker BH, Schreiber F. Biológiai hálózatok elemzése. - Hoboken, NJ: John Wiley & Sons, 2008. - ISBN 978-0-470-04144-4 .
Newman MEJ Networks: Bevezetés. – Oxford, Egyesült Királyság: Oxford University Press, 2010.
Vigna S. Spektrális rangsor // Hálózattudomány. - 2016. - 4. évf. , sz. 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. A dinamikus hálózatközpontúság összefoglalja a tanulást az emberi agyban // Journal of Complex Networks. - 2013. - 1. évf. , szám. 1 .
Peter Grindrod, Desmond J. Higham. Fejlődő gráfok: Dinamikus modellek, inverz problémák és terjedés // Proc. Roy. szoc. A. - 2010. - T. 466 .
Peter Grindrod, Mark C. Parsons, Desmond J. Higham, Ernesto Estrada. Kommunikálhatóság a fejlődő hálózatokon át // Fizikai Szemle E. - APS, 2011. - T. 83 .
Peter Laflin, Alexander V. Mantzaris, Fiona Ainley, Amanda Otley, Peter Grindrod, Desmond J. Higham. Befolyás felfedezése és érvényesítése egy dinamikus online közösségi hálózatban // Social Network Analysis and Mining. - Springer, 2013. - V. 3. , 4. sz .
Jack McKay Fletcher, Thomas Wennekers. A szerkezettől a tevékenységig: A központi mérőszámok használata a neuronális aktivitás előrejelzésére // International Journal of Neural Systems. - 2017. - T. 0 , 0. sz . - doi : 10.1142/S0129065717500137 .