Nodpåverkanspoäng

En nodpåverkanspoäng är ett mått som rangordnar eller kvantifierar påverkan av varje nod (även kallad vertex) [1] i en graf. Exponenterna är relaterade till centralitetsindex . Tillämpningar av indikatorn inkluderar mått på varje persons inflytande i ett socialt nätverk , förståelse av nodernas roll i transportnätverk , Internet eller stadsnätverk , och rollen av en given nod i sjukdomsdynamiken.

Ursprung och utveckling

Den traditionella metoden för att förstå vikten av en nod genom är att beräkna centralitetspoäng . Centralitetsindex utformades för att producera rankningar som exakt identifierar de mest inflytelserika noderna. Sedan mitten av 2000-talet har dock sociologer och nätverksforskare börjat ifrågasätta relevansen av att använda centralitetsindex för att förstå nodstyrka, eftersom centralitetsindex kan visa de mest inflytelserika noderna, men är mindre informativa för lejonparten av noder som inte gör det. ha det högsta inflytandet.

En granskning 2006 av Bogatti och Everett [2] visade att noggrannheten hos centralitetsindexen starkt beror på nätverkets topologi. Denna slutsats har sedan dess bekräftats upprepade gånger (t.ex. [3] [4] ). 2012 påminde Bauer och kollegor oss om att centralitetsindex endast rangordnar noder, men inte ger en numerisk uppskattning av skillnaden mellan dem [5] . Under 2013 tillhandahöll Sikik et al starka bevis för att centralitetsindex kraftigt underskattar styrkan hos icke-hubnoder [6] . Anledningen är ganska tydlig - noggrannheten hos centralitetsmåttet beror på uppsättningens topologi, och komplexa nätverk har en olikformig topologi. Som en konsekvens kommer centralitetsmått som är lämpliga för att identifiera mycket inflytelserika noder med största sannolikhet vara olämpliga för resten av nätverket [4] .

Detta var anledningen till utvecklingen av nya metoder för att mäta alla nätverksnoder. De vanligaste måtten är tillgänglighet , som använder slumpmässiga vandringar av olika slag för att mäta nåbarheten för resten av nätverket från den initiala noden [7] , och den förväntade styrkan , erhållen från det förväntade värdet av infektionsstyrkan för nod [4] .

Båda dessa mått kan på ett meningsfullt sätt beräknas endast baserat på nätverkets struktur.

Tillgänglighet

Tillgänglighet kommer från random walk theory. Exponenten mäter spridningen av icke-fram- och återgående promenader med början från den givna noden. En promenad på ett nätverk är en sekvens av angränsande hörn. En oåterkallelig promenad besöker varje vertex endast en gång. Det ursprungliga arbetet använde en promenadsimulering av längd 60 för att beskriva det urbana gatunätet i en brasiliansk stad [7] . Tillgänglighet formaliserades senare som en form av hierarkisk grad som styr både sannolikheten för passage och variationen av promenader av en given fast längd [8] .

Definition

Den hierarkiska graden mäter antalet noder som kan nås från startnoden med en längdvandring . För en fast och typ av promenad nås var och en av dessa grannar med (eventuellt olika) sannolikheter . Givet en vektor med sådana sannolikheter bestäms tillgängligheten av en nod för ett värde av formeln

Sannolikheter kan användas för enhetliga sannolikhet slumpmässiga promenader och dessutom justeras för kantvikter och/eller explicit (för kanter) sannolikhet för att passera [8] .

Applikationer

Tillgänglighet, som visas i exemplet med att identifiera strukturen hos stadsnätverk [7] , motsvarar antalet noder som kan besökas under en viss tidsperiod [8] och är en förutsägelse av resultatet av den epidemiologiska SIR-modellen av spridningsprocessen till nätverk med stor diameter och låg densitet [3] .

Förväntad styrka

Förväntad styrka mäter effekten av en nod i termer av epidemiologi. Det är lika med den matematiska förväntan på infektionsstyrkan som bildas av noden efter två överföringar.

Definition

Den förväntade knutstyrkan ges av formeln

,

där summan tas över mängden av alla möjliga överföringskluster som är resultatet av två överföringar med början från , och är den normaliserade graden av klustret .

Definitionen sträcker sig naturligtvis till riktade nätverk genom att begränsa ordningen efter kanternas riktning. På liknande sätt är utvidgning till viktade nätverk, eller nätverk med heterogen sannolikhetsöverföring, en fråga om att justera normaliseringen för att inkludera sannolikheten för att klustret bildas. Det är också möjligt att använda fler än två bindestreck för att definiera en uppsättning [4] .

Applikationer

Förväntad styrka har visat sig vara starkt korrelerad med resultaten av SI-, SIS- och SIR-epidemimodeller över ett brett spektrum av nätverkstopologier, både simulerade och empiriska [4] [9] . Det har också använts för att mäta pandemipotentialen hos världens flygplatser, [10] och har nämnts i samband med digitala betalningar [11] , ekologi [12] , fitness [13] och projektledning [14] .

Andra tillvägagångssätt

Andra föreslagna mått kodar explicit dynamiken i en viss process som utspelar sig på nätverket. Den dynamiska påverkan är andelen obegränsade promenader som börjar vid varje nod där gångstegen är skalade så att systemets linjära dynamik förväntas konvergera till ett stabilt tillstånd som inte är noll [15] . Som ett resultat, med en ökning av längden på promenader, finns det en möjlighet att överföra till den sista noden av promenaden, som inte skulle ha besökts under kortare promenader [5] . Även om båda måtten är bra på att förutsäga utdata från de dynamiska system de kodar, är författarna i varje fall överens om att dynamikens resultat inte överförs till annan dynamik.

Anteckningar

  1. ↑ Artikeln syftar främst på teorin om nätverk och det är vanligt att använda ordet nod istället för ordet vertex i det .
  2. ↑ Borgatti, Everett, 2006 , sid. 466–484.
  3. ↑ 1 2 da Silva, Viana, da F. Costa, 2012 , sid. P07005.
  4. ↑ 1 2 3 4 5 Advokat, 2015 , sid. 8665.
  5. ↑ 1 2 Bauer och Lizier, 2012 , sid. 68007.
  6. ↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , sid. 1–13.
  7. ↑ 1 2 3 Travencolo, da F. Costa, 2008 , sid. 89–95.
  8. ↑ 1 2 3 Viana, Batista, da F. Costa, 2012 , sid. 036105.
  9. ↑ Advokat, 2014 .
  10. ↑ Advokat, 2016 , sid. 70.
  11. ↑ Milkau, Bott, 2015 .
  12. ↑ Jordan, Maguire, Hofmann, Kohda, 2016 , sid. 20152359.
  13. ↑ Pereira, Gama, Sousa et al., 2015 , sid. 10489.
  14. ↑ Ellinas, Allan, Durugbo, Johansson, 2015 , sid. e0142469.
  15. ↑ Klemm, Serrano, Eguiluz, Miguel, 2012 , sid. 292.

Litteratur