KADABRA is an ADaptive Algorithm for Betweenness
via Random Approximation∗
Michele Borassi1 and Emanuele Natale2
1

arXiv:1604.08553v4 [cs.DS] 12 Aug 2016

IMT Insitute for Advanced Studies, 55100 Lucca, Italy,
michele.borassi@imtlucca.it
2
Sapienza University of Rome, 00185 Roma, Italy, natale@di.uniroma1.it
15th August 2016

Abstract
We present KADABRA, a new algorithm to approximate betweenness centrality in
directed and undirected graphs, which significantly outperforms all previous approaches
on real-world complex networks. The efficiency of the new algorithm relies on two new
theoretical contributions, of independent interest.
The first contribution focuses on sampling shortest paths, a subroutine used by
most algorithms that approximate betweenness centrality. We show that, on realistic
1
random graph models, we can perform this task in time |E| 2 +o(1) with high probability,
obtaining a significant speedup with respect to the Θ(|E|) worst-case performance. We
experimentally show that this new technique achieves similar speedups on real-world
complex networks, as well.
The second contribution is a new rigorous application of the adaptive sampling
technique. This approach decreases the total number of shortest paths that need to
be sampled to compute all betweenness centralities with a given absolute error, and
it also handles more general problems, such as computing the k most central nodes.
Furthermore, our analysis is general, and it might be extended to other settings, as
well.

1

Introduction

In this work we focus on estimating the betweenness centrality, which is one of the most
famous measures of centrality for nodes and edges of real-world complex networks [21, 33].
The rigorous definition of betweenness centrality has its roots in sociology, dating back to the
Seventies, when Freeman formalized the informal concept discussed in the previous decades
in different scientific communities [6, 43, 42, 19, 15], although the definition already appeared
in [4]. Since then, this notion has been very successful in network science [48, 34, 25, 33].
A probabilistic way to define the betweenness centrality1 bc(v) of a node v in a graph
G = (V, E) is the following. We choose two nodes s and t, and we go from s to t through a
shortest path π; if the choices of s, t and π are made uniformly at random, the betweenness
centrality of a node v is the probability that we pass through v.
In a seminal paper [16], Brandes showed that it is possible to exactly compute the
betweenness centrality of all the nodes in a graph in time O(mn), where n is the number of
nodes and m is the number of edges. A corresponding lower bound was proved in [13]: if we
∗ This
1 As

work was done while the authors were visiting the Simons Institute for the Theory of Computing.
explained in see Section 2, to simplify notation we consider the normalized betweenness centrality.

1

are able to compute the betweenness centrality of a single node in time O(mn1− ) for some
 > 0, then the Strong Exponential Time Hypothesis [26] is false.
This result further motivates the rich line of research on computing approximations of
betweenness centrality, with the goal of trading precision with efficiency. The main idea
is to define a probability distribution over the set of all paths, by choosing two uniformly
random nodes s, t, and then a uniformly distributed st-path π, so that Pr(v ∈ π) = bc(v).
As a consequence, we can approximate bc(v)
Pτby sampling paths π 1 , . . . , π τ according to
this distribution, and estimating b̃(v) := τ1 i=1 X i (v), where X i (v) = 1 if v ∈ π i (and
v 6= s, t), 0 otherwise.
The tricky part of this approach is to provide probabilistic guarantees on the quality of this
approximation: the goal is to obtain a 1 − δ confidence interval I(v) = [b̃(v) − λL , b̃(v) + λU ]
for bc(v), which means that Pr(∀v ∈ V, bc(v) ∈ I(v)) ≥ 1 − δ. Thus, the research for
approximating betweenness centrality has been focusing on obtaining, as fast as possible,
the smallest possible I.
Our Contribution
In this work, we propose a new and faster algorithm to approximate betweenness centrality in
directed and undirected graphs, named KADABRA. In the standard task of approximating
betweenness centralities with absolute error at most λ, we show that, on average, the new
algorithm is more than 100 times faster than the previous ones, on graphs with approximately
10 000 nodes. Moreover, differently from previous approaches, our algorithm can perform
more general tasks, since it does not need all confidence intervals to be equal. As an example,
we consider the computation of the k most central nodes: all previous approaches compute
all centralities with an error λ, and use this approximation to obtain the ranking. Conversely,
our approach allows us to use small confidence interval only when they are needed, and
allows bigger confidence intervals for nodes whose centrality values are “well separated”.
This way, we can compute for the first time an approximation of the k most central nodes
in networks with millions of nodes and hundreds of millions of edges, like the Wikipedia
citation network and the IMDB actor collaboration network.
Our results rely on two main theoretical contributions, which are interesting in their
own right, since their generality naturally extends to other applications.
Balanced bidirectional breadth-first search. By leveraging on recent advanced
results, we prove that, on many realistic random models of real-world complex networks, it
1
is possible to sample a random path between two nodes s and t in time m 2 +o(1) if the degree
4−β
distribution has finite second moment, or m 2 +o(1) if the degree distribution is power law
with exponent 2 < β < 3. The models considered are the Configuration Model [11], and
all Rank-1 Inhomogeneous Random Graph models [45, Chapter 3], such as the Chung-Lu
model [32], the Norros-Reittu model [35], and the Generalized Random Graph [45, Chapter
3]. Our proof techniques have the merit of adopting a unified approach that simultaneously
works in all models considered. These models well represent metric properties of real-world
networks [14]: indeed, our results are confirmed by practical experiments.
The algorithm used is simply a balanced bidirectional BFS (bb-BFS): we perform a
BFS from each of the two endpoints s and t, in such a way that the two BFSs are likely
to explore about the same number of edges, and we stop as soon as the two BFSs “touch
each other”. Rather surprisingly, this technique was never implemented to approximate
betweenness centrality, and it is rarely used in the experimental algorithm community. Our
theoretical analysis provides a clear explanation of the reason why this technique improves
over the standard BFS: this means that many state-of-the-art algorithm for real-world
complex networks can be improved by the bb-BFS.

2

Adaptive sampling made rigorous. To speed up the estimation of the betweenness
centrality, previous work make use of the technique of adaptive sampling, which consists
in testing during the execution of the algorithm whether some condition on the sample
obtained so far has been met, and terminating the execution of the algorithm as soon as
this happens. However, this technique introduces a subtle stochastic dependence between
the time in which the algorithm terminates and the correctness of the given output, which
previous papers claiming a formal analysis of the technique did not realize (see Section 3 for
details). With an argument based on martingale theory, we provide a general analysis of
such useful technique. Through this result, we do not only improve previous estimators, but
we also make it possible to define more general stopping conditions, that can be decided
“on the fly”: this way, with little modifications, we can adapt our algorithm to perform more
general tasks than previous ones.
To better illustrate the power of our techniques, we focus on the unweighted, static
graphs, and to the centrality of nodes. However, our algorithm can be easily adapted to
compute the centrality of edges, to handle weighted graphs and, since its core part consists
merely in sampling paths, we conjecture that it may be coupled with the existing techniques
in [9] to handle dynamic graphs.
Related Work
Computing Betweenness Centrality. With the recent event of big data, the major
shortcoming of betweenness centrality has been the lack of efficient methods to compute it
[16]. In the worst case, the best exact algorithm to compute the centrality of all the nodes is
due to Brandes [16], and its time complexity is O(mn): the basic idea of the algorithm is to
P
(v)
define the dependency δs (v) = t∈V σst
σst , which can be computed in time O(m), for each
v ∈ V (we denote by σst (v) the number of shortest paths from s to t passing through v, and
by σst the number of st-shortest paths). In [13], it is also shown that Brandes algorithm is
almost optimal on sparse graphs: an algorithm that computes the betweenness centrality
of a single vertex in time O(mn1− ) falsifies widely believed complexity assumptions, such
as the Strong Exponential Time Hypothesis [26], the Orthogonal Vector conjecture [2],
or the Hitting Set conjecture [49]. Corresponding results in the dense, weighted case are
available in [1]: computing the betweenness centrality exactly is as hard as computing
the All Pairs Shortest Path, and computing an approximation with a given relative error
is as hard as computing the diameter. For both these problems, there is no algorithm
with running-time O(n3− ), for any  > 0. This shows that, for dense graphs, having an
additive approximation rather than a multiplicative one is essential for a provably fast
algorithm to exist. These negative results further motivate the already rich line of research
on approaches that overcome this barrier. A first possibility is to use heuristics, that
do not provide analytical guarantees on their performance [41, 23, 46]. Another line of
research has defined variants of betweenness centrality, that might be easier to compute
[17, 36, 20]. Finally, a third line of research has investigated approximation algorithms,
which trade accuracy for speed [27, 18, 25, 29]. Our work follows the latter approach. The
first approximation algorithm proposed in the literature [27] adapts Eppstein and Wang’s
approach for computing closeness centrality [22], using Hoeffding’s inequality and the union
bound technique. This way, it is possible to obtain an estimate of the betweenness centrality
of every node that is correct up to an additive error λ with probability δ, by sampling
2
n
O( D
λ2 log δ ) nodes, where D is the diameter of the graph. In [25], it is shown that this
can lead to an overestimation. Riondato and Kornaropoulos improve this sampling-based
approach by sampling single shortest paths instead of the whole dependency of a node [39],
introducing the use of the VC-dimension. As a result, the number of samples is decreased
to λc2 (blog2 (VD −2)c + 1 + log( 1δ )), where VD is the vertex diameter, that is, the minimum
number of nodes in a shortest path in G (it can be different from D + 1 if the graph is
weighted). This use of the VC-dimension is further developed and generalized in [40]. Finally,

3

many of these results were adapted to handle dynamic networks [9, 40].
Approximating the top-k betweenness centrality set. Let us order the nodes
v1 , ..., vn such that bc(v1 ) ≥ ... ≥ bc(vn ) and define T OP (k) = {(vi , bc(vi )) : i ≤ k}. In [39]
and [40], the authors provide an algorithm that, for any given δ, , with probability 1 − δ
outputs a set T]
OP (k) = {(vi , b̃(vi ))} such that: i) If v ∈ T OP (k) then v ∈ T]
OP (k) and
]
| bc(v) − b̃(v)| ≤  bc(v); ii) If v ∈ T OP (k) but v 6∈ T OP (k) then b̃(v) ≤ (bk − )(1 + )
where bk is the k-th largest betweenness given by a preliminary phase of the algorithm.
Adaptive sampling. In [5, 40], the number of samples required is substantially
reduced using the adaptive sampling technique introduced by Lipton and Naughton in
[31, 30]. Let us clarify that, by adaptive sampling, we mean that the termination of the
sampling process depends on the sample observed so far (in other cases, the same expression
refers to the fact that the distribution of the new samples is a function of the previous ones
[3], while the sample size is fixed in advance). Except for [37], previous approaches tacitly
assume that there is little dependency between the stopping time and the correctness of the
output: indeed, they prove that, for each fixed τ , the probability that the estimate is wrong
at time τ is below δ. However, the stopping time τ is a random variable, and in principle
there might be dependency between the event τ = τ and the event that the estimate is
correct at time τ . As for [37], they consider a specific stopping condition and their proof
technique does not seem to extend to other settings. For a more thorough discussion of this
issue, we defer the reader to Section 3.
Bidirectional BFS. The possibility of speeding up a breadth-first search for the
shortest-path problem by performing, at the same time, a BFS from the final end-point, has
been considered since the Seventies [38]. Unfortunately, because of the lack of theoretical
results dealing with its efficiency, the bidirectional BFS has apparently not been considered
a fundamental heuristic improvement [28]. However, in [39] (and in some public talks by M.
Riondato), the bidirectional BFS was proposed as a possible way to improve the performance
of betweenness centrality approximation algorithms.
Structure of the Paper
In Section 2, we describe our algorithm, and in Section 3 we discuss the main difficulty of
the adaptive sampling, and the reasons why our techniques are not affected. In Section 4, we
define the balanced bidirectional BFS, and we sketch the proof of its efficiency on random
graphs. In Section 5, we show that our algorithm can be adapted to compute the k most
central nodes. In Section 6 we experimentally show the effectiveness of our new algorithm.
Finally, all our proofs are in the appendix.

2

Algorithm Overview

To simplify notation, we always consider the normalized betweenness centrality of a node v,
which is defined by:
X σst (v)
1
bc(v) =
n(n − 1)
σst
s6=v6=t

where σst is the number of shortest paths between s and t, and σst (v) is the number of
shortest paths between s and t that pass through v. Furthermore, to simplify the exposition,
we use bold symbols to denote random variables, and light symbols to denote deterministic
quantities. On the same line of previous works, our algorithm samples random paths
π 1 , . . . , π τ , where π i is chosen by selecting uniformly at random two nodes s, t, and then

4

selecting uniformly at
one of the shortest paths from s to t. Then, it estimates
Prandom
τ
bc(v) hwith ib̃(v) := τ1 i=1 X i (v), where X i (v) = 1 if v ∈ π i , 0 otherwise. By definition of
π i , E b̃(v) = bc(v).

The tricky part is to bound the distance between b̃(v) and its expected value. With a
straightforward application
of Hoeffding’s
(Lemma 5 in the appendix), it is possible

 inequality
−2τ λ2
to prove that Pr b̃(v) − bc(v) ≥ λ ≤ 2e
. A direct application of this inequality
considers a union bound on all possible nodes v, obtaining Pr(∃v ∈ V, |b̃(v) − bc(v)| ≥ λ) ≤
2
2
2ne−2τ λ . This means that the algorithm can safely stop as soon as 2ne−2τ λ ≤ δ, that is,
after τ = 2λ1 2 log( 2n
δ ) steps.
In order to improve this idea, we can
instead of
 start from Lemma
 7 in the appendix,
τ λ2
Hoeffding inequality, obtaining that Pr b̃(v) − bc(v) ≥ λ ≤ 2 exp(− 2(bc(v)+λ/3)
).
If we assume the error λ to be small, this inequality is stronger than the previous one for
all values of bc(v) < 14 (a condition which holds for almost all nodes, in almost all graphs
considered). However, in order to apply this inequality, we have to deal with the fact that
we do not know bc(v) in advance, and hence we do not know when to stop. Intuitively, to
solve this problem, we make a “change of variable”, and we rewrite the previous inequality
as




(v)
(v)
Pr bc(v) ≤ b̃(v) − f ≤ δL
and Pr bc(v) ≥ b̃(v) + g ≤ δU ,
(1)
(v)

(v)

