Metropolis-Hastings Algorithms for Estimating
Betweenness Centrality in Large Networks
Mostafa Haghir Chehreghani1 , Talel Abdessalem2 , and Albert
Bifet3
1
2

arXiv:1704.07351v3 [cs.DS] 3 May 2017

3

LTCI, Télécom ParisTech, Université Paris-Saclay, Paris, France
mostafa.chehreghani@gmail.com
LTCI, Télécom ParisTech, Université Paris-Saclay, Paris, France
talel.abdessalem@telecom-paristech.fr
LTCI, Télécom ParisTech, Université Paris-Saclay, Paris, France
albert.bifet@telecom-paristech.fr

Abstract
Betweenness centrality is an important index widely used in diﬀerent domains such as social networks, traﬃc 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, ﬁrst 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 sampling proposed for betweenness
centrality estimation. We show that our MCMC sampler provides an (ǫ, δ)-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 ⊂ 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 ri , rj ∈ R, the ratio of the expected values
of the estimated relative betweenness scores of ri and rj 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 ri respect to rj , where the number
of required samples depends on the position of rj in G and in many cases, it is a constant.
1998 ACM Subject Classification G.2.2 [Discrete Mathematics] Graph Theory, Graph algorithms
Keywords and phrases Network analysis, betweenness centrality, relative betweenness score,
approximate algorithm, Metropolis-Hastings algorithm, MCMC algorithm
Digital Object Identifier 10.4230/LIPIcs.—.—.-

1

Introduction

Centrality is a structural property of vertices (or edges) in the network that quantiﬁes their
relative importance. For example, it determines the importance of a person within a social
network, or a road within a road network. Freeman [16] introduced and deﬁned betweenness
centrality of a vertex as the number of shortest paths from all (source) vertices to all others
that pass through that vertex. He used it for measuring the control of a human over
the communications among others in a social network [16]. Betweenness centrality is also
used in some well-known algorithms for clustering and community detection in social and
information networks [19].
Although there exist polynomial time and space algorithms for betweenness centrality
estimation, the algorithms are expensive in practice. Currently, the most eﬃcient existing
© Mostafa Haghir Chehreghani and Talel Abdessalem and Albert Bifet;
licensed under Creative Commons License CC-BY
–.
Editors: —; Article No. -; pp. -:1—:14
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

-:2

Estimating Betweenness Centrality

exact method is Brandes’s algorithm [8]. Time complexity of this algorithm is O(nm) for
unweighted graphs and O(nm + n2 log n) for weighted graphs with positive weights, where
n and m are the number of vertices and the number of edges of the network, respectively.
This means exact betweenness centrality computation is not applicable, even for mid-size
networks. However, there exist observations that may improve computation of betweenness
scores in practice.
First, in several applications it is suﬃcient to compute betweenness score of only one or
a few vertices. For instance, this index might be computed for only core vertices of communities in social/information networks [34] or for only hubs in communication networks.
Note that these vertices are not necessarily those that have the highest betweenness scores.
Hence, algorithms that identify vertices with the highest betweenness scores [30] are not
applicable. While exact computation of this index for one vertex is not easier than that
for all vertices, Chehreghani [13] and later Riondato and Kornaropoulos [30] respectively
showed that this index can be estimated more eﬀectively for one arbitrary vertex and for
k vertices that have the highest scores.
Second, in practice, instead of computing betweenness scores, it is usually suﬃcient to
compute betweenness ratios or rank vertices according to their betweenness scores [30].
For example, Daly and Haahr [14] exploited betweenness ratios for ﬁnding routes that
provide good delivery performance and low delay in Mobile Ad hoc Networks. In the
Girvan and Newman’s iterative algorithm for community detection [19], at each iteration
it is required to detect the edge with the highest betweenness score and remove it from
the network. The other application discussed in [1], is handling cascading failures.
While the above mentioned observations do not yield a better algorithm when exact
betweenness scores are used, they may improve approximate algorithms. In particular,
algorithms such as [13] and [31] have used the ﬁrst observation to propose algorithms that
can estimate betweenness of a single vertex or a few vertices better than estimating it for
all vertices.
In the current paper, we exploit both observations to design more eﬀective approximate
algorithms. In the ﬁrst problem studied in this paper, we assume that we are given a vertex
r ∈ V (G) and we want to estimate its betweenness score. In the second problem, we assume
that we are given a set R ⊂ V (G) and we want to estimate the ratio of betweenness scores
of vertices in R. The second problem is formally deﬁned as follows: given a graph G and
a set R ⊂ V (G), for any two vertices ri and rj in R, we want to estimate the relative
betweenness score of ri respect to rj , denoted by BCrj (ri ) (see Equation 23 of Section 4.3
for the formal deﬁnition of relative betweenness score). The ratio of our estimations of
BCrj (ri ) and BCri (rj ) is equal to the ratio of betweenness scores of ri and rj . To address
these problems, we use a technique which is new in the context of network analysis, but has
already been used in statistical physics to estimate free energy diﬀerences [5]. Our technique
is based on a sampling method that belongs to a speciﬁc class of Monte Carlo Markov Chain
(MCMC) algorithms, called Metropolis Hastings [25].
In this paper, our key contributions are as follows.
Given a graph G and a vertex r ∈ V (G), in order to estimate betweenness score of r, we
develop a MCMC sampler that samples from the space V (G). We show that our MCMC
sampler can provide an (ǫ, δ)-approximation ofh the betweenness scorei of r, where ǫ ∈ R+
....
and δ ∈ (0, 1). In particular, we prove that P |BC(r) − BC(r)| > ǫ ≤ δ, where BC(r)
....
is the betweenness score of r and BC(r) is its estimated value. Unlike existing work, our
samples are non-iid and the stationary distribution of our MCMC sampler is the optimal

