Skóre vlivu uzlu

Skóre vlivu uzlu je míra, která řadí nebo kvantifikuje vliv každého uzlu (nazývaného také vrchol) [1] v grafu. Exponenty se vztahují k indexům centrality . Aplikace indikátoru zahrnují měření vlivu každého člověka v sociální síti , pochopení role uzlů v dopravních sítích , internetu nebo městských sítích a roli daného uzlu v dynamice onemocnění.

Vznik a vývoj

Tradiční přístup k pochopení důležitosti uzlu skrz je vypočítat skóre centrality . Indexy centrality byly navrženy tak, aby vytvořily hodnocení, která přesně identifikují nejvlivnější uzly. Od poloviny roku 2000 však sociologové a síťoví vědci začali zpochybňovat relevanci použití indexů centrality k pochopení síly uzlů, protože indexy centrality mohou zobrazovat nejvlivnější uzly, ale jsou méně informativní pro lví podíl uzlů, které ne. mají nejvyšší vliv.

Přehledový dokument z roku 2006 od Bogattiho a Everetta [2] ukázal, že přesnost indexů centrality silně závisí na topologii sítě. Tento závěr byl od té doby opakovaně potvrzen (např. [3] [4] ). V roce 2012 nám Bauer a kolegové připomněli, že indexy centrality řadí pouze uzly, ale neposkytují číselný odhad rozdílu mezi nimi [5] . V roce 2013 Sikik et al poskytli silné důkazy o tom, že indexy centrality značně podhodnocují sílu neuzlových uzlů [6] . Důvod je zcela jasný – přesnost měření centrality závisí na topologii množiny a složité sítě mají nejednotnou topologii. V důsledku toho budou opatření centrality, která jsou vhodná pro identifikaci vysoce vlivných uzlů, s největší pravděpodobností nevhodná pro zbytek sítě [4] .

To byl důvod pro vývoj nových metod měření všech uzlů sítě. Nejběžnějšími měřítky jsou dostupnost , která využívá náhodné procházky různého druhu k měření dosažitelnosti zbytku sítě z počátečního uzlu [7] , a očekávaná síla získaná z očekávané hodnoty síly infekce pro uzel [4] .

Obě tato opatření lze smysluplně vypočítat pouze na základě struktury sítě.

Dostupnost

Přístupnost vychází z teorie náhodné procházky. Exponent měří šíření nevratných procházek počínaje daným uzlem. Procházka po síti je posloupnost sousedních vrcholů. Nevratná procházka navštíví každý vrchol pouze jednou. Původní práce používala simulaci chůze o délce 60 k popisu městské uliční sítě brazilského města [7] . Přístupnost byla později formalizována jako forma hierarchického stupně, který řídí jak pravděpodobnost průchodu, tak rozmanitost procházek dané pevné délky [8] .

Definice

Hierarchický stupeň měří počet uzlů dosažitelných z počátečního uzlu o procházku délky . Pro pevný a typ chůze je každý z těchto sousedů dosažen s (možná odlišnou) pravděpodobností . Vzhledem k vektoru takových pravděpodobností je dostupnost uzlu pro hodnotu určena vzorcem

Pravděpodobnosti lze použít pro náhodné procházky s jednotnou pravděpodobností a dodatečně je upravit pro váhy hran a/nebo explicitní (pro hrany) pravděpodobnost průchodu [8] .

Aplikace

Dostupnost, jak ukazuje příklad identifikace struktury městských sítí [7] , odpovídá počtu uzlů, které lze navštívit v určitém časovém období [8] a je predikcí výsledku epidemiologického modelu SIR procesu šíření do sítí s velkým průměrem a nízkou hustotou [3] .

Očekávaná síla

Očekávaná síla měří dopad uzlu z hlediska epidemiologie. Rovná se matematickému očekávání síly infekce vytvořené uzlem po dvou přenosech.

Definice

Předpokládaná pevnost uzlu je dána vzorcem

,

kde součet přebírá množinu všech možných přenosových shluků vyplývajících ze dvou přenosů počínaje , a je normalizovaným stupněm shluku .

Definice se přirozeně rozšiřuje na směrované sítě zúžením uspořádání podle směru hran. Podobně rozšíření na vážené sítě nebo sítě s heterogenním přenosem pravděpodobnosti je záležitostí úpravy normalizace tak, aby zahrnovala pravděpodobnost, že se shluk vytvoří. Pro definici množiny je také možné použít více než dvě pomlčky [4] .

Aplikace

Ukázalo se, že očekávaná síla vysoce koreluje s výsledky modelů epidemie SI, SIS a SIR v širokém rozsahu topologií sítí, simulovaných i empirických [4] [9] . Byl také použit k měření pandemického potenciálu světových letišť [10] a byl zmíněn v souvislosti s digitálními platbami [11] , ekologií [12] , fitness [13] a projektovým řízením [14] .

Jiné přístupy

Jiné navrhované metriky explicitně kódují dynamiku konkrétního procesu, který se v síti odvíjí. Dynamický dopad je podíl neohraničených procházek začínajících v každém uzlu, kde jsou kroky chůze škálovány tak, že se očekává, že lineární dynamika systému bude konvergovat k nenulovému ustálenému stavu [15] . Díky tomu s narůstající délkou vycházek vzniká možnost přesunu do konečného uzlu vycházky, který by při kratších vycházkách nebyl navštěvován [5] . Přestože obě měření jsou dobrá v predikci výstupu dynamických systémů, které kódují, v každém případě se autoři shodují, že výsledky dynamiky se nepřenášejí do jiné dynamiky.

Poznámky

  1. ↑ Článek se týká především teorie sítí a je v něm zvykem místo slova vertex používat slovo uzel .
  2. ↑ Borgatti, Everett, 2006 , str. 466–484.
  3. ↑ 1 2 da Silva, Viana, da F. Costa, 2012 , str. P07005.
  4. ↑ 1 2 3 4 5 Právník, 2015 , str. 8665.
  5. ↑ 1 2 Bauer a Lizier, 2012 , s. 68007.
  6. ↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , str. 1–13.
  7. ↑ 1 2 3 Travencolo, da F. Costa, 2008 , str. 89–95.
  8. ↑ 1 2 3 Viana, Batista, da F. Costa, 2012 , str. 036105.
  9. ↑ Právník, 2014 .
  10. ↑ Právník, 2016 , str. 70.
  11. ↑ Milkau, Bott, 2015 .
  12. ↑ Jordan, Maguire, Hofmann, Kohda, 2016 , str. 20152359.
  13. ↑ Pereira, Gama, Sousa et al., 2015 , str. 10489.
  14. ↑ Ellinas, Allan, Durugbo, Johansson, 2015 , str. e0142469.
  15. ↑ Klemm, Serrano, Eguiluz, Miguel, 2012 , str. 292.

Literatura