Edge percolation centrality: A new measure to quantify the influence of edges during percolation in networks

Abstract

Numerous centrality measures exist to quantify the influence of edges within a network, with edge betweenness being one of the more well-known measures. However, such measures are inadequate in network percolation scenarios (e.g., the transmission of a disease over a transportation network of highways) as they fail to consider the changing percolation states of edges over time. This paper addresses this limitation by extending percolation centrality, a measure originally developed to evaluate the influence of vertices during a percolation process (i.e., a dynamic spread of a contagion) in the network, to the edge level. The proposed measure, edge percolation centrality, captures both the topological connectivity of the network as well as the percolation states of the edges. Although the algorithm’s observed complexity of O(|V|3.57) makes it computationally intensive, the utility of the proposed edge measure is evident in its application to both synthetic and real-world networks undergoing percolation processes.