M. H. Chehreghani et. al.

-:3

probability distribution proposed in [13]. Moreover, the number of samples required by
our sampler depends on the position of the vertex in the graph and in several cases, it is
a constant.
Given a graph G and a set R ⊂ V (G), in order to estimate relative betweenness scores of
all pairs of vertices in R, we develop a MCMC sampler that samples from the joint space
R and V (G). This means each sample (state) in our MCMC sampler is a pair hr, vi,
where r ∈ R and v ∈ V (G). For any two vertices ri , rj ∈ R, we show that our joint-space
MCMC sampler provides an (ǫ, δ)-approximation of the relative betweenness score of ri
respect to rj , where the number of required samples depends only on the position of rj
in the graph and in several cases, it is a constant.
The rest of this paper is organized as follows. In Section 2, preliminaries and necessary
deﬁnitions related to betweenness centrality and MCMC algorithms are introduced. A brief
overview on related work is given in Section 3. In Section 4, we present our MCMC samplers
and their analysis. Finally, the paper is concluded in Section 5.

2

Preliminaries

In this section, we present deﬁnitions and notations widely used in the paper. We assume
that the reader is familiar with basic concepts in graph theory. Throughout the paper, G
refers to a graph (network). For simplicity, we assume that G is a undirected, connected
and loop-free graph without multi-edges. Throughout the paper, we assume that G is an
unweighted graph, unless it is explicitly mentioned that G is weighted. V (G) and E(G) refer
to the set of vertices and the set of edges of G, respectively. For a vertex v ∈ V (G), by G \ v
we refer to the set of connected graphs generated by removing v from G. In the following, ﬁrst
in Section 2.1 we introduce deﬁnitions and concepts related to betweenness centrality. Then
in Section 2.2, we present a brief overview of MCMC and Metropolis-Hastings algorithms.

2.1

Betweenness centrality

A shortest path (also called a geodesic path) between two vertices u, v ∈ V (G) is a path
whose size is minimum, among all paths between u and v. For two vertices u, v ∈ V (G), we
use d(u, v), to denote the size (the number of edges) of a shortest path connecting u and v.
By deﬁnition, d(u, v) = 0 and d(u, v) = d(v, u). For s, t ∈ V (G), σst denotes the number of
shortest paths between s and t, and σst (v) denotes the number of shortest paths between s
and t that also pass through v. Betweenness centrality of a vertex v is deﬁned as:
BC(v) =

1
|V (G)| · (|V (G)| − 1)

X

s,t∈V (G)\{v}

σst (v)
.
σst

(1)

A notion which is widely used for counting the number of shortest paths in a graph is
the directed acyclic graph (DAG) containing all shortest paths starting from a vertex s (see
e.g., [8]). In this paper, we refer to it as the shortest-path-DAG, or SPD in short, rooted at
s. For every vertex s in graph G, the SPD rooted at s is unique, and it can be computed
in O(|E(G)|) time for unweighted graphs and in O (|E(G)| + |V (G)| log |V (G)|) time for
weighted graphs with positive weights [8].
Brandes [8] introduced the notion of the dependency score of a vertex s ∈ V (G) on a
vertex v ∈ V (G) \ {s}, which is deﬁned as:
X
δst (v)
(2)
δs• (v) =
t∈V (G)\{v,s}

—

-:4

Estimating Betweenness Centrality

where δst (v) =
BC(v) =

σst (v)
σst .

We have:

1
|V (G)| · (|V (G)| − 1)

X

δs• (v).

(3)

s∈V (G)\{v}

Brandes [8] showed that dependency scores of a source vertex on diﬀerent vertices in the
network can be computed using a recursive relation, deﬁned as the following:
X
σsv
(1 + δs• (w)),
(4)
δs• (v) =
σsw
w:v∈Ps (w)

where Ps (w) is deﬁned as {u ∈ V (G) : {u, w} ∈ E(G) ∧ dG (s, v) = dG (s, u) + 1}. In other
words, Ps (w) contains the set of all parents (predecessors) of w in the SPD rooted at s. As
mentioned in [8], given the SPD rooted at s, for unweighted graphs and weighted graphs with
positive weights, dependency scores of s on all other vertices can be computed in O(|E(G)|)
time and O(|V (G)| log |V (G)| + |E(G)|) time, respectively.

2.2

MCMC and Metropolis-Hastings algorithms

