Metropolis-Hastings Algorithms for Estimating Betweenness Centrality Talel Abdessalem

Mostafa Haghir Chehreghani (1) , Talel Abdessalem (2, 1) , Albert Bifet (3, 4, 1)

1 LTCI - Laboratoire Traitement et Communication de l'Information
2 IPAL - Image & Pervasive Access Lab
3 DIG - Data, Intelligence and Graphs
4 INFRES - Département Informatique et Réseaux

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 .

Domaines: Intelligence artificielle [cs.AI]

Mostafa Haghir Chehreghani, Talel Abdessalem, Albert Bifet. Metropolis-Hastings Algorithms for Estimating Betweenness Centrality Talel Abdessalem. 22nd International Conference on Extending Database Technology EDBT 2019, Mar 2019, Lisbon, Portugal. ⟨10.5441/002/edbt.2019.87⟩. ⟨hal-02339557⟩