  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
$\mathcal{O}(m \log^2 n)$ randomized approximation algorithm for the
percolation centrality for every vertex of $G$, generalizing techniques
developed by Riondato, Upfal e Kornaropoulos (this complexity is reduced to
$\mathcal{O}((m+n) \log n)$ for unweighted graphs). The estimation obtained by
the algorithm is within $\epsilon$ of the exact value with probability
$1-\delta$, for {\it fixed} constants $0 < \epsilon,\delta \leq 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.
