Betweenness centrality

Percolation centrality è una versione della betweenness centrality ponderata, ma considera lo ‘stato’ dei nodi sorgente e destinazione di ogni percorso più breve nel calcolare questo peso. La percolazione di un “contagio” si verifica nelle reti complesse in una serie di scenari. Per esempio, un’infezione virale o batterica può diffondersi su reti sociali di persone, note come reti di contatto. La diffusione della malattia può anche essere considerata a un livello più alto di astrazione, contemplando una rete di città o centri abitati, collegati da collegamenti stradali, ferroviari o aerei. I virus informatici possono diffondersi su reti di computer. Voci o notizie su offerte e affari possono anche diffondersi attraverso reti sociali di persone. In tutti questi scenari, un “contagio” si diffonde sui collegamenti di una rete complessa, alterando gli “stati” dei nodi mentre si diffonde, in modo recuperabile o meno. Per esempio, in uno scenario epidemiologico, gli individui passano dallo stato “suscettibile” a quello “infetto” mentre l’infezione si diffonde. Gli stati che i singoli nodi possono assumere negli esempi precedenti potrebbero essere binari (come ricevere/non ricevere una notizia), discreti (suscettibile/infetto/recuperato), o anche continui (come la proporzione di persone infette in una città), man mano che il contagio si diffonde. La caratteristica comune a tutti questi scenari è che la diffusione del contagio porta al cambiamento degli stati dei nodi nelle reti. La centralità di percolazione (PC) è stata proposta con questo in mente, che misura specificamente l’importanza dei nodi in termini di aiuto alla percolazione attraverso la rete. Questa misura è stata proposta da Piraveenan et al.

La centralità di percolazione è definita per un dato nodo, in un dato momento, come la proporzione di ‘percorsi percolati’ che passano attraverso quel nodo. Un “percorso percolato” è un percorso più breve tra una coppia di nodi, dove il nodo sorgente è percolato (ad esempio, infetto). Il nodo di destinazione può essere percolato o non percolato, o in uno stato parzialmente percolato.

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

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

è il numero totale di cammini più brevi dal nodo s {displaystyle s}

al nodo r {displaystyle r}

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

è il numero di quei cammini che passano attraverso v {\displaystyle v}

. Lo stato di percolazione del nodo i {\displaystyle i}

al tempo t {displaystyle t}

è denotato da x t i {displaystyle {x^{t}}_{i}

e due casi speciali sono quando x t i = 0 {displaystyle {x^{t}}_{i}=0}

che indica uno stato non percolato al tempo t {\displaystyle t}

mentre quando x t i = 1 {displaystyle {x^{t}}_{i}=1}

che indica uno stato completamente percolato al tempo t {\displaystyle t}

. I valori intermedi indicano stati parzialmente percolati (ad esempio, in una rete di comuni, questo sarebbe la percentuale di persone infette in quella città).

I pesi assegnati ai percorsi di percolazione dipendono dai livelli di percolazione assegnati ai nodi sorgente, basati sulla premessa che più alto è il livello di percolazione di un nodo sorgente, più importanti sono i percorsi che hanno origine da quel nodo. I nodi che si trovano sui percorsi più brevi che hanno origine da nodi altamente percolati sono quindi potenzialmente più importanti per la percolazione. La definizione di PC può anche essere estesa per includere anche i pesi dei nodi di destinazione. I calcoli della centralità di percolazione si eseguono in O ( N M ) {\displaystyle O(NM)}

tempo con un’implementazione efficiente adottata dall’algoritmo veloce di Brandes e se il calcolo deve considerare i pesi dei nodi target, il tempo peggiore è O ( N 3 ) {displaystyle O(N^{3})}