for some functions f = f (b̃(v), δL , τ ), g = g(b̃(v), δU , τ ). Our algorithm fixes at the
(v) (v)
(v)
beginning the values δL , δU for each node v, and, at each step, it tests if f (b̃(v), δL , τ )
(v)
and g(b̃(v), δU , τ ) are small enough. If this condition is satisfied, the algorithm stops. Note
that this approach lets us define very general stopping conditions, that might depend on the
centralities computed until now, on the single nodes, and so on.
(v)

(v)

Remark 1. Instead of fixing the values δL , δU at the beginning, one might want to decide
them during the algorithm, depending on the outcome. However, this is not formally correct,
(v) (v)
because of dependency issues (for example, (1) does not even make sense, if δL , δU are
random). Finding a way to overcome this issue is left as a challenging open problem (more
details are provided in Section 3).
In order to implement this idea, we still need to solve an issue: (1) holds for each fixed
time τ , but the stopping time of our algorithm is a random variable τ , and there might be
dependency between the value of τ and the probability in (1). To this purpose, we use a
stronger inequality (Theorem 8 in the appendix), that holds even if τ is a random variable.
However, to use this inequality, we need to assume that τ < ωfor some deterministic ω: in
our algorithm, we choose ω = λc2 blog2 (VD −2)c + 1 + log 2δ , because, by the results in
[39], after ω samples, the maximum error is at most λ, with probability 1 − 2δ . Furthermore,
also f and g should be modified, since they now depend on the value of ω. The pseudocode
of the algorithm obtained is available in Algorithm 1 (as was done in previous approaches,
we can easily parallelize the while loop in Line 5).
The correctness of the algorithm follows from the following theorem, which is the base
of our adaptive sampling, and which we prove in Appendix C (where we also define the
functions f and g).
Theorem 2. Let b̃(v) be the output of Algorithm 1, and let τ be the number of samples at
the end of the algorithm. Then, with probability 1 − δ, the following conditions hold:
• if τ = ω, |b̃(v) − bc(v)| < λ for all v;
(v)

(v)

• if τ < ω, −f (τ , b̃(v), δL , ω) ≤ bc(v) − b̃(v) ≤ g(τ , b̃(v), δU , ω) for all v.

5

Algorithm 1: our algorithm for approximating betweenness centrality.
Input : a graph G = (V, E)
Output : for each v ∈ V , an approximation
b̃(v) of bc(v) such that

Pr ∀v, |b̃(v) − bc(v)| ≤ λ ≥ 1 − δ

log 2δ ;

c
1 ω ←
blog2 (VD −2)c + 1 +
λ2
(v) (v)
2 (δ
,
δ
L
U ) ← computeDelta();
3
4
5
6
7
8
9

τ ← 0;
foreach v ∈ V do b̃(v) ← 0
while τ < ω and not haveToStop (b̃, δL , δU , ω, τ ) do
π = samplePath();
foreach v ∈ π do b̃(v) ← b̃(v) + 1 τ ← τ + 1;
end
foreach v ∈ V do b̃(v) ← b̃(v)/τ return b̃

Remark 3. This theorem says that, at the beginning of the algorithm, we know that, with
probability 1 − δ, one of the two conditions will hold when the algorithm stops, independently
of the final value of τ . This is essential to avoid the stochastic dependence that we discuss
in Section 3.
In order to apply this theorem, we choose λ such that our goal is reached if all centralities
are known with error at most λ. Then, we choose the function haveToStop in a way that
our goal is reached if the stopping condition is satisfied. This way, our algorithm is correct,
both if τ = ω and if τ < ω. For example, if we want to compute all centralities with
bounded absolute error, we simply choose λ as the bound we want to achieve, and we plug
the stopping condition f, g ≤ λ in the function haveToStop. Instead, if we want to compute
an approximation of the k most central nodes, we need a different definition of f and g,
which is provided in Section 5.
To complete the description of this algorithm, we need to specify the following functions.
(v)

(v)

computeDelta The algorithm works for any choice of the δL , δU s, but a good choice
yields better running times. We propose a heuristic way to choose them in Appendix D.
samplePath In order to sample a path between two random nodes s and t, we use a
balanced bidirectional BFS, which is defined in Appendix E.

3

Adaptive Sampling

In this section, we highlight the main technical difficulty in the formalization of adaptive
sampling, which previous works claiming analogous results did not address. Furthermore,
we sketch the way we overcome this difficulty: our argument is quite general, and it could
be easily adapted to formalize these claims.
As already said, the problem is the stochastic dependence between the time τ in which
the algorithm terminates and the event Aτ = “at time τ , the estimate is within the required
distance from the true value”, since both τ and Aτ are functions of the same random
sample. Since it is typically possible to prove that Pr(¬Aτ ) ≤ δ for every fixed τ , one
may be tempted to argue that also Pr(¬Aτ ) ≤ δ, by applying these inequalities at time
τ . However, this is not correct: indeed, if we have no assumptions on τ , τ could even be
defined as the smallest τ such that Aτ does not hold!
More formally, if we want to link Pr(¬Aτ ) to Pr(¬Aτ ), we have to use the law of total

6

probability, that says that:
Pr(¬Aτ ) =

∞
X

Pr(¬Aτ | τ = τ ) Pr(τ = τ )

(2)

τ =1

= Pr(¬Aτ | τ < τ ) Pr(τ < τ ) + Pr(¬Aτ | τ ≥ τ ) Pr(τ ≥ τ ).

(3)

Then, if we want to bound Pr(¬Aτ ), we need to assume that
Pr(¬Aτ | τ = τ ) ≤ Pr(¬Aτ )

or that

Pr(¬Aτ | τ ≥ τ ) ≤ Pr(¬Aτ ),

(4)

which would allow to bound (2) or (3) from above. The equations in (4) are implicitly
assumed to be true in previous works adopting adaptive sampling techniques. Unfortunately,
because of the stochastic dependence, it is quite difficult to prove such inequalities, even if
some approaches managed to overcome these difficulties [37].
For this reason, our proofs avoid dealing with such relations: in the proof of Theorem 2,
we fix a deterministic time ω, we impose that τ ≤ ω, and we apply the inequalities with
τ = ω. Then, using martingale theory, we convert results that hold at time ω to results that
hold at the stopping time τ (see Appendix C).

4

Balanced Bidirectional BFS

A major improvement of our algorithm, with respect to previous counterparts, is that we
sample shortest paths through a balanced bidirectional BFS, instead of a standard BFS. In
this section, we describe this technique, and we bound its running time on realistic models
of random graphs, with high probability. The idea behind this technique is very simple: if
we need to sample a uniformly random shortest path from s to t, instead of performing a
full BFS from s until we reach t, we perform at the same time a BFS from s and a BFS
from t, until the two BFSs touch each other (if the graph is directed, we perform a “forward”
BFS from s and a “backward” BFS from t).
More formally, assume that we have visited up to level ls from s and to level lt from
t, let Γls (s) be the set of nodesPat distance ls fromPs, and similarly let Γlt (t) be the set of
nodes at distance lt from t. If v∈Γls (s) deg(v) ≤ v∈Γlt (t) deg(v), we process all nodes in
Γls (s), otherwiseP
we process all nodes in Γlt (t) (since the time needed to process level ls is
proportional to v∈Γls (s) deg(v), this choice minimizes the time needed to visit the next
level). Assume that we are processing the node v ∈ Γls (s) (the other case is analogous). For
each neighbor w of v we do the following:
• if w was never visited, we add w to Γls +1 (s);
• if w was already visited in the BFS from s, we do not do anything;
• if w was visited in the BFS from t, we add the edge (v, w) to the set Π of candidate
edges in the shortest path.
After we have processed a level, we stop if Γls (s) or Γlt (t) is empty (in this case, s and t
are not connected), or if Π is not empty. In the latter case, we select an edge from Π, so
that the probability of choosing the edge (v, w) is proportional to σsv σwt (we recall that
σxy is the number of shortest paths from x to y, and it can be computed during the BFS
as in [18]). Then, the path is selected by considering the concatenation of a random path
from s to v, the edge (v, w), and a random path from w to t. These random paths can
be easily chosen by backtracking, as shown in [39] (since the number of paths might be
exponential in the input size, in order to avoid pathological cases, we assume that we can
perform arithmetic operations in O(1) time).

7

4.1

Analysis on Random Graph

