Centralidad de percolación (medida de centralidad)

Existe una gran cantidad de medidas de centralidad para determinar la «importancia» de un solo Node en una red compleja. Sin embargo, estas medidas cuantifican la importancia de un Node en términos puramente topológicos, y el valor del Node no depende de ningún modo del «estado» del Node. Permanece constante independientemente de la dinámica de la red. Esto es cierto incluso para las medidas de intermediación ponderadas. Sin embargo, un Node puede muy bien estar centralmente ubicado en términos de centralidad de intermediación u otra medida de centralidad, pero puede no estar ‘centralmente’ ubicado en el contexto de una red en la que hay filtración. La filtración de un ‘contagio’ ocurre en redes complejas en varios escenarios. Por ejemplo, la infección viral o bacteriana puede propagarse a través de las redes sociales de las personas, conocidas como redes de contacto. La propagación de enfermedades también se puede considerar en un nivel más alto de abstracción, contemplando una red de ciudades o centros de población conectados por carretera, ferrocarril o enlaces aéreos. Los virus informáticos pueden propagarse a través de las redes informáticas. Los rumores o noticias sobre ofertas y acuerdos comerciales también pueden difundirse a través de las redes sociales de las personas. En todos estos escenarios, un ‘contagio’ se propaga por los enlaces de una red compleja, alterando los ‘estados’ de los Nodes a medida que se propaga, ya sea de manera recuperable o no. Por ejemplo, en un escenario epidemiológico, las personas pasan del estado ‘susceptible’ al estado ‘infectado’ a medida que se propaga la infección. Los estados que pueden tomar los Nodes individuales en los ejemplos anteriores pueden ser binarios (como recibir/no recibir una noticia), discretos (susceptible/infectado/recuperado), o incluso continuo (como la proporción de personas infectadas en un pueblo), a medida que se propaga el contagio. La característica común en todos estos escenarios es que la propagación del contagio da como resultado el cambio de estado de los Nodes en las redes. Con esto en mente, se propuso la centralidad de percolación (PC), que mide específicamente la importancia de los Nodes en términos de ayudar a la percolación a través de la red. Esta medida fue propuesta por Piraveenan et al.

Definición matemática

La Centralidad de Percolación se define para un Node dado, en un momento dado, como la proporción de ‘caminos filtrados’ que pasan por ese Node. Una ‘ruta filtrada’ es la ruta más corta entre un par de Nodes, donde el Node de origen se filtra (p. ej., se infecta). El Node de destino puede estar filtrado o no filtrado, o en un estado parcialmente filtrado.

where is total number of shortest paths from node to node and is the number of those paths that pass through . The percolation state of the node at time is denoted by and two special cases are when which indicates a non-percolated state at time whereas when which indicates a fully percolated state at time . The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).

Los pesos adjuntos a las rutas de percolación dependen de los niveles de percolación asignados a los Nodes de origen, según la premisa de que cuanto mayor sea el nivel de percolación de un Node de origen, más importantes son las rutas que se originan en ese Node. Los Nodes que se encuentran en los caminos más cortos que se originan en Nodes altamente filtrados son, por lo tanto, potencialmente más importantes para la filtración. La definición de PC también se puede ampliar para incluir también los pesos de los Nodes de destino. Los cálculos de centralidad de percolación se ejecutan en el tiempo con una implementación eficiente adoptada del algoritmo rápido de Brandes y si el cálculo debe tener en cuenta los pesos de los Nodes objetivo, el tiempo en el peor de los casos es .

Referencias
https://en.wikipedia.org/wiki/Centrality