Abstract
In this work we investigate the problem of estimating the percolation centrality of every vertex in a graph. This centrality measure quantifies the importance of each vertex in a graph going through a contagious process. It is an open problem whether the percolation centrality can be computed in $\mathcal{O}(n^{3-c})$ time, for any constant $c>0$. In this paper we present a $\tilde{\mathcal{O}}(m)$ randomized approximation algorithm for the percolation centrality for every vertex of $G$, generalizing techniques developed by Riondato, Upfal and Kornaropoulos. The estimation obtained by the algorithm is within $\epsilon$ of the exact value with probability $1- \delta$, for {\it fixed} constants $0 < \epsilon,\delta < 1$. In fact, we show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm is significantly closer to the exact values than its guarantee in terms of theoretical worst case analysis.
