Nodepåvirkningsscore

En nodepåvirkningsscore er et mål, der rangerer eller kvantificerer indflydelsen af ​​hver node (også kaldet et vertex) [1] i en graf. Eksponenterne er relateret til centralitetsindekser . Anvendelser af indikatoren omfatter målinger af indflydelsen fra hver person i et socialt netværk , forståelse af nodernes rolle i transportnetværk , internettet eller bynetværk og rollen af ​​en given knude i sygdomsdynamikken.

Oprindelse og udvikling

Den traditionelle tilgang til at forstå vigtigheden af ​​en node through er at beregne centralitetsscore . Centralitetsindekser blev designet til at producere rangeringer, der nøjagtigt identificerer de mest indflydelsesrige noder. Siden midten af ​​2000'erne er sociologer og netværksforskere imidlertid begyndt at stille spørgsmålstegn ved relevansen af ​​at bruge centralitetsindekser til at forstå nodestyrke, da centralitetsindekser kan vise de mest indflydelsesrige noder, men er mindre informative for broderparten af ​​noder, der ikke gør det. have størst indflydelse.

Et reviewpapir fra 2006 af Bogatti og Everett [2] viste, at nøjagtigheden af ​​centralitetsindekserne afhænger stærkt af netværkets topologi. Denne konklusion er siden blevet bekræftet gentagne gange (f.eks. [3] [4] ). I 2012 mindede Bauer og kolleger os om, at centralitetsindekser kun rangerer noder, men giver ikke et numerisk skøn over forskellen mellem dem [5] . I 2013 leverede Sikik et al stærke beviser for, at centralitetsindekser i høj grad undervurderer styrken af ​​non-hub noder [6] . Årsagen er ret klar - nøjagtigheden af ​​centralitetsmålet afhænger af sættets topologi, og komplekse netværk har en ikke-ensartet topologi. Som en konsekvens heraf vil mål for centralitet, der er egnede til at identificere meget indflydelsesrige noder, højst sandsynligt være uegnede for resten af ​​netværket [4] .

Dette var årsagen til udviklingen af ​​nye metoder til måling af alle netværksknuder. De mest almindelige mål er tilgængelighed , som bruger tilfældige ture af forskellig art til at måle tilgængeligheden af ​​resten af ​​netværket fra den indledende node [7] , og den forventede styrke , opnået fra den forventede værdi af infektionsstyrke for node [4] .

Begge disse mål kan beregnes meningsfuldt kun baseret på netværkets struktur.

Tilgængelighed

Tilgængelighed kommer fra tilfældig gangteori. Eksponenten måler spredningen af ​​ikke-frem- og tilbagegående gåture startende fra den givne knude. En tur på et netværk er en sekvens af tilstødende hjørner. En irreversibel gåtur besøger kun hvert toppunkt én gang. Det originale værk brugte en gangsimulering af længde 60 til at beskrive bygadenetværket i en brasiliansk by [7] . Tilgængelighed blev senere formaliseret som en form for hierarkisk grad, der kontrollerer både sandsynligheden for passage og variationen af ​​ture af en given fast længde [8] .

Definition

Den hierarkiske grad måler antallet af noder, der kan nås fra startknudepunktet med en gåtur . For en fast og type gåtur nås hver af disse naboer med (muligvis forskellige) sandsynligheder . Givet en vektor med sådanne sandsynligheder bestemmes tilgængeligheden af ​​en node for en værdi af formlen

Sandsynligheder kan bruges til ensartede sandsynlighedstilfældige ture og yderligere justeres for kantvægte og/eller eksplicit (for kanter) beståelsessandsynlighed [8] .

Ansøgninger

Tilgængelighed, som vist i eksemplet med at identificere strukturen af ​​bynetværk [7] , svarer til antallet af knudepunkter, der kan besøges i en vis periode [8] og er en forudsigelse af resultatet af den epidemiologiske SIR-model af processen med spredning til netværk med stor diameter og lav tæthed [3] .

Forventet styrke

Forventet styrke måler virkningen af ​​en knude i form af epidemiologi. Det er lig med den matematiske forventning om infektionsstyrken dannet af noden efter to transmissioner.

Definition

Den forventede knudestyrke er givet af formlen

,

hvor summen overtages sættet af alle mulige transmissionsklynger som følge af to transmissioner startende fra , og er den normaliserede grad af klyngen .

Definitionen strækker sig naturligvis til rettede netværk ved at indsnævre rækkefølgen efter retningen af ​​kanterne. Tilsvarende er udvidelse til vægtede netværk eller netværk med heterogen sandsynlighedsoverførsel et spørgsmål om at justere normaliseringen af ​​til at inkludere sandsynligheden for, at klyngen dannes. Det er også muligt at bruge mere end to bindestreger til at definere et sæt [4] .

Ansøgninger

Forventet styrke har vist sig at være stærkt korreleret med resultaterne af SI-, SIS- og SIR-epidemimodeller over en bred vifte af netværkstopologier, både simulerede og empiriske [4] [9] . Det er også blevet brugt til at måle pandemipotentialet i verdens lufthavne, [10] og er blevet nævnt i forbindelse med digitale betalinger [11] , økologi [12] , fitness [13] og projektledelse [14] .

Andre tilgange

Andre foreslåede målinger koder eksplicit for dynamikken i en bestemt proces, der udspiller sig på netværket. Den dynamiske påvirkning er andelen af ​​ubegrænsede vandreture, der starter ved hver knude, hvor gangtrinene skaleres således, at systemets lineære dynamik forventes at konvergere til en stabil tilstand, der ikke er nul [15] . Som følge heraf er der med en stigning i længden af ​​gåture mulighed for overførsel til gåturens sidste knudepunkt, som ikke ville have været besøgt under kortere gåture [5] . Selvom begge mål er gode til at forudsige outputtet af de dynamiske systemer, de koder, er forfatterne i hvert tilfælde enige om, at dynamikkens resultater ikke overføres til andre dynamikker.

Noter

  1. ↑ Artiklen refererer hovedsageligt til teorien om netværk , og det er sædvanligt at bruge ordet node i stedet for ordet vertex i det .
  2. ↑ Borgatti, Everett, 2006 , s. 466-484.
  3. ↑ 1 2 da Silva, Viana, da F. Costa, 2012 , s. P07005.
  4. ↑ 1 2 3 4 5 Advokat, 2015 , s. 8665.
  5. ↑ 1 2 Bauer og Lizier, 2012 , s. 68007.
  6. ↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , s. 1-13.
  7. ↑ 1 2 3 Travencolo, da F. Costa, 2008 , s. 89-95.
  8. ↑ 1 2 3 Viana, Batista, da F. Costa, 2012 , s. 036105.
  9. ↑ Advokat, 2014 .
  10. ↑ Advokat, 2016 , s. 70.
  11. ↑ Milkau, Bott, 2015 .
  12. ↑ Jordan, Maguire, Hofmann, Kohda, 2016 , s. 20152359.
  13. ↑ Pereira, Gama, Sousa et al., 2015 , s. 10489.
  14. ↑ Ellinas, Allan, Durugbo, Johansson, 2015 , s. e0142469.
  15. ↑ Klemm, Serrano, Eguiluz, Miguel, 2012 , s. 292.

Litteratur