Betweenness centrality

Percolation centrality is een versie van gewogen betweenness centrality, maar houdt bij de berekening van dit gewicht rekening met de “toestand” van de bron- en doelknooppunten van elk kortste pad. Percolatie van een “besmetting” komt in complexe netwerken in een aantal scenario’s voor. Een virale of bacteriële infectie kan zich bijvoorbeeld verspreiden over sociale netwerken van mensen, de zogenaamde contactnetwerken. De verspreiding van ziekten kan ook op een hoger abstractieniveau worden bekeken, door te denken aan een netwerk van steden of bevolkingscentra, verbonden door weg-, spoor- of luchtverbindingen. Computervirussen kunnen zich via computernetwerken verspreiden. Geruchten of nieuws over zakelijke aanbiedingen en deals kunnen zich ook verspreiden via sociale netwerken van mensen. In al deze scenario’s verspreidt een “besmetting” zich over de schakels van een complex netwerk, waarbij de “toestanden” van de knooppunten veranderen naarmate de besmetting zich verspreidt, al dan niet op herstelbare wijze. In een epidemiologisch scenario bijvoorbeeld gaan individuen van “vatbaar” naar “besmet” naarmate de infectie zich verspreidt. De toestanden die de individuele knooppunten in de bovenstaande voorbeelden kunnen aannemen, kunnen binair zijn (zoals wel/niet een nieuwtje ontvangen), discreet (vatbaar/geïnfecteerd/hersteld), of zelfs continu (zoals het percentage geïnfecteerde mensen in een stad), naarmate de besmetting zich verspreidt. Het gemeenschappelijke kenmerk van al deze scenario’s is dat de verspreiding van besmetting leidt tot een verandering van de toestand van knooppunten in netwerken. Met dit in gedachten werd de percolatiecentraliteit (PC) voorgesteld, die specifiek het belang van knooppunten meet in termen van het helpen van de percolatie door het netwerk. Deze maatstaf werd voorgesteld door Piraveenan et al.

Percolation centrality wordt voor een gegeven knooppunt, op een gegeven tijdstip, gedefinieerd als het aandeel van “gepercoleerde paden” die door dat knooppunt gaan. Een “gepercoleerd pad” is een kortste pad tussen een paar knooppunten, waarbij het bronknooppunt gepercoleerd (bv. geïnfecteerd) is. Het doelknooppunt kan gepercoleerd of niet-gepercoleerd zijn, of in een gedeeltelijk gepercoleerde toestand verkeren.

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 _{sigma _{sr}(v)}{{sigma _{sr}}}{\frac {{x^{t}}_{s}}{sum {}-{x^{t}}}_{v}}}}

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

het totale aantal kortste paden is van knooppunt s {\displaystyle s}

naar knooppunt r {\displaystyle r}

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

is het aantal paden dat door v gaat {\displaystyle v}

. De percolatietoestand van knooppunt i {\displaystyle i}

op tijdstip t {\displaystyle t}

wordt aangeduid met x t i {x^{t}}_{i}}

en twee speciale gevallen zijn wanneer x t i = 0 {\displaystyle {x^{t}}_{i}=0}

wat wijst op een niet-gepercoleerde toestand op tijdstip t {\displaystyle t}

terwijl wanneer x t i = 1 {\displaystyle {x^{t}}_{i}=1}

wat wijst op een volledig gepercolateerde toestand op tijdstip t {\displaystyle t}

. De waarden daartussen geven een gedeeltelijk doortrokken toestand aan (bv. in een netwerk van steden zou dit het percentage besmette mensen in die stad zijn).

De aan de percolatiepaden toegekende gewichten hangen af van de percolatieniveaus die aan de bronknooppunten zijn toegekend, uitgaande van de premisse dat hoe hoger het percolatieniveau van een bronknooppunt is, hoe belangrijker de paden zijn die van dat knooppunt uitgaan. Knooppunten die op kortste paden liggen die van hoog gepercoleerde knooppunten uitgaan, zijn dus potentieel belangrijker voor de percolatie. De definitie van PC kan ook worden uitgebreid met de gewichten van doelknooppunten. Percolatiecentraliteitsberekeningen verlopen in O ( N M ) {\displaystyle O(NM)}

tijd met een efficiënte implementatie die is overgenomen van het snelle algoritme van Brandes. Als bij de berekening ook gewichten van doelknooppunten moeten worden meegenomen, is de tijd in het ergste geval O ( N 3 ) {Displaystyle O(N^{3})}