Percolation Centrality via Rademacher Complexity


In this work we investigate the problem of estimating the percolation centrality of all vertices in a weighted graph. The percolation centrality measure quantifies the importance of a vertex in a graph that is going through a contagious process. The fastest exact algorithm for the computation of this measure in a graph G with n vertices and m edges runs in O(n^3). Let Diam_V(G) be the maximum number of vertices in a shortest path in G. In this paper we present an expected O(m log n log Diam_V(G)) time approximation algorithm for the estimation of the percolation centrality for all vertices of G. We show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm returns approximations that are even closer to the exact values than its guarantee in terms of theoretical worst case analysis.

In Discrete Applied Mathematics
André Vignatti
André Vignatti
Associate Professor