In this section, we brieﬂy review some basic notions and deﬁnitions in MCMC and MetropolisHasting algorithms. For a comprehensive study, the interested reader can refer to e.g., [10].
A Markov chain is a sequence of dependent random variables (states) such that the probability distribution of each variable given the past variables depends only on the last variable.
A Markov chain has stationary distribution if the conditional distribution of the k + 1th state
given the k th state does not depend on k.
Let P[x] be a probability distribution deﬁned on the random variable x. When the
function f (x), which is proportional to the density of P[x], can be eﬃciently computed,
the Metropolis-Hastings algorithm is used to draw samples from P[x]. In a simple form
(with symmetric proposal distribution), the Metropolis-Hastings algorithm ﬁrst chooses an
arbitrary initial state x0 . Then, iteratively:
Let x be the current state. It generates a candidate x′ using the proposal distribution
q(x′ |x).
o
n
′
)
It moves from x to x′ with probability min 1, ff(x
(x) .
The proposal distribution q(x′ |x) deﬁnes the conditional probability of proposing a state x′
given the state x. In the Independence Metropolis-Hastings algorithm, q(x′ |x) is independent
of x, i.e., q(x′ |x) = g(x′ ). A suﬃcient but not necessary condition for the existence of
stationary distribution in a Metropolis-Hastings algorithm is the detailed balance condition.
It says that for each pair of states x and x′ , the probability of being in state x and moving to
state x′ is equal to the probability of being in state x′ and moving to state x. By T R(x′ |x),
we denote the probability of moving from state x to state x′ .

3

Related work

Brandes [8] introduced an eﬃcient algorithm for computing betweenness centrality of a
vertex, which is performed in O(|V (G)||E(G)|) and O(|V (G)||E(G)| + |V (G)|2 log |V (G)|)
times for unweighted and weighted networks with positive weights, respectively. Çatalyürek
et. al. [11] presented the compression and shattering techniques to improve eﬃciency of
Brandes’s algorithm for large graphs. During compression, vertices with known betweenness
scores are removed from the graph and during shattering, the graph is partitioned into smaller
components. Holme [21] showed that betweenness centrality of a vertex is highly correlated

M. H. Chehreghani et. al.

-:5

with the fraction of time that the vertex is occupied by the traﬃc of the network. Barthelemy
[4] showed that many scale-free networks [3] have a power-law distribution of betweenness
centrality.

3.1

Generalization to sets

Everett and Borgatti [15] deﬁned group betweenness centrality as a natural extension of
betweenness centrality for sets of vertices. Group betweenness centrality of a set is deﬁned
as the number of shortest paths passing through at least one of the vertices in the set
[15]. The other natural extension of betweenness centrality is co-betweenness centrality. Cobetweenness centrality is deﬁned as the number of shortest paths passing through all vertices
in the set. Kolaczyk et. al. [22] presented an O(|V (G)|3 ) time algorithm for co-betweenness
centrality computation of sets of size 2. Chehreghani [12] presented eﬃcient algorithms for
co-betweenness centrality computation of any set or sequence of vertices in weighted and
unweighted networks. Puzis et. al. [28] proposed an O(|K|3 ) time algorithm for computing
successive group betweenness centrality, where |K| is the size of the set. The same authors
in [29] presented two algorithms for ﬁnding most prominent group. A most prominent group
of a network is a set vertices of minimum size, so that every shortest path in the network
passes through at least one of the vertices in the set. The ﬁrst algorithm is based on a
heuristic search and the second one is based on iterative greedy choice of vertices.

3.2

Approximate algorithms

Brandes and Pich [9] proposed an approximate algorithm based on selecting k source vertices and computing dependency scores of them on the other vertices in the graph. They
used various strategies for selecting the source vertices, including: MaxMin, MaxSum and
MinSum [9]. In the method of [2], some source vertices are selected uniformly at random,
and their dependency scores are computed and scaled for all vertices. Geisberger et. al.
[17] presented an algorithm for approximate ranking of vertices based on their betweenness
scores. In this algorithm, the method for aggregating dependency scores changes so that
vertices do not proﬁt from being near the selected source vertices. Chehreghani [13] proposed a randomized framework for unbiased estimation of the betweenness score of a single
vertex. Then, to estimate betweenness score of vertex v, he proposed a non-uniform sampler,
d(v,s)
, where s ∈ V (G) \ {v}.
deﬁned as follows: P[s] = P
d(v,u)
u∈V (G)\{v}

Riondato and Kornaropoulos [30] presented shortest path samplers for estimating betweenness centrality of all vertices or the k vertices that have the highest betweenness scores in
a graph. They determined the number of samples needed to approximate the betweenness
with the desired accuracy and conﬁdence by means of the VC-dimension theory [33]. Recently, Riondato and Upfal [30] introduced algorithms for estimating betweenness scores of
all vertices in a graph. They also discussed a variant of the algorithm that ﬁnds the top-k
vertices. They used Rademacher average [32] to determine the number of required samples.
Finally, Borassi and Natale [7] presented the KADABRA algorithm, which uses balanced
bidirectional BFS (bb-BFS) to sample shortest paths. In bb-BFS, a BFS is performed from
each of the two endpoints s and t, in such a way that they are likely to explore about the
same number of edges.

—

-:6

Estimating Betweenness Centrality

3.3

Dynamic graphs

Lee et. al. [24] proposed an algorithm to eﬃciently update betweenness centralities of
vertices when the graph obtains a new edge. They reduced the search space by ﬁnding a
candidate set of vertices whose betweenness centralities can be updated. Bergamini et. al.
[6] presented approximate algorithms that update betweenness scores of all vertices when
an edge is inserted or the weight of an edge decreases. They used the algorithm of [30] as
the building block. Hayashi et. al. [20] proposed a fully dynamic algorithm for estimating
betweenness centrality of all vertices in a large dynamic network. Their algorithm is based
on two data structures: hypergraph sketch that keeps track of SPDs, and two-ball index that
helps to identify the parts of hypergraph sketches that require updates.

4

MCMC Algorithms for estimating betweenness centrality

In this section, we present our MCMC sampler for estimating betweenness score of a single
vertex; and our joint-space MCMC sampler for estimating relative betweenness scores of
vertices in a given set.

4.1

Betweenness centrality as a probability distribution

Chehreghani [13] presented a randomized algorithm that admits a probability mass function
as an input parameter. Then, he proposed an optimal sampling technique that computes
betweenness score of a vertex r ∈ V (G) with error 0. In optimal sampling, each vertex v is
chosen with probability
Pr [v] = P

δv•(r)
v ′ ∈V (G) δv ′ •(r)

(5)

In other words, for estimating betweenness score of vertex r, each source vertex v ∈ V (G)
whose dependency score on r is greater than 0, is chosen with probability P [v] deﬁned in
Equation 5.
In the current paper, for r ∈ V (G) we want to estimate BC(r) and also for all pairs of
BC(ri )
. For this purpose, we follow a source
vertices ri , rj in a set R ⊂ V (G), the ratios BC(r
j)
vertex sampling procedure where for each vertex r, we consider Pr [·] deﬁned in Equation 5 as
the target probability distribution used to sample vertices v ∈ V (G). It is, however, compuP
tationally expensive to calculate the normalization constant v′ ∈V (G) δv′ •(r) in Equation 5,
as it gives the betweenness score of r. However, for two vertices v1 , v2 ∈ V (G), it might
δv1 • (r)
1]
be feasible to compute the ratio PPrr [v
[v2 ] = δv2 • (r) , as it can be done in O(|E(G)|) time for
unweighted graphs and in O(|E(G)| + |V (G)| log |V (G)|) time for weighted graphs with positive weights. This motivates us to propose Metropolis-Hastings sampling algorithms that
for a vertex r, sample each vertex v ∈ V (G) with the probability distribution Pr [v] deﬁned
in Equation 5.

4.2

A single-space MCMC sampler

In this section, we propose a MCMC sampler, deﬁned on the space V (G), to estimate
betweenness centrality of a single vertex r. Our MCMC sampler consists of the following
steps:
First, we choose a vertex v0 ∈ V (G), as the initial state, uniformly at random.
Then, at each iteration t, 1 ≤ t ≤ T :

M. H. Chehreghani et. al.

-:7

Let v(t) be the current state of the chain.
We choose vertex v′ (t) ∈ V (G), uniformly at random.
With probability


δv′ (t)• (r)
min 1,
δv(t)• (r)

(6)

we move from state v(t) to the state v′ (t).
The sampler is an iterative procedure where at each iteration t, one transition may occur
in the Markov chain. Let M be the multi-set (i.e., the set where repeated members are
allowed) of samples (states) accepted by our sampler. In the end of sampling, betweenness
score of r is estimated as
....
BC(r) =

X
1
(T + 1)(|V (G)| − 1)

X

v∈M u∈V (G)\{v}

σvu (r)
.
σvu

(7)

This estimation does....
not give an unbiased estimation of BC(r), however as we discuss
below, by increasing T , BC(r) can be arbitrarily close to BC(r). In the rest of this section,
we show that our MCMC sampler provides an (ǫ, δ)-approximation of BC(r), where ǫ ∈ R+
and δ ∈ (0, 1). Our proof is based on a theorem presented in [23] for the analysis of MCMC
samples and a theorem presented in [26] about the uniformly ergodicity of Independence
Metropolis-Hastings algorithms. We ﬁrst present these two theorems.
1. Suppose that we have a uniformly Ergodic MCMC with the proposal density q, which is
deﬁned on the space S and satisﬁes the following condition: there exist a constant λ > 0
and a probability measure ϕ such that:
q(· | x) ≥ λ × ϕ(·), for every x ∈ S.

(8)

Let f : S → R be some (Borel measurable) function deﬁned from S to R, and θ be
P
1
x∈S f (x). We deﬁne:
|S|
k f ksp = sup f (x) − inf f (x).
x∈S

x∈S

Pn
Now, suppose that we draw samples {x1 , x2 , . . . , xn } from the MCMC. Let θ̂n be n1 i=1 f (xi ).
The authors of [23] presented the following extension of Hoeﬀding’s inequality for these
MCMC samples:
(

2 )
h
i
2λ
3
n−1
,
(9)
ǫ−
P |θ̂n − θ| > ǫ ≤ 2 exp −
2
k f ksp
n−1
where ǫ ∈ R+ .
2. The authors of [26] showed that an Independence Metropolis-Hastings algorithm with
the stationary probability distribution P [·] and proposal distribution g(·) is uniformly
ergodic if there exists a constant β such that
g(·) ≥ β × P [·] .

(10)

In this case, λ and ϕ(·) in Inequation 8 will be β and P [·], respectively (and of course
q(· | x) will be g(·)).

—

-:8

Estimating Betweenness Centrality

.... Now, for a vertex r ∈ V (G), we use Inequalities 8, 9 and 10 to derive an error bound for
BC(r).
◮ Theorem 1. Let δ(r) be the average of dependency scores of vertices in V (G) on r, i.e.,
P
v∈V (G) δv• (r)
.
δ(r) =
|(V (G)|
Suppose that there exists some value µ(r) such that for each vertex v ∈ V (G), the following
holds:
δv• (r) ≤ µ(r) × δ(r).

(11)

Then, for a given ǫ ∈ R+ , by our MCMC sampler and starting from any arbitrary initial
state, we have
(

2 )
h ....
i
2ǫ
3
T
.
(12)
−
P |BC(r) − BC(r)| > ǫ ≤ 2 exp −
2 µ(r) T
Proof. Our MCMC sampler is an Independence Metropolis Hastings MCMC whose proposal
1
density is |V (G)|
. Inequation 11 yields that
δv• (r)
δ(r)

|V (G)| · δv• (r)
≤ µ(r),
=P
v∈V (G) δv• (r)

which yields

1
1
δv• (r)
≥
×P
.
|V (G)|
µ(r)
v∈V (G) δv• (r)

(13)

1
,
Hence, our MCMC sampler satisﬁes Inequation 10, where the proposal density is |V (G)|
1
P [·] is Pr [v] deﬁned in Equation 5 and β is µ(r) . Now, if we apply Inequation 9 with:
P
σvu (r)
1
n = T + 1, S = V (G), x a vertex v in V (G) and f (v) = |V (G)|−1
u∈V (G)\{v} σvu , we
....
P
P
1
1
get: k f ksp = 1, θ = |V (G)|
v∈V (G) f (v) = BC(r), θ̂n = T +1
v∈M f (v) = BC(r), and
1
λ = µ(r)
. Putting these values into Inequation 9, we get Inequation 12.
◭

Note that since Inequation 9 holds for any arbitrary initial distribution, Inequation 12
does not depend on the initial state. Furthermore, since in Inequation 9 it is not required
to discard an initial part of the chain, called burn-in, Inequation 12 holds without need for
burn-in. T is usually large enough so that we can approximate T3 by 0. Hence, Inequation 12
yields that for given values ǫ ∈ R+ and δ ∈ (0, 1), if T is chosen such that
2

µ(r)
2
ln
(14)
2
2ǫ
δ
then, our MCMC sampler can estimate the betweenness score of r within an additive error
ǫ with probability δ.
Similar to the error bounds presented in e.g., [30], [31] and [7], worst case time complexity of processing each sample in our algorithm is O(|E(G)|) for unweighted graphs (and
O(|V (G)| log |V (G)| + |E(G)|) for weighted graphs with positive weights). The number of
samples required by our algorithm to estimate betweenness score of vertex r depends on the
parameter µ(r). The value of µ(r) depends on the position of r in the graph. In the rest
of this section, we show that in several cases (where r is an important vertex in the graph),
µ(r) is a constant and as a result, our MCMC sampler can give an (ǫ, δ)-approximation of
betweenness score of r using only a constant number of samples.
T ≥

M. H. Chehreghani et. al.

-:9

◮ Theorem 2. Let G be a graph, r ∈ V (G) and C = {C1 , . . . , Cl } be the set G \ r. For an
i ∈ [1..l], let Vi refer to the sum of the number of vertices of the graphs in the set C \ Ci . If
for all i ∈ [1..l] we have: Vi = Θ(|V (G)|), then µ(r) is a constant.
Proof. Let m be a vertex in V (G) \ {r} such that for each vertex v ∈ V (G) \ {r}, the
following holds: δm• (r) ≥ δv• (r). In order to prove that µ(r) is a constant, we need to
prove that δm• (r) is a constant. Without loss of generality, assume that m belongs to C1 .
δ(r)
On the one hand, all shortest paths between m and all vertices in C2 , . . . , Cl pass through
r and none of the shortest paths between m and any vertex in C1 pass through r. Hence,
dependency score of m on r is |V (C2 )| + . . . + |V (Cl )|. On the other hand, all shortest paths
between v1 ∈ V (Ci ) and v2 ∈ V (Cj ) so that i 6= j pass through r and none of the shortest
paths between
v3 ∈ V (Ci ) and v4 ∈ V (Cj ) so that i = j pass through r. Hence, we have:
Pl 
P
δ(r) = i=1 |V (Ci )| · j∈{1,...,l}\{i} |V (Cj )| . As a result:
δm• (r)

= Pl

|V (G)| · V1

(|V (Ci )| · Vi )
Pl
V1 · i=1 V (Ci )
≤ 1 + Pl
.
i=1 (V (Ci ) · Vi )

δ(r)

i=1

(15)

Since for all i ∈ [1..l], Vi = Θ(|V (G)|), therefore for any j ∈ [2..l] we have: Vj = Kj · V1 ,
where Kj is a constant. Let K be the minimum of such constants. Inequality 15 yields
δm• (r)
δ(r)
Therefore,

≤1+
δm• (r)
δ(r)

V1 ·

Pl

K · V1

i=1

Pl

V (Ci )

i=1 V (Ci )

= 1+

1
.
K

is a constant.

(16)
◭

Theorem 2 proposes the general conditions under which µ(r) is a constant. In several
cases (where r is an important vertex of the graph), Theorem 2 holds and as a result, µ(r)
is a constant. A simple example is where r a balanced vertex separator of G. Vertex x is a
vertex separator for G, if there exist vertices u and v that belong to distinct components of
G \ x, or if G \ x contains less than two vertices. Vertex separator x is balanced, if at least
two components in G \ x contains Θ(|V (G)|) vertices1 .

4.3

A joint-space MCMC sampler

In this section, we present a MCMC sampler to estimate the ratios of betweenness scores of
the vertices in a set R ⊂ V (G). Each state of this sampler is a pair (r, v), where r ∈ R and
v ∈ V (G). Since this sampler is deﬁned on the joint space R and V (G), we refer to it as
joint-space MCMC sampler. Given a state s of the chain, we denote by s.r the ﬁrst element
of s, which is a vertex in R; and by s.v the second element of s, which is a vertex in V (G).
Our joint-space MCMC sampler consists of the following steps:
First, we choose a pair hr0 , v0 i, as the initial state, where r0 and v0 are chosen uniformly
at random from R and V (G), respectively.
Then, at each iteration t, 1 ≤ t ≤ T :
Let s(t) be the current state of the chain.
1

Note that in order to cover more cases, balanced vertex separator defined here is more general than its
tradition definitional in graph theory.

—

-:10

Estimating Betweenness Centrality

We choose elements r(t) ∈ R and v(t) ∈ V (G), uniformly at random.
With probability


δv(t)• (r(t))
min 1,
δs(t).v• (s(t).r)

(17)

we move from state s(t) to the state hr(t), v(t)i.
Techniques similar to our joint-space MCMC sampler have been used in statistical physics
to estimate free energy diﬀerences [5]. Our joint-space MCMC sampler is a MetropolisHastings algorithm that possess a unique stationary distribution [27, 18] deﬁned as follows:
P [r, v] = P

r ′ ∈R

δ (r)
P v•

v ′ ∈V (G) δv ′ • (r

′)

(18)

.

All samples that have a speciﬁc value r for their r component form an Independence
Metropolis-Hastings chain that possess the stationary distribution deﬁned in Equation 5.
Samples drawn by our MCMC and joint-space MCMC samplers are non-iid. In Theorem 3,
we show how our joint-space MCMC sampler can be used to estimate the ratios of betweenness scores of the vertices in R.
◮ Theorem 3. In our joint-space MCMC sampler, for any two vertices ri , rj ∈ R, we have:
h
n
oi
v• (ri )
EPrj [v] min 1, δδv•
(rj )
BC(ri )
oi
h
n
(19)
=
δ (r )
BC(rj )
E
min 1, v• j
Pri [v]

δv• (ri )

where EPri [v] (respectively EPrj [v] ) denotes the expected value with respect to Pri [v] (respectively Prj [v]).
Proof. In our joint-space MCMC sampler, consider all the transitions that keep the v element, but change the r element. According to the detailed balance property of MetropolisHastings algorithms, for any v ∈ V (G), we have
P [ri , v] × T R(hrj , vi | hri , vi) = P [rj , v] × T R(hri , vi | hrj , vi)

(20)

Using Equation 18, we get




δv• (ri )
δv• (rj )
= δv• (rj ) × min 1,
δv• (ri ) × min 1,
δv• (ri )
δv• (rj )

(21)

Equation 21 holds for all v ∈ V (G). If we sum both sides of Equation 21 with respect to
v ∈ V (G) and then, divide/multiply by BC(ri ) and BC(rj ), we get



BC(ri )









X  δv• (ri )
X  δv• (rj )
δv• (ri ) 
δv• (rj ) 


 = BC(rj )

×
min
1,
×
min
1,
 BC(ri )
 BC(rj )
δv• (ri ) 
δv• (rj ) 


v∈V (G) | {z }
v∈V (G) | {z }
Pri [v]

which yields Equation 19.

Prj [v]

◭

Let ri , rj ∈ R, and M (i) and M (j) be the multi-sets of samples taken by our joint-space
MCMC sampler whose r components are respectively ri and rj . Equation 19 suggests to

M. H. Chehreghani et. al.

estimate
1
|M(j)|
1
|M(i)|

BC(ri )
BC(rj )

-:11

as the ratio:

n
o
δs.v (ri )
min
1,
s∈M(j)
δs.v (rj )
o.
n
P
δs.v (rj )
× s∈M(i) min 1, δs.v (ri )
×

P

(22)

We use Equation 22 to estimate the ratio of the betweenness scores of ri and rj . We then
deﬁne the relative betweenness score of ri respect to rj , denoted by BCrj (ri ), as follows:
BCrj (ri ) =



X
δv• (ri )
1
min 1,
.
|V (G)|
δv• (rj )

(23)

v∈V (G)

When we want to compare betweenness centrality of vertices ri and rj , using relative betweenness score makes more sense than using the ratio of betweenness scores. In relative betweenness centrality, for each v ∈ V (G), the ratio of the dependency scores of v on ri and rj is
computed and in the end, all the ratios are summed. Hence, for each vertex v independent
from the others, the eﬀects of ri and rj on the shortest paths starting from v are examined2 .
In the following, we show that the numerator of Equation 22, i.e.,


X
δs.v (ri )
1
min 1,
,
|M (j)|
δs.v (rj )
s∈M(j)

....
can accurately estimate BCrj (ri ). We refer to the estimated value of BCrj (ri ) as BC rj (ri ).
Our proof is similar to the analysis we gave in Section 4.2 and is based on the theorems
presented in [23] and [26]. For a pair of vertices
ri , rj ∈ R, in Theorem 4, we use Inequalities 8,
....
9 and 10 to derive an error bound for BC rj (ri ).
◮ Theorem 4. Let ri , rj ∈ R, M (j) be the multi-set of samples whose r components are rj ,
and δ(rj ) be the average of dependency scores of vertices in V (G) on rj , i.e.,
P
v∈V (G) δv• (rj )
.
δ(rj ) =
|(V (G)|
Suppose that there exists some value µ(rj ) such that for each vertex v ∈ V (G), the following
holds:
δv• (rj ) ≤ µ(rj ) × δ(rj ).

(24)

Then, for a given ǫ ∈ R+ , by our joint-space MCMC sampler and starting from any arbitrary
initial state, we have
(

2 )
i
h ....
2ǫ
3
|M (j)| − 1
.
(25)
−
P |BC rj (ri ) − BCrj (ri )| > ǫ ≤ 2 exp −
2
µ(ri ) |M (j)| − 1
Proof. As discussed in [5], our joint-space MCMC sampler can be implemented as |R|
parallel MCMC samplers, each deﬁned on the state space V (G). In this way, samples

2

Note that the notion of relative betweenness score can ben further extended
and presented as follows:
o
BCrj (ri ) =

1
|V (G)|·(|V (G)|−1)

P

v∈V (G)

P

t∈V (G)\{v}

min 1,

δvt (ri )
δvt (rj )

.

—

-:12

Estimating Betweenness Centrality

whose r components are rj (i.e., samples that are in M (j)) are drawn from an Independence
1
Metropolis Hastings MCMC whose proposal density is |V (G)|
. Inequation 11 yields that
|V (G)| · δv• (rj )
≤ µ(rj ),
=P
δ(rj )
v∈V (G) δv• (rj )

δv• (rj )

which yields

1
1
δv• (rj )
.
≥
×P
|V (G)|
µ(rj )
v∈V (G) δv• (rj )

(26)

Hence, the MCMC formed by the samples in M (j) satisﬁes Inequation 10, where the
1
proposal density is |V (G)|
, P [·] is Prj [v] deﬁned in Equation 5 and β is µ(r1 j ) . Now, if
we apply Inequation 9 on thenMCMC formed
by the samples in M (j) with: n = |M (j)|,
o
P
δv• (ri )
1
S = V (G), and f (v) = min 1, δv• (rj ) , we get: θ = |V (G)|
v∈V (G) f (v) = BCrj (ri ),
....
P
1
1
θ̂n = |M(j)| s∈M(j) f (s.v) = BC rj (ri ), k f ksp = 1, and λ = µ(rj ) . Putting these values
◭
into Inequation 9, we get Inequation 25.
Similar to Inequation 12, Inequation 25 does not depend on the initial state and it holds
without need for burn-in. Furthermore, for given values ǫ ∈ R+ and δ ∈ (0, 1), if we have
2

|M (j)| ≥

µ(rj )
2
ln
2
2ǫ
δ

(27)

then, our joint-space MCMC sampler can estimate relative betweenness score of ri respect
to rj within an additive error ǫ with probability δ. Finally, similar to our discussion in
Section 4.2, in several cases µ(rj ) is a constant and as a result, our joint-space MCMC
sampler can give an (ǫ, δ)-approximation of relative betweenness score of ri respect to rj
using only a constant number of samples.

5

Conclusion and future work

In this paper, ﬁrst given a network G and a vertex r ∈ V (G), we proposed a MetropolisHastings MCMC algorithm that samples from the space V (G) and estimates betweenness
score of r. We showed that our MCMC sampler provides an (ǫ, δ)-approximation, where
the number of required samples depends on the position of r in G and in several cases, it
is a constant. Then, given a network G and a set R ⊂ V (G), we presented a MetropolisHastings MCMC sampler that samples from the joint space R and V (G) and estimates
relative betweenness scores of the vertices in R. We showed that for any pair ri , rj ∈ R,
the ratio of the expected values of the estimated relative betweenness scores of ri and rj
respect to each other is equal to the ratio of their betweenness scores. We also showed that
our joint-space MCMC sampler provides an (ǫ, δ)-approximation of the relative betweenness
score of ri respect to rj , where the number of required samples depends on the position of
rj in G and in many cases, it is a constant.
The sampling techniques presented in this paper have similarity to the techniques used in
statistical physics to estimate e.g., energy diﬀerences. Our current paper takes the ﬁrst step
in bridging these two domains. This step can be further extended by proposing algorithms
similar to our work that estimate other network indices. As a result, a novel family of
techniques might be introduced into the ﬁeld of network analysis, that are used to estimate
diﬀerent indices.

M. H. Chehreghani et. al.

-:13

References
1

2

3
4
5
6

7

8
9
10
11

12

13

14

15
16

Manas Agarwal, Rishi Ranjan Singh, Shubham Chaudhary, and Sudarshan Iyengar.
Betweenness Ordering Problem : An Eﬃcient Non-Uniform Sampling Technique for Large
Graphs. CoRR, abs/1409.6470, 2014. URL: http://arxiv.org/abs/1409.6470.
D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality.
In Proceedings of 5th International Conference on Algorithms and Models for the WebGraph (WAW), pages 124–137, 2007.
A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509–
512, 1999.
M. Barthelemy. Betweenness centrality in large complex networks. The Europ. Phys. J. B
- Condensed Matter, 38(2):163–168, 2004.
C. H. Bennett. Eﬃcient estimation of free energy diﬀerences from Monte-Carlo data. J.
Comput. Phys., 22:245, 1976.
Elisabetta Bergamini, Henning Meyerhenke, and Christian Staudt. Approximating
betweenness centrality in large evolving networks.
In Ulrik Brandes and David
Eppstein, editors, Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015,
pages 133–146. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973754.12,
doi:10.1137/1.9781611973754.12.
Michele Borassi and Emanuele Natale. KADABRA is an adaptive algorithm for betweenness via random approximation. In Piotr Sankowski and Christos D. Zaroliagis, editors,
24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2016.
URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.20,
doi:10.4230/LIPIcs.ESA.2016.20.
U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177, 2001.
U. Brandes and C. Pich. Centrality estimation in large networks. Intl. Journal of Bifurcation
and Chaos, 17(7):303–318, 2007.
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of markov chain
monte carlo, 2011.
Ümit V. Çatalyürek, Kamer Kaya, Ahmet Erdem Sariyüce, and Erik Saule. Shattering and compressing networks for betweenness centrality. In Proceedings of the 13th
SIAM International Conference on Data Mining, May 2-4, 2013. Austin, Texas, USA.,
pages 686–694. SIAM, 2013. URL: http://dx.doi.org/10.1137/1.9781611972832.76,
doi:10.1137/1.9781611972832.76.
Mostafa Haghir Chehreghani. Eﬀective co-betweenness centrality computation. In Seventh
ACM International Conference on Web Search and Data Mining (WSDM), pages 423–432,
2014.
Mostafa Haghir Chehreghani.
An eﬃcient algorithm for approximate betweenness centrality computation.
Comput. J., 57(9):1371–1382, 2014.
URL:
http://dx.doi.org/10.1093/comjnl/bxu003, doi:10.1093/comjnl/bxu003.
Elizabeth M. Daly and Mads Haahr. Social network analysis for information ﬂow in disconnected delay-tolerant manets. IEEE Trans. Mob. Comput., 8(5):606–621, 2009. URL:
http://dx.doi.org/10.1109/TMC.2008.161, doi:10.1109/TMC.2008.161.
M. Everett and S. Borgatti. The centrality of groups and classes. Journal of Mathematical
Sociology, 23(3):181–201, 1999.
L. C. Freeman. A set of measures of centrality based upon betweenness, sociometry. Social
Networks, 40:35–41, 1977.

—

-:14

Estimating Betweenness Centrality

17

18
19
20

21
22
23

24

25

26

27
28
29
30

31

32
33
34

R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments
(ALENEX), pages 90–100, 2008.
W. R. Gilks, S. Richardson, and D. J. Spiegelhalter. Markov Chain Monte Carlo in Practice.
Chapman and Hall, London, 1996 (ISBN: 0-412-05551-1).
M. Girvan and M. E. J. Newman. Community structure in social and biological networks.
Natl. Acad. Sci. USA, 99:7821–7826, 2002.
Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. Fully dynamic betweenness centrality maintenance on massive networks. Proceedings of the VLDB Endowment (PVLDB),
9(2):48–59, 2015. URL: http://www.vldb.org/pvldb/vol9/p48-hayashi.pdf.
P. Holme. Congestion and centrality in traﬃc ﬂow on complex networks. Adv. Complex.
Syst., 6(2):163–176, 2003.
E. D. Kolaczyk, D. B. Chua, and M. Barthelemy. Group-betweenness and co-betweenness:
Inter-related notions of coalition centrality. Social Networks, 31(3):190–203, 2009.
Krzysztof Łatuszyński, Błażej Miasojedow, and Wojciech Niemiro.
Nonasymptotic Bounds on the Mean Square Error for MCMC Estimates via Renewal Techniques, pages 539–555.
Springer Berlin Heidelberg, Berlin, Heidelberg,
2012.
URL:
http://dx.doi.org/10.1007/978-3-642-27440-4_31,
doi:10.1007/978-3-642-27440-4_31.
M. J. Lee, J. Lee, J. Y. Park, R. H. Choi, and C.-W. Chung. Qube: A quick algorithm for
updating betweenness centrality. In Proceedings of the 21st World Wide Web Conference
(WWW), pages 351–360, 2012.
K. L. Mengersen and R. L. Tweedie.
Rates of convergence of the hastings and metropolis algorithms.
Ann. Statist., 24(1):101–121, 02 1996.
URL:
http://dx.doi.org/10.1214/aos/1033066201, doi:10.1214/aos/1033066201.
K. L. Mengersen and R. L. Tweedie. Rates of convergence of the Hastings and Metropolis algorithms. The Annals of Statistics, 24(1):101–121, February 1996. URL:
http://dx.doi.org/10.1214/aos/1033066201, doi:10.1214/aos/1033066201.
S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer-Verlag,
London, 1993.
R. Puzis, Y. Elovici, and S. Dolev. Fast algorithm for successive computation of group
betweenness centrality. Phys. Rev. E, 76(5):056709, 2007.
R. Puzis, Y. Elovici, and S. Dolev. Finding the most prominent group in complex networks.
AI Commun., 20(4):287–296, 2007.
Matteo Riondato and Evgenios M. Kornaropoulos. Fast approximation of betweenness
centrality through sampling. Data Mining and Knowledge Discovery, 30(2):438–475, 2016.
URL: http://dx.doi.org/10.1007/s10618-015-0423-0.
Matteo Riondato and Eli Upfal. ABRA: Approximating betweenness centrality in static
and dynamic graphs with rademacher averages. In Proceedings of the 22nd ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining (KDD), page 10 pages,
2016.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory
to Algorithms. Cambridge University Press, New York, NY, USA, 2014.
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies
of events to their probabilities. Theory of Probab. and its Applications, 16(2):264–280, 1971.
Y. Wang, Z. Di, and Y. Fan. Identifying and characterizing nodes important to community
structure using the spectrum of the graph. PLoS ONE, 6(11):e27418, 2011.

