Centralidad de la interrelación

La centralidad de la percolación es una versión de la centralidad de la interrelación ponderada, pero tiene en cuenta el «estado» de los nodos de origen y destino de cada camino más corto para calcular este peso. La percolación de un «contagio» se produce en redes complejas en una serie de escenarios. Por ejemplo, una infección viral o bacteriana puede propagarse por redes sociales de personas, conocidas como redes de contacto. La propagación de una enfermedad también puede considerarse a un nivel superior de abstracción, contemplando una red de ciudades o núcleos de población, conectados por carretera, ferrocarril o aire. Los virus informáticos pueden propagarse por las redes de ordenadores. Los rumores o las noticias sobre ofertas y tratos comerciales también pueden propagarse a través de las redes sociales de personas. En todos estos escenarios, un «contagio» se extiende por los enlaces de una red compleja, alterando los «estados» de los nodos a medida que se propaga, ya sea de forma recuperable o no. Por ejemplo, en un escenario epidemiológico, los individuos pasan del estado «susceptible» al «infectado» a medida que la infección se propaga. Los estados que pueden adoptar los nodos individuales en los ejemplos anteriores pueden ser binarios (como haber recibido/no haber recibido una noticia), discretos (susceptible/infectado/recuperado), o incluso continuos (como la proporción de personas infectadas en una ciudad), a medida que se propaga el contagio. La característica común en todos estos escenarios es que la propagación del contagio provoca el cambio de los estados de los nodos en las redes. Para ello se propuso la centralidad de percolación (PC), que mide específicamente la importancia de los nodos en términos de ayuda a la percolación a través de la red. Esta medida fue propuesta por Piraveenan et al.

La centralidad de percolación se define para un nodo dado, en un momento dado, como la proporción de ‘caminos percolados’ que pasan por ese nodo. Un «camino percolado» es el camino más corto entre un par de nodos, donde el nodo de origen está percolado (por ejemplo, infectado). El nodo destino puede estar percolado o no percolado, o en un estado parcialmente percolado.

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

donde σ s r {{sigma _{sr}}

es el número total de caminos más cortos desde el nodo s {\displaystyle s}

al nodo r {\displaystyle r}

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

es el número de esos caminos que pasan por v {\displaystyle v}

. El estado de percolación del nodo i {\displaystyle i}

en el momento t {\displaystyle t}

se denota por x t i {\displaystyle {x^{t}_{i}}

y dos casos especiales son cuando x t i = 0 {\displaystyle {x^{t}_{i}=0}

que indica un estado no percolado en el tiempo t {\displaystyle t}

mientras que cuando x t i = 1 {\displaystyle {x^{t}_{i}=1}

que indica un estado totalmente percolado en el tiempo t {\displaystyle t}

. Los valores intermedios indican estados parcialmente percolados (por ejemplo, en una red de municipios, esto sería el porcentaje de personas infectadas en ese pueblo).

Los pesos asignados a los caminos de percolación dependen de los niveles de percolación asignados a los nodos fuente, basándose en la premisa de que cuanto más alto es el nivel de percolación de un nodo fuente, más importantes son los caminos que se originan en ese nodo. Por lo tanto, los nodos que se encuentran en los caminos más cortos que se originan en los nodos de alto nivel de percolación son potencialmente más importantes para la percolación. La definición de CP también puede ampliarse para incluir los pesos de los nodos objetivo. Los cálculos de centralidad de percolación se ejecutan en O ( N M ) {\displaystyle O(NM)}

tiempo con una implementación eficiente adoptada del algoritmo rápido de Brandes y si el cálculo necesita considerar los pesos de los nodos objetivo, el peor caso de tiempo es O ( N 3 ) {\displaystyle O(N^{3})}