Nodpåverkansmått

I grafteori och nätverksanalys är nodpåverkansmått mätningar som rangordnar eller kvantifierar påverkan av varje nod ( även kallad vertex) i en graf. De är relaterade till centralitetsindex . Tillämpningar inkluderar mätning av varje persons inflytande i ett socialt nätverk , förståelse av infrastrukturnodernas roll i transportnätverk , Internet eller stadsnätverk , och deltagandet av en given nod i sjukdomsdynamiken.

Ursprung och utveckling

Den traditionella metoden för att förstå nodens betydelse är via centralitetsindikatorer . Centralitetsindex är utformade för att ge en rankning som exakt identifierar de mest inflytelserika noderna. Sedan mitten av 2000-talet har dock samhällsvetare och nätverksfysiker börjat ifrågasätta centralitetsindexens lämplighet för att förstå nodpåverkan. Centraliteter kan indikera de mest inflytelserika noderna, men de är ganska mindre informativa för de allra flesta noder som inte är särskilt inflytelserika.

Borgatti och Everetts översiktsartikel från 2006 visade att noggrannheten hos centralitetsindex är starkt beroende av nätverkstopologi. Detta fynd har observerats upprepade gånger sedan dess. (t.ex). 2012 påminde Bauer och kollegor oss om att centralitetsindex bara rangordnar noder men inte kvantifierar skillnaden mellan dem. Under 2013 presenterade Sikic och kollegor starka bevis för att centralitetsindex avsevärt underskattar kraften hos icke-hubnoder. Anledningen är ganska tydlig. Noggrannheten hos ett centralitetsmått beror på nätverkstopologi, men komplexa nätverk har heterogen topologi. Därför kommer ett centralitetsmått som är lämpligt för att identifiera mycket inflytelserika noder med största sannolikhet vara olämpligt för resten av nätverket.

Detta har inspirerat utvecklingen av nya metoder utformade för att mäta påverkan av alla nätverksnoder. De mest allmänna av dessa är tillgängligheten , som använder mångfalden av slumpmässiga vandringar för att mäta hur tillgänglig resten av nätverket är från en given startnod, och den förväntade kraften , härledd från det förväntade värdet av infektionskraften som genereras av en nod. Båda dessa mått kan på ett meningsfullt sätt beräknas enbart utifrån nätverkets struktur.

Tillgänglighet

Tillgängligheten härrör från teorin om slumpmässiga promenader . Den mäter mångfalden av självundvikande promenader som startar från en given nod. En promenad på ett nätverk är en sekvens av angränsande hörn; en självundvikande promenad besöker (listar upp) varje vertex högst en gång. Det ursprungliga verket använde simulerade promenader av längd 60 för att karakterisera nätverket av urbana gator i en brasiliansk stad. Det formaliserades senare som en modifierad form av hierarkisk grad som kontrollerar både överföringssannolikheter och mångfalden av promenader av en given fast längd.

Definition

Den hierarkiska graden mäter antalet noder som kan nås från en startnod genom att utföra promenader med längden $h$ . För en fast $h$ och gångtyp nås var och en av dessa grannar med en (potentiellt olika) sannolikhet $p_{j}^{(h)}$ . Givet en vektor med sådana sannolikheter definieras tillgängligheten för nod $i$ i skala $h$

$\kappa _{i}^{(h)}=\exp \left(-\summa _ {j}p_{j}^{(h)}\log p_{j}^{(h)}\right)$

Sannolikheterna kan baseras på slumpmässiga vandringar med likformig sannolikhet, eller dessutom modulerade av kantvikter och/eller explicita (per kant) överföringssannolikheter.

Ansökningar

Tillgängligheten har visat sig avslöja samhällsstruktur i stadsnätverk, motsvarar antalet noder som kan besökas under en definierad tidsperiod och är förutsägande för resultatet av epidemiologiska SIR-modellspridningsprocesser på nätverk med stor diameter och låg densitet .

Förväntad kraft

Den förväntade kraften mäter nodpåverkan ur ett epidemiologiskt perspektiv. Det är det förväntade värdet av infektionskraften som genereras av noden efter två överföringar.

Definition

Den förväntade kraften för en nod $i$ ges av

$\kappa _{i}=-\summa _{j=1}^{J}d_{j}\log(d_{j })$

där summan tas över mängden $J$ av alla möjliga överföringskluster som är resultatet av två överföringar som börjar från $i$ . Det vill säga nod $i$ och två av dess grannar eller $i$ , en av dess grannar (kallas infekterad) och en granne till den infekterade grannen. $J$ innehåller alla möjliga ordningsföljder av överföringshändelser, så två kluster kan innehålla samma noder om de blev infekterade i en annan ordning. $d_{j}$ är den normaliserade klustergraden för kluster ${\displaystyle j\in J} ,$ det vill säga antalet kanter med exakt en slutpunkt i kluster $j$ .

Definitionen sträcker sig naturligtvis till riktade nätverk genom att begränsa uppräkningen $J$ med kantriktning. På samma sätt är utvidgning till viktade nätverk, eller nätverk med heterogena överföringssannolikheter, en fråga om att justera normaliseringen av $d_{j}$ för att inkludera sannolikheten att det klustret bildas. Det är också möjligt att använda mer än två sändningar för att definiera uppsättningen $J$ .

Ansökningar

Den förväntade kraften har visat sig starkt korrelera med SI-, SIS- och SIR-epidemiresultat över ett brett spektrum av nätverkstopologier, både simulerade och empiriska. Det har också använts för att mäta den pandemipotential som världens flygplatser har och nämnts i samband med digitala betalningar, ekologi, fitness och projektledning.

Andra tillvägagångssätt

Andra föreslår mått som uttryckligen kodar dynamiken i en specificerad process som utspelar sig på nätverket. Det dynamiska inflytandet är andelen oändliga vandringar som börjar från varje nod, där vandringssteg skalas så att den linjära dynamiken i systemet förväntas konvergera till ett stabilt tillstånd som inte är noll. Impact överföring till promenadens slutnod och att slutnoden inte tidigare har besökts av en kortare promenad. Även om båda måtten väl förutsäger resultatet av de dynamiska system de kodar, medger författarna i varje fall att resultat från en dynamik inte översätts till annan dynamik.