Centrality vlastního vektoru - Eigenvector centrality

v teorie grafů, centrality vlastního vektoru (také zvaný vlastní výstřednost nebo prestižní skóre^[1]) je měřítkem vlivu a uzel v síť. Relativní skóre je přiřazeno všem uzlům v síti na základě konceptu, že připojení k uzlům s vysokým skóre přispívá více ke skóre daného uzlu než stejná připojení k uzlům s nízkým skóre. Vysoké vlastní číslo vektoru znamená, že uzel je spojen s mnoha uzly, kteří sami mají vysoké skóre.^{[2] [3]}

Google je PageRank a Katzova ústřednost jsou varianty ústřednosti vlastních vektorů.^[4]

Použití matice sousedství k nalezení ústřednosti vlastních vektorů

Pro daný graf ${displaystyle G: = (V, E)}$ s ${displaystyle | V |}$ vrcholy nechat ${displaystyle A = (a_ {v, t})}$ být matice sousedství, tj. ${displaystyle a_ {v, t} = 1}$ pokud vrchol ${displaystyle v}$ je spojen s vrcholem ${displaystyle t}$, a ${displaystyle a_ {v, t} = 0}$ v opačném případě. Relativní ústřednost, ${displaystyle x}$, skóre vrcholu ${displaystyle v}$ lze definovat jako:

${displaystyle x_ {v} = {frac {1} {lambda}} součet _ {tin M (v)} x_ {t} = {frac {1} {lambda}} součet _ {tin G} a_ {v, t } x_ {t}}$

kde ${displaystyle M (v)}$ je sada sousedů ${displaystyle v}$ a ${displaystyle lambda}$ je konstanta. S malým přeskupením to může být přepsáno do vektorového zápisu jako vlastní vektor rovnice

${displaystyle mathbf {Axe} = lambda mathbf {x}}$

Obecně bude existovat mnoho různých vlastní čísla ${displaystyle lambda}$ pro které existuje nenulové řešení vlastního vektoru. Dodatečný požadavek, aby všechny položky ve vlastním vektoru byly nezáporné, však znamená (podle Perron – Frobeniova věta ), že pouze největší vlastní číslo má za následek požadovanou míru ústřednosti.^[5] The ${displaystyle v ^ {ext {th}}}$ složka souvisejícího vlastního vektoru pak udává relativní skóre centrálnosti vrcholu ${displaystyle v}$ v síti. Vlastní vektor je definován pouze do společného faktoru, takže jsou dobře definovány pouze poměry středů vrcholů. Chcete-li definovat absolutní skóre, musíte normalizovat vlastní vektor, např. takže součet všech vrcholů je 1 nebo celkový počet vrcholůn. Iterace výkonu je jedním z mnoha algoritmy vlastních čísel které lze použít k nalezení tohoto dominantního vlastního vektoru.^[4] Dále to lze zobecnit, aby záznamy v A mohou být reálná čísla představující sílu spojení, jako v a stochastická matice.

Normalizované bodové hodnocení vlastní centrality

Google je PageRank je založen na normalizované vlastní centralitě vlastního vektoru nebo na normalizované prestiži v kombinaci s předpokladem náhodného skoku.^[1] PageRank uzlu ${displaystyle v}$ má rekurzivní závislost na PageRank jiných uzlů, které na ni odkazují. Normalizovaná matice sousedství ${displaystyle N}$ je definován jako:

$${displaystyle N (u, v) = {egin {cases} {1 over operatorname {od} (u)}, & {ext {if}} (u, v) in E 0, & {ext {if}} (u, v) ot in Eend {cases}}}$$

${displaystyle od (u)}$

${displaystyle u}$

Normalizované skóre centrality vlastních vektorů je definováno jako:

$${displaystyle p (v) = součet _ {u} {N ^ {T} (v, u) cdot p (u)}}$$

Aplikace

Centrálnost vlastních vektorů je měřítkem vlivu uzlu na síť. Pokud na uzel ukazuje mnoho uzlů (které mají také vysokou centrálnost vlastních vektorů), pak tento uzel bude mít vysokou vlastní ústřednost.^[6]

Nejdříve se využívá centrality vlastních vektorů do Edmund Landau v článku z roku 1895 o bodování šachových turnajů.^[7][8]

V poslední době vědci z mnoha oborů analyzovali aplikace, projevy a rozšíření centrality vlastních vektorů v různých doménách:

• Centrality vlastního vektoru je jedinečným měřítkem uspokojujícím určité přirozené axiomy pro systém hodnocení.^[9][10]
• v neurovědy, centrality vlastního vektoru a neuron v modelové neurální síti bylo zjištěno, že koreluje s její relativní rychlostí střelby.^[6]
• Ve standardní třídě modelů aktualizace názorů nebo učení (někdy nazývaných DeGroot učení modely), sociální vliv uzlu na případné názory je stejný s jeho vlastní vektorovou centrálností.
• Definice ústřednosti vlastních vektorů byla rozšířena na multiplexní nebo vícevrstvé sítě.^[11]
• Ve studii využívající údaje z Filipín autoři ukázali, jak rodiny politických kandidátů měly v místních sňatkových sítích neúměrně vysokou ústřední postavu vlastního vektoru.^[12]
• V ekonomickém veřejné zboží problémy, lze vlastní ústřední vektorovou osobnost interpretovat tak, jak moc její preference ovlivňují efektivní sociální výsledek (formálně Paretova váha v Pareto efektivní sociální výsledek).^[13]

Viz také

• Centrálnost

Reference