Centrální uzel Kac

Centralita uzlu Kac je mírou centrality v síti . Koncept centrality zavedl Leo Katz v roce 1953; používá se k měření relativního stupně vlivu aktéra (nebo uzlu) v rámci sociální sítě [1] . Na rozdíl od typických měření centrality, které berou v úvahu pouze nejkratší cesty ( geodetické ) mezi dvojicí aktivních objektů, Katzova centralita měří dopad tím, že bere v úvahu celkový počet tras mezi dvojicí aktivních objektů [2] .

Ukazatel je podobný hodnocení odkazů Google PageRank a míře ovlivnění [3] .

Rozměr

Katzova centralita vypočítává relativní vliv uzlu v síti měřením počtu nejbližších sousedů (uzlů prvního stupně) a také všech ostatních uzlů v síti, které jsou připojeny přes tyto nejbližší sousedy. Jakékoli cestě nebo spojnici mezi párem uzlů je přiřazena váha definovaná hodnotou a vzdáleností mezi uzly jako . V tomto případě je váha spojení se vzdálenými sousedy snížena o faktor [4] . $\alpha$ ${\displaystyle \alpha ^{d))$ $\alpha$

Například na obrázku vpravo si představte, že se měří centrálnost „Johna“ a že . Váha přiřazená každému odkazu, který spojuje „Johna“ s jeho bezprostředními sousedy „Jane“ a „Bob“, bude . Vzhledem k tomu, že "Jose" je spojen s "John" nepřímo prostřednictvím "Bob", váha přiřazená tomuto spojení (skládající se ze dvou odkazů) bude . Podobně váha přiřazená spojení mezi „Agneta“ a „John“ prostřednictvím „Aziz“ a „Jane“ bude , a váha přiřazená spojení mezi „Agneta“ a „John“ prostřednictvím „Diego )“, „Jose “ a „Bob“ se bude rovnat . $\alpha =0,5$ $(0,5)^{1}=0,5$ $(0,5)^{2}=0,25$ $(0,5)^{3}=0,125$ $(0,5)^{4}=0,0625$

Matematická formulace

Nechť A je matice sousedství uvažované sítě. Prvky matice A jsou proměnné, které mají hodnotu 1, pokud je uzel i spojen s uzlem j , a hodnotu 0 v opačném případě. Stupně matice A ukazují přítomnost (nebo nepřítomnost) vazeb mezi dvěma uzly prostřednictvím prostředníků. Například v matici , pokud je prvek , pak to znamená, že uzly 2 a 12 jsou spojeny nějakou cestou délky 3. Jestliže označuje Kac centralitu uzlu i , pak matematicky $(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}~.

Všimněte si, že výše uvedená definice používá skutečnost, že prvek na pozici matice odráží celkový počet stupňů spojení mezi uzly a . Hodnota faktoru tlumení by měla být zvolena tak, aby byla menší než převrácená hodnota absolutní hodnoty největšího vlastního čísla matice A [5] . V tomto případě lze pro výpočet centrality Kac použít následující výraz: $(i,j)$ $A^{k}$ $k$ $i$ $j$ $\alpha$

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

kde:

$E$ je matice identity;

${\overrightarrow {I}}$ je vektor velikosti n ( n se rovná počtu uzlů) skládající se z jedniček;

$A^{T}$ je transponovaná matice matice A;

$(E-\alpha A^{T})^{-1}$ je invertibilní matice matice [5] . $(E-\alpha A^{T})$

Rozšíření tohoto konceptu umožňuje výpočet tras za dynamických podmínek [6] [7] . Směr času je zachován, takže příspěvek je asymetrický ve směru šíření informace.

Sítě poskytují data ve tvaru:

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

pro

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

představující matici sousedství v každém okamžiku . Tudíž, $t_k$

$\left(A^{[k]}\right)_{ij}=1$ pokud existuje hrana od uzlu k uzlu v čase a 0 jinak. $i$ $j$ $t_k$

Časy jsou seřazené, ale ne nutně rovnoměrně rozložené. pro každou je vážený počet počtu dynamických tras délky od uzlu k uzlu . Typ dynamické komunikace mezi uzly: ${\displaystyle t_{0}<t_{1}<\cdots <t_{M))$ $Q\in \mathbb {R} ^{N\times N}$ ${\displaystyle (Q)_{ij))$ $w$ $i$ $j$

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

V normalizované podobě:

{\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]}\right)^{-1}\right\|}}~.

Centralita tedy ukazuje, jak efektivně může uzel „posílat“ a „přijímat“ dynamické zprávy přes síť: $n$

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

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

Aplikace

Katzova centralita může být použita k výpočtu centrality v řízených sítích, jako jsou sítě nabídek a World Wide Web [8] . Nejužitečnější je při analýze orientovaných acyklických grafů, ve kterých tradičně používané míry, jako je míra vlivu , ztrácí smysl [8] .

Katzova centralita může být také použita při hodnocení relativního stavu nebo vlivu objektů v sociální síti. Článek Laughlina et al [9] demonstruje analýzu aplikace dynamické verze Katz centrality na data Twitteru, přičemž identifikuje objekty, které mají status stabilních vedoucích diskusí. Aplikace Katzova konceptu centrality umožňuje porovnávat metodiky, které zahrnují lidské experty, a hodnotit shodu jejich výsledků s panelem odborníků na sociální sítě.

V neurovědách bylo zjištěno, že centralita Kac koreluje s relativní rychlostí vypalování neuronů v neuronové síti [10] . Katzova časová expanze centrality byla aplikována na data fMRI získaná z experimentů s učením hudby [11] , ve kterých jsou data sbírána před a po procesu učení. Výsledky ukázaly, že změny ve struktuře sítě vytvářely v každé relaci kvantitativní spojení, která tvoří shluky na tzv. linii úspěšného učení.

Poznámky

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

Literatura

Katz L. Nový stavový index odvozený ze sociometrického indexu // Psychometrics. — 1953.
Hanneman RA, Riddle M. Úvod do metod sociálních sítí. — Riverside, CA: University of California, Riverside, 2005.
Analýza dat sociálních sítí Aggarwal CC . — New York, NY: Springer, 2011.
Junker BH, Schreiber F. Analýza biologických sítí. - Hoboken, NJ: John Wiley & Sons, 2008. - ISBN 978-0-470-04144-4 .
Newman MEJ Networks: Úvod. — Oxford, UK: Oxford University Press, 2010.
Vigna S. Spectral ranking // Network Science. - 2016. - svazek 4 , č. 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. Dynamická síťová centralita shrnuje učení v lidském mozku // Journal of Complex Networks. - 2013. - Vol. 1 , vydání. 1 .
Peter Grindrod, Desmond J. Higham. Vyvíjející se grafy: Dynamické modely, inverzní problémy a šíření // Proc. Royi. soc. A. - 2010. - T. 466 .
Peter Grindrod, Mark C. Parsons, Desmond J. Higham, Ernesto Estrada. Komunikovatelnost napříč vyvíjejícími se sítěmi // Physical Review E. - APS, 2011. - T. 83 .
Peter Laflin, Alexander V. Mantzaris, Fiona Ainley, Amanda Otley, Peter Grindrod, Desmond J. Higham. Objevování a ověřování vlivu v dynamické online sociální síti // Analýza a těžba sociálních sítí. - Springer, 2013. - V. 3 , č. 4 .
Jack McKay Fletcher, Thomas Wennekers. Od struktury k aktivitě: Použití centralitních opatření k predikci neuronové aktivity // International Journal of Neural Systems. - 2017. - T. 0 , č. 0 . - doi : 10.1142/S0129065717500137 .