Metropolis-hastings algorithms for estimating betweenness centrality

Recently, an optimal probability distribution was proposed to sample vertices for estimating betweenness centrality, that yields the minimum approximation error. However, it is computationally expensive to directly use it. In this paper, we investigate exploiting Metropolis-Hastings technique to sample based on this distribution. As a result, first given a network G and a vertex r ϵ V(G), we propose a Metropolis-Hastings MCMC algorithm that samples from the space V(G) and estimates betweenness score of r. The stationary distribution of our MCMC sampler is the optimal distribution. We also show that our MCMC sampler provides an (ϵ,δ)-approximation. Then, given a network G and a set R ⊂ V(G), we present a Metropolis-Hastings MCMC sampler that samples from the joint space R and V(G) and estimates relative betweenness scores of the vertices in R. We show that for any pair ri,r_j ϵ R, the ratio of the expected values of the estimated relative betweenness scores of r_i and r_j with respect to each other is equal to the ratio of their betweenness scores. We also show that our joint-space MCMC sampler provides an (ϵ,δ)-approximation of the relative betweenness score of r_i with respect to r_j.