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 .
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.telecom-paristech.fr/hal-02339557
Contributor : Albert Bifet <>
Submitted on : Wednesday, October 30, 2019 - 2:45:14 PM
Last modification on : Wednesday, November 6, 2019 - 1:29:07 AM

File

EDBT19_paper_320.pdf
Publisher files allowed on an open archive

Identifiers

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

2