Katzova ústřednost - Katz centrality

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie Přechodnost Preferenční příloha Teorie rovnováhy Síťový efekt Sociální vliv
Typy sítí
Informační (výpočetní) Telekomunikace Doprava Sociální Vědecká spolupráce Biologický Umělý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů Assortativity Vzdálenost Modularita Účinnost
Modely
Topologie Náhodný graf Erdős – Rényi Barabási – Albert Fitness model Watts – Strogatz Exponenciální náhodné (ERGM) Náhodné geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

v teorie grafů, Katzova ústřednost uzlu je míra ústřednost v síť. To bylo představeno Leo Katz v roce 1953 a slouží k měření relativní míry vlivu aktéra (nebo uzlu) v rámci a sociální síť.^[1] Na rozdíl od typických opatření ústřednosti, která zohledňují pouze nejkratší cestu ( geodetické ) mezi dvojicí aktérů, Katzova centralita měří vliv zohledněním celkového počtu procházky mezi dvojicí herců.^[2]

Je to podobné jako Google je PageRank a do centrality vlastního vektoru.^[3]

Měření

Jednoduchá sociální síť: uzly představují lidi nebo aktéry a hrany mezi uzly představují určitý vztah mezi aktéry

Katzova centralita počítá relativní vliv uzlu v síti měřením počtu bezprostředních sousedů (uzly prvního stupně) a také všech ostatních uzlů v síti, které se připojují k uvažovanému uzlu prostřednictvím těchto bezprostředních sousedů. Spojení se vzdálenými sousedy jsou však penalizována útlumovým faktorem ${ displaystyle alpha}$.^[4] Každá cesta nebo spojení mezi dvojicí uzlů je přiřazena váha určená ${ displaystyle alpha}$ a vzdálenost mezi uzly jako ${ displaystyle alpha ^ {d}}$.

Například na obrázku vpravo předpokládejme, že se měří Johnova ústřednost a to ${ displaystyle alpha = 0,5}$. Hmotnost přiřazená každému článku, který spojuje Johna s jeho bezprostředními sousedy Jane a Bobem, bude ${ displaystyle (0,5) ^ {1} = 0,5}$. Jelikož se Jose připojuje k Johnovi nepřímo prostřednictvím Boba, váha přiřazená tomuto spojení (složenému ze dvou odkazů) bude ${ displaystyle (0,5) ^ {2} = 0,25}$. Podobně bude váha přiřazená spojení mezi Agneta a Johnem přes Aziz a Jane ${ displaystyle (0,5) ^ {3} = 0,125}$ a váha přiřazená spojení mezi Agnetou a Johnem přes Diega, Joseho a Boba bude ${ displaystyle (0,5) ^ {4} = 0,0625}$.

Matematická formulace

Nechat A být matice sousedství uvažované sítě. Elementy ${ displaystyle (a_ {ij})}$ z A jsou proměnné, které mají hodnotu 1, pokud je uzel i je připojen k uzlu j a 0 jinak. Pravomoci A označují přítomnost (nebo nepřítomnost) spojení mezi dvěma uzly prostřednictvím zprostředkovatelů. Například v matici ${ displaystyle A ^ {3}}$, pokud prvek ${ displaystyle (a_ {2,12}) = 1}$, znamená to, že uzel 2 a uzel 12 jsou spojeny nějakým krokem délky 3. Pokud ${ displaystyle C _ { mathrm {Katz}} (i)}$ označuje Katzovu centralitu uzlui, pak matematicky:

${ displaystyle C _ { mathrm {Katz}} (i) = součet _ {k = 1} ^ { infty} součet _ {j = 1} ^ {n} alpha ^ {k} (A ^ { k}) _ {ji}}$

Všimněte si, že výše uvedená definice využívá skutečnost, že prvek v umístění ${ displaystyle (i, j)}$ z ${ displaystyle A ^ {k}}$ odráží celkový počet ${ displaystyle k}$ stupně spojení mezi uzly ${ displaystyle i}$ a ${ displaystyle j}$. Hodnota faktoru útlumu ${ displaystyle alpha}$ musí být zvolen tak, aby byl menší než převrácená hodnota absolutní hodnoty největšího vlastní číslo z A.^[5] V tomto případě lze k výpočtu Katzovy ústřednosti použít následující výraz:

${ displaystyle { overrightarrow {C}} _ ​​{ mathrm {Katz}} = ((I- alpha A ^ {T}) ^ {- 1} -I) { overrightarrow {I}}}$

