Betweenness centrality

Percolation centrality är en version av vägd betweenness centrality, men den tar hänsyn till ”tillståndet” hos käll- och målnoderna för varje kortaste väg vid beräkningen av denna vikt. Perkolation av en ”smitta” förekommer i komplexa nätverk i ett antal scenarier. En virus- eller bakterieinfektion kan till exempel spridas över sociala nätverk av människor, så kallade kontaktnät. Sjukdomsspridning kan också betraktas på en högre abstraktionsnivå genom att tänka på ett nätverk av städer eller befolkningscentra som är sammankopplade genom väg-, järnvägs- eller flygförbindelser. Datorvirus kan spridas via datornätverk. Rykten eller nyheter om affärserbjudanden och affärer kan också spridas via sociala nätverk av människor. I alla dessa scenarier sprids en ”smitta” över länkarna i ett komplext nätverk och ändrar nodernas ”tillstånd” när den sprids, antingen på ett återställbart sätt eller på annat sätt. I ett epidemiologiskt scenario går t.ex. individer från ett ”mottagligt” till ett ”infekterat” tillstånd när smittan sprids. De tillstånd som de enskilda noderna kan anta i ovanstående exempel kan vara binära (t.ex. mottagit/inte mottagit en nyhet), diskreta (mottaglig/infekterad/återställd) eller till och med kontinuerliga (t.ex. andelen infekterade personer i en stad) när smittan sprids. Det gemensamma draget i alla dessa scenarier är att smittspridningen leder till att nodtillståndet i nätverken förändras. Med detta i åtanke föreslogs perkolationscentralitet (PC), som särskilt mäter betydelsen av noder när det gäller att underlätta perkolationen genom nätverket. Detta mått föreslogs av Piraveenan et al.

Perkolationscentralitet definieras för en given nod, vid en given tidpunkt, som andelen ”perkolerade vägar” som går genom den noden. En ”perkolerad väg” är den kortaste vägen mellan ett par noder där källnoden är perkolerad (t.ex. infekterad). Målnoden kan vara perkolaterad, icke perkolaterad eller i ett delvis perkolaterat tillstånd.

P C t ( v ) = 1 N – 2 ∑ s ≠ v ≠ r σ s r ( v ) σ s r x t s ∑ – x t v {\displaystyle PC^{t}(v)={\frac {1}{N-2}}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}}_{s}}{{\sum {}-{x^{t}}_{v}}}}

varvid σ s r {\displaystyle \sigma _{sr}}

är det totala antalet kortaste vägar från nod s {\displaystyle s}

till nod r {\displaystyle r}

och σ s r ( v ) {\displaystyle \sigma _{sr}(v)}

är antalet banor som passerar genom v {\displaystyle v}

. Perkolationstillståndet för noden i {\displaystyle i}

vid tiden t {\displaystyle t}

betecknas med x t i {\displaystyle {x^{t}}_{i}}

och två specialfall är när x t i = 0 {\displaystyle {x^{t}}}_{i}=0}

vilket indikerar ett icke-perkolerat tillstånd vid tiden t {\displaystyle t}

medan när x t i = 1 {\displaystyle {x^{t}}}_{i}=1}

vilket indikerar ett fullständigt perkolerat tillstånd vid tiden t {\displaystyle t}

. Värdena däremellan anger delvis perkolerade tillstånd (t.ex. i ett nätverk av städer skulle detta vara den procentuella andelen människor som är smittade i den staden).

De bifogade vikterna för perkolationsvägarna beror på de perkolationsnivåer som tilldelats källnoderna, utifrån förutsättningen att ju högre perkolationsnivå en källnod har, desto viktigare är de vägar som utgår från den noden. Noder som ligger på kortaste vägar som utgår från noder med hög perkolation är därför potentiellt viktigare för perkolationen. Definitionen av PC kan också utvidgas till att även omfatta målnodsvikter. Beräkningar av perkolationens centralitet tar O ( N M ) {\displaystyle O(NM)}

med en effektiv implementering som är hämtad från Brandes snabba algoritm, och om beräkningen måste ta hänsyn till målnodernas vikter är tiden i värsta fall O ( N 3 ) {\displaystyle O(N^{3})}.