In order to show the effectiveness of the balanced bidirectional BFS, we bound its running
time in several models of random graphs: the Configuration Model (CM, [11]), and Rank-1
Inhomogeneous Random Graph models (IRG, [45, Chapter 3]), such as the Chung-Lu model
[32], the Norros-Reittu model [35], and the Generalized Random Graph [45, Chapter 3].
In these models, we fix the number n of nodes, and we give a weight ρu to each node.
In the CM, we create edges by giving ρu half-edges to each node u, and pairing these
half-edges uniformly at random;P
in IRG we connect each pair of nodes (u, v) independently
with probability close to ρu ρv / w∈V ρw . With some technical assumptions discussed in
Appendix E, we prove the following theorem.
Theorem 4. Let G be a graph generated through the aforementioned models. Then, for
each fixed  > 0, and for each pair of nodes s, t, w.h.p., the time needed to compute an
1
st-shortest path through a bidirectional BFS is O(n 2 + ) if the degree distribution λ has finite
4−β
second moment, O(n 2 + ) if λ is a power law distribution with 2 < β < 3.
Sketch of proof. The idea of the proof is that the time needed by a bidirectional BFS is
proportional to the number of visited edges, which is close to the sum of the degrees of the
visited nodes, which are very close to their weights. Hence, we have to analyze the weights
of the P
visited edges: for this reason, if V 0 is a subset of V , we define the volume of V 0 as
ρV 0 = v∈V 0 ρv .
Our visit proceeds by “levels” in the BFS trees from s and t: if we never process a
1
level with total weight at least n 2 + , since the diameter is O(log n), the volume of the set
1
of processed vertices is O(n 2 + log n), and the number of visited edges cannot be much
bigger (for example, this happens if s and t are not connected). Otherwise, assume that,
1
at some point, we process a level ls in the BFS from s with total weight n 2 + : then, the
1
corresponding level lt in the BFS from t has also weight n 2 + (otherwise, we would have
expanded from t, because weights and degrees are strongly correlated). We use the “birthday
paradox”: levels ls + 1 in the BFS from s, and level lt + 1 in the BFS from t are random
1
sets of nodes with size close to n 2 + , and hence there is a node that is common to both,
w.h.p.. This means that the time needed by the bidirectional BFS is proportional to the
volume of all levels in the BFS tree from s, until ls , plus the volume of all levels in the BFS
tree from t, until lt (note that we do not expand levels ls + 1 and lt + 1). All levels except
1
the last have volume at most n 2 + , and there are O(log n) such levels because the diameter
is O(log n): it only remains to estimate the volume of the last level.
By definition of the models, the probability that a node v with weight ρv belongs to the
ρv ρΓls −1 (s)
1
last level is about
≤ ρv n− 2 + : hence, the expected volume of Γls (s) is at most
M
P
P
1
ls −1
(s)) ≤ v∈V ρ2v n− 2 + . Through standard concentration inequalities,
v∈V ρv Pr(v ∈ Γ
we prove that this random variable is concentrated: hence, we only needP
to compute this
expected value. If the degree distribution has finite second moment, then v∈V ρ2v = O(n),
concluding the proof. If the degree distribution is power law with 2 < β < 3, then we have
1
1
to consider separately nodes v such that ρv < n 2 and such that ρv > n 2 . In the first case,
1
1
P
Pn 2
Pn 2
3−β
2
2
2−β
1 ρ
≈ n1+ 2 . In the second case, we prove that
v ≈
d=0 nd λ(d) ≈
d=0 nd
2
ρv <n

1

the volume of the set of nodes with weight bigger than n 2 is at most n
3−β
4−β
4−β
1
volume of Γls (s) is at most n− 2 + n1+ 2 + n 2 ≈ n 2 .

5

4−β
2

. Hence, the total

Computing the k Most Central Nodes

Differently from previous works, our algorithm is more flexible, making it possible to compute
the betweenness centrality of different nodes with different precision. This feature can be
exploited if we only want to rank the nodes: for instance, if v is much more central than
8

all the other nodes, we do not need a very precise estimation on the centrality of v to
say that it is the top node. Following this idea, in this section we adapt our approach to
the approximation of the ranking of the k most central nodes: as far as we know, this is
the first approach which computes the ranking without computing a λ-approximation of
all betweenness centralities, allowing significant speedups. Clearly, we cannot expect our
ranking to be always correct, otherwise the algorithm does not terminate if two of the k
most central nodes have the same centrality. For this reason, the user fixes a parameter λ,
and, for each node v, the algorithm does one of the following:
• it provides the exact position of v in the ranking;
• it guarantees that v is not in the top-k;
• it provides a value b̃(v) such that | bc(v) − b̃(v)| ≤ λ.
In other words, similarly to what is done in [39], the algorithm provides a set of k 0 ≥ k
nodes containing the top-k nodes, and for each pair of nodes v, w in this subset, either we
can rank correctly v and w, or v and w are almost even, that is, | bc(v) − bc(w)| ≤ 2λ. In
order to obtain this result, we plug into Algorithm 1 the aforementioned conditions in the
function haveToStop (see Algorithm 3 in the appendix).
(v)
Then, we have to adapt the function computeDelta to optimize the δL s and the
(v)
δU s to the new stopping condition: in other words, we have to choose the values of
(v)
(v)
λL and λU that should be plugged into the function computeDelta (we recall that the
(v)
heuristic computeDelta chooses the δL s so that we can guarantee as fast as possible that
(v)
(v)
b̃(v) − λL ≤ bc(v) ≤ b̃(v) + λU ). To this purpose, we estimate the betweenness of all nodes
with few samples and we sort all nodes according to these approximate values b̃(v), obtaining
(v )
v1 , . . . , vn . The basic idea is that, for the first k nodes, we set λU i = b̃(vi−1 2)−b̃(vi ) , and
(v )

λL i = b̃(vi )−2b̃(vi+1 ) (the goal is to find confidence intervals that separate the betweenness
of vi from the betweenness of vi+1 and vi−1 ). For nodes that are not in the top-k, we
(v)
(v)
(v )
choose λL = 1 and λU = b̃(vk ) − λL k − b̃(vi ) (the goal is to prove that vi is not in the
(v
)
(v
)
(v )
(v )
top-k). Finally, if b̃(vi ) − b̃(vi+1 ) is small, we simply set λL i = λU i = λL i+1 = λU i+1 = λ,
because we do not know if bc(vi+1 ) > bc(vi ), or viceversa.

6

Experimental Results

In this section, we test the four variations of our algorithm on several real-world networks,
in order to evaluate their performances. The platform for our tests is a server with 1515 GB
RAM and 48 Intel(R) Xeon(R) CPU E7-8857 v2 cores at 3.00GHz, running Debian GNU
Linux 8. The algorithms are implemented in C++, and they are compiled using gcc 5.3.1.
The source code of our algorithm is available at https://sites.google.com/a/imtlucca.
it/borassi/publications.
Comparison with the State of the Art
The first experiment compares the performances of our algorithm KADABRA with the
state of the art. The first competitor is the RK algorithm [39], available in the opensource NetworKit framework [44]. This algorithm uses the same estimator as our algorithm, but the stopping condition
is different: it simply stops after sampling k =

c
1
blog
(VD
−2)c
+
1
+
log
,
and
it
uses a heuristic to upper bound the vertex diameter.
2
2

δ
Following suggestions by the author of the NetworKit implementation, we set to 20 the
number of samples used in the latter heuristic [7].
The second competitor is the ABRA algorithm [40], available at http://matteo.rionda.
to/software/ABRA-radebetw.tbz2. This algorithm samples pairs of nodes (s, t), and it
9

Undirected

Directed

KADABRA
RK
ABRA-Aut
ABRA-1.2

1 min

Network

wiki-Vote

subelj-jdk-jdk

subelj-jung-j-jung-j

subelj-cora-cora

polblogs

soc-Epinions1

p2p-Gnutella31

opsahl-openflights

freeassoc

lasagne-spanishbook

ego-gplus

ego-twitter

cit-HepTh

cfinder-google

as-caida20071105

oregon2 010526

oregon1 010526

hprd pp

Mus musculus

Homo sapiens

email-Enron

HC-BIOGRID

D melanogaster

dip20090126 MAX

C elegans

com-amazon.all

ca-GrQc

ca-HepTh

advogato

1 sec
0.1 sec
as20000102

Time

1 hour

Network

Figure 1: The time needed by the different algorithms, on all the graphs of our dataset.
adds the fraction of st-paths passing from v to the approximation of the betweenness of
v, for each node v. The stopping condition is based on a key result in statistical learning
theory, and there is a scheduler that decides when it should be tested. Following the
suggestions by the authors, we use both the automatic scheduler ABRA-Aut, which uses a
heuristic approach to decide when the stopping condition should be tested, and the geometric
scheduler ABRA-1.2, which tests the stopping condition after (1.2)i k iterations, for each
integer i.
The test is performed on a dataset made by 15 undirected and 15 directed real-world
networks, taken from the datasets SNAP (snap.stanford.edu/), LASAGNE (piluc.dsi.
unifi.it/lasagne), and KONECT (http://konect.uni-koblenz.de/networks/). As in
[40], we have considered all values of λ ∈ {0.03, 0.025, 0.02, 0.015, 0.01, 0.005}, and δ = 0.1.
Allthe algorithms have to
 provide an approximation b̃(v) of bc(v) for each v such that
Pr ∀v, b̃(v) − bc(v) ≤ λ ≥ 1 − δ. In Figure 1, we report the time needed by the different

algorithms on every graph for λ = 0.005 (the behavior with different values of λ is very
similar). More detailed results are reported in Appendix F.
From the figure, we see that KADABRA is much faster than all the other algorithms,
on all graphs: on average, our algorithm is about 100 times faster than RK in undirected
graphs, and about 70 times faster in directed graphs; it is also more than 1 000 times faster
than ABRA. The latter value is due to the fact that the ABRA algorithm has large running
times on few networks: in some cases, it did not even conclude its computation within one
hour. The authors confirmed that this behavior might be due to some bugs in the code,
which seems to affect it only on specific graphs: indeed, in most networks, the performances
of ABRA are better than those of the RK algorithm (but, still, not better than KADABRA).
In order to explain these data, we take a closer look at the improvements obtained
through the bidirectional BFS, by considering the average number of edges mavg that the
algorithm visits in order to sample a shortest path (for all our competitors, mavg = m, since
log(mavg )
they perform a full BFS). In Figure 2, for each graph in our dataset, we plot α = log(m)
(intuitively, this means that the average number of edges visited is mα ).
The figure shows that, apart from few cases, the number of edges visited is close to
1
n 2 , confirming the results in Section 4. This means that, since many of our networks
have approximately 10 000 edges, the bidirectional BFS is about 100 times faster than the
standard BFS. Finally, for each value of λ, we report in Figure 3 the number of samples
needed by all the algorithms, averaged over all the graphs in the dataset.
From the figure, KADABRA needs to sample the smallest amount of shortest paths,
and the average improvement over RK grows when λ tends to 0, from a factor 1.14 (resp.,
10

1

Undirected Networks

Directed Networks

α

0.8
0.6
0.4
0.2

Network

wiki-Vote

subelj-jdk-jdk

subelj-jung-j-jung-j

subelj-cora-cora

polblogs

soc-Epinions1

p2p-Gnutella31

opsahl-openflights

freeassoc

lasagne-spanishbook

ego-gplus

ego-twitter

cit-HepTh

cfinder-google

as-caida20071105

oregon2 010526

oregon1 010526

hprd pp

Mus musculus

Homo sapiens

email-Enron

HC-BIOGRID

D melanogaster

dip20090126 MAX

C elegans

com-amazon.all

ca-GrQc

ca-HepTh

advogato

as20000102

0

Network

Figure 2: The exponent α such that the average number of edges visited during a bidirectional
BFS is nα .
KADABRA
RK
ABRA-Aut
ABRA-1.2

Directed Networks

Undirected Networks

Iterations

106
105
104
0.01

0.02
λ

0.03

0.01

0.02
λ

0.03

Figure 3: The average number of samples needed by the different algorithms.
1.14) if λ = 0.03, to a factor 1.79 (resp., 2.05) if λ = 0.005 in the case of undirected (resp.,
directed) networks. Again, the behavior of ABRA is highly influenced by the behavior on
few networks, and as a consequence the average number of samples is higher. In any case,
also in the graphs where ABRA has good performances, KADABRA still needs a smaller
number of samples.
Computing Top-k Centralities
In the second experiment, we let KADABRA compute the top-k betweenness centralities of
large graphs, which were unfeasible to handle with the previous algorithms.
The first set of graph is a series of temporal snapshots of the IMDB actor collaboration
network, in which two actors are connected if they played together in a movie. The
snapshots are taken every 5 years from 1940 to 2010, including a last snapshot in 2014, with
1 797 446 nodes and 145 760 312 edges. The graphs are extracted from the IMDB website
(http://www.imdb.com), and they do not consider TV-series, awards-shows, documentaries,
game-shows, news, realities and talk-shows, in accordance to what was done in http:
//oracleofbacon.org.
The other graph considered is the Wikipedia citation network, whose nodes are Wikipedia
pages, and which contains an edge from page p1 to page p2 if the text of page p1 contains a
link to page p2 . The graph is extracted from DBPedia 3.7 (http://wiki.dbpedia.org/),
and it consists of 4 229 697 nodes and 102 165 832 edges.
11

Time

45 min
30 min
15 min
0

0.5
1
1.5
Millions of nodes

0

50
100
Millions of edges

150

Figure 4: The total time of computation of KADABRA on increasing snapshots of the
IMDB graph.
We have run our algorithm with λ = 0.0002 and δ = 0.1: as discussed in Section 5, this
means that either two nodes are ranked correctly, or their centrality is known with precision
at most λ. As a consequence, if two nodes are not ranked correctly, the difference between
their real betweenness is at most 2λ. The full results are available in Appendix G.2.
All the graphs were processed in less than one hour, apart from the Wikipedia graph,
which was processed in approximately 1 hour and 38 minutes. In Figure 4, we plot the
running times for the actor graphs: from the figure, it seems that the time needed by
our algorithm scales slightly sublinearly with respect to the size of the graph. This result
respects the results in Section 4, because the degrees in the actor collaboration network
are power law distributed with exponent β ≈ 2.13 (http://konect.uni-koblenz.de/
networks/actor-collaboration). Finally, we observe that the ranking is quite precise:
indeed, most of the times, there are very few nodes in the top-5 with the same ranking, and
the ranking rarely contains significantly more than 10 nodes.

Acknowledgements. The authors would like to thank Matteo Riondato for several
constructive comments on an earlier version of this work. We also thank Elisabetta Bergamini,
Richard Lipton, and Sebastiano Vigna for helpful discussions and Holger Dell for his help
with the experiments.
12

References
[1] Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, apsp and diameter. In Proceedings of the
Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1681–1697.
SIAM, 2015.
[2] Amir Abboud, Virginia V. Williams, and Joshua Wang. Approximation and fixed
parameter subquadratic algorithms for radius and diameter. In Proceedings of the 26th
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377–391, may 2016.
URL: http://arxiv.org/abs/1506.0179, arXiv:1506.0179.
[3] Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive Sampling for kMeans Clustering. In Irit Dinur, Klaus Jansen, Joseph Naor, and Jos Rolim, editors,
Approximation, Randomization, and Combinatorial Optimization. Algorithms and
Techniques, number 5687 in Lecture Notes in Computer Science. Springer Berlin
Heidelberg, 2009.
[4] Jac M Anthonisse. The rush in a directed graph. Stichting Mathematisch Centrum.
Mathematische Besliskunde, BN(9/71):1–10, 1971.
[5] David A. Bader, Shiva Kintali, Kamesh Madduri, and Milena Mihail. Approximating
betweenness centrality. The 5th Workshop on Algorithms and Models for the Web-Graph,
2007.
[6] Alex Bavelas. A mathematical model for group structures. Human organization,
7(3):16–30, 1948.
[7] Elisabetta Bergamini. private communication, 2016.
[8] Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, and Henning
Meyerhenke. Computing top-k closeness centrality faster in unweighted graphs. In
ALENEX, 2016.
[9] Elisabetta Bergamini and Henning Meyerhenke. Fully-dynamic approximation of
betweenness centrality. In ESA, 2015.
[10] Paolo Boldi, Andrea Marino, Massimo Santini, and Sebastiano Vigna. BUbiNG:
Massive crawling for the masses. In Proceedings of the Companion Publication of the
23rd International Conference on World Wide Web, pages 227–228, 2014.
[11] Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of
labelled regular graphs. European Journal of Combinatorics, 1(4):311–316, 1980.
doi:10.1016/S0195-6698(80)80030-8.
[12] Béla Bollobás, Svante Janson, and Oliver Riordan. The phase transition in inhomogeneous random graphs. Random Structures and Algorithms, 31(1):3–122, 2007.
[13] Michele Borassi, Pierluig Crescenzi, and Michel Habib. Into the square - On the
complexity of some quadratic-time solvable problems. In Proceedings of the 16th Italian
Conference on Theoretical Computer Science (ICTCS), pages 1–17, 2015.
[14] Michele Borassi, Pierluigi Crescenzi, and Luca Trevisan. An Axiomatic and an
Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs.
arXiv:1604.01445 [cs], April 2016. arXiv: 1604.01445.
[15] Stephen P. Borgatti and Martin G. Everett. A graph-theoretic perspective on centrality.
Social Networks, 28:466–484, 2006.

13

[16] Ulrik Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163–177, jun 2001. doi:10.1080/0022250X.2001.9990249.
[17] Ulrik Brandes. On variants of shortest-path betweenness centrality and their generic
computation. Social Networks, 30:136–145, 2008.
[18] Ulrik Brandes and Christian Pich. Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos, 17(07):2303–2318, 2007. doi:10.1142/
S0218127407018403.
[19] Bernard S Cohn and McKim Marriott. Networks and centres of integration in indian
civilization. Journal of social Research, 1(1):1–9, 1958.
[20] Shlomi Dolev, Yuval Elovici, and Rami Puzis. Routing betweenness centrality. J. ACM,
57, 2010.
[21] David A. Easley and Jon M. Kleinberg. Networks, crowds, and markets - reasoning
about a highly connected world. In DAGLIB, 2010.
[22] David Eppstein and Joseph Wang. Fast approximation of centrality. J. Graph Algorithms
Appl., 8:39–45, 2001.
[23] Dra Erds, Vatche Ishakian, Azer Bestavros, and Evimaria Terzi. A divide-and-conquer
algorithm for betweenness centrality. In Proceedings of the 2015 SIAM International
Conference on Data Mining, pages 433–441, 2015.
[24] Daniel Fernholz and Vijaya Ramachandran. The diameter of sparse random graphs.
Random Structures and Algorithms, 31(4):482–516, 2007. doi:10.1002/rsa.
[25] Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction
hierarchies: Faster and simpler hierarchical routing in road networks. In Catherine C.
McGeoch, editor, Experimental Algorithms: 7th International Workshop, WEA 2008,
pages 319–333. Springer Berlin Heidelberg, 2008.
[26] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have
Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512–
530, dec 2001. doi:10.1006/jcss.2001.1774.
[27] Riko Jacob, Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, and Dagmar
Tenfelde-Podehl. Algorithms for centrality indices. In DAGSTUHL, 2004.
[28] Hermann Kaindl and Gerhard Kainz. Bidirectional heuristic search reconsidered. J.
Artif. Intell. Res. (JAIR), 7:283–317, 1997.
[29] Yeon-sup Lim, Daniel S Menasché, Bruno Ribeiro, Don Towsley, and Prithwish Basu.
Online estimating the k central nodes of a network. Proceedings of IEEE NSW, pages
118–122, 2011.
[30] Richard J. Lipton and Jeffrey F. Naughton. Query Size Estimation by Adaptive
Sampling. Journal of Computer and System Sciences, 51(1):18–25, August 1995.
doi:10.1006/jcss.1995.1050.
[31] Richard J. Lipton and Naughton, Jeffrey F. Estimating the size of generalized transitive
closures. In Proceedings of the 15th Int. Conf. on Very Large Data Bases, 1989.
[32] Linyuan Lu and Fan R. K. Chung. Complex graphs and networks. Number no. 107
in CBMS regional conference series in mathematics. American Mathematical Society,
2006.
[33] Mark Newman. Networks: an introduction. OUP Oxford, 2010.
14

[34] Mark EJ Newman. Scientific collaboration networks. ii. shortest paths, weighted
networks, and centrality. Physical review E, 64(1):016132, 2001.
[35] Ilkka Norros and Hannu Reittu. On a conditionally Poissonian graph process. Advances
in Applied Probability, 38(1):59–75, 2006.
[36] Jürgen Pfeffer and Kathleen M Carley. k-centralities: local approximations of global
measures based on shortest paths. In Proceedings of the 21st international conference
companion on World Wide Web, pages 1043–1050. ACM, 2012.
[37] Andrea Pietracaprina, Matteo Riondato, Eli Upfal, and Fabio Vandin. Mining TopK Frequent Itemsets Through Progressive Sampling. Data Mining and Knowledge
Discovery, 21(2):310–326, September 2010. doi:10.1007/s10618-010-0185-7.
[38] Ira Pohl. Bi-directional and heuristic search in path problems. PhD thesis, Dept. of
Computer Science, Stanford University., 1969.
[39] Matteo Riondato and Evgenios M Kornaropoulos. Fast approximation of betweenness
centrality through sampling. Data Mining and Knowledge Discovery, 30(2):438–475,
2015.
[40] Matteo Riondato and Eli Upfal. ABRA: Approximating Betweenness Centrality in
Static and Dynamic Graphs with Rademacher Averages. arXiv preprint 1602.05866,
pages 1–27, 2016. arXiv:1602.05866.
[41] Ahmet Erdem Sariyüce, Erik Saule, Kamer Kaya, and Ümit V Çatalyürek. Shattering
and compressing networks for betweenness centrality. In SIAM Data Mining Conference
(SDM). SIAM, 2013.
[42] Marvin E Shaw. Group structure and the behavior of individuals in small groups. The
Journal of psychology, 38(1):139–149, 1954.
[43] Alfonso Shimbel. Structural parameters of communication networks. The bulletin of
mathematical biophysics, 15(4):501–507, 1953.
[44] Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: an
interactive tool suite for high-performance network analysis. arXiv preprint 1403.3005,
pages 1–25, 2014.
[45] Remco van der Hofstad. Random graphs and complex networks. Vol. II. Manuscript,
2014.
[46] Flavio Vella, Giancarlo Carbone, and Massimo Bernaschi. Algorithms and heuristics for scalable betweenness centrality computation on multi-gpu systems. CoRR,
abs/1602.00963, 2016.
[47] Sebastiano Vigna. private communication, 2016.
[48] Stanley Wasserman and Katherine Faust. Social network analysis: Methods and
applications, volume 8. Cambridge university press, 1994.
[49] Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1867–1877, 2014. URL: http://epubs.siam.org/doi/abs/10.1137/
1.9781611973402.135, doi:10.1137/1.9781611973402.135.

15

A

Pseudocode

Algorithm 2: the function computeDelta.
Input

(v)

(v)


exp − c



: a graph G = (V, E), and two values λL , λU

for each v ∈ V

(v) (v)
δL , δ U

1
2
3
4
5
6
7
8

Output : for each v ∈ V , two values
ω
;
α ← 100
 ← 0.0001;
foreach i ∈ [1, α] do
π = samplePath();
foreach v ∈ π do b̃(v) ← b̃(v) + 1
end
foreach v ∈ V do
b̃(v) ← b̃(v)/α;
cL (v) ←

9

cU (v) ←

10

2b̃(v)ω

;

(v)

(λL )2
2b̃(v)ω
(v)

(λU )2

;

11

end

12

Binary search to find C such that

13
14
15

foreach v ∈ V 
do

(v)
δL ← exp − c C(v) +
 L 
(v)
δU ← exp − c C(v) +
U

16
17

P

v∈V

C
L (v)


+ exp − c

C
U (v)



=

δ
2

− δ;

δ
;
2n
δ
;
2n

end
return b;

Algorithm 3: the function haveToStop to compute the top-k nodes.
(v)

1
2
3

(v

4

6
7
8
9
10
11
12
13
14
15
16

B

)

(v )

if b̃(vi−1 ) − f (b̃(vi−1 ), δL i−1 , ω, τ ) < b̃(vi ) + g(b̃(vi ), δU i , ω, τ ) or
(v )
f (b̃(vi ), δL i , ω, τ )

5

(v)

Input : for each node v, the values of b̃(v), δL , δU , and the values of ω and τ
Output : True if the algorithm should stop, False otherwise
Sort nodes in decreasing order of b̃(v), obtaining v1 , . . . , vn ;
for i ∈ [1, . . . , k] do
(v )
(v )
if f (b̃(vi ), δL i , ω, τ ) > λ or g(b̃(vi ), δU i , ω, τ ) > λ then
b̃(vi ) −
return False;
end

< b̃(vi+1 ) +

(v
)
g(b̃(vi+1 ), δU i+1 , ω, τ )

then

end
end
for i ∈ [k + 1, . . . , n] do
(v )
(v )
if f (b̃(vi ), δL i , ω, τ ) > λ or g(b̃(vi ), δU i , ω, τ ) > λ then
(vk )
(v )
if b̃(vk ) − f (b̃(vk ), δL , ω, τ ) < b̃(vi ) + g(b̃(vi ), δU i , ω, τ ) then
return False;
end
end
end
return True;

Concentration Inequalities

Lemma 5 (Hoeffding’s inequality). Let X 1 , . . . , X k be independent random variables such
Pk
that ai < X i < bi , and let X = i=1 X i . Then,
(
)
2λ2
Pr (|X − E[X]| ≥ λ) ≤ exp − Pk
.
2
i=1 (bi − ai )
Pk
Remark 6. If we apply Hoeffding’s inequality with X i = Xvπ , X = kb(v) = i=1 Xvπ ,
2
2
ai = 0, bi = 1, we obtain that Pr (|b(v) − bc(v)| > λ) < 2e−2kλ . Then, if we fix δ = 2e−2kλ ,
16

q
the error is λ = log(2/δ)
, and the minimum k needed to obtain an error λ on the betweenness
2k
1
of a single node is 2λ2 log(2/δ).
Lemma 7 (Chernoff bound ([32])). Let X 1 , . . . , X k be independent random variables such
Pk
that X i ≤ M for each 1 ≤ i ≤ n, and let X = i=1 X i . Then,


λ2
Pr (X ≥ E[X] + λ) ≤ exp − Pn
.
2( i=1 E[X 2i ] + M λ/3)
Theorem 8 (McDiarmid ’98 ([32])). Let X be a martingale associated with a filter F,
satisfying
• Var (Xi | Fi ) ≤ σi for 1 ≤ i ≤ `,
• |Xi − Xi−1 | ≤ M , for 1 ≤ i ≤ `.
Then, we have




λ2

 .
Pr (X − E (X) ≥ λ) ≤ exp − P
`
2 + M λ/3
2
σ
i=1 i

C

Proof of Theorem 2

In our algorithm, we sample τ shortest paths π i , where τ is a random variable such that
τ = τ can be decided by looking at the first τ paths sampled (see Algorithm 1). Furthermore,
thanks to Eq. (3) in [39], we assume that τ ≤ ω for some fixed ω ∈ R+ such that, after ω
steps, Pr(∀v, |b̃(v) − bc(v)| ≤ λ) ≥ 1 − 2δ . When the algorithm stops, our estimate of the
Pτ
betweenness is b̃(v) := τ1 i=1 X i (v), where X i (v) is 1 if v belongs to π i , 0 otherwise.
To estimate the error, we use the following theorem.
Theorem 9. For each node v and for every fixed real numbers δL , δU , it holds



Pr bc(v) ≤ b̃(v) − f b̃(v), δL , ω, τ
≤ δL and



Pr bc(v) ≥ b̃(v) + g b̃(v), δU , ω, τ
≤ δU ,
where
v


u
2
1 1 ω u
ω
1
1
2
b̃(v)ω
 and
− +t
−
f b̃(v), δL , ω, τ = log
+
τ
δL 3 τ
3 τ
log δ1L
v


u
2


1
1 1 ω u
1
ω
2
b̃(v)ω
.
g b̃(v), δU , ω, τ = log
+ +t
+
+
τ
δU 3 τ
3 τ
log δ1U




(5)

(6)

We prove Theorem 9 in Section C.1. In the rest of this section, we show how this theorem
implies Theorem 2. To simplify notation, we often omit the arguments of the function f
and g.
Proof of Theorem 2. Let E 1 be the event (τ = ω ∧ ∃v ∈ V, |b̃(v) − bc(v)| > λ), and let E 2
be the event
Pτ(τ < ω ∧ (∃v ∈ V, −f ≥ bc(v) − b̃(v) ∨ bc(v) − b̃(v) ≥ g)). Let us also denote
b̃τ (v) = τ1 i=1 X i (v) (note that b̃τ (v) = b̃(v)).
By our choice of ω and Eq. (3) in [39],
Pr(E 1 ) ≤ Pr(∃v ∈ V, |b̃ω (v) − bc(v)| > λ) ≤
17

δ
2

where b̃ω (v) is the approximate betweenness of v after ω samples. Furthermore, by Theorem 9,
X
Pr(E 2 ) ≤
Pr(τ < ω ∧ −f ≥ bc(v) − b̃(v)) + Pr(τ < ω ∧ bc(v) − b̃(v) ≤ g)
v∈V

≤

X

(v)

(v)

δL + δU ≤

v∈V

δ
.
2

By a union bound, Pr(E 1 ∨ E 2 ) ≤ Pr(E 1 ) + Pr(E 1 ) ≤ δ, concluding the proof of Theorem 2.

C.1

Proof of Theorem 9

Since this theorem deals with aPsingle node v, let us simply write bc = bc(v), b̃ = b̃(v), X i =
τ
X i (v). Let us consider Y τ = i=1 (X i − bc) (we recall that X i = 1 if v is in the i-th path
sampled, X i = 0 otherwise). Clearly, Y τ is a martingale, and τ is a stopping time for Y τ :
this means that also Z τ = Y min(τ ,τ ) is a martingale.
Let us apply Theorem 8 to the martingales Z and −Z: for each fixed λL , λU > 0 we
have




λ2L
ω
Pr (Z ≥ λL ) = Pr τ b̃ − τ bc ≥ λL ≤ exp −
= δL and (7)
2 (ω bc +λL /3)




λ2U
Pr (−Z ω ≥ λU ) = Pr τ b̃ − τ bc ≤ −λU ≤ exp −
= δU .
(8)
2 (ω bc +λU /3)
We now show how to prove (5) from (7). The way to derive (6) from (8) is analogous.
If we express λL as a function of δL we get


1
2
1
λL
1
2
λL = 2 log
⇐⇒ λ2L − λL log
ω bc +
− 2ω bc log
= 0,
δL
3
3
δL
δL
which implies that
1
1
λL = log
±
3
δL

s 
2
1
1
1
log
+ 2ω bc log .
9
δL
δL

Since (7) holds for any positive value λL , it also holds for the value corresponding to the
positive solution of this equation, that is,
s 
2
1
1
1
1
1
λL = log
+
log
+ 2ω bc log .
3
δL
9
δL
δL
Plugging this value into (7), we obtain


s 
2
1
1
1
1
1
Pr τ b̃ − τ bc ≥ log
+
log
+ 2ω bc log  ≤ δL .
3
δL
9
δL
δL

(9)

log( δ1L ), the event in (9) can be rewritten as


 2
1
1
1
2
1
2
(τ bc) − 2 bc τ 2 b̃ + ω log
− τ log
− log τ b̃ + τ b̃ ≥ 0.
δL
3
δL
3
δL

By assuming b̃ − bc ≥

1
3τ

By solving the previous quadratic equation w.r.t. bc we get

v
!2
u
u
1 ω
1
b̃
ω
1
t
bc ≤ b̃ + log
−
−
+ 2−
−

δL τ 2
3τ
τ
3τ
log δ1L
18

b̃
log δ1L



!2
+

2
b̃ 
,
3τ log δ1L

where we only considered the solution which upper bounds bc, since we assumed b̃ − bc ≥
1
1
3τ log( δL ). After simplifying the terms under the square root in the previous expression, we
get
v


u
2
u
1 ω
1
ω
1
2b̃ω 
bc ≤ b̃ + log
−
−
,
−t
+ 2
δL τ 2
3τ
τ2
3τ
τ log δ1L
which means that




Pr bc ≤ b̃ − f b̃, δL , ω, τ
≤ δL ,

concluding the proof.

D

(v)

(v)

How to Choose δL , δU

(v)

(v)

In Appendix C, we proved that our algorithm works for any choice of the values δL , δU .
In this section, we show how we can heuristically compute such values, in order to obtain
the best performances.
(v)
(v)
For each node v, let λL , λU be the lower and the upper maximum error that we want
to obtain on the betweenness of v: if we simply want all errors to be smaller than λ, we
(v)
(v)
choose λL , λU = λ, but for other purposes different values might be needed. We want to
minimize the time τ such that the approximation of the betweenness at time τ is in the
confidence interval required. In formula, we want to minimize
n
 



o
(v)
(v)
(v)
(v)
min τ ∈ N : ∀v ∈ V, f b̃τ (v), δL , ω, τ ≤ λL ∧ g b̃τ (v), δU , ω, τ ≤ λU
(10)
where b̃τ (v) is the approximation of bc(v) obtained at time τ , and
v


u
2

 1
1 1 ω u
1
ω
2
b̃
ω
τ
 and
− +t
−
+
f τ, b̃τ , δL , ω = log
τ
δL 3
τ
3
τ
log δ1L
v


u
2

 1
u
1 1 ω t 1 ω
2b̃τ ω 
g τ, b̃τ , δU , ω = log
+ +
+
+
.
τ
δU 3
τ
3
τ
log δ1U
(v)

(v)

The goal of this section is to provide deterministic values of δL , δU that minimize
P
(v)
(v)
the value in (10), and such that v∈V δL + δU < 2δ . To obtain our estimate, we replace
b̃τ (v) with an approximation b̃(v), that we compute by sampling α paths, before starting
ω
the algorithm (in our code, α = 100
). Furthermore, we consider a simplified version
of (10): in most cases, λL is much smaller than all other quantitiesq
in play, and since
(v)

2b̃(v)ω
ω is proportional to λ12 , we can safely assume f (τ, b̃(v), δL , ω) ≈
log δ1L and
τ2
q L
(v)
g(τ, b̃(v), δU , ω) ≈ 2b̃(v)ω
log δ1U . Hence, in place of the value in (10), our heuristic tries
τ2
to minimize


v
v
u
u


u 2b̃(v)ω
u
1
2
b̃(v)ω
1
(v)
(v)
t
min τ ∈ N : ∀v ∈ V, t
log
≤
λ
∧
log
≤
λ
.
L
U
(v)
(v)


τ2
τ2
δ
δ
L

U

Solving with respect to τ , we are trying to minimize



v
v
u
u

u 2b̃(v)ω

1 u
1 
u 2b̃(v)ω
u

max 
max 
t  (v) 2 log (v) , t  (v) 2 log (v)  .
v∈V 
δL
δU
λL
λU
19



1
1
which is the same as minimizing maxv∈V max cL (v) log (v)
, cU (v) log (v)
for some conδL
δU
P
(v)
(v)
stants cL (v), cU (v), conditioned on v∈V δL + δU < 2δ . We claim that, among the possible
(v) (v)
choices of δL , δU , the best choice makes all the terms in the maximum equal: otherwise, if
two terms were different, we would be able to slightly increase and decrease the corresponding
values, in order to decrease the maximum. This means that, for some constant C, for each
(v)
(v)
1
1
v, cL (v) log (v)
= cU (v) log (v)
= C, that is, δL = exp(− cLC(v) ), δU = exp(− cUC(v) ). In
δL
δL
P
(v)
(v)
order to find the largest constant C such that v∈V δL + δU ≤ 2δ , we use a binary search
procedure on all possible constants C.
(v)
Finally, if cL (v) = 0 or cU (v) = 0, this procedure chooses δL = 0: to avoid this problem,
P
(v)
(v)
(v)
(v)
δ
we impose v∈V δL + δU ≤ 2δ − δ, and we add 2n
to all the δL s and all the δU s (in our
code, we choose  = 0.001). The pseudocode of the algorithm is available in Algorithm 2.

E

Balanced Bidirectional BFS on Random Graphs

In this appendix, we formally prove that the bidirectional BFS is efficient in several models
of random graphs: the Configuration Model (CM, [11]), and Rank-1 Inhomogeneous Random
Graph models (IRG, [45, Chapter 3]), such as the Chung-Lu model [32], the Norros-Reittu
model [35], and the Generalized Random Graph [45, Chapter 3]. All these models are
defined by fixing the number n of nodes and n weights ρv , and by creating edges at random,
in a way that node v gets degree close to ρv .
More formally, the edges are generated as follows:
• in the CM, each node is associated
to ρv half-edges, or stubs; edges are created by
P
randomly pairing these M = v∈V ρv stubs (we assume the number of stubs to be
even, by adding a stub to a random node if necessary).
ρv ρw
• in IRG,
Pan edge between a node v and a node w exists with probability f ( M ), where
M = v∈V ρv , and the existence of different edges is independent. Different choices
of the function f create different models.

– In general, we assume that f satisfies the following conditions:
∗ f is derivable at least twice in 0;
∗ f is increasing;
∗ f 0 (0) = 1;
– in the Chung-Lu model, f (x) = min(x, 1);
– in the Norros-Reittu model, f (x) = 1 − e−x ;
– in the Generalized Random Graph model, f (x) =

x
1+x .

It remains to define how we choose the weights ρv , when the number of nodes n tends
to infinity. In the line of previous works [35, 24, 45], we consider a sequence of graphs Gi ,
whose number of nodes ni tends to infinity, and whose degree distribution λi satisfy the
following:
1. there is a probability distribution λ such that the λi s tend to λ in distribution;
2. M1 (λi ) tends to M1 (λ) < ∞, where M1 (λ) is the first moment of λ;
3. one of the following two conditions hold:
(a) M2 (λi ) tends to M2 (λ) < ∞, where M2 (λ) is the second moment of λ;
(b) λ is a power law distribution with 2 < β < 3, and there is a global constant C
C
.
such that, for each d, Pr(λi ≥ d) ≤ dβ−1
20

For example, these assumptions are satisfied with probability 1 if we choose the degrees
independently, according to a distribution λ with finite mean [45, Section 6.1,7.2].
Remark 10. Note that an aspect often neglected in previous work when it comes to computing
shortest paths is the fact that the number of shortest paths between a pair of nodes may be
exponential, thus requiring to work with a linear number of bits. While real-world complex
networks are typically sparse with logarithmic diameter, in order to avoid such issue it is
sufficient to assume that addition and comparison require constant time.
Remark 11. These assumptions cover the Erdös-Renyi random graph with constant average
degree, and all power law distributions with β > 2 (because, if β > 3, then M2 (λ) is finite).
Remark 12. Assumption 3b seems less natural than the other assumptions. However, it is
necessary to exclude pathological cases: for example, assume that Gi has n − 2 nodes chosen
according to a power law distribution, and 2 nodes u, v with weight n1− . All assumption
except 3b are satisfied, but the bidirectional BFS is not efficient, because if s is a neighbor of
u with degree 1, and t is a neighbor of v with degree 1, then a bidirectional BFS from s and
t needs to visit all neighbors of u or all neighbors of v, and the time needed is Ω(n1− ).
We say that a random graph has a property π asymptotically almost surely (a.a.s.) if
Pr(π(Gi )) tends to 1 when n tends to infinity. We say that a random graph has a property
i ))
tends to 0 for each k > 0.
π with high probability (w.h.p.) if Pr(π(G
nk
i
Before proving the main theorem, we need two more definitions and a technical assumption.
M2 (λ)
2 (λ)
Definition 13. In the CM, let ρres = M
M1 (λ) − 1. In IRG, let ρres = M1 (λ) (if λ is a power
law distribution with 2 < β < 3, we simply define ρres = +∞).
P
Definition 14. Given a set V 0 ⊆ V , the volume of V 0 is ρV 0 = v∈V 0 ρv . Furthermore, if
V 0 = Γd (s), we abbreviate ρΓd (s) with r l (s).
l+1

(s)
The value ρres is closely related to rrl (s)
: informally, the expected value of this fraction
is ρres . For this reason, if ρres < 1, then the size of neighbors tends to decrease, and
all connected components have O(log n) nodes. Conversely, if ρres > 1, then the size of
neighbors tends to increase, and there is a giant component of size Θ(n) (for a proof of these
facts, see [45, Section 2.3 and Chapter 4]). Our last assumption is that ρres > 1, in order to
ensure the existence of the giant component.
Under these assumptions, we prove Theorem 4, following the sketch in Section 4. We
start by linking the degrees and the weights of nodes.

Lemma 15. For each node v, ρv n− ≤ deg(v) ≤ ρv n w.h.p..
Proof. We use [14, Lemmas 32 and 37]2 : these lemmas imply that, for each  > 0, if ρv > n ,
(1 − )ρv ≤ deg(v) ≤ (1 + )ρv w.h.p.. We have to handle the case where ρv < n : one of
the two inequalities is empty, while for the other inequality we observe that, if we decrease
the weight of v, the degree of v can only decrease. Hence, if ρv < n , deg(v) < (1 + )n ,
and the result follows by changing the value of .
Following the intuitive proof, we have linked the number of visited edges with their
weights. Let us define an abbreviation for the volume of the nodes at distance l from s.
Definition 16. We denote by r l (s) the volume of nodes at distance exactly l from s. In
the CM, we denote by Rl (s) the set of stubs at distance l from s.
1

Now, we need to show that, if r ls (s), r lt (t) > n 2 + , then d(s, t) ≤ ls + lt + 2 w.h.p..
2 This paper uses a further assumption on IRG, but the proofs of Lemmas 32 and 39 do not rely on this
assumption.

21

1

1

1

Lemma 17. Assume that r ls (s) > n 2 + , r lt (t) > n 2 + , and r ls −1 (s), r lt −1 (t) < (1−)n 2 + .
Then, d(s, t) ≤ ls + lt + 2.
Proof. Let us assume that we know the structure of N ls (s) and N lt (t), that is, for each
possible structure S of the subgraph induced by all nodes at distance ls from s and
distance lt from t, let ES be the event that N ls (s) and N lt (t) are exactly
S. If we
P
prove that Pr(d(s, t)P≤ l + l0 + 2|ES ) < , then Pr(r l+1 (s) > r l (s)) = S Pr(r l+1 (s) >
r l (s)|ES ) Pr(ES ) < S  Pr(ES ) = . First of all, if S is such that the two neighborhoods
touch each other, Pr(d(s, t) ≤ l + l0 + 2|ES ) = 0 < . Otherwise, we consider separately the
CM and IRG.
In the CM, conditioned on ES , the stubs that are paired with stubs in Rls (s) are a
random subset of the set of stubs that are not paired in S. This random subset has size at
1+
1
least n 2 + ≥ n 2 (because  is a fixed constant, and n tends to infinity). Since the total
1+
number of stubs is O(n), and since the number of stubs in Rlt (t) is at least n 2 , one of
the stubs in Rlt (t) is paired with a stub in r ls (s) w.h.p., and d(s, t) ≤ ls + lt + 1.
ls
In IRG,
that a Q
node v is not connected to any
P node in Γρw(s) is
Q the probability
ρv ρw
ρw
at most w∈Γls (s) (1 − f ( M )) = w∈Γls (s) (1 − Ω( M )) = exp(− w∈Γls (s) Ω( M )) =
ls

ls

exp(−Ω( r M(s) )) = 1 − Ω( r M(s) ) = 1 − Ω(n− 2 + ). This means that v belongs to Γls +1 (s)
1
1
with probability Ω(n− 2 + ), and similarly it belongs to Γlt +1 (t) with probability Ω(n− 2 + ).
−1+2
Since the two events are independent, the probability that v belongs to both is Ω(n
).
Since, for each node v, the events that v belongs to Γls +1 (s) ∩ Γlt +1 (t) are independent,
by a straightforward application of Hoeffding’s inequality, w.h.p., there is a node v that
belongs to Γls +1 (s) ∩ Γlt +1 (t), and d(s, t) ≤ ls + lt + 2 w.h.p., concluding the proof.
1

1

The next ingredient is used to bound the first integers ls , lt such that r ls (s), r lt (t) > n 2 + .
Theorem 18 (Theorem 5.1 in [24] for the CM, Theorem 14.8 in [12] for IRG (see also
[45, 14])). The diameter of a graph generated through the aforementioned models is O(log n).
The last ingredient of our proof is an upper bound on the size of r ls (s) and r lt (t).
Pl
Lemma 19. With high probability, for each s ∈ V and for each l such that i=0 r l (s) <
4−β
1
1
n 2 + , r l+1 (s) < n 2 +3 if λ has finite second moment, r l+1 (s) < n 2 +3 if λ is power law
with 2 < β < 3.
1

Proof. We consider separately nodes with weight at most n 2 −2 from nodes with bigger
weights: in the former case, we bound the number of such nodes that are in Rl+1 (s), while
1
in the latter case we bound the total number of nodes with weight at least n 2 −2 . Let us
start with nodes with the
P latter case.
1
+3
1 − ρv is smaller than n 2
Claim: for each ,
if λ has finite second moment,
2
and it is smaller than n

ρv ≥n
4−β
2 +3

if λ is power law with 2 < β < 3.

Proof of claim. If λ has finite second moment, by Chebyshev inequality, for each α,



 Var(λ )

1
M2 (λi )
M2 (λ)
i
+α
2
Pr λi > n
≤ 1+2α ≤ 1+2α = O
= O n−1−2α .
1+2α
n
n
n
1

For α = , this means that no node has weight bigger than n 2 + , and for α = −, this
1
means
weight bigger than n 2 − is at most n2 . We conclude
Pthat the number
P of nodes with
1
1
+
+3
1 − ρv ≤
1 − n 2
that
≤ n2
.
2
2
ρv ≥n

ρv ≥n

22

If λ is power law with 2 < β < 3, by Assumption 3b the number of nodes with weight at
least d is at most Cnd−β+1 . Consequently, using Abel’s summation technique,
X

+∞
X

ρv =

1
ρv ≥n 2 −

d|{v : ρv = d}|

d=ρv
+∞
X

=

d(|{v : ρv ≥ d}| − |{v : ρv ≥ d + 1}|)

1
d=n 2 −

+∞
X

=

d|{v : ρv ≥ d}| −

1
d=n 2 −

+∞
X

(d − 1)|{v : ρv ≥ d}|

1
d=n 2 − +1
1

1

= n 2 − |{v : ρv ≥ n 2 − }| +

+∞
X

|{v : ρv ≥ d}|

1
d=n 2 − +1

≤ Cn 2 − n1−( 2 −)(β−1) +
1

1

+∞
X

Cnd−β+1

1

d=n 2 − +1



=O n

By this claim,

4−β
2 +β


 4−β

1
+ n1−( 2 −)(β−2) = O n 2 +β .

1

P

1

v∈Γl+1 (s),ρv ≥n 2 −2
4−β
2 +6

ρv is smaller than n 2 +6 if λ has finite second moment,

and it is smaller than
Pn
only have to bound

if λ is power law with 2 < β < 3. To conclude the proof, we
1
ρv .
v∈Γl+1 (s),ρv <n 2 −2
P
1
1
Claim: with high probability,
ρv < n 2 + if λ has finite second
v∈Γl+1 (s),ρv <n 2 −2
P
4−β
+
1 −2 ρv < n 2
moment,
if λ is power law with 2 < β < 3.
l+1
2
v∈Γ

(s),ρv <n

Proof of claim, CM. As in the proof of Lemma 17, we can safely assume that we know
the structure S of N l (s). Let us sort the stubs in Rl (s), not paired by S, obtaining
a1 , . . . , ak , and let ai be the stub paired with ai . Let res(a) be the number of stubs
1
of the node a, minus a, and let X i = res(ai ) if res(ai ) < n 2 −2 , 0 otherwise: clearly,
P
Pk
1 −2 ρv ≤
l+1
i=1 X i (with equality if there are no horizontal or diagonal
2
v∈Γ

(s),ρv ≤n

1

edges in the BFS tree). After thefirst i − 1 stubs
are paired, since i < n 2 + and since the

1
1
number of stubs paired in S is O n 2 + log n , for each k < n 2 −2 ,
Pr (X i = k) = Pr (res (ai ) = k)
|{a ∈ A : a unpaired after i rounds, res(a) = k}|
|{a ∈ A : a unpaired after i rounds}|
 1 
|{a ∈ A : res(a) = k}| + O n 2 +
 1 
=
|A| + O n 2 +
 1 
(k + 1)λ(k + 1)
=
+ O n− 2 + .
M1 (λ)
=

Consequently, conditioned on all pairings of aj for j < i, E [X i ] =
− 21 +

O(n

Pn 21 −2
k=0

k (k+1)λ(k+1)
+
M1 (λ)

log n) = α(n), where α(n) = O(1) if λ has finite second moment, and α(n) =

23

Pk
3−β
O(n 2 ) if λ is power law with 2 < β < 3. Hence, for each , i=1 X i − i(M1 (λ) + ) is a
supermartingale, and by Azuma’s inequality
!
!
k
X
α(n)2
≤ exp(−n ).
Pr
X i − kα(n) ≥ α(n) ≤ exp − Pk
1
2 −2
2
n
i=1
i=1
Then, w.h.p.,

Pk

i=1

1

X i ≤ n 2 + (α(n) + 2), concluding the proof of the claim.
1

Proof of claim, IRG.PThe number of nodes
w with weight at most n 2 −2 that belong to
P
l+1
1 −2
Γ (s) is at most
l
w∈V ρw X v,w , where X v,w = 1 with probability

 v∈Γ (s),ρv <n 2
ρv ρw
ρv ρw
1−
f M = O M because ρv ρw < n . Moreover,


P


X
X
ρ2


ρw X v,w  = O r l (s) v∈V v = r l (s)α(n)
E
n
1
v∈Γl (s),ρv <n 2 −2

w∈V

 3−β 
where α(n) = O(1) if λ has finite second moment, and α(n) = O n 2
if λ is power
law with 2 < β < 3.
By Hoeffding inequality,


r l (s)α(n)
X
X
1 −2


l
l
l
Pr 
ρw X v,w − r (s)α(n) ≥ r (s)α(n) ≤ n r (s)n 2
≤ n− .
1

v∈Γl (s),ρv <n 2 −2

w∈V

This concludes the proof.
This claim lets us conclude the proof of the lemma.
P
P
Proof of Theorem 4. Let Dsi = v∈Γi (s) deg(v), Dtj = w∈Γj (t) deg(w), and let us suppose
1

that we have visited until level ls from s, until level lt from t, and that Dsls , Dtlt > n 2 +2 . If
this situation never occurs, by Theorem 18, the total number of visited edges is at most
1
1
O(log n)n 2 +2 = O(n 2 +3 ), and the conclusion follows. Otherwise, again by Theorem 18,
1
the number of edges visited in the two BFS trees before levels ls and lt is O(n 2 +3 ).
1
Furthermore, by Lemma 15, r ls (s), r lt (t) > n 2 +2 . We claim that, without loss of generality,
we can assume r ls −1 (s) < r ls (s), to apply Lemma 17. Indeed, if r ls −1 (s) is too big, we
iteratively decrease ls until we find a neighbor verifying r ls (s) > (1 − 0 )r ls −1 (s). This
process can last at most O(log n) steps, and hence it is stopped at a point ls such that
0
1
1
r ls (s) > n 2 +2 (1 − 0 )O(log n) ≥ n 2 + if 0 is small enough. Similarly, we can suppose
without loss of generality that r lt (t) > (1 − 0 )r lt −1 (t). By Lemma 17, d(s, t) ≤ ls + lt + 2,
and the number of nodes needed to conclude the BFS is at most Dsls + Dtlt (note that, if we
extend twice the visit from s, it means that Dsls +1 < Dtlt ). By Lemma 15, Dsls ≤ n r ls (s),
4−β
1
and by Lemma 19 this value is at most n 2 +3 if λ has finite second moment, and n 2 +3 if
λ is power law with 2 < β < 3. We conclude that the total number of visited nodes is at
4−β
1
1
1
most n 2 +3 + Dsls + Dtlt ≤ n 2 +3 + r ls (s) + r lt (t) ≤ n 2 +4 (resp., n 2 +4 ) if λ has finite
second moment (resp., if λ is power law with 2 < β < 3). The theorem follows by changing
the value of .

24

F

Detailed Experimental Results

Table 1: Detailed experimental results (undirected graphs). Empty values correspond to
graphs on which the algorithm needed more than 1 hour.
Graph
λ = 0.005
advogato
as20000102
ca-GrQc
ca-HepTh
C elegans
com-amazon.all
dip20090126 MAX
D melanogaster
email-Enron
HC-BIOGRID
Homo sapiens
hprd pp
Mus musculus
oregon1 010526
oregon2 010526
λ = 0.010
advogato
as20000102
ca-GrQc
ca-HepTh
C elegans
com-amazon.all
dip20090126 MAX
D melanogaster
email-Enron
HC-BIOGRID
Homo sapiens
hprd pp
Mus musculus
oregon1 010526
oregon2 010526
λ = 0.015
advogato
as20000102
ca-GrQc
ca-HepTh
C elegans
com-amazon.all
dip20090126 MAX
D melanogaster
email-Enron
HC-BIOGRID
Homo sapiens
hprd pp
Mus musculus
oregon1 010526
oregon2 010526

KADABRA

Number of iterations
RK ABRA-Aut

Time (s)
RK ABRA-Aut

ABRA-1.2

KADABRA
0.193
0.231
0.126
0.222
0.132
0.340
1.374
0.123
0.280
0.177
0.151
0.127
0.168
0.228
0.236

11.450
6.990
5.574
14.921
6.876
122.020
34.595
19.253
79.296
7.751
32.078
18.323
4.058
13.281
15.823

9.557
611.584
3.500
7.389
5.693
12.011

10.498
136.764
2.839
8.168
5.261
11.849

15.061
101.529
7.534
23.716
13.425
7.723
442.370
452.554

16.882
106.278
6.951
24.449
13.458
6.083
185.711
229.234

0.081
0.071
0.049
0.188
0.048
0.312
0.395
0.063
0.198
0.052
0.085
0.074
0.061
0.087
0.088

2.804
1.777
1.417
3.771
1.803
31.004
8.578
4.983
19.877
1.979
7.876
4.348
1.055
3.254
3.983

2.576
88.886
0.987
2.078
1.586
5.196

2.788
35.049
0.753
2.275
1.483
7.623

3.891
24.997
1.989
6.442
4.097
1.965
70.383
73.942

4.715
27.296
1.906
6.636
3.714
1.718
47.740
59.103

0.050
0.047
0.031
0.167
0.034
0.301
0.203
0.053
0.170
0.043
0.072
0.056
0.033
0.056
0.060

1.428
0.776
0.637
1.641
0.782
13.814
3.851
2.216
8.845
0.858
3.717
1.919
0.458
1.522
1.773

1.227
22.939
0.493
0.939
0.740

1.299
16.136
0.361
1.050
0.732
7.785

1.904
10.510
0.946
3.076
1.719
0.906
26.420
26.070

2.182
12.423
0.947
3.061
1.752
0.812
21.871
27.298

64427
115797
61611
31735
69729
40711
156552
51227
74745
78804
60060
59125
92081
114829
115764

126052
126052
146052
146052
146052
166052
166052
126052
146052
146052
146052
146052
146052
126052
126052

174728
18329844
142982
121587
204634
69708

185998
4126626
129165
129165
185998
74747

144680
257989
245780
156973
151499
504669
6798931
5714183

154998
267838
223198
154998
154998
385688
2865712
2865712

19811
29062
18535
13761
19888
14641
39314
15136
21637
22924
20273
18403
25146
30514
29117

31513
31513
36513
36513
36513
41513
41513
31513
36513
36513
36513
36513
36513
31513
31513

47076
2688614
37529
31721
54327
18007

48243
1070372
33501
33501
48243
19386

37219
65392
62413
41006
39994
130384
1104167
954515

40202
69471
57892
40202
40202
100040
743313
743313

9570
13035
8668
7524
10956
8228
17578
9350
11209
12694
10142
10659
11825
13662
13024

14006
14006
16228
16228
16228
18451
18451
14006
16228
16228
16228
16228
16228
14006
14006

21027
705483
17419
15002
25233

22204
492651
15419
15419
22204
15419

17229
29134
28805
18491
17969
59756
426845
333638

18503
31974
26645
18503
18503
46043
342118
342118

25

ABRA-1.2

Edges
KADABRA
261.2
377.6
353.4
9.9
270.7
21.9
15354.9
520.8
1408.0
713.2
643.8
456.4
226.6
681.6
822.2
258.2
377.3
350.6
10.0
269.4
21.5
15301.7
519.9
1387.2
712.5
642.7
456.4
223.9
683.3
822.1
261.0
377.6
345.8
11.5
267.6
21.9
15197.2
519.3
1367.4
708.6
640.4
451.5
222.8
681.4
833.6

Graph
λ = 0.020
advogato
as20000102
ca-GrQc
ca-HepTh
C elegans
com-amazon.all
dip20090126 MAX
D melanogaster
email-Enron
HC-BIOGRID
Homo sapiens
hprd pp
Mus musculus
oregon1 010526
oregon2 010526
λ = 0.025
advogato
as20000102
ca-GrQc
ca-HepTh
C elegans
com-amazon.all
dip20090126 MAX
D melanogaster
email-Enron
HC-BIOGRID
Homo sapiens
hprd pp
Mus musculus
oregon1 010526
oregon2 010526
λ = 0.030
advogato
as20000102
ca-GrQc
ca-HepTh
C elegans
com-amazon.all
dip20090126 MAX
D melanogaster
email-Enron
HC-BIOGRID
Homo sapiens
hprd pp
Mus musculus
oregon1 010526
oregon2 010526

KADABRA

Number of iterations
RK ABRA-Aut

Time (s)
RK ABRA-Aut

ABRA-1.2

KADABRA
0.054
0.037
0.032
0.191
0.030
0.331
0.148
0.056
0.174
0.026
0.064
0.050
0.026
0.051
0.059

0.710
0.441
0.356
0.891
0.439
7.683
2.165
1.236
4.916
0.505
1.944
1.089
0.255
0.863
1.031

0.665
10.066
0.293
0.694
0.436
4.338

0.765
7.819
0.268
0.611
0.439
5.459

1.265
6.102
0.602
1.672
0.930
0.507
13.584
11.676

1.306
6.034
0.582
1.814
1.050
0.532
12.989
13.290

0.052
0.033
0.028
0.176
0.025
0.338
0.125
0.056
0.574
0.029
0.077
0.052
0.026
0.058
0.050

0.450
0.285
0.242
0.573
0.292
4.744
1.397
0.793
3.289
0.321
1.245
0.687
0.168
0.516
0.638

0.421
4.097
0.180
0.374
0.293
9.644

0.468
5.108
0.162
0.416
0.293
7.217

0.827
3.888
0.414
1.154
0.579
0.302
5.762
7.140

0.870
4.705
0.404
1.215
0.647
0.385
7.014
7.420

0.048
0.029
0.025
0.190
0.026
0.330
0.300
0.052
0.172
0.024
0.066
0.048
0.033
0.052
0.048

0.361
0.199
0.169
0.435
0.198
3.631
0.972
0.562
2.735
0.367
0.897
0.478
0.127
0.366
0.509

0.335
3.899
0.145
0.286
0.218
8.491
1958.083
0.620
2.724
0.316
0.842
0.458
0.237
5.402
4.972

0.322
3.182
0.175
0.341
0.217
6.852

5874
7436
5313
5115
7172
5467
9966
5610
7458
8459
6292
6611
7227
7733
7381

7879
7879
9129
9129
9129
10379
10379
7879
9129
9129
9129
9129
9129
7879
7879

11993
312581
9939
8708
14871
12232

12915
238814
10762
8968
12915
10762

10201
16443
17406
10481
10501
31634
220948
152242

10762
15498
15498
10762
10762
26782
199011
165842

3883
4829
3982
3773
4477
4059
6457
3993
4576
5940
4796
5071
4477
5027
4763

5043
5043
5843
5843
5843
6643
6643
5043
5843
5843
5843
5843
5843
5043
5043

7439
130506
6427
6016
9557
58995

7110
157779
5925
5925
8532
14745

6279
11001
11109
7109
6772
18626
92520
86287

7110
12287
10239
7110
7110
17694
109568
91306

3256
3388
2981
2992
3707
3157
4499
2893
3619
3883
3322
3355
3806
3542
3355

3502
3502
4057
4057
4057
4613
4613
3502
4057
4057
4057
4057
4057
3502
3502

5521
122988
4686
4022
6905
39917
12373086
4883
7321
7499
4982
5028
14290
85854
61841

5090
94140
4241
4241
6108
12668
5090
7330
7330
5090
5090
10556
78450
65375

26

ABRA-1.2

0.807
2.806
0.307
0.877
0.503
0.233
5.039
5.302

Edges
KADABRA
260.3
376.2
347.9
10.5
263.5
17.9
15188.3
520.9
1371.7
716.6
644.8
449.8
221.0
679.2
836.0
263.4
373.5
342.1
11.8
266.6
21.3
15193.8
522.6
1381.5
714.0
647.2
446.3
219.8
681.0
847.5
260.6
378.7
344.7
7.9
265.9
17.5
15199.0
510.4
1399.7
720.8
654.2
448.8
221.4
675.7
822.8

Table 2: Detailed experimental results (directed graphs). Empty values correspond to graphs
on which the algorithm needed more than 1 hour.
Graph
λ = 0.005
as-caida20071105
cfinder-google
cit-HepTh
ego-gplus
ego-twitter
freeassoc
lasagne-spanishbook
opsahl-openflights
p2p-Gnutella31
polblogs
soc-Epinions1
subelj-cora-cora
subelj-jdk-jdk
subelj-jung-j-jung-j
wiki-Vote
λ = 0.010
as-caida20071105
cfinder-google
cit-HepTh
ego-gplus
ego-twitter
freeassoc
lasagne-spanishbook
opsahl-openflights
p2p-Gnutella31
polblogs
soc-Epinions1
subelj-cora-cora
subelj-jdk-jdk
subelj-jung-j-jung-j
wiki-Vote
λ = 0.015
as-caida20071105
cfinder-google
cit-HepTh
ego-gplus
ego-twitter
freeassoc
lasagne-spanishbook
opsahl-openflights
p2p-Gnutella31
polblogs
soc-Epinions1
subelj-cora-cora
subelj-jdk-jdk
subelj-jung-j-jung-j
wiki-Vote

KADABRA

Number of iterations
RK ABRA-Aut

103488
137313
98054
37862
37125
41602
112266
73744
39193
71423
58223
68112
42361
43637
47003

146052
146052
166052
66052
66052
166052
146052
146052
166052
126052
146052
186052
146052
126052
126052

30382
34452
27203
13123
13310
13222
32527
22473
13101
22286
17061
23078
14047
14894
17380

36513
36513
41513
16513
16513
41513
36513
36513
41513
31513
36513
46513
36513
36513
31513

14157
15400
13002
7205
7403
7095
14542
11550
7227
10296
9273
11297
8360
8712
8668

16228
16228
18451
7340
7340
18451
16228
16228
18451
14006
16228
20673
14006
16228
14006

Time (s)
RK ABRA-Aut

ABRA-1.2

KADABRA

546951

462826

481476

89424
8918751
200164
81335
387278
109607
180740
84549
84225
100153

462826
2388093
154998
89697
4126626
185998
89697
321406
107637
185998
89697
89697
107637

0.253
0.820
0.579
0.136
0.178
0.116
0.250
0.179
0.254
0.174
0.671
0.185
0.110
0.216
0.131

35.652
14.190
22.651
6.266
6.181
9.384
17.374
6.191
50.542
1.165
100.516
19.012
2.955
2.397
5.916

132997

120048

117633

23586
1366576
52196
21567
101466
28493
47936
22038
22266
26352

120048
4602412
83366
23264
1070372
48243
23264
83366
27917
48243
23264
23264
27917

0.135
0.156
0.255
0.085
0.086
0.080
0.101
0.059
0.192
0.046
0.320
0.128
0.066
0.064
0.088

8.902
3.664
5.654
1.584
1.518
2.335
4.339
1.475
12.950
0.298
27.194
4.797
0.734
0.696
1.446

55049

55252

47035

46043
2118317
114573
10707
410542
22204
10707
38369
12849
22204
10707
10707
12849

0.477
0.123
0.232
0.080
0.082
0.297
0.068
0.034
0.190
0.029
0.450
0.502
0.052
0.046
0.408

3.963
1.666
2.529
0.710
0.704
1.072
1.936
0.649
5.732
0.136
12.115
2.135
0.288
0.312
0.659

1958981
10956
437041
24433
10002
46648
13571
20940
10045
10319
12406

27

ABRA-1.2

96.312

85.201

38.339

1.036
687.815
5.165
10.213
3.522
62.524
8.464
0.230
0.238
2.990

37.720
11.912
4.804
0.997
318.784
4.849
10.662
3.017
62.167
8.873
0.257
0.211
3.219

22.251

20.315

8.803

0.238
104.916
1.348
2.677
1.078
16.516
1.988
0.099
0.113
0.792

9.677
22.510
3.500
0.227
83.610
1.339
2.831
0.834
15.974
2.101
0.075
0.083
0.870

8.518

8.914

3.807

3.766
12.808
5.304
0.110
33.153
0.648
1.444
0.435
7.629
1.073
0.049
0.042
0.429

14.021
0.115
34.098
0.643
1.317
0.516
7.661
0.937
0.080
0.068
0.380

Edges
KADABRA
1066.4
554.4
5773.1
1.9
2.3
223.5
552.8
431.1
162.1
190.3
671.9
440.4
51.5
45.9
162.4
1066.1
553.2
5798.8
2.3
2.2
220.7
553.4
432.0
162.1
190.6
659.5
432.4
52.2
46.4
155.7
1059.6
558.1
5883.0
2.2
2.3
222.0
552.8
433.9
157.1
189.5
662.0
445.6
51.6
45.6
152.6

Graph
λ = 0.020
as-caida20071105
cfinder-google
cit-HepTh
ego-gplus
ego-twitter
freeassoc
lasagne-spanishbook
opsahl-openflights
p2p-Gnutella31
polblogs
soc-Epinions1
subelj-cora-cora
subelj-jdk-jdk
subelj-jung-j-jung-j
wiki-Vote
λ = 0.025
as-caida20071105
cfinder-google
cit-HepTh
ego-gplus
ego-twitter
freeassoc
lasagne-spanishbook
opsahl-openflights
p2p-Gnutella31
polblogs
soc-Epinions1
subelj-cora-cora
subelj-jdk-jdk
subelj-jung-j-jung-j
wiki-Vote
λ = 0.030
as-caida20071105
cfinder-google
cit-HepTh
ego-gplus
ego-twitter
freeassoc
lasagne-spanishbook
opsahl-openflights
p2p-Gnutella31
polblogs
soc-Epinions1
subelj-cora-cora
subelj-jdk-jdk
subelj-jung-j-jung-j
wiki-Vote

G

KADABRA

Number of iterations
RK ABRA-Aut

9086
8745
8679
4785
4950
4268
8338
7392
4697
6325
5489
6325
5456
5643
4939

9129
9129
10379
4129
7879
10379
9129
9129
10379
7879
9129
11629
9129
9129
7879

5723
6275
5206
2989
2958
2804
5409
4557
3069
3880
3689
5264
3201
3168
3265

5843
5843
6643
5043
2643
6643
5043
5843
6643
5043
5843
7443
5843
5043
5043

3956
4419
4062
2434
2270
2105
3820
3450
2367
3567
2659
3790
2425
2436
2633

4057
4057
4613
1835
1835
4613
4057
4057
4613
3502
4057
5169
4057
3502
3502

Time (s)
RK ABRA-Aut

ABRA-1.2

KADABRA

31242

32139

27755

7125

32139
1478684
138201
6227
286577
12915
6227
22318
7473
12915
6227
6227
7473

0.104
0.353
1.249
0.081
0.083
0.065
0.058
0.029
0.190
0.023
0.457
0.500
0.191
0.217
0.075

2.226
0.946
1.442
0.395
0.743
0.609
1.074
0.364
3.162
0.076
6.738
1.203
0.192
0.176
0.368

21020

21233

15915

4285
129999
10116
3931
15986
5060
7699
9428
13471
4566

21233
4200646
157779
4114
131482
8532
4114
14745
4937
8532
4937
5925
4937

0.022
0.019
0.034
0.013
0.012
0.009
0.013
0.009
0.043
0.007
0.188
0.020
0.008
0.007
0.009

1.465
0.648
0.940
0.485
0.248
0.399
0.592
0.236
2.149
0.049
4.158
0.781
0.122
0.098
0.241

12696

15202

13172

12668
4330990
135562
3534
94140
6108
2945
8796
3534
5090
5090
5090
3534

0.017
0.013
0.033
0.009
0.008
0.006
0.010
0.007
0.036
0.007
0.312
0.016
0.006
0.006
0.006

1.029
0.412
0.672
0.188
0.174
0.285
0.487
0.165
1.412
0.036
3.211
0.564
0.097
0.079
0.188

6509
294793
14202
5700
25593
7686
12437
6070

98839
3008
158028
6556
2874
11357
3585
5681
25575
43584
3467

ABRA-1.2

4.954

5.087

2.225

0.221

2.684
9.234
5.079
0.073
22.468
0.391
0.816
0.252
4.335
0.520
0.044
0.045
0.259

3.129

3.340

1.351

0.061
10.040
0.290
0.590
0.185
2.798
0.360
0.065
0.057
0.137

1.891
20.309
6.291
0.058
10.221
0.267
0.663
0.176
2.791
0.408
0.036
0.045
0.178

1.973

2.434

1.195

1.059
21.395
5.510
0.091
7.855
0.195
0.445
0.122
2.046
0.265
0.064
0.059
0.149

0.078
22.405
0.390
0.695
0.283
4.506
0.571
0.062

4.909
0.101
12.564
0.184
0.422
0.151
2.186
0.272
0.100
0.140
0.148

Edges
KADABRA
1064.2
551.9
5758.0
2.6
2.4
216.4
555.0
432.3
156.7
188.4
651.8
450.8
52.3
46.6
152.2
1093.4
758.0
6130.5
2.6
2.4
261.5
626.1
561.3
176.8
241.9
888.1
436.5
57.2
57.7
174.7
1285.2
770.5
6131.6
3.1
2.2
250.7
656.8
481.4
166.5
207.9
918.3
422.6
57.4
57.0
188.2

Wikipedia and IMDB Results

In this section, we report our results on the Wikipedia citation network, and on all snapshots
of the IMDB actors collaboration network. In the ranking column, we report one number if
the position in the ranking is guaranteed with probability 0.9, otherwise we report a lower
and an upper bound, which hold with the same probability.
We remark that, as for the IMDB database, the top-k betweenness centralities of a
single snapshot of a similar graph (hollywood-2009 in [10]) have been previously computed
exactly, with one week of computation on a 40-core machine [47].

G.1

The Results on the IMDB Graph

In 2014, the most central actor is Ron Jeremy, who is listed in the Guinness Book of World
Records for “Most Appearances in Adult Films”, with more than 2000 appearances. Among
his non-adult ones, we mention The Godfather Part III, Ghostbusters, Crank: High Voltage
and Family Guy 3 . His topmost centrality in the actor collaboration network has been
previously observed by similar experiments on betweenness centrality [47]. Indeed, around 3
actors out of 100 in the IMDB database played in adult movies, which explains why the
3 The

latter is a TV-series, which are not taken into account in our data.

28

high number of appearances of Ron Jeremy both in the adult and non-adult film industry
rises his betweenness to the top.
The second most-central actor is Lloyd Kaufman, which is best known as a co-founder
of Troma Entertainment Film Studio and as the director of many of their feature films,
including the cult movie The Toxic Avenger. His high betweenness score is likely due to his
central role in the low-budget independent film industry.
The third “actor” is the historical German dictator Adolf Hitler, since his appearances
in several historical footages, that were re-used in several movies (e.g. in The Imitation
Game), are credited by IMDB as cameo role. Indeed, he appears among the topmost actors
since the 1984 snapshot, being the first one in the 1989 and 1994 ones, and during those
years many movies about the World War II were produced.
Observe that the betweenness centrality measure on our graph does not discriminate
between important and marginal roles. For example, the actress Bess Flowers, who appears
among the top actors in the snapshots from 1959 to 1979, rarely played major roles, but she
appeared in over 700 movies in her 41 years career.

G.2

The Results on the Wikipedia Graph

All topmost pages in the betweenness centrality ranking, except for the World War II, are
countries. This is not surprising if we consider that, for most topics (such as important
people or events), the corresponding Wikipedia page refers to their geographical context
(since it mentions the country of origin of the given person or where a given event took
place). It is also worth noting the correlation between the high centrality of the World War
II Wikipedia page and that of Adolf Hitler in the IMDB graph.
Interestingly, a similar ranking is obtained by considering the closeness centrality measure
in the inverse graph, where a link from page p1 to page p2 exists if a link to page p1 appears
in page p2 [8]. However, in contrast with the results in [8] when edges are oriented in the
usual way, the pages about specific years do not appear in the top ranking. We note that
the betweenness centrality of a node in a directed graph does not change if the orientation
of all edges is flipped.
Finally, the most important pages is the United States, confirming a common conjecture.
Indeed, in http://wikirank.di.unimi.it/, it is shown that the United States are the
center according to harmonic centrality, and many other measures. Further evidence for
this conjecture comes from the Six Degree of Wikipedia game (http://thewikigame.com/
6-degrees-of-wikipedia), where a player is asked to go from one page to the other
following the smallest possible number of links: a hard variant of this game forces the player
not to pass from the United States page, which is considered to be central. Our results thus
confirm that the conjecture is indeed true for the betweenness centrality measure.

29

Table 3: The top-k betweenness centralities of the Wikipedia graph computed by KADABRA
with δ = 0.1 and λ = 0.0002.
Ranking Wikipedia page
Lower bound Estimated betweenness Upper bound
1)
United States
0.046278
0.047173
0.048084
2)
France
0.019522
0.020103
0.020701
3)
United Kingdom
0.017983
0.018540
0.019115
4)
England
0.016348
0.016879
0.017428
5-6)
Poland
0.012092
0.012287
0.012486
5-6)
Germany
0.011930
0.012124
0.012321
7)
India
0.009683
0.010092
0.010518
8-12)
World War II
0.008870
0.009065
0.009265
8-12)
Russia
0.008660
0.008854
0.009053
8-12)
Italy
0.008650
0.008845
0.009045
8-12)
Canada
0.008624
0.008819
0.009018
8-12)
Australia
0.008620
0.008814
0.009013

Table 4: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1939 (69011 nodes), computed by KADABRA with δ = 0.1 and
λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Meyer, Torben
0.022331
0.022702
0.023049
2)
Roulien, Raul
0.021361
0.021703
0.022071
3)
Myzet, Rudolf
0.014229
0.014525
0.014747
4)
Sten, Anna
0.013245
0.013460
0.013723
5)
Negri, Pola
0.012509
0.012768
0.012943
6-7)
Jung, Shia
0.012250
0.012379
0.012509
6-7)
Ho, Tai-Hau
0.012195
0.012324
0.012454
8)
Goetzke, Bernhard
0.010721
0.010978
0.011201
9-10)
Yamamoto, Togo
0.010095
0.010224
0.010354
9-10)
Kamiyama, Sōjin
0.010087
0.010215
0.010344

Table 5: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1944 (83068 nodes), computed by KADABRA with δ = 0.1 and
λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Meyer, Torben
0.018320
0.018724
0.019136
2)
Kamiyama, Sōjin
0.012629
0.012964
0.013308
3-4)
Jung, Shia
0.010751
0.010901
0.011053
3-4)
Ho, Tai-Hau
0.010704
0.010854
0.011005
5)
Myzet, Rudolf
0.010365
0.010514
0.010666
6-7)
Sten, Anna
0.009778
0.009928
0.010080
6-7)
Goetzke, Bernhard
0.009766
0.009915
0.010066
8)
Yamamoto, Togo
0.009108
0.009327
0.009539
9)
Parı̀s, Manuel
0.008649
0.008859
0.009108
10)
Hayakawa, Sessue
0.007916
0.008158
0.008369

30

Table 6: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1949 (97824 nodes), computed by KADABRA with δ = 0.1 and
λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Meyer, Torben
0.016139
0.016679
0.017236
2)
Kamiyama, Sōjin
0.012351
0.012822
0.013312
3)
Parı̀s, Manuel
0.011104
0.011552
0.011861
4)
Yamamoto, Togo
0.010342
0.010639
0.011086
5-6)
Jung, Shia
0.008926
0.009120
0.009318
5-6)
Goetzke, Bernhard
0.008567
0.008762
0.008962
7-9)
Paananen, Tuulikki
0.008147
0.008341
0.008539
7-9)
Sten, Anna
0.007969
0.008164
0.008363
7-9)
Mayer, Ruby
0.007967
0.008162
0.008362
10-12)
Ho, Tai-Hau
0.007538
0.007732
0.007930
10-12)
Hayakawa, Sessue
0.007399
0.007593
0.007792
10-12)
Haas, Hugo (I)
0.007158
0.007352
0.007552

Table 7: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1954 (120430 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Meyer, Torben
0.013418
0.013868
0.014334
2)
Kamiyama, Sōjin
0.010331
0.010726
0.011089
3-4)
Ertugrul, Muhsin
0.009956
0.010141
0.010331
3-4)
Jung, Shia
0.009643
0.009826
0.010013
5-6)
Singh, Ram (I)
0.008657
0.008841
0.009030
5-6)
Paananen, Tuulikki
0.008383
0.008567
0.008755
7-9)
Parı̀s, Manuel
0.007886
0.008070
0.008257
7-10)
Goetzke, Bernhard
0.007802
0.007987
0.008176
7-10)
Yamaguchi, Shirley
0.007531
0.007716
0.007905
8-10)
Hayakawa, Sessue
0.007473
0.007657
0.007845

Table 8: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1959 (146253 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1-2)
Singh, Ram (I)
0.010683
0.010877
0.011075
1-2)
Frees, Paul
0.010372
0.010566
0.010763
3)
Meyer, Torben
0.009478
0.009821
0.010235
4-5)
Jung, Shia
0.008623
0.008816
0.009013
4-5)
Ghosh, Sachin
0.008459
0.008651
0.008847
6-7)
Myzet, Rudolf
0.007085
0.007278
0.007476
6-7)
Yamaguchi, Shirley
0.006908
0.007101
0.007299
8)
de Còrdova, Arturo
0.006391
0.006582
0.006778
9-11)
Kamiyama, Sōjin
0.005861
0.006054
0.006254
9-12)
Paananen, Tuulikki
0.005810
0.006003
0.006202
9-12)
Flowers, Bess
0.005620
0.005813
0.006012
10-12)
Parı̀s, Manuel
0.005442
0.005635
0.005835

31

Table 9: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1964 (174826 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Frees, Paul
0.013140
0.013596
0.014067
2)
Meyer, Torben
0.007279
0.007617
0.007856
3-4)
Harris, Sam (II)
0.006813
0.006967
0.007124
3-5)
Myzet, Rudolf
0.006696
0.006849
0.007005
4-5)
Flowers, Bess
0.006422
0.006572
0.006726
6)
Kong, King (I)
0.005909
0.006104
0.006422
7)
Yuen, Siu Tin
0.005114
0.005264
0.005420
8)
Miller, Marvin (I)
0.004708
0.004859
0.005015
9-12)
de Còrdova, Arturo
0.004147
0.004299
0.004457
9-18)
Haas, Hugo (I)
0.003888
0.004039
0.004197
9-18)
Singh, Ram (I)
0.003854
0.004004
0.004160
9-18)
Kamiyama, Sōjin
0.003848
0.003999
0.004155
10-18)
Sauli, Anneli
0.003827
0.003978
0.004135
10-18)
King, Walter Woolf
0.003774
0.003923
0.004078
10-18)
Vanel, Charles
0.003716
0.003867
0.004024
10-18)
Kowall, Mitchell
0.003684
0.003834
0.003990
10-18)
Holmes, Stuart
0.003603
0.003752
0.003907
10-18)
Sten, Anna
0.003582
0.003733
0.003890

Table 10: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1969 (210527 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Frees, Paul
0.010913
0.011446
0.012005
2-3)
Yuen, Siu Tin
0.006157
0.006349
0.006547
2-3)
Tamiroff, Akim
0.006097
0.006291
0.006490
4-6)
Meyer, Torben
0.005675
0.005869
0.006069
4-7)
Harris, Sam (II)
0.005639
0.005830
0.006027
4-8)
Rubener, Sujata
0.005427
0.005618
0.005815
5-8)
Myzet, Rudolf
0.005253
0.005444
0.005641
6-8)
Flowers, Bess
0.005136
0.005328
0.005526
9-10)
Kong, King (I)
0.004354
0.004544
0.004741
9-10)
Sullivan, Elliott
0.004208
0.004398
0.004596

32

Table 11: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1974 (257896 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Frees, Paul
0.008507
0.008958
0.009295
2)
Chen, Sing
0.007734
0.008056
0.008507
3)
Welles, Orson
0.006115
0.006497
0.006903
4-5)
Loren, Sophia
0.005056
0.005221
0.005392
4-7)
Rubener, Sujata
0.004767
0.004933
0.005106
5-8)
Harris, Sam (II)
0.004628
0.004795
0.004967
5-8)
Tamiroff, Akim
0.004625
0.004790
0.004962
6-10)
Meyer, Torben
0.004382
0.004548
0.004720
8-12)
Flowers, Bess
0.004259
0.004425
0.004598
8-12)
Yuen, Siu Tin
0.004229
0.004397
0.004571
9-12)
Carradine, John
0.004026
0.004192
0.004364
9-12)
Myzet, Rudolf
0.003984
0.004151
0.004325

Table 12: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1979 (310278 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Chen, Sing
0.007737
0.008220
0.008647
2)
Frees, Paul
0.006852
0.007255
0.007737
3-5)
Welles, Orson
0.004894
0.005075
0.005263
3-6)
Carradine, John
0.004623
0.004803
0.004989
3-6)
Loren, Sophia
0.004614
0.004796
0.004985
4-6)
Rubener, Sujata
0.004284
0.004464
0.004651
7-17)
Tamiroff, Akim
0.003516
0.003696
0.003885
7-17)
Meyer, Torben
0.003479
0.003657
0.003844
7-17)
Quinn, Anthony (I)
0.003447
0.003626
0.003815
7-17)
Flowers, Bess
0.003446
0.003625
0.003815
7-17)
Mitchell, Gordon (I)
0.003417
0.003596
0.003785
7-17)
Sullivan, Elliott
0.003371
0.003551
0.003740
7-17)
Rietty, Robert
0.003368
0.003547
0.003735
7-17)
Tanba, Tetsurō
0.003360
0.003537
0.003724
7-17)
Harris, Sam (II)
0.003331
0.003510
0.003699
7-17)
Lewgoy, Josè
0.003223
0.003402
0.003590
7-17)
Dalio, Marcel
0.003185
0.003364
0.003553

33

Table 13: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1984 (375322 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Chen, Sing
0.007245
0.007716
0.008218
2-4)
Welles, Orson
0.005202
0.005391
0.005587
2-4)
Frees, Paul
0.005174
0.005363
0.005559
2-5)
Hitler, Adolf
0.004906
0.005094
0.005290
4-6)
Carradine, John
0.004744
0.004932
0.005127
5-7)
Mitchell, Gordon (I)
0.004418
0.004606
0.004802
6-8)
Jürgens, Curd
0.004169
0.004356
0.004551
7-8)
Kinski, Klaus
0.003938
0.004123
0.004318
9-12)
Rubener, Sujata
0.003396
0.003585
0.003785
9-12)
Lee, Christopher (I)
0.003391
0.003576
0.003771
9-12)
Loren, Sophia
0.003357
0.003542
0.003738
9-12)
Harrison, Richard (II)
0.003230
0.003417
0.003614

Table 14: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1989 (463078 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1-2)
Hitler, Adolf
0.005282
0.005467
0.005658
1-3)
Chen, Sing
0.005008
0.005192
0.005382
2-4)
Carradine, John
0.004648
0.004834
0.005027
3-4)
Harrison, Richard (II)
0.004515
0.004697
0.004887
5-6)
Welles, Orson
0.004088
0.004271
0.004462
5-9)
Mitchell, Gordon (I)
0.003766
0.003948
0.004139
6-9)
Kinski, Klaus
0.003691
0.003874
0.004065
6-11)
Lee, Christopher (I)
0.003610
0.003793
0.003984
6-11)
Frees, Paul
0.003582
0.003766
0.003960
8-13)
Jürgens, Curd
0.003306
0.003486
0.003676
8-13)
Pleasence, Donald
0.003299
0.003479
0.003670
10-13)
Mitchell, Cameron (I)
0.003105
0.003285
0.003476
10-13)
von Sydow, Max (I)
0.002982
0.003161
0.003350

34

Table 15: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1994 (557373 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Hitler, Adolf
0.005227
0.005676
0.006164
2-6)
Harrison, Richard (II)
0.003978
0.004165
0.004362
2-6)
von Sydow, Max (I)
0.003884
0.004069
0.004264
2-7)
Lee, Christopher (I)
0.003718
0.003907
0.004106
2-7)
Carradine, John
0.003696
0.003883
0.004079
2-7)
Chen, Sing
0.003683
0.003871
0.004068
4-10)
Jeremy, Ron
0.003336
0.003524
0.003722
7-11)
Pleasence, Donald
0.003253
0.003439
0.003637
7-11)
Rey, Fernando (I)
0.003234
0.003420
0.003617
7-15)
Smith, William (I)
0.003012
0.003199
0.003397
8-15)
Welles, Orson
0.002885
0.003072
0.003271
10-15)
Mitchell, Gordon (I)
0.002851
0.003036
0.003232
10-15)
Kinski, Klaus
0.002705
0.002890
0.003087
10-15)
Mitchell, Cameron (I)
0.002671
0.002858
0.003058
10-15)
Quinn, Anthony (I)
0.002640
0.002826
0.003026

Table 16: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 1999 (681358 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Jeremy, Ron
0.007380
0.007913
0.008484
2)
Hitler, Adolf
0.004601
0.005021
0.005480
3-4)
Lee, Christopher (I)
0.003679
0.003849
0.004028
3-4)
von Sydow, Max (I)
0.003604
0.003775
0.003953
5-6)
Harrison, Richard (II)
0.003041
0.003211
0.003390
5-7)
Carradine, John
0.002943
0.003114
0.003296
6-11)
Chen, Sing
0.002662
0.002834
0.003018
7-14)
Rey, Fernando (I)
0.002569
0.002740
0.002922
7-14)
Smith, William (I)
0.002559
0.002729
0.002910
7-14)
Pleasence, Donald
0.002556
0.002725
0.002906
7-14)
Sutherland, Donald (I)
0.002449
0.002617
0.002796
8-14)
Quinn, Anthony (I)
0.002307
0.002476
0.002658
8-14)
Mastroianni, Marcello
0.002271
0.002440
0.002621
8-14)
Saxon, John
0.002251
0.002420
0.002602

35

Table 17: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 2004 (880032 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Jeremy, Ron
0.010653
0.011370
0.012136
2)
Hitler, Adolf
0.005333
0.005840
0.006396
3-4)
von Sydow, Max (I)
0.003424
0.003608
0.003802
3-4)
Lee, Christopher (I)
0.003403
0.003587
0.003781
5-6)
Kier, Udo
0.002898
0.003081
0.003275
5-8)
Keitel, Harvey (I)
0.002646
0.002828
0.003023
6-12)
Hopper, Dennis
0.002424
0.002607
0.002804
6-16)
Smith, William (I)
0.002322
0.002504
0.002700
7-17)
Sutherland, Donald (I)
0.002241
0.002422
0.002617
7-23)
Carradine, David
0.002149
0.002329
0.002526
7-23)
Carradine, John
0.002147
0.002328
0.002524
7-23)
Harrison, Richard (II)
0.002054
0.002234
0.002430
8-23)
Sharif, Omar
0.002043
0.002222
0.002418
8-23)
Steiger, Rod
0.001988
0.002165
0.002358
8-23)
Quinn, Anthony (I)
0.001974
0.002151
0.002344
8-23)
Depardieu, Gèrard
0.001966
0.002148
0.002346
9-23)
Sheen, Martin
0.001913
0.002093
0.002291
10-23)
Rey, Fernando (I)
0.001866
0.002044
0.002238
10-23)
Kane, Sharon
0.001857
0.002038
0.002237
10-23)
Pleasence, Donald
0.001859
0.002037
0.002232
10-23)
Skarsgȧrd, Stellan
0.001848
0.002026
0.002221
10-23)
Mueller-Stahl, Armin
0.001789
0.001969
0.002166
10-23)
Hong, James (I)
0.001780
0.001957
0.002152

Table 18: The top-k betweenness centralities of a snapshot of the IMDB collaboration
network taken at the end of 2009 (1237879 nodes), computed by KADABRA with δ = 0.1
and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Jeremy, Ron
0.010531
0.011237
0.011991
2)
Hitler, Adolf
0.005500
0.006011
0.006568
3-4)
Kaufman, Lloyd
0.003620
0.003804
0.003997
3-4)
Kier, Udo
0.003472
0.003654
0.003845
5-6)
Lee, Christopher (I)
0.003056
0.003240
0.003435
5-8)
Carradine, David
0.002866
0.003050
0.003245
6-8)
Keitel, Harvey (I)
0.002659
0.002840
0.003034
6-9)
von Sydow, Max (I)
0.002532
0.002713
0.002907
8-13)
Hopper, Dennis
0.002237
0.002419
0.002616
9-15)
Skarsgȧrd, Stellan
0.002153
0.002333
0.002529
9-15)
Depardieu, Gèrard
0.002001
0.002181
0.002377
9-15)
Hauer, Rutger
0.001894
0.002074
0.002271
9-15)
Sutherland, Donald (I)
0.001875
0.002054
0.002250
10-15)
Smith, William (I)
0.001811
0.001990
0.002186
10-15)
Dafoe, Willem
0.001805
0.001986
0.002186

36

Table 19: The top-k betweenness centralities of a snapshot of the IMDB collaboration network
taken in 2014 (1797446 nodes), computed by KADABRA with δ = 0.1 and λ = 0.0002.
Ranking Actor
Lower bound Estimated betweenness Upper bound
1)
Jeremy, Ron
0.009360
0.010058
0.010808
2)
Kaufman, Lloyd
0.005936
0.006492
0.007100
3)
Hitler, Adolf
0.004368
0.004844
0.005373
4-6)
Kier, Udo
0.003250
0.003435
0.003631
4-6)
Roberts, Eric (I)
0.003178
0.003362
0.003557
4-6)
Madsen, Michael (I)
0.003120
0.003305
0.003501
7-9)
Trejo, Danny
0.002652
0.002835
0.003030
7-9)
Lee, Christopher (I)
0.002551
0.002734
0.002931
7-12)
Estevez, Joe
0.002350
0.002534
0.002732
9-17)
Carradine, David
0.002116
0.002296
0.002492
9-17)
von Sydow, Max (I)
0.002023
0.002206
0.002405
9-17)
Keitel, Harvey (I)
0.001974
0.002154
0.002352
10-17)
Skarsgȧrd, Stellan
0.001945
0.002125
0.002323
10-17)
Dafoe, Willem
0.001899
0.002080
0.002279
10-17)
Hauer, Rutger
0.001891
0.002071
0.002269
10-17)
Depardieu, Gèrard
0.001763
0.001943
0.002142
10-17)
Rochon, Debbie
0.001745
0.001926
0.002126

37

