Percolation Centrality via Rademacher Complexity

Abstract

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.