Metropolis-Hastings Algorithms for Estimating Betweenness Centrality Talel Abdessalem

Abstract : Recently, an optimal probability distribution was proposed to sample vertices for estimating betweenness centrality, that yields the minimum approximation error. However, it is computation-ally 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 sam-pler 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 r i , 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 .