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. [ABSTRACT FROM AUTHOR]