Title: Metropolis-Hastings Algorithms for Estimating Betweenness Centrality in Large Networks,
Abstract: Betweenness centrality is an important index widely used in different domains
such as social networks, traffic networks and the world wide web. However, even
for mid-size networks that have only a few hundreds thousands vertices, it is
computationally expensive to compute exact betweenness scores. Therefore in
recent years, several approximate algorithms have been developed. In this
paper, first given a network $G$ and a vertex $r \in 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 sampling proposed for betweenness centrality estimation.
We show that our MCMC sampler provides an $(\epsilon,\delta)$-approximation,
where the number of required samples depends on the position of $r$ in $G$ and
in many cases, it is a constant. Then, given a network $G$ and a set $R \subset
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 $r_i, r_j \in R$, the ratio of the
expected values of the estimated relative betweenness scores of $r_i$ and $r_j$
respect to each other is equal to the ratio of their betweenness scores. We
also show that our joint-space MCMC sampler provides an
$(\epsilon,\delta)$-approximation of the relative betweenness score of $r_i$
respect to $r_j$, where the number of required samples depends on the position
of $r_j$ in $G$ and in many cases, it is a constant.