Betweenness centrality

Percolation centrality er en version af vægtet betweenness centrality, men den tager hensyn til “tilstanden” af kilde- og målknudepunkterne for hver korteste vej ved beregningen af denne vægt. Perkolation af en “smitte” forekommer i komplekse netværk i en række scenarier. F.eks. kan en virus- eller bakterieinfektion sprede sig over sociale netværk af mennesker, de såkaldte kontaktnet. Sygdomsspredning kan også betragtes på et højere abstraktionsniveau ved at tænke på et netværk af byer eller befolkningscentre, der er forbundet via vej-, jernbane- eller luftforbindelser. Computervirusser kan spredes over computernetværk. Rygter eller nyheder om forretningstilbud og -aftaler kan også spredes via sociale netværk af mennesker. I alle disse scenarier spreder en “smitte” sig over forbindelserne i et komplekst netværk og ændrer knudernes “tilstand”, efterhånden som den spredes, enten på en måde, der kan genoprettes eller ej. I et epidemiologisk scenario går enkeltpersoner f.eks. fra en “modtagelig” til en “inficeret” tilstand, efterhånden som smitten spredes. De tilstande, som de enkelte knudepunkter kan antage i ovenstående eksempler, kan være binære (f.eks. modtaget/ikke modtaget en nyhed), diskrete (modtagelig/smittet/genoprettet) eller endog kontinuerlige (f.eks. andelen af smittede personer i en by), efterhånden som smitten spreder sig. Fælles for alle disse scenarier er, at smittens spredning resulterer i en ændring af knudetilstanden i netværkene. Med dette for øje blev der foreslået en perkolationscentralitet (PC), som specifikt måler knudernes betydning for at fremme perkolationen gennem netværket. Dette mål blev foreslået af Piraveenan et al.

Perkolationscentralitet defineres for et givet knudepunkt på et givet tidspunkt som andelen af “perkolerede stier”, der går gennem det pågældende knudepunkt. En “perkoleret vej” er den korteste vej mellem et par knudepunkter, hvor kildeknuden er perkoleret (f.eks. inficeret). Målknuden kan være perkoleret eller ikke perkoleret eller i en delvist perkoleret tilstand.

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}}}}

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

er det samlede antal korteste stier fra node s {\displaystyle s}

til knudepunkt r {\displaystyle r}

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

er antallet af de stier, der passerer gennem v {\displaystyle v}

. Perkolationstilstanden for knudepunktet i {\displaystyle i}

på tidspunkt t {\displaystyle t}

betegnes ved x t i {\displaystyle {x^{t}}_{i}}

og to særlige tilfælde er, når x t i = 0 {\displaystyle {x^{t}}}_{i}=0}

, hvilket angiver en ikke-perkoleret tilstand på tidspunkt t {\displaystyle t}

mens når x t i = 1 {\displaystyle {x^{{t}}}_{i}=1}

, hvilket indikerer en fuldt perkoleret tilstand på tidspunktet t {\displaystyle t}

. De mellemliggende værdier angiver delvist perkolerede tilstande (f.eks. vil dette i et netværk af kommuner være den procentvise andel af personer, der er smittet i den pågældende by).

De tilknyttede vægte til perkolationsstierne afhænger af de perkolationsniveauer, der er tildelt kildeknudepunkterne, ud fra den forudsætning, at jo højere perkolationsniveauet for en kildeknudepunkt er, jo vigtigere er de stier, der stammer fra dette knudepunkt. Knudepunkter, der ligger på de korteste stier, der stammer fra knudepunkter med høj perkolation, er derfor potentielt vigtigere for perkolationen. Definitionen af PC kan også udvides til også at omfatte målknudevægte. Beregninger af perkolationscentralitet tager O ( N M ) {\displaystyle O(NM)}

tid med en effektiv implementering, der er overtaget fra Brandes’ hurtige algoritme, og hvis beregningen skal tage hensyn til målknudepunkters vægte, er tiden i værste tilfælde O ( N 3 ) {\displaystyle O(N^{3})}