Tady ${ displaystyle I}$ je matice identity, ${ displaystyle { overrightarrow {I}}}$ je vektor velikosti n (n je počet uzlů) skládající se z těch. ${ displaystyle A ^ {T}}$ označuje transponovaná matice A a ${ displaystyle (I- alpha A ^ {T}) ^ {- 1}}$ označuje inverze matice termínu ${ displaystyle (I- alpha A ^ {T})}$.^[5]

Rozšíření tohoto rámce umožňuje počítat procházky v dynamickém prostředí.^[6][7] Pořízením časově závislé řady snímků sousednosti sítě přechodových hran je prezentována závislost procházek, které přispívají k kumulativnímu účinku. Šipka času je zachována, takže příspěvek aktivity je asymetrický ve směru šíření informací.

Síť produkující data formuláře:

${ displaystyle left {A ^ {[k]} in mathbb {R} ^ {N krát N} right } qquad { text {pro}} quad k = 0,1,2 , ldots, M,}$

vždy představující matici sousedství ${ displaystyle t_ {k}}$. Proto,

${ displaystyle left (A ^ {[k]} right) _ {ij} = { begin {cases} 1 & { text {existuje hrana od uzlu}} i { text {k uzlu}} j { text {v čase}} t_ {k} 0 & { text {jinak}} end {případů}}}$

Časové body ${ displaystyle t_ {0}$ jsou uspořádány, ale nemusí být rovnoměrně rozmístěny ${ displaystyle Q in mathbb {R} ^ {N krát N}}$ pro který ${ displaystyle (Q) _ {ij}}$ je vážený počet počtu dynamických procházek délky ${ displaystyle w}$ z uzlu ${ displaystyle i}$ do uzlu ${ displaystyle j}$. Formulář pro dynamickou komunikaci mezi zúčastněnými uzly je:

${ displaystyle { mathcal {Q}} = vlevo (I- alpha A ^ {[0]} vpravo) ^ {- 1} cdots vlevo (I- alpha A ^ {[M]} vpravo) ^ {- 1}.}$

To lze normalizovat pomocí:

${ displaystyle { hat { mathcal {Q}}} ^ {[k]} = { frac {{ hat { mathcal {Q}}} ^ {[k-1]} left (I- alpha A ^ {[k]} right) ^ {- 1}} { left | { hat { mathcal {Q}}} ^ {[k-1]} left (I- alpha A ^ {[k]} right) ^ {- 1} right |}}.}$

Proto opatření ústřednosti, která kvantifikují, jak efektivně uzel ${ displaystyle n}$ může „vysílat“ a „přijímat“ dynamické zprávy po síti,

${ displaystyle C_ {n} ^ { mathrm {broadcast}}: = sum _ {k = 1} ^ {N} { mathcal {Q}} _ {nk} quad mathrm {a} quad C_ {n} ^ { mathrm {receive}}: = sum _ {k = 1} ^ {N} { mathcal {Q}} _ {kn}}$.

Aplikace

Katzovu ústřednost lze použít k výpočtu ústřednosti v cílených sítích, jako jsou citační sítě a síť WWW.^[8]

Katzova centralita je vhodnější při analýze směrovaných acyklických grafů, kde se tradičně používají míry jako centrality vlastního vektoru jsou k ničemu.^[8]

Katzovu centralitu lze také použít k odhadu relativního stavu nebo vlivu aktérů v sociální síti. Práce prezentovaná v ^[9] ukazuje případovou studii aplikace dynamické verze ústřednosti Katz na data z Twitteru a zaměřuje se na konkrétní značky, které mají stabilní vedoucí diskuse. Aplikace umožňuje srovnání metodiky s metodikou lidských odborníků v oboru a toho, jak jsou výsledky po dohodě s panelem odborníků na sociální média.

v neurovědy, bylo zjištěno, že Katzova ústřednost koreluje s relativní rychlostí střelby neurony v neuronové síti.^[10] Časové rozšíření Katzovy ústřednosti se použije na data fMRI získaná z experimentu s hudebním učením v ^[11] kde se shromažďují údaje od subjektů před a po procesu učení. Výsledky ukazují, že změny struktury sítě v průběhu hudební expozice vytvářely v každé relaci kvantifikaci křížové komunikace, která vytvořila shluky v souladu s úspěchem učení.

Zobecněnou formu ústřednosti Katz lze použít jako intuitivní systém hodnocení sportovních týmů, například v školní fotbal.^[12]

Reference