Percolation Centrality

The Percolation Centrality is defined for a given node, at a given time, as the proportion of ‘percolated paths’ that go through that node. A ‘percolated path’ is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state [PIRAVEENAN, M., 2013].
Formally, percolation centrality of node v at time t is:

where σ_sr(V) is total number of shortest paths from node S to node r and σ_sr is the number of those paths that pass through v. The percolation state of the node i at time t is denoted by  X^t_i and two special cases are when  X^t_i=0 which indicates a non-percolated state at time t whereas when X^t_i=1 which indicates a fully percolated state at time t. 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).

The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well.

Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network [Centrality. (2014, July 31). In Wikipedia].

de Limaa, A.M., da Silvaa, M.V. and Vignattia, A.L., Percolation Centrality via Rademacher Complexity.

de Lima, A.M., da Silva, M.V. and Vignatti, A.L., 2019. Approximating the Percolation Centrality through Sampling and Pseudo-dimension. arXiv preprint arXiv:1910.00494.

• Centrality. (2014, July 31). In Wikipedia, The Free Encyclopedia. Retrieved 10:39, August 6, 2014, from http://en.wikipedia.org/wiki/Centrality#Percolation_Centrality
• PIRAVEENAN, M., PROKOPENKO, M. & HOSSAIN, L. 2013. Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks. PLoS ONE, 8, e53095.
• Saad, K.M., 2017. Bulk Synchronous Parallel Implementation of Percolation Centrality for Large Scale Graphs (Doctoral dissertation, Case Western Reserve University).