Approximating the Percolation Centrality through Sampling and Pseudo-dimension
share
In this work we investigate the problem of percolation centrality, a generalization of betweenness centrality, in a weighted graph G under the light of sample complexity theory. For both betweenness and percolation centrality the computation of the exact value for a given vertex v is not known to be easier than the computation the same value, all at once, for all n vertices of G. In any one of these cases it is an open problem whether these measures can be computed in O(n^3-c) time, for any constant c>0. In this paper we first present a O(m log^2 n) randomized approximation algorithm for the percolation centrality for every vertex of G, generalizing techniques developed by <cit.> (this complexity is reduced to O((m+n) log n) for unweighted graphs). The estimative obtained by the algorithm is within ϵ of the exact value with probability 1- δ, for fixed constants 0 < ϵ,δ≤ 1. Additionally, we show that sample complexity theory can be used to distinguish the problem of estimating the percolation centrality of a single vertex, refered as computing p̃(v), from the problem of estimating the percolation centrality of every vertex of G, refered as computing p̃(G). More precisely, we show that p̃(v) and p̃(G) can be estimated respectively in time O(m log n) and O(m log^2 n). Our results also imply a similar "separation" for percolation estimation in unweighted dense graphs as well as separations for the estimation of betweenness centrality that holds in any combination of the following scenarios: weighted or unweighted for either sparse or dense graphs.
READ FULL TEXT