 |
Conference papers
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 .
Cited literature [24 references]
https://hal.telecom-paris.fr/hal-02339557
Contributor : Albert Bifet <>
Submitted on : Wednesday, October 30, 2019 - 2:45:14 PM
Last modification on : Friday, July 31, 2020 - 11:28:03 AM
Contributor : Albert Bifet <>
Submitted on : Wednesday, October 30, 2019 - 2:45:14 PM
Last modification on : Friday, July 31, 2020 - 11:28:03 AM
File
EDBT19_paper_320.pdf
Publisher files allowed on an open archive