Towards Improving Brandes’ Algorithm for Betweenness
Centrality

arXiv:1802.06701v1 [] 19 Feb 2018

Matthias Bentert
Alexander Dittmann
Leon Kellerhals
André Nichterlein
Rolf Niedermeier
Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany,
{alexander.dittmann,leon.kellerhals}@campus.tu-berlin.de
{matthias.bentert,andre.nichterlein,rolf.niedermeier}@tu-berlin.de

Abstract
Betweenness centrality, measuring how many shortest paths pass through a vertex, is one
of the most important network analysis concepts for assessing the (relative) importance of
a vertex. The famous state-of-art algorithm of Brandes [2001] computes the betweenness
centrality of all vertices in O(mn) worst-case time on an n-vertex and m-edge graph. In
practical follow-up work, significant empirical speedups were achieved by preprocessing degreeone vertices. We extend this by showing how to also deal with degree-two vertices (turning
out to be much richer in mathematical structure than the case of degree-one vertices). For
our new betweenness centrality algorithm we prove the running time upper bound O(kn),
where k is the size of a minimum feedback edge set of the input graph.

1

Introduction

One of the most important building blocks in network analysis is to determine a vertex’s relative
importance in the network. A key concept herein is betweenness centrality as introduced in 1977
by Freeman [6]; it measures centrality based on shortest paths. Intuitively, for each vertex, betweenness centrality counts the (relative) number of shortest paths that pass through the vertex.
A straightforward algorithm for computing betweenness centrality on undirected (unweighted) nvertex graphs runs in Θ(n3 ) time and improving this to O(n3−ε ) time for any ǫ > 3 would break
the APSP-conjecture [1]. In 2001, Brandes [4] presented the to date theoretically fastest algorithm,
improving the running time to O(mn) for graphs with m edges. As many real-world networks
are sparse, this is a tremendous improvement, having a huge impact also in practice.1 Since betweenness centrality is a measure of outstanding importance in network science, it finds numerous
applications in diverse areas, e.g. in data mining [5, 15] or neuroscience [10, 11]. Speeding up
betweenness centrality computations is the ultimate goal of our research. To this end, we extend
previous work and provide a rigorous mathematical analysis that yields a new upper bound on its
worst-case running time.
Our work is in line with numerous research efforts concerning the development of algorithms
for computing betweenness centrality, including approximation algorithms [2, 7, 14], parallel and
distributed algorithms [16, 17], and streaming and incremental algorithms [9, 13].
Formally, we study the following problem:
Betweenness Centrality
Input: An undirected graph G.
P
Task: Compute the betweenness centrality CB (v) := s,t∈V (G)
V (G).
1 According

σst (v)
σst

for each vertex v ∈

to Google Scholar, accessed in February 2018, Brandes’ paper [4] has been cited almost 3000 times.

1

Herein, σst is the number of shortest paths in G from vertex s to vertex t, and σst (v) is the number
of shortest paths from s to t that additionally pass through v.
Extending previous work of Baglioni et al. [3], our main result is an algorithm for Betweenness Centrality that runs in O(kn) time, where k denotes the feedback edge number of the
input graph G. The feedback edge number of G is the minimum number of edges one needs to
delete from G in order to make it a forest.2 Obviously, by depth-first search one can compute k
in linear time; in addition, typically k ≈ m − n, so there is no asymptotic improvement over
Brandes’ algorithm for most graphs. When the input graph is very tree-like, however, our new
algorithm can be much faster than Brandes’s algorithm. Indeed, Baglioni et al. [3], building on
Brandes’ algorithm and basically shrinking the input graph by deleting degree-one vertices (in a
preprocessing step), report on significant speedups in comparison with Brandes’ basic algorithm
in tests with real-world social networks.
Our technical contribution is to extend the work of Baglioni et al. [3] by, roughly speaking,
additionally dealing with degree-two vertices. These vertices are much harder to deal with and
to analyze since, other than degree-one vertices, they may lie on shortest paths between two
vertices. Thus, we have to significantly refine and extend the approaches underlying Brandes [4]
and Baglioni et al. [3]. Moreover, to prove correctness and our “improved” asymptotic upper
bound we perform an extensive mathematical analysis. Notably, the work of Baglioni et al. [3]
mainly focuses on the empircial side and the algorithmic techniques there would not suffice to
prove our upper bound O(kn).
Our work is purely theoretical in spirit. To the best of our knowledge, it provides the first
theoretical “improvement” over Brandes’ algorithm. It is conceivable that our (more complicated)
algorithms finally can be turned into practically useful tools in the spirit of Brandes [4] and
Baglioni et al. [3].
Notation. We use mostly standard graph notation. Given a graph G, V (G) and E(G)
denote the vertex respectively edge set of G with n = |V (G)| and m = |E(G)|. We denote the
vertices of degree one, two, and at least three by V =1 (G), V =2 (G), and V ≥3 (G), respectively. A
path P = v0 . . . va is a graph with V (P ) = {v0 , . . . , va } and E(P ) = {{vi , vi+1 } | 0 ≤ i < a}. The
length of the path P is |E(P )|. Adding the edge {va , v0 } to P gives a cycle C = v0 . . . va v0 . The
distance dG (s, t) between vertices s, t ∈ V (G) is the length of the shortest path between s and t
in G. The number of shortest s-t–paths is denoted by σst . The number of shortest s-t–paths
containing v is denoted by σst (v). We set σst (v) = 0 if s = v or t = v (or both).
We set [j, k] := {j, j + 1, . . . k} and denote for a set X by Xi the size-i subsets of X.

2

Algorithm Overview

In this section, we review our algorithmic strategy to compute the betweenness centrality of each
vertex. Before doing so, since we build on the works of Brandes [4] and Baglioni et al. [3], we first
give the high-level ideas behind their algorithmic approaches. Then, we describe the ideas behind
our extension.
We remark that we assume throughout our paper that the input graph is connected. Otherwise,
we can process the connected components one after another.
The algorithms of Brandes [4] and Baglioni et al. [3]. Brandes [3] developed an O(nm)time algorithm which essentially runs heavily modified breadth-first searches (BFS) from each
vertex of the graph. In each of these modified BFS, Brandes’ algorithm computes the “effect” that
the starting vertex s of the modified BFS has on the betweenness centrality values of all other
2 Notably, Betweenness Centrality computations have also been studied when the input graph is a tree [17],
indicating the practical relevance of this special case. We mention in passing that in recent work [12] we employed
the parameter “feedback edge number” in terms of theoretically analyzing practically useful data redcution rules
for computing maximum-cardinality matchings.

2

vertices. More formally, the modified BFS starting at vertex s computes for each vertex v ∈ V (G):
X σst (v)
.
σst

t∈V (G)

In order to reduce the number of performed modified BFS in Brandes’ algorithm, Baglioni
et al. [3] removed in a preprocessing step all degree-one vertices from the graph. Since removing
vertices influences the betweenness centrality of the remaining vertices, Baglioni et al. [3] modified Brandes’ algorithm (without changing the worst-case running time). Concerning degree-one
vertices, observe that in each shortest path P starting at degree-one vertex v, the second vertex
in P is the single neighbor u of v. Hence, after deleting v, one only needs to store the information
that u had a neighboring degree-one vertex. By repeatedly removing degree-one vertices whole
“pending trees” can be deleted. Baglioni et al. [3] added for each vertex w of the graph a counter
Pen[w] that stores the size of the subtree that was pending on w.
Remark. In contrast to Baglioni et al. [3], we initialize for each vertex v ∈ V the value Pen[v] with
one instead of zero (so we count v as well). This is a minor technical change that simplifies most
of our formulas.
The idea of the preprocessing step of Baglioni et al. [3] is given in the next observation.
Observation 1 ([3]). Let G be a graph, let s ∈ V (G) be a degree-one vertex, and let v ∈ V (G) be
the neighbor of s. Then,
X

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

σst (v)
= Pen[v] ·
σst

X

Pen[t].

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

Hence, the influence of P
a degree-one vertex to the betweenness centrality of its neighbor can be
computed in O(1) time as w∈V (G)\{s,v} Pen[w] = norig − Pen[v] − Pen[s] where norig denotes the
number of vertices in the original graph. Baglioni et al. [3] also adapted Brandes’ algorithm in order
to compute the betweenness centrality values of the remaining vertices using the counters Pen[·].
To this end, they showed that the betweenness centrality of a vertex v that is not removed in the
preprocessing step is
CB (v) =

X

Pen[s] · Pen[t] ·

s,t∈V (G)

σst (v)
=
σst

X

γ(s, t, v).

(1)

s,t∈V (G)

Inhere, we use the following notation which simplifies many formulas in this work.
Definition 1. Let γ(s, t, v) = Pen[s] · Pen[t] ·

σst (v)
σst .

Our algorithm—basic idea. Starting with the graph where all degree-one vertices are
removed [3], our algorithm copes with degree-two vertices. In contrast to degree-one vertices,
degree-two vertices can lie on shortest paths between two other vertices. This difference makes
degree-two vertices harder to handle: Removing a degree-two vertex v in a similar way as done
with degree-one vertices (see Observation 1) affects many other shortest paths that neither start
nor end in v. Hence, we deal with degree-two vertices in a different manner. Instead of removing
vertices one-by-one as Baglioni et al. [3], we process multiple degree-two vertices at once. To
this end we exploit that consecutive degree-two vertices behave similarly. We distinguish two
possibilities for consecutive degree-two vertices captured by the following definitions.
Definition 2. Let G be a graph. A path P = v0 v1 . . . vℓ is a maximal path in G if ℓ ≥ 2, the
inner vertices v1 , v2 , . . . , vℓ−1 all have degree two in G, but the endpoints v0 and vℓ do not, that
is, degG (v1 ) = . . . = degG (vℓ−1 ) = 2, degG (v0 ) 6= 2, and degG (vℓ ) 6= 2. Moreover, P max is the set
of all maximal paths in G.

3

Definition 3. Let G be a graph. A cycle C = v0 v1 . . . vℓ v0 is a pending cycle in G if at most one
vertex in C does not have degree two in G. Moreover, C pen is the set of all pending cycles in G.
Section 3 presents a preprocessing step that deals with pending cycles. We first show how to
break the graph into two independent parts at any cut vertex (a vertex whose removal makes the
graph disconnected). These two parts can then be solved independently. Second, we show that
the betweenness centrality can be computed in O(n) time on a cycle with n vertices where each
vertex is equipped with a value Pen[·]. Putting both results together we can deal with pending
cycles: First break the graph into two parts with one part being the cycle. Then, the pending cycle
is just a cycle and we can compute the betweenness centrality for all its vertices. The remaining
part of the graph then has one pending cycle less and we can repeat this process. Overall, the
preprocessing step removes all pending cycles from the graph in O(n) time.
The rest of the algorithm deals with maximal paths (described in Section 4). Maximal paths
turn out to be more challenging than pending cycles and we are not able to remove or shrink them
in a preprocessing step. However, using standard arguments, one can show that the number of
maximal paths is upper-bounded in the feedback edge number k of the input graph:
Lemma 1. Let G be a graph with feedback edge number k containing no degree-one vertices. Then
the cardinalities |V ≥3 (G)|, |C pen |, and |P max | are upper-bounded by O(min{n, k}).
Proof. Let X ⊆ E(G) be a feedback edge set of G of size at most k. Since G does not contain any
degree-one vertices, in the forest G′ = (V (G), E(G) \ X) there are at most 2k leaves, since each
leaf must be incident to an edge in X. Since G′ is a forest, it has less vertices of degree at least
three than leaves, thus |V ≥3 (G′ )| < 2k. Observe that every edge in X can increase the degree
of its two incident vertices in G by one and thus we may obtain at most 2k additional vertices
of degree at least three in G. With this, and the fact that there are at most n vertices of degree
three, we have |V ≥3 (G)| ≤ |V ≥3 (G′ )| + 2k ∈ O(min{k, n}).
Since every pending cycle contains an edge in X, it follows that |C pen| ∈ O(min{k, n}). For a
maximal path P max observe that the path contains an edge e ∈ X, or its endpoints are in V ≥3 (G′ ).
In the latter case, for every P max there exists a unique leaf to which it is leading, otherwise G′
contains a cycle. With this we obtain |P max | ∈ O(min{k, n}).
Our algorithm will process the maximal paths one by one and compute several additional
values in O(n) time per maximal path. Using these additional values, the algorithm runs a
modified version of Brandes’ algorithm starting the modified BFS only in vertices with degree at
least three. Since there are at most O(min{k, n}) maximal paths and vertices of degree at least
three, this results in a running time of O(kn).
Our algorithm—further details. We now provide more details for our algorithm—see
Algorithm 1 for pseudocode. To this end, we use our main results in Sections 3 and 4 mainly as
black boxes and concentrate on describing the interaction between the different parts.
As mentioned earlier, we start with the preprocessing of Baglioni et al. [3] (see Lines 4 to 7).
For a degree-one vertex v we update the betweenness centrality of its neighbor u. The idea behind
this is, that if Pen[v] = 1, then the betweenness centrality of v is zero. Otherwise, the betweenness
centrality of v was computed in a previous iteration of the for-loop in Line 4. Refer to Baglioni
et al. [3] for the proof that the betweenness centrality values of all removed vertices are computed
correctly. As a consequence of the preprocessing, we have to consider the Pen[·] values and use
Equation (1) for the computation of the betweenness centrality values.
Next we compute all pending cycles and maximal paths in linear time (see Line 9).
Lemma 2. Let G be a graph. Then the set P max of all maximal paths and the set C pen of all
pending cycles can be computed in O(n + m) time.
Proof. Iterate through all vertices v ∈ V (G). If v ∈ V =2 (G), then iteratively traverse the two
edges incident to v to discover adjacent degree-two vertices until finding endpoints vℓ , vr ∈ V ≥3 (G).
If vℓ = vr , then add C pen = vℓ . . . vr vℓ to C pen. Otherwise, add P max = vℓ . . . vr to P max .
4

Algorithm 1: Algorithm for computing the betweenness centrality of a graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

26
27

Input: An undirected graph G with feedback edge number k.
Output: The betweenness centrality values of all vertices.
foreach v ∈ V (G) do
// initialization
BC[v] ← 0
// in the end the table BC will contain the betweenness centrality values
Pen[v] ← 1
while ∃v ∈ V (G) : degG (v) = 1 do
// remove degree-one vertices as done by Baglioni et al. [3]
u ← neighbor of v P
BC[u] ← 2 Pen[v] · ( w∈V (G)\{u,v} Pen[w])
// takes O(1) time [3]
delete v from G
F ← feedback edge set of G
// in O(n + m) time with a BFS
P max ← all maximal paths of G; C pen all pending cycles of G
// by Lemma 2 computable in O(n + m) time
foreach C pen ∈ C pen do
// dealing with pending cycles in O(n) time, see Section 3
update BC for all u ∈ C pen
// in O(|C pen |) time, see Proposition 5 and Lemma 5
pen
v ← vertex of C
with degree at least three (if existing)
Pen[v] ← Pen[v] + |C pen | − 1; remove each vertex u ∈ C pen \ {v} from G
foreach s ∈ V ≥3 (G) do
// some precomputations, takes O(kn) time by Lemma 4
compute dG (s, t) and σst for each t ∈ V (G) \ {s}
Inc[s, t] ← 2 · Pen[s] · Pen[t]/σst for each t ∈ V =2 (G)
Inc[s, t] ← Pen[s] · Pen[t]/σst for each t ∈ V ≥3 (G) \ {s}
foreach x0 x1 . . . xa = P max ∈ P max do
// initialize W left and W right ; takes O(n) time
left
right
W [x0 ] ← Pen[x0 ]; W
[xa ] ← Pen[xa ]
for i = 1 to a do W left [xi ] ← W left [xi−1 ] + Pen[xi ]
for i = a − 1 to 0 do W right [xi ] ← W right [xi+1 ] + Pen[xi ]
foreach x0 x1 . . . xa = P1max ∈ P max do
// case s ∈ V =2 (P1max ), see Section 4
max
max
max
foreach y0 y1 . . . yb = P2
∈P
\ {P1 } do
// case t ∈ V =2 (P2max ), see Section 4.1
max
max
/* update BC for the case v ∈ V (P1 ) ∪ V (P2 ) (cf. Definition 1)
*/
foreach v ∈ V (P1max ) ∪ V (P2max ) do BC[v] ← BC[v] + γ(s, t, v)
/* now deal with the case v ∈
/ V (P1max ) ∪ V (P2max )
*/
update Inc[x0 , y0 ], Inc[xa , y0 ], Inc[x0 , yb ], and Inc[xa , yb ]
/* now deal with the case that t ∈ V =2 (P1max ), see Section 4.2
*/
foreach v ∈ V (P1max ) do BC[v] ← BC[v] + γ(s, t, v)
update Inc[x0 , xa ]
// this deals with the case v ∈
/ V (P1max )

29

foreach s ∈ V ≥3 (G) do
// perform modified BFS from s, see Section 4.3
foreach t, v ∈ V (G) do BC[v] ← BC[v] + Inc[s, t] · σst (v)

30

return BC.

28

For every H1 , H2 ∈ C pen ∪ P max it holds that either V =2 (H1 ) ∩ V =2 (H2 ) = ∅ or H1 = H2 .
Hence, we do not need to reconsider any degree-two vertex found in the traversal above; thus we
require O(m + n) time to find all maximal paths and pending cycles.
Having computed all pending cycles, we can process them one after another (see Lines 10 to 13).
The main idea herein is that if a connected graph contains a vertex v whose removal disconnects
the graph, then we can split the graph into at least two parts whose vertex sets overlap in v. After
the splitting, we can compute the betweenness centrality values of the two parts independently.
Applying this idea to a pending cycle C pen yields the following. Let v be the connection of C pen to
the rest of the graph. Then, we can split C pen from G and update the betweenness centrality values
of all vertices in C pen (see Line 11). After that, we can remove all vertices of C pen except v (see
Line 12). To store the information that there was a pending cycle connected to v, we update Pen[v]
(see Line 13). In Section 3 we provide the details for the splitting of the graph and the algorithm
that computes the betweenness centrality values in a cycle.

5

Lastly, we need to deal with the maximal paths (see Lines 14 to 29). This part of the algorithm
is more involved and requires its own pre- and postprocessing (see Lines 14 to 21 and Lines 28
to 29 respectively). In the preprocessing, we initialize tables used frequently in the main part (of
Section 4). The postprocessing computes the final betweenness centrality values of each vertex as
this computation is too time-consuming to be executed for each maximal path. When explaining
our basic ideas, we will first present the postprocessing as this explains why certain values will be
computed before.
P
Recall that we want to compute
s,t∈V (G) γ(s, t, v) for each v ∈ V (G) (see Equation (1)).
Using the following observations, we split Equation (1) into different parts:
Observation 2. For s, t, v ∈ V (G) it holds that γ(s, t, v) = γ(t, s, v).
Proof. Since G is undirected, for every path v1 v2 . . . vℓ there also exists its reverse vℓ . . . v2 v1 .
Hence, we have σst = σts and σst (v) = σts (v), and thus γ(s, t, v) = γ(t, s, v).
Observation 3. Let G be a graph without degree-one vertices and without pending cycles. Let v ∈
V (G). Then,
X
X
X
γ(s, t, v) =
γ(s, t, v) +
γ(t, s, v)
s∈V ≥3 (G),t∈V (G)

s∈V (G),t∈V (G)

+

X

s∈V =2 (G),t∈V ≥3 (G)

γ(s, t, v) +

s∈V =2 (P1max ),t∈V =2 (P2max )
P1max 6=P2max ∈P max

X

γ(s, t, v).

s,t∈V =2 (P max )
P max ∈P max

Proof. The first two sums cover all pairs of vertices in which at least one of the two vertices is of
degree at least three. The other two sums cover all pairs of vertices which both have degree
S two.
As all vertices of degree two must be part of some maximal path we have V =2 (G) = V =2 ( P max ).
Two vertices of degree two can thus either be in two different maximal paths (third sum) or in
the same maximal path (fourth sum).
In the remaining graph, by Lemma 1, there are at most O(min{k, n}) vertices of degree at least
three and at most O(k) maximal paths. This implies that we can afford to run the modified BFS
(similar to Brandes’ algorithm) from each vertex s ∈ V ≥3 (G) in O(min{k, n}) · (n + k)) = O(kn)
time. This computes the first summand and, by Observation 2, also the second summand of the
sum given in Observation 3. However, we cannot afford to run such a BFS from every vertex
in V =2 (G). Thus, we need to compute the third and fourth summand in a different way.
Notice that the only factor in γ(s, t, v) that depends on v is the term σst (v). Our goal is then
to precompute the factor γ(s, t, v)/σst (v) = Pen[s] · Pen[t]/σst for as many vertices as possible. We
will store precomputed values in table Inc[·, ·] (see Lines 17, 25 and 27). Then, we plug this factor
into the next lemma which provides our postprocessing and will be proven in Section 4.3.
Lemma 3. Let s be a vertex and let f : V (G)2 7→ N be a function such that
Pfor each u, v ∈ V (G)
the value f (u, v) can be computed in O(τ ) time. Then, one can compute t∈V (G) f (s, t) · σst (v)
for all v ∈ V in overall O(n · τ + m) time.
Our strategy is to start the algorithm behind Lemma 3 only from vertices in V ≥3 (G) (see
Line 29). Since the term τ in the above lemma will be constant, we obtain a running time
of O(kn) for this postprocessing. The most technical part will be to precompute the factors in
Inc[·, ·] (see Lines 25 and 27). We defer the details to Sections 4.1 and 4.2. In these parts, we need
the tables W left [·], and W right [·]. These tables store values depending on the maximal path a vertex
is in. More precisely, for a vertex xi in a maximal path P max = x0 x1 . . . xa , we store in W left [xk ]
Pk
the sum of the Pen[·]-values of vertices “left of” xk in P max ; formally, W left [xk ] = i=1 Pen[xj ].
Pa−1
Similarly, we have W right [xk ] = i=k Pen[xk ]. The reason for having these tables is easy to see:
Assume for the vertex xk ∈ P max that the shortest paths to t ∈
/ V (P max ) leave P max through x0 .
Then, it is equivalent to just consider the shortest path(s) starting in x0 and simulate the vertices
between xk and x0 in P max by “temporarily increasing” Pen[x0 ] by W left [xk ]. This is also the
6

idea behind the argument that we only need to increase the values Inc[·, ·] for the endpoints of the
maximal paths in Line 25.
This leaves us with the remaining part of the preprocessing, the computation of the distances dG (s, t), the number of shortest paths σst , and Inc[s, t] for s ∈ V ≥3 (G), t ∈ V (G) (see
Lines 14 to 17). This can be done in O(kn) time as well:
Lemma 4. The initialization in the for-loop in Lines 14 to 17 of Algorithm 1 can be done in O(kn)
time.
Proof. Following Brandes [4, Corollary 4], computing the distances and the number of shortest paths from a fixed vertex s to every t ∈ V (G) takes O(m) = O(n + k) time. Once these
values are computed for a fixed s, computing Inc[s, t] for t ∈ V (G) takes O(n) time since the values Pen[s], Pen[t] and σst are known. Since by Lemma 1 there are O(min{k, n}) vertices of degree
at least three, it takes O(min{k, n} · (n + k + n)) = O(kn) time to compute Lines 14 to 17.
Putting all parts together, we arrive at our main theorem (see Section 4.3 for the proof).
Theorem 4. Betweenness Centrality can be solved in O(kn) time, where k is the feedback
edge number of the input graph.

3

Preprocessing for pending cycles

In this section, we describe our preprocessing that removes all pending cycles from the input
graph. To this end, let C pen be a pending cycle. There are two cases: Either C pen has one vertex
in V ≥3 (G) or C pen has no such vertex. In the latter case the graph is a cycle. Our strategy is as
follows: If C pen has no vertex in V ≥3 (G), then we compute all betweenness centrality values in
linear time using a dynamic program. Otherwise, we split the graph into two parts with one part
being C pen (now without a vertex in V ≥3 (G)) and the other part being the rest. After splitting
the graph, we can process the two parts independently.
We next describe the basic idea behind the splitting operation. Let C pen be a pending cycle
with v ∈ V ≥3 (G) being its connection to the rest of the graph. Obviously, every shortest path P
that starts in C pen and ends outside C pen has to pass through v. Thus, for the betweenness
centrality values of the vertices outside C pen it is not important where exactly P starts. Similarly,
for the betweenness centrality values of the vertices inside C pen it is not important where exactly P
ends. The only relevant information is the size of C pen and the rest as this determines how many
paths start in C pen and end outside C pen . Hence, we can split the graph at v (where each part
gets a copy of v). All we need to take care of is to increase the Pen[·]-value of each copy of v by
the size of the respective part. Generalizing this idea, we arrive at the following lemma.
Lemma 5 (Split Lemma). Let G be a connected graph. If there is a vertex v ∈ V (G) such that
the removing v (and all adjacent edges) from G yields k ≥ 2 connected components C1 , C2 , . . . Ck ,
then remove v, add a new vertex vi to each component Ci , make them adjacent
to all vertices
P
in the respective component that were adjacent to v, and set Pen[vi ] =
w∈V (G)\V (Ci ) Pen[w].
Computing the betweenness centrality of each connected component independently, increasing the
betweenness centrality of v by
k 
X
i=1

Ci
CB
(vi ) + (

X

s∈V (Ci )\{vi }


Pen[s])(Pen[vi ] − Pen[v])

and ignoring all new vertices vi is the same as computing the betweenness centrality in G, that is,
( C
CB i (u),
G
if u ∈ V (Ci ) \ {vi };
P
CB (u) = Pk  Ci
if u = v.
s∈V (Ci )\{vi } Pen[s])(Pen[vi ] − Pen[v]) ,
i=1 CB (vi ) + (
7

Ci
G
Proof. First, we will show that CB
(u) = CB
(u) if u ∈ V (Ci ) \ {vi } and afterwards that the
computations for v are correct. Let u ∈ V (G) \ {v} be any vertex except v in G and let Ci be the
connected component
that u is contained in after removing v from G. By definition of γ it holds
P
Ci
G
(u) and afterwards
that CB
(u) = s,t∈V (G) γ(s, t, u). We show how this can be rewritten to CB
justify the equalities.
X
γ(s, t, u)
s,t∈V (G)

=

+

γ(s, t, u) +

s,t∈V (Ci )\{vi }

s∈V (Ci )\{vi }
t∈V (G)\V (Ci )

X

γ(s, t, u) +

X

X

γ(s, t, u) + 2 ·

γ(s, t, u)

X

γ(s, t, u)

X

γ(s, vi , u) + 2 ·

X


Pen[s] (

s∈V (Ci )\{vi }

=

Ci
CB
(u)

(3)

X

γ(s, t, u)

(4)

s∈V (Ci )\{vi }
t∈V (G)\V (Ci )

s∈V (Ci )\{vi }
Ci
= CB
(u) + 2

(2)

s∈V (Ci )\{vi }
t∈V (G)\V (Ci )

s,t∈V (Ci )\{vi }
Ci
= CB
(u) − 2

γ(s, t, u)

s,t∈V (G)\V (Ci )

s∈V (G)\V (Ci )
t∈V (Ci )\{vi }

=

X

X

X

t∈V (G)\V (Ci )

Pen[t]

σst (u)
σsv (u) 
) − Pen[vi ] i
σst
σsvi
(5)

We now prove the correctness of the equalities above. First, observe that each vertex v ∈ V (G) is
either contained in V (Ci )\{vi } or in V (G)\V (Ci ) and therefore Equation (2) is only a simple case
distinction. Second, each shortest path between two vertices that are not in V (Ci ) will never pass
through any vertex in V (Ci ) \ {vi } as it would pass v twice. Hence the fourth sum in Equation (2)
is 0. The factor 2 in Equation (3) is due to symmetry of γ. To see that Equation (4) is correct,
notice that the first sum in Equation (3) is actually the betweenness centrality
of u in the connected
P
component Ci without vi . Lastly, observe that by definition Pen[vi ] = w∈V (G)\V (Ci ) Pen[w] and
by definition of v it holds v lies on all shortest path from a vertex s to any vertex t ∈ V (G) \ V (Ci ).
Thus, σst = σsvi and σst (u) = σsvi (u).
We will now show that the computations for v are correct as well. Again, we explain the
equations after we state them. First observe that each copy of v is in a different component and

8

therefore we only need to consider s, t ∈ V (G) \ {v}. Hence, it holds that
X
G
γ(s, t, v)
CB
(v) =
s,t∈V (G)\{v}

=

k
X

X

i=1 s,t∈V (Ci )\{vi }

=

X

i=1 j=1 s∈V (Ci )\{vi } t∈V (Cj )\{vj }
i6=j
k
X

k
 X
Ci
CB
(vi ) +

X

Pen[s]

k
X

k
 X
Ci
CB
(vi ) +

X


Pen[s](Pen[vi ] − Pen[v])

i=1

=

X

k
X
i=1

=

k X
k
 X
γ(s, t, v) +

k 

X
Ci
CB
(vi ) +
i=1

X

s∈V (Ci )\{vi }

Pen[t]

j=1 t∈V (Cj )\{vj }
i6=j

i=1 s∈V (Ci )\{vi }

i=1 s∈V (Ci )\{vi }

X


γ(s, t, v)

(6)

σst (v) 
σst
(7)



Pen[s] (Pen[vi ] − Pen[v])

Notice that Equation (6) is only a case distinguish between the cases that s and t are in the
same connected component or in different ones. To see that Equation (7) is correct, observe
P
P
Pk
that j=1,i6=j t∈V (Cj )\{vj } Pen[t] = t∈(V (G)\V (Ci ))\{v} Pen[t] = Pen[vi ] − Pen[v] by definition
of Pen[vi ]. This concludes the proof.
Observe that we can split all pending cycles off the graph using Lemma 5. It is easy to see that
these splits can be done in overall linear time. If the graph is split into multiple
components in the
Pk P
process, then we can just solve them independently and increase BC[v] by i=1 s∈V (Ci )\{vi } Pen[s](Pen[vi ]−
P
Pen[v]) in linear time. Notice that ki=1 |V (Ci ) \ {vi }| ≤ n. Having split the pending cycle from
the remaining graph, it remains to show that the betweenness centrality values of the vertices in
a cycle can be computed in linear time. To this end, notice that the vertices in the cycle can have
different betweenness centrality values as they can have different Pen[·]-values.
Proposition 5. Let C = x0 . . . xa x0 be a cycle. Then, the betweenness centrality of the vertices
in C can be computed in O(a) time.
Proof. We first introduce some notation needed for the proof, then we will show how to compute BC[v] for v ∈ V (C) efficiently. Finally, we prove the running time.
We denote by [xi , xj ] for 0 ≤ i, j ≤ a the vertices {xi , xi+1 mod a+1 , xi+2 mod a+1 , . . . , xj }. Similarly to W left [·] and W [·, ·] on maximal paths we define


Pen[xi ],
if i = j;


i
 left
X
left
if i < j;
i ],
W left [xi ] =
Pen[xi ], and W [xi , xj ] = W left[xj ] − W left[xi ] + Pen[x
left

W
[x
]
−
W
[x
]
+
W
[x
]

a
i
j
k=0

if i > j.

+ Pen[xi ],

The value W [xi , xj ] computes the sum of all values Pen[·] from xi to xj , clockwise. Further, we
denote by ϕ(i) = ( a+1
2 + i) mod a + 1 the index that is “opposite” to i on the cycle. Notice that
if ϕ(i) ∈ N, then xϕ(i) is the unique vertex in C to which there are two shortest paths from xi ,
one visiting xi+1 mod a+1 and one visiting xi−1 mod a+1 . Otherwise, if ϕ(i) 6∈ N, then there is only
one shortest path from xk to any t ∈ V (C). For the sake of convenience in the next parts of the
proof, if ϕ(i) 6∈ N, we say that Pen[xϕ(xi ) ] = 0. Further, by ϕleft (i) = ⌈ϕ(i)⌉ − 1 mod a + 1 we
denote the index of the vertex to the left of index ϕ(i) and by ϕright (i) = ⌊ϕ(i)⌋ + 1 mod a + 1
the index of the vertex to the right of index ϕ(i).
We now lay out the algorithm. For every vertex xk , 0 ≤ k ≤ a, we need to compute
BC[xk ] :=

X

γ(s, t, xk ) =

a
X
X

i=0 t∈V (C)

s,t∈V (C)

9

γ(xi , t, xk ).

We compute these values in a dynamic programming manner. We first show how to compute the
betweenness centrality of x0 , and then present how to compute values BC[xk+1 ] for 0 ≤ k ≤ a − 1
given the value BC[xk ].
Towards computing BC[x0 ], observe that γ(xi , t, x0 ) = 0 if xi = x0 or t = x0 . Also, for every
shortest path starting in xϕ(0) and ending in some xj , 1 ≤ j ≤ a, it holds that dC (xϕ(0) , xj ) <
dC (xϕ(0) , x0 ). Thus there is no shortest path starting in xϕ(0) that visits x0 . Hence, we do not
need to consider the cases i = 0 or i = ϕ(0) and we have
a
X

BC[x0 ] =

X

γ(xi , t, x0 )

i=0
t∈V (C)
06=i6=ϕ(0)
ϕleft (0)

X

=

i=1

a
X

X

γ(xi , t, x0 ) +

X

X

Pen[xi ] · Pen[t] ·

i=1

t∈V (C)

a
X

+

γ(xi , t, x0 )

i=ϕright (0) t∈V (C)

t∈V (C)

ϕleft (0)

=

X

X

σxi t (x0 )
σxi t

Pen[xi ] · Pen[t] ·

i=ϕright (0) t∈V (C)

σxi t (x0 )
σxi t

By definition of ϕ(i) we have that dC (xi , xϕleft (i) ) = dC (xi , xϕright (i) ) < a+1
2 . Hence, there is a
unique shortest path from xi to xϕleft (i) visiting xi+1 mod a+1 , and there is a unique shortest path
from xi to xϕright (i) visiting xi−1 mod a+1 . This gives us that in the equation above, in the first
sum, all shortest paths from xi to t ∈ [xϕright (i) , xa ] visit x0 , and in the second sum, all shortest
paths from xi to t ∈ [x1 , xϕleft (i) ] visit x0 . If ϕ(xi ) ∈ N, then there are two shortest paths from xi
to xϕ(i) , and one of them visits x0 . With this we can rewrite the sum as follows:
BC[x0 ] =

ϕleft (0) 

X

Pen[xi ] · Pen[xϕ(i) ] ·

i=1

a
X

+

i=ϕright (0)
ϕ

=
+



1
+
2

Pen[xi ] · Pen[xϕ(i) ] ·

X

Pen[xi ] · Pen[t]

t∈[xϕright (i) ,xa ]

1
+
2

X



Pen[xi ] · Pen[t]

t∈[x1 ,xϕleft (i) ]



left

X(0)
i=1
a
X

Pen[xi ]

i=ϕright (0)

1

2

Pen[xi ]

Pen[xϕ(i) ] + W [xϕright (i) , xa ]
1

2




Pen[xϕ(i) ] + W [x1 , xϕleft (i) ] .

Since the values Pen[·] are given, the values W left [·] can be precomputed in O(a) time and
thus, when computing BC[x0 ], the values W [·, ·] can be obtained in constant time. The values ϕ(i), ϕleft (i) and ϕright (i) can be computed in constant time as well, and thus it takes O(a)
time to compute BC[x0 ].
Assume now that we have computed BC[xk ]. Then we claim that BC[xk+1 ], 0 ≤ k < a, can
be computed as follows:

BC[xk+1 ] = BC[xk ] − Pen[xk+1 ] Pen[xϕ(k+1) ] + 2W [xϕright (k+1) , xk−1 mod a+1 ]
(8)
+ Pen[xk ] Pen[xϕ(k) ] + 2W [xk+2 mod a+1 , xϕleft (k) ]).
To this end, observe that all shortest paths in C that visit xk also visit xk+1 , except for those
paths that start or end in xk+1 . Likewise, all shortest paths in C that visit xk+1 also visit xk ,
10

except for those paths that start or end in xk . Hence, to compute BC[xk+1 ] from BC[xk ], we
need to subtract the γ-values for shortest paths starting in xk+1 and visiting xk , and we need to
add the γ-values for shortest paths starting in xk and visiting xk+1 . Since by Observation 2, each
path contributes the same value to the betweenness centrality as its reverse, and thus
X
γ(xk , t, xk+1 ) − γ(xk+1 , t, xk ).
(9)
BC[xk+1 ] = BC[xk ] + 2 ·
t∈V (C)

With a similar argumentation as above for the computation of BC[x0 ] one can show that shortest
paths starting in xk and visiting xk+1 must end in t ∈ [xk+2 , xϕleft (k) ], or in xϕ(k+1) . Shortest
paths starting in xk+1 and visiting xk must end in t ∈ [xϕright (k+1) , xk−1 ], or in xϕ(k) . As similarly
stated above, for both i = k and i = k + 1, some fixed vertex xj is visited by only half of the
shortest paths from xi to xϕ(i) . With the arguments above we can rewrite Equation (9) to obtain
the claimed Equation (8).
For the running time, after precomputing the values W left [·] and BC[x0 ] in O(a) time, we can
compute each of the values BC[xk+1 ] for 0 ≤ k < a in constant time. This yields an overall
running time of O(a).

4

Dealing with maximal paths

In this section, we put our focus on degree-two vertices contained in maximal paths in order to
compute the betweenness centrality CB (v) (cf. Equation (1)) for all v ∈ V (G) in overall O(kn)
time. In the end of this section, we also prove Theorem 4.
Based on Observation 3, we compute Equation (1) in three steps. By starting a modified BFS
from vertices in V ≥3 (G) similar to Baglioni et al. [3] and Brandes [4], we can compute
X
X
γ(t, s, v) +
γ(s, t, v)
s∈V ≥3 (G),t∈V (G)

s∈V =2 (G),t∈V ≥3 (G)

in O(kn) time. We show in the next two subsections how to compute the remaining two parts
given in Observation 3. In the last subsection we describe the postprocessing and prove our main
theorem.

4.1

Paths with endpoints in different maximal paths

In this subsection, we look at shortest paths between pairs of maximal paths P1max = x0 . . . xa
and P2max = y0 . . . yb whose endpoints are in different maximal paths, and how to efficiently
compute how these paths affect the betweenness centrality. Our goal is to prove the following:
Proposition 6. The following can be computed for all v ∈ V (G) in overall O(kn) time:
X
γ(s, t, v).
s∈V =2 (P1max ),t∈V =2 (P2max )
P1max 6=P2max ∈P max

Notice that in the course of the algorithm, we first gather all increments to Inc[·, ·] and in the
final step compute for each s, t ∈ V ≥3 (G) the values Inc[s, t] · σst (v) in O(m) time (Lemma 3).
This postprocessing (see Lines 28 and 29 in Algorithm 1) can be done in overall O(kn) time. To
keep the following proofs simple we assume that these values Inc[s, t] · σst (v) can be computed in
constant time for every s, t ∈ V ≥3 (G) and v ∈ V (G).
For every pair P1max 6= P2max ∈ P max of maximal paths, we consider two cases: First, we look
at how the shortest paths between vertices in P1max and P2max affect the betweenness centrality of
those vertices that are not contained in the two maximal paths, and second, how they affect the
betweenness centrality of those vertices that are contained in the two maximal paths. Finally, we
prove Proposition 6.
11

Throughout the following proofs, we will need the following definitions. Let t ∈ P2max . Then we
right
choose vertices xleft
∈ V =2 (P1max ) such that shortest paths from t to s ∈ {x1 , x2 , . . . , xleft
t , xt
t } =:
right
left
max
Xt enter P1
only via x0 , and shortest paths from t to s ∈ {xt , . . . , xa−2 , xa−1 } =: Xtright
max
enter P1
only via xa . There may exist a vertex xmid
to which there are shortest paths both
t
via x0 and via xa . For computing the indices of those vertices, we determine index i such
that dG (x0 , t) + i = dG (xa , t) + b − i which is equivalent to i = 21 (a − dG (x0 , t) + dG (xa , t)).
If i is integral, then xmid
= xi , xleft
= xi−1 and xright
= xi+1 . Otherwise, xmid
does not exist,
t
t
t
t
right
left
mid
and xt = xi−1/2 and xt
= xi+1/2 . For easier argumentation, if xt does not exist, then we
say that Pen[xmid
] = σtxmid
(v)/σ
= 0, and hence, γ(xmid
, t, v) = 0. For computing the indices
txmid
t
t
t
t
mid
of xleft
and xright
note that t = yj for some 1 ≤ j < b. Since we compute the distances
t , xt
t
between all pairs of vertices of degree at least three beforehand, the value i can be computed in
constant time.

4.1.1

Vertices outside of the maximal paths

We now show how to compute how the shortest paths between two fixed maximal paths P1max
and P2max affect the betweenness centrality of vertices that are not contained in P1max or in P2max ,
that is v ∈ V (G) \ (V (P1max ) ∪ V (P2max )). Recall that in the final step of the algorithm we compute
the values Inc[s, t] · σs,t (v) for every s, t ∈ V ≥3 (G) and v ∈ V (G). Thus, to keep the following
proof simple, we assume that these values can be computed in constant time.
Lemma 6. Let P1max 6= P2max ∈ P max , P1max = x0 . . . xa , P2max = y0 . . . yb . Then, assuming
that the values dG (s, t) and W left [v] and W right [v] are known for s, t ∈ V ≥3 (G) and v ∈ V =2 (G)
respectively, and that the values Inc[s, t] · σst (v) can be computed in constant time for every s, t ∈
V ≥3 (G) and v ∈ V (G), the following can be computed for all v ∈ V (G) \ (V (P1max ∪ V (P2max ))
in O(b) time:
X
γ(s, t, v).
(10)
s∈V =2 (P1max ),t∈V =2 (P2max )

Proof. WePfix P1max 6= P2max ∈ P max with P1max = x0 . . . xa and P2max = y0 . . . yb . We show how to
compute s∈V =2 (P max ) γ(s, t, v) for a fixed t ∈ V =2 (P2max ) and v ∈ V (G) \ (V (P1max ) ∪ V (P2max )).
1
Afterwards we analyze the time required.
Since we can split the vertices in V =2 (P1max ) into those that can be reached from t via both x0
and xa , only via x0 , or only via xa , we have
X
X
X
γ(s, t, v).
(11)
γ(s, t, v) +
γ(s, t, v) = γ(xmid
, t, v) +
t
s∈V =2 (P1max )

s∈Xtleft

s∈Xtright

By definition of maximal paths, all shortest paths from s ∈ V =2 (P1max ) to t visit either y0 or yb .
For each ψ ∈ {x0 , xa } let S(t, ψ) be a maximal subset of {y0 , yb } such that for each ϕ ∈ S(t, ψ) there
is a shortest st-path via ψ and ϕ. Then, for s ∈ Xtleft, all st-paths visit x0 and ϕ ∈ S(t, x0 ). Hence,
P
P
we have that σst = ϕ∈S(t,x0 ) σx0 ϕ and σst (v) = ϕ∈S(t,x0 ) σx0 ϕ (v). Analogously, for s ∈ Xtright
P
may
we have that σst = ϕ∈S(t,xa ) σxa ,ϕ and the similar equality for σst (v). Paths from t to xmid
t
P
P
visit x0 and ϕ ∈ S(t, x0 ) or xa and ϕ ∈ S(t, xa ). Hence, σtxmid
= ϕ∈S(tx0 ) σx0 ϕ + ϕ∈S(t,xa ) σxa ϕ .
t
The equality holds analogously for σtxmid
(v).
With
this
at
hand,
we can simplify the computation
t
of the first sum of Equation (11):
X
X
σst (v)
Pen[s] · Pen[t] ·
γ(s, t, v) =
σst
s∈Xtleft
s∈Xtleft
P
 X

ϕ∈S(t,x0 ) σx0 ϕ (v)
=
Pen[s] · Pen[t] · P
ϕ∈S(t,x0 ) σx0 ϕ
s∈Xtleft
P
ϕ∈S(t,x0 ) σx0 ϕ (v)
left left
.
(12)
= W [xt ] · Pen[t] · P
ϕ∈S(t,x0 ) σx0 ϕ
12

Analogously,
X

γ(s, t, v) = W

right

[xright
]
t

s∈Xtright

and
γ(xmid
, t, v)
t

=

Pen[xmid
]
t

· Pen[t] ·

P

With this we can rewrite Equation (11) as
X
γ(s, t, v)

P

ϕ∈S(t,xa )
· Pen[t] · P

ϕ∈S(t,x0 )

P

ϕ∈S(t,xa )

σx0 ϕ (v) +

ϕ∈S(t,x0 )

σxa ϕ (v)

σx0 ϕ +

σxa ϕ

P

Pϕ∈S(t,xa )

ϕ∈S(t,xa )

,

σxa ϕ (v)

(13)

.

(14)

σx0 ϕ (v)

(15)

σxa ϕ

s∈V =2 (P1max )

(12),(13),(14)

=

W left [xleft
t ] · Pen[t]
P
·
ϕ∈S(t,x0 ) σx0 ϕ

X

σx0 ϕ (v)

ϕ∈S(t,x0 )

X
W right [xright
] · Pen[t]
t
P
σxa ϕ (v)
·
ϕ∈S(t,xa ) σxa ϕ
ϕ∈S(t,xa )
P
P
ϕ∈S(t,xa ) σxa ϕ (v)
ϕ∈S(t,x0 ) σx0 ϕ (v) +
mid
P
P
.
+ Pen[xt ] · Pen[t] ·
σ
+
ϕ∈S(t,xa ) σxa ϕ
ϕ∈S(t,x0 ) x0 ϕ

+

By joining values σx0 ϕ (v) and σxa ϕ (v) we obtain
X
γ(s, t, v)
s∈V =2 (P1max )

=

 W left [xleft ] · Pen[t]

Pen[xmid
] · Pen[t]
t
t
P
P
·
+P
ϕ∈S(t,xa ) σxa ϕ
ϕ∈S(t,x0 ) σx0 ϕ
ϕ∈S(t,x0 ) σx0 ϕ +

X

ϕ∈S(t,x0 )

 W right [xright ] · Pen[t]

X
Pen[xmid
] · Pen[t]
t
t
P
P
σxa ϕ (v)
·
+P
ϕ∈S(t,xa ) σxa ϕ
ϕ∈S(t,xa ) σxa ϕ
ϕ∈S(t,x0 ) σx0 ϕ +
ϕ∈S(t,xa )
X
X
σxa ϕ (v).
σx0 ϕ (v) + X2 ·
=: X1 ·
+

ϕ∈S(t,x0 )

(16)

ϕ∈S(t,xa )

We need to increasee the betweenness centrality of all vertices on shortest paths from s to t
via x0 by the value of Term (15), and those shortest paths via xa by the value of Term (16). By
Lemma 3, increasing Inc[s, t] by some value A ensures the increment of the betweenness centrality
of v by A · σst (v) for all vertices v that are on a shortest path between s and t. Hence, increasing Inc[x0 , ϕ] for every ϕ ∈ S(t, x0 ) by X1 is equivalent to increasing the betweenness centrality
of v by the value of Term (15). Analogously, increasing Inc[xa , ϕ] for every ϕ ∈ S(t, xa ) by X2 is
equivalent to increasing the betweenness centrality of v by the value of Term (16).
We now have incremented Inc[ψ, ϕ] for ψ ∈ {x0 , xa } and ϕ ∈ {y0 , yb } by certain values, and
we have shown that this increment is correct, if the vertices that are on the shortest paths from ψ
to ϕ are not contained in V (P1max ) or V (P2max ). We still need to show that we increase Inc[ψ, ϕ]
only if there is no shortest path between ϕ and ψ visiting inner vertices of P1max or P2max . Let ϕ̄ 6=
ϕ be the second endpoint of P2max , and let dG (ψ, ϕ) = dG (ψ, ϕ̄) + dG (ϕ̄, ϕ), that is, there is
a shortest path between ψ and ϕ that visits the inner vertices of P2max . Then, for all 1 ≤
i < b, dG (ψ, ϕ) + dG (ϕ, yi ) > dG (yi , ϕ̄) + dG (ϕ̄, ψ), that is, there is no shortest path from yi
to ψ via ϕ, and thus Inc[ψ, ϕ] will not be increased. The same holds if dG (ψ, ϕ) = dG (ψ, ψ̄) +
dG (ψ̄, ϕ). Increasing Inc[ψ, ϕ] also does not affect the betweenness centrality of vertices ψ and ϕ
since σψϕ (ψ) = σψϕ (ϕ) = 0.
13

Finally, we analyze the running time. The values W left [·], W right [·] and Pen[·] as well as the
distances and number of shortest paths between all pairs of vertices of degree at least three are
assumed to be known. With this, S(t, x0 ) and S(t, xa ) can be computed in constant time. Hence,
we have that the values X1 and X2 can be computed in constant time for a fixed t ∈ V =2 (P2max ).
Thus the running time needed to compute the increments of Inc[·, ·] is upper-bounded by O(b).
4.1.2

Vertices inside the maximal paths

We now consider how the betweenness centrality of vertices inside of a pair P1max 6= P2max ∈ P max
of maximal paths is affected by shortest paths between vertices in the two maximal paths.
Observe that, when iterating through all pairs P1max 6= P2max ∈ P max , one will encounter the
pair (P1max , P2max ) and its reverse (P2max , P1max ). Since our graph is undirected, instead of looking
at the betweenness centrality of the vertices in both maximal paths, it suffices to consider only
the vertices inside the second maximal path of the pair. This is shown in the following lemma.
Lemma 7. Computing for every P1max 6= P2max ∈ P max , for v ∈ V (P1max ) ∪ V (P2max )
X
γ(s, t, v)

(17)

s∈V =2 (P1max ),t∈V =2 (P2max )

is equivalent to computing for every P2max 6= P2max ∈ P max , for each v ∈ V (P2max )
X

γ(s, t, v), if v ∈ V (P1max ) ∩ V (P2max );



s∈V =2 (P1max ),t∈V =2 (P2max )
X
Xv =

γ(s, t, v), otherwise.
2
·


s∈V =2 (P1max ),t∈V =2 (P2max )

Proof. We will first assume that V (P1max ) ∩ V (P2max ) = ∅ for every P1max 6= P2max ∈ P max , and
will discuss the special case V (P1max ) ∩ V (P2max ) 6= ∅ afterwards.
max 
For every fixed {P1max , P2max } ∈ P 2 , for every v ∈ V (P2max ), we compute
X
X
γ(s, t, v),
γ(s, t, v) +
s∈V =2 (P2max ),t∈V =2 (P1max )

s∈V =2 (P1max ),t∈V =2 (P2max )

and since by Observation 2, γ(s, t, v) = γ(t, s, v), this is equal to
X
γ(s, t, v)
2·

(18)

s∈V =2 (P1max ),t∈V =2 (P2max )

Analogously, for every w ∈ V (P1max ), we compute
X
2·

γ(s, t, w).

s∈V =2 (P1max ),t∈V =2 (P2max )

Thus, computing Sum (18) for v ∈ V (P2max ) for every pair P1max 6= P2max ∈ P max is equivalent to computing Sum (17) for v ∈ V (P1max ) ∪ V (P2max ) for every pair P1max 6= P2max ∈ P max ,
since when iterating over pairs of maximal paths we will encounter both the pairs (P1max , P2max )
and (P2max , P1max ).
If there exists a v ∈ V (P1max ) ∩ V (P2max ), then it is covered once when performing the computations for (P1max , P2max ), and once when performing the computations for (P2max , P1max ). Hence, we
are doing computations twice. We compensate for this by dividing the values of the computations
in half, that is, we compute
X
γ(s, t, v)
s∈V =2 (P1max ),t∈V =2 (P2max )

for all P1max 6= P2max , for vertices v ∈ V (P1max ) ∩ V (P2max ).
14

With this at hand we can show how to compute Xv for each v ∈ V (P2max ), for a pair P1max 6=
∈ P max of maximal paths. To this end, we show the following lemma.

P2max

Lemma 8. Let P1max 6= P2max ∈ P max , P1max = x0 . . . xa , P2max = y0 . . . yb . Then, given that the
values dG (s, t) and W left [v] and W right [v] are known for s, t ∈ V ≥3 (G) and v ∈ V =2 (G) respectively,
the following can be computed for v ∈ V (P2max ) in O(b) time:
X
γ(s, t, v).
(19)
s∈V =2 (P1max ),t∈V =2 (P2max )

Proof. Let P1max = x0 . . . xa , P2max = y0 . . . yb . For v = yi , 0 ≤ i ≤ b, we need to compute
X

γ(s, t, yi ) =

=2

s∈V
(P1max )
t∈V =2 (P2max )

s∈V

X

=2 (P max )
1

b−1
X

γ(s, yk , yi ) =

b−1
X

X

γ(s, yk , yi ).

(20)

k=1 s∈V =2 (P1max )

k=1

For easier reading, we define for 0 ≤ i ≤ b and for 1 ≤ k < b
X
γ(s, yk , yi ).
λ(yk , yi ) =
s∈V =2 (P1max )

Recall that all shortest paths from yk to s ∈ Xyright
visit x0 and all shortest paths from yk
k
to s ∈ Xyright
visit
x
.
Recall
also
that
there
may
exist
a
unique vertex xmid
a
yk from which there are
k
shortest paths to yk via x0 and via xa .
With this at hand, we have
X
X
λ(yk , yi ) = γ(xmid
γ(s, yk , yi )
γ(s, yk , yi ) +
yk , yk , yi ) +
s∈Xyleft

s∈Xyright
k

k

= Pen[xmid
yk ] · Pen[yk ] ·

σyk xmid
(yi )
y
k

σyk xmid
y
k

+

σsyk (yi )
Pen[s] · Pen[yk ] ·
+
σsyk
left

X

s∈Xy

k

X

Pen[s] · Pen[yk ] ·

s∈Xyright
k


σyk xmid
(yi )
yk
= Pen[yk ] · Pen[xmid
yk ] ·
σyk xmid
yk
X σsy (yi )
k
+ W left [xleft
+ W right [xright
yk ] ·
yk ] ·
σsyk
left
s∈Xy

k

X

s∈Xyright
k

σsyk (yi )
σsyk

σsyk (yi ) 
.
σsyk

(21)

Next, we rewrite λ in such a way that we can compute it in constant time. For this, we need
to make the values σ independent of s and yi . To this end, note that if k < i, yi is visited only by
those shortest paths from yk to s ∈ V =2 (P1max ) that also visit yb . If k > i, then yi is only visited
by those paths that also visit y0 . Hence, we need to know whether there are shortest paths from yk
to some endpoint of P1max via either y0 or yb . For this we define η(yk , ϕ, ψ), which informally tells
us whether there is a shortest path from yk , 1 ≤ k < b, to ψ ∈ {x0 , xa } via ϕ ∈ {y0 , yb }. Formally,
(
1, if dG (yk , ϕ) + dG (ϕ, ψ) = dG (yk , ψ);
η(yk , ϕ, ψ) =
0, otherwise.
We now show how to compute σsyk (yi )/σsyk . Let ω = yb if k < i, and ω = y0 if k > i. As stated
above, for yi to be on a shortest path from yk to s ∈ V =2 (P1max ), the path must visit ω. If we
have s ∈ Xyleft
, then the shortest paths enter P1max via x0 , and σsyk (yi )/σsyk = σx0 yk (yi ) /σx0 yk
k
15

for s ∈ V =2 (P1max ). Notice that there may be shortest syk -paths that go via y0 and syk -paths
that go via yb . Thus we have
σx0 yk (yi )
η(yk , ω, x0 )σx0 ω
.
=
σx0 yk
η(yk , y0 , x0 )σx0 y0 + η(yk , yb , x0 )σx0 yb

(22)

With σx0 yk (yi ) we count the number of shortest x0 yk -paths visiting yi . Notice that any such path
must visit ω. If there is such a shortest path visiting ω, then all shortest x0 yk -paths visit yi , and
since there is only one shortest ωyk -path, the number of shortest x0 yk -paths visiting ω is equal to
the number of shortest x0 ω-paths, which is σx0 ω .
If s ∈ Xyright
, then
k
η(yk , ω, xa )σxa ω
σsyk (yi )
.
=
σsyk
η(yk , y0 , xa )σxa y0 + η(yk , yb , xa )σxa yb

(23)

Shortest paths from yk to xmid
yk may visit any ϕ ∈ {y0 , yb } and ψ ∈ {x0 , xa }, and thus
σyk xmid
(yi )
y
k

σyk xmid
y

P

= P

ψ∈{x0 ,xa }

ϕ∈{y0 ,yb }

k

η(yk , ω, ψ)σψω

P

ψ∈{x0 ,xa }

η(yk , yb , ψ)σψyb

.

(24)

With this, we made the values of σ independent of s and yi . We define
P

ψ∈{x0 ,xa } η(yk , ω, ψ)σψω
mid
P
κ(yk , ω) = Pen[yk ] · Pen[xyk ] · P
ϕ∈{y0 ,yb }
ψ∈{x0 ,xa } η(yk , ϕ, ψ)σψϕ
η(yk , ω, x0 )σx0 ω
η(yk , y0 , x0 )σx0 y0 + η(yk , yb , x0 )σx0 yb

η(yk , ω, xa )σxa ω
.
+ W right [xright
]
·
yk
η(yk , y0 , xa )σxa y0 + η(yk , yb , xa )σxa yb

+ W left [xleft
yk ] ·

Recall that W left [xj ] =
λ(yk , yi )

=

Pj

i=1

Pen[xi ] for 1 ≤ j < b. We can observe that if k < i, then


σyk xmid
(yi )
yk
Pen[yk ] · Pen[xmid
yk ] ·
σyk xmid
yk
X
X
σsyk (yi )
σsyk (yi ) 
+
Pen[s] ·
Pen[s] ·
+
σsyk
σsyk
left
right
s∈Xy

s∈Xyk

k

(22),(23),(24)

=

Pen[yk ] ·



Pen[xmid
yk ]

P

ψ∈{x0 ,xa }

·P

ϕ∈{y0 ,yb }

η(yk , yb , ψ)σψyb

P

ψ∈{x0 ,xa }

η(yk , ϕ, ψ)σψϕ

η(yk , yb , x0 )σx0 yb
η(yk , y0 , x0 )σxa y0 + η(yk , yb , x0 )σxa yb

η(yk , yb , xa )σxa yb
+ W right [xright
= κ(yk , yb ).
yk ] ·
η(yk , y0 , xa )σxa y0 + η(yk , yb , xa )σxa yb

+ W left [xleft
yk ] ·

Analogously, if k > i, then λ(yk , yi ) = κ(yk , y0 ). Notice that if k = i, then σsyk (yi ) = 0, and
thus γ(s, yk , yi ) = λ(yk , yi ) = 0. Hence, we can rewrite Sum (20) as
b−1
X

X

k=1 s∈V =2 (P1max )

γ(s, yk , yi ) =

b−1
X

λ(yk , yi ) =

k=1
k6=i

i−1
X

λ(yk , yi ) +

i−1
X

κ(yk , yb ) +

k=1

=

k=1

16

b−1
X


λ(yk , yi )

b−1
X


κ(yk , y0 ) .

k=i+1

k=i+1

Now we can show how to compute Sum (19) in O(b) time. For 0 ≤ i ≤ b we define ρi =
Pi−1
Pb−1
Pb−1
k=1 κ(yk , yb ) +
k=i+1 κ(yk , y0 ), which is equal to Sum (19). Then, ρ0 =
k=1 κ(yk , y0 )
and ρi+1 = ρi −κ(yi+1 , yb )+κ(yi , y0 ). The value of ρ0 can be computed in O(b) time. Every ρi , 1 ≤
i ≤ b, can then be computed in constant time, since the values of Pen[·], W left [·], W right [·] and
the distances and number of shortest paths between all pairs of vertices of degree at least three
are assumed to be known. Hence, computing all ρi , 0 ≤ i ≤ b and thus computing Sum (19) for
every v ∈ V (P2max ) takes O(b) time.
We are now ready to combine Lemmata 6 to 8 to prove Proposition 6. As mentioned above,
to keep the proposition simple, we assume that the values Inc[s, t] · σst (v) can be computed in
constant time for every s, t ∈ V ≥3 (G) and v ∈ V (G). In fact, these values are computed in the
last step of the algorithm taking overall O(kn) time (see Lines 28 and 29 in Algorithm 1 and
Lemma 3).
Proposition 6 (Restated). The following value can be computed for all v ∈ V (G) in overall O(kn)
time:
X
γ(s, t, v).
s∈V =2 (P1max ),t∈V =2 (P2max )
P1max 6=P2max ∈P max

Proof. Let P1max 6= P2max ∈ P max . Then, for each v ∈ V (G) = (V (G) \ (V (P1max ) ∪ V (P2max ))) ∪
(V (P1max ) ∪ V (P2max )), we need to compute
X
γ(s, t, v).
(25)
s∈V =2 (P1max ),t∈V =2 (P2max )

We first compute in O(kn) time the values dG (s, t) and σst for every s, t ∈ V ≥3 (G), as well as
the values W left [v], and W right [v] for every v ∈ V =2 (G), see Lines 14 to 21 in Algorithm 1. By
Lemma 6 we then can compute Sum (25) in O(b) time for v ∈ V (G)\(V (P1max )∪V (P2max )). Given
the values ρi of Lemma 8 we can compute values Xv of Lemma 7 for v = yi ∈ V (P2max ) as follows:
(
ρi , if v ∈ V (P1max ) ∩ V (P2max );
Xv = Xy i =
2ρi , otherwise.
This can be done in constant time for a single v ∈ V (P2max ), and hence, in O(b) time overall. Thus,
by Lemma 7, we can compute Sum (25) for V (P1max ) ∪ V (P2max ) in O(b) = O(|V (P2max )|) time.
Sum (25) must be computed for every pair P1max 6= P2max ∈ P max . Thus overall we require



X
X
X

|V (P2max )| ⊆ O
|V =2 (P2max )| + |V ≥3 (P2max )|
O
P1max
6=P2max ∈P max

P1max ∈P max P2max ∈P max
P1max 6=P2max

⊆O



X

n + min{k, n}

P1max ∈P max



(26)


⊆ O k(n + min{k, n}) = O(kn)

time. By Lemma 1 there are O(k) vertices of degree at least three and O(k) maximal paths. Since
the number of vertices of degree at least three can also be upper-bounded by O(n), Equation (26)
holds.

4.2

Paths with endpoints in the same maximal path

In this subsection, we look at shortest paths starting and ending in a maximal path P max =
x0 . . . xa and how to efficiently compute how these paths affect the betweenness centrality. Our
goal is to prove the following:

17

Proposition 7. The following value can be computed for each v ∈ V (G) in overall O(kn) time:
X
γ(s, t, v).
s,t∈V =2 (P max )
P max ∈P max

Notice that in the course of the algorithm, as in Section 4.1, we first gather all increments
to Inc[·, ·] and in the final step compute for each s, t ∈ V ≥3 (G) the values Inc[s, t] · σst (v) in O(m)
time (Lemma 3). This postprocessing (see Lines 28 and 29 in Algorithm 1) can be done in overall O(kn) time (see Lemma 3). To keep the following proofs simple we assume that these values Inc[s, t] · σst (v) can be computed in constant time for every s, t ∈ V ≥3 (G) and v ∈ V (G).
Let P max = x0 x1 . . . xa , where x0 , xa ∈ V ≥3 (G) and xi ∈ V =2 (G) for 1 ≤ i ≤ a − 1. Then
X

γ(s, t, v) =

s,t∈V =2 (P max )

X

γ(xi , xj , v) = 2 ·

a−1
X a−1
X

γ(xi , xj , v).

i=1 j=i+1

i,j∈[1,a−1]

For the sake of readability we say that v ∈ [xp , xq ], p < q, if there exists an k ∈ [p, q] such that v =
xk , and v ∈
/ [xp , xq ] otherwise. We will distinguish between two different cases that we then treat
in corresponding subsubsections: Either v ∈ [xi , xj ] or v ∈
/ [xi , xj ]. We will show that both cases
can be solved in P
overall O(a) time for P max . Doing this for all maximal paths results in an overall
running time of P max ∈P max V =2 (P max ) ∈ O(n). In the calculations we will distinguish between
the two main cases—all shortest xi xj -paths are fully contained in P max , or all shortest xi xj -paths
leave P max —and the corner case that there are some shortest paths inside P max and some that
partially leave it. Observe that for any fixed pair i < j the distance between xi and xj is given
by din = j − i if the shortest path is contained in P max and by dout = i + dG (x0 , xa ) + a − j if
shortest xi xj -paths leave P max . The corner case that there are shortest paths both inside and
outside of P max occurs when din = dout . In this case it holds that j − i = i + dG (x0 , xa ) + a − j
which is equivalent to
j =i+

dG (x0 , xa ) + a
,
2

(27)

where j is an integer smaller than a. For convenience, we will again use a notion of “mid-elements”
for a fixed starting vertex xi . We distinguish between the two cases that this mid-element has
dG (x0 ,xa )+a
−
and jmid
=
a higher index in P max or a lowerone. Formally, we say that i+
mid = i +
2
dG (x0 ,xa )+a
j−
.
We
also
distinguish
between
the
(v)/σ
.
We
next
analyze
the
factor
σ
xi xj
xi xj
2
cases v ∈ V (P max ) and v ∈
/ V (P max ). Observe that


0,
if dout < din ∧ v ∈ [xi , xj ] or din < dout ∧ v ∈
/ [xi , xj ];





if din < dout ∧ v ∈ [xi , xj ];
1,



if dout < din ∧ v ∈
/ [xi , xj ] ∧ v ∈ V (P max );

1,
σxi xj (v)  σx0 xa (v) , if d < d ∧ v ∈
/ V (P max );
out
in
=
(28)
σx0 xa
 1
σxi xj


,
if
d
=
d
∧
v
∈
[x
,
x
];
in
out
i
j

σx0 xa +1


σx0 xa

max

,
if
d
=
d
∧
v
∈
/
[x
,
x
);

in
out
i
j ] ∧ v ∈ V (P
σx0 xa +1



σ
(v)
x
x
 0 a , if din = dout ∧ v ∈
/ V (P max ).
σx x +1
0 a

The denominator σxo xa + 1 is correct since there are σx0 xa shortest paths from x0 to xa (and
therefore σx0 xa shortest paths from xi to xj that leave P max ) and one shortest path from xi
to xj within P max . Notice that if there are shortest paths that are not contained in P max ,
then dG (x0 , xa ) < a as we consider the case that 0 < i < j < a. Thus, P max is not a shortest path from x0 to xa .

18

4.2.1

Paths completely contained in a maximal path

We now will compute the value for all paths that only consist of vertices in P max , that is, we will
compute for each xk with i < k < j in overall O(a) time by a dynamic program
2·

a−1 X
a−1
X

γ(xi , xj , xk ).

i=1 j=i+1

This can be simplified to
X
2·

X

X

γ(xi , xj , xk ) = 2 ·

X

γ(xi , xj , xk ).

i∈[1,k−1] j∈[k+1,a−1]

i∈[1,a−1] j∈[i+1,a−1]
k<j
i<k

Lemma 9. For a fixed maximal path P max = x0 x1 . . . xa , for all xk with 0 ≤ k ≤ a we can
compute the following in overall O(a) time:
X
X
γ(xi , xj , xk ).
2·
i∈[1,k−1] j∈[k+1,a−1]

Proof. For the sake of readability we define
X
αxk = 2 ·

X

γ(xi , xj , xk ).

i∈[1,k−1] j∈[k+1,a−1]

P P
Notice that i ≥ 1 and k > i and thus for x0 we have αx0 = 2 i∈∅ j∈[1,a−1] γ(xi , xj , x0 ) = 0.
This will be the anchor of the dynamic program.
For every vertex xk with 1 ≤ k < a it holds that
X
X
X
γ(xk−1 , xj , xk ).
γ(xi , xj , xk ) + 2 ·
γ(xi , xj , xk ) = 2 ·
αxk = 2 ·
j∈[k+1,a−1]

i∈[1,k−2]
j∈[k+1,a−1]

i∈[1,k−1]
j∈[k+1,a−1]

Similarly, for xk with 1 < k ≤ a it holds that
X
X
γ(xi , xj , xk−1 ) = 2 ·
αxk−1 = 2 ·

γ(xi , xj , xk−1 ) + 2 ·

γ(xi , xk , xk−1 ).

i∈[1,k−2]

i∈[1,k−2]
j∈[k+1,a−1]

i∈[1,k−2]
j∈[k,a−1]

X

Next, notice that any path from xi to xj with i ≤ k − 2 and j ≥ k + 1 that contains xk also
contains xk−1 and vice versa. Substituting this into the equations above yields
X
X
γ(xi , xk , xk−1 ).
γ(xk−1 , xj , xk ) − 2 ·
αxk = αxk−1 + 2 ·
i∈[1,k−2]

j∈[k+1,a−1]

P
Lastly, we prove that
i∈[1,k−2] γ(xi , xk , xk−1 ) can be
j∈[k+1,a−1] γ(xk−1 , xj , xk ) and 2 ·
left
right
computed in constant time once W [·] and W
[·] are precomputed, see Lines 18 to 21 in
Algorithm 1. (These tables can also be computed in O(a) time.) For convenience we say that γ(xi , xj , xk ) =
Pj
0 if i or j are not integral or are not in [1, a − 1] and define W [xi , xj ] =
ℓ=i Pen[xℓ ] =
W left [xj ] − W left [xi−1 ]. Then we can use Equations (27) and (28) to show that
P

X

γ(xk−1 , xj , xk ) =

X

Pen[xk−1 ] · Pen[xj ] ·

j∈[k+1,a−1]

j∈[k+1,a−1]

= γ(xk−1 , x(k−1)+ , xk ) +
mid

X

σxk−1 xj (xk )
σxk−1 xj

Pen[xk−1 ] · Pen[xj ]

j∈[k+1,min{⌈(k−1)+
mid ⌉−1,a−1}]


if (k − 1)+

mid ≥ a;
Pen[xk−1 ] · W [xk+1 , xa−1 ],
+
+
+
Pen[x
]
·
W
[x
,
x
],
if
(k
−
1)
<
a
∧
(k
−
1)
/ Z;
=
k−1
k+1
mid
mid ∈
⌈(k−1)mid ⌉−1


1
Pen[xk−1 ] · (Pen[x(k−1)+ ] · σx ,x +1 + W [xk+1 , x(k−1)+ −1 ]), otherwise.
mid

0

mid

a

19

Herein we use (k − 1)+
/ Z to say that (k − 1)+
mid ∈
mid is not integral. Analogously,
X

X

γ(xi , xk , xk−1 ) =

Pen[xi ] · Pen[xk ] ·

i∈[1,k−2]

i∈[1,k−2]

= γ(xk−1 , xk− , xk−1 ) +
mid

X

σxi xk (xk−1 )
σxi xk

Pen[xi ] · Pen[xk ]

i∈[max{1,⌊(k−1)−
mid ⌋+1},k−2]



Pen[xk ] · W [x1 , xk−2 ],
−
= Pen[xk ] · W [x⌊kmid
⌋+1 , xk−2 ],


Pen[xk ] · (Pen[xk− ] · σx ,x1 +1 + W [x1 , xk−
mid

0

−
if kmid

mid +1

a

−
if kmid
< 1;
−
≥ 1 ∧ kmid ∈
/ Z;

]),

otherwise.

−
This completes the proof since (k − 1)+
mid , kmid , an arbitrary entry in W [·], and all other variables
in the equation above can be computed in constant time once W left [·] is computed, and therefore,
computing αxi for each vertex xi in P max takes constant time. As there are a vertices in P max
the computations for the whole maximal path P max take O(a) time.

4.2.2

Paths partially contained in a maximal path

We will now compute the value for all paths that partially leave P max . We will again assume
that Inc[s, t] · σst (v) can be computed in constant time for fixed vertices s and t to simplify the
analysis.
Lemma 10. Let P max = x0 x1 . . . xa ∈ P max . Then, assuming that Inc[s, t]·σst (v) can be computed
in constant time for some s, t ∈ V ≥3 (G), one can compute
X
X
γ(xi , xj , v)
βv =
i∈[1,a−1] j∈[i+1,a−1]

in O(a) time, where v ∈ V (G) \ [xi , xj ].
Proof. We start with all vertices v ∈
/ V (P max ) and then compute the value for all vertices xk
with k ≤ i or k ≥ j. As stated above, the distance from xi to xi+ (if existing) is the boundary
mid

max
such that all shortest paths to vertices xj with j > i+
and the unique shortest path
mid leave P
+
to any xj with i < j < imid is xi xi+1 · · · xj . Thus we can use Equations (27) and (28) to show
that for each v ∈
/ P max and each fixed i ∈ [1, a − 1] it holds that

X

γ(xi , xj , v) =

Pen[xi ] · Pen[xj ] ·

j∈[i+1,a−1]

j∈[i+1,a−1]



0,


P

X

σ

σxi xj (v)
σxi xj
if i+
mid > a − 1;

(v)

+
Pen[xi ] · Pen[xj ] · xσ0xxax ,
if i+
/ Z;
mid ≤ a − 1 ∧ imid ∈
0 a
mid



P

σ
(v)
σx0 xa (v)

Pen[xi ] · Pen[xi+ ] · σxx0 xxa +1 + j∈[x +
,
otherwise;
,a−1] · Pen[xj ] · σx0 xa
mid
0 a
⌊i
⌋+1
mid


0,
if i+

mid > a − 1;

σx0 xa (v)
+
right
W
[x⌊i+ ⌋+1 ] · σx x ,
if imid ≤ a − 1 ∧ i+
/ Z;
= Pen[xi ] · 
mid ∈
mid
0 a



σ
(v)
σ
(v)
x
x
x
x
a
a
right
Pen[xi ] · Pen[x + ] · 0
,
otherwise.
+W
[x +
] · Pen[xj ] · 0

=

j∈[x⌊i+

⌋+1

,a−1]

imid

σx0 xa +1

⌊imid ⌋+1

σx0 xa

All variables except for σx0 xa (v) can be computed in constant time once W right and σx0 xa are
computed. Thus we can compute in overall O(a) time the value
P
P
X
X
2 · i∈[1,a−1] j∈[i+1,a−1] γ(xi , xj , v)
Pen[xi ] Pen[xj ]σxi ,xj . (29)
X=
=2·
σx0 xa (v)
i∈[1,a−1] j∈[i+1,a−1]

20

Due to the postprocessing (see Lines 28 and 29 in Algorithm 1) it is sufficient to add X to Inc[x0 , xa ]
/ V (P max ).
This ensures that X · σx0 xa (v) is added to the betweenness centrality of each vertex v ∈
Notice that if X > 0, then dG (x0 , xa ) < a and thus the betweenness centrality of any vertex v ∈ V =2 (P max ) is not affected by Inc[x0 , xa ]. This also holds for x0 and xa since σx0 xa (v) = 0
for v ∈ {x0 , xa }.
Next, we will compute βv for all vertices v ∈ V (P max ) (recall that v ∈
/ [xi , xj ]). We start with
the simple observation that all paths that leave P max at some point have to contain x0 . Thus βx0
is equal to X from Equation (29). We will use this as the anchor for a dynamic program that
iterates through P max and computes βxk for each vertex k ∈ [0, a] in constant time.
Similarly to Section 4.2.1 we observe that


X
X
X
X
γ(xi , xj , xk )
γ(xi , xj , xk )
+
βx k = 2
i∈[1,k−1] j∈[i+1,k−1]

i∈[k+1,a−1] j∈[i+1,a−1]

=2



X

X

γ(xi , xj , xk )

+

X

X

+

X

j∈[k+2,a−1]

βxk+1 = 2



=2



γ(xi , xj , xk )

i∈[1,k−1] j∈[i+1,k−1]

i∈[k+2,a−1] j∈[i+1,a−1]

X

X

γ(xi , xj , xk+1 )

X

X

γ(xi , xj , xk+1 )

+

X


γ(xk+1 , xj , xk ) and

X

i∈[1,k] j∈[i+1,k]

i∈[k+2,a−1] j∈[i+1,a−1]

+

X


γ(xi , xj , xk+1 )

X

γ(xi , xj , xk+1 )

i∈[1,k−1] j∈[i+1,k−1]

i∈[k+2,a−1] j∈[i+1,a−1]

+

X

i∈[1,k−1]


γ(xi , xk , xk+1 ) .

Furthermore, observe that every st-path with s, t 6= xk , xk+1 that contains xk also contains xk+1
and vice versa. Thus we can conclude that

 X
X
γ(xk+1 , xj , xk ) .
γ(xi , xk , xk+1 ) −
βxk+1 = βxk + 2
j∈[k+2,a−1]

i∈[1,k−1]

P

P
It remains to show that i∈[1,k−1] γ(xi , xk , xk+1 ) and j∈[k+2,a−1] γ(xk+1 , xj , xk ) can be computed in constant
time once W left [·] and W right [·] are computed. Using Equations (27) and (28)
P
we get that i∈[1,k−1] γ(xi , xk , xk+1 )

−

if kmid
< 1;

0,
−
−
left
−
Pen[x
]
·
W
[x
],
if
k
≥
1
∧
k
∈
/
Z;
k
=
mid
mid
⌊kmid ⌋



σ

x
x
−
a
left
0
Pen[xk ] · W [x −
,
otherwise;
] + Pen[k ] ·
kmid −1

mid

σx0 xa +1

P

j∈[k+2,a−1] γ(xk+1 , xj , xk )

+

if kmid
< 1;

0,
+
+
right
+
Pen[x
]
·
W
[x
],
if
(k
+
1)
≤
a
−
1
∧
(k
+
1)
∈
/
Z;
k+1
=
mid
mid
⌊(k+1)mid ⌋



σ

x
x
+
0 a
Pen[xk+1 ] · W right [x
otherwise.
(k+1)+ −1 ] + Pen[(k + 1)mid ] · σx x +1 ,

and

mid

0 a

Since all variables in these two equalities can be computed in constant time, this concludes the
proof.

4.3

Postprocessing and algorithm summary

In this section we discuss our postprocessing that finishes our algorithm. For this we will state a
generalized version of Brandes’ algorithm. We will then describe how we use it to compute the
betweenness centrality correctly.
21

Lemma 11 (Restated). Let s be a vertex and let f : V (G)2 7→ N be a function such that
for each
P u, v ∈ V (G) the value f (u, v) can be computed in O(τ ) time. Then, one can compute t∈V (G) f (s, t) · σst (v) for all v ∈ V in overall O(n · τ + m) time.

Proof. This proof generally follows the structure of the proof by Brandes [4, Theorem 6, Corollary
7]. Analogously to Brandes we define σst (v, w) as the number of shortest paths from s to t that
contain the edge {v, w} and Ss (v) as the set of successors of a vertex v on shortest path from s,
that is, Ss (v) = {wP∈ V (G) | {v, w} ∈ E ∧ dG (s, w) = dG (s, v) + 1}. For the sake of readability we
also define χsv = t∈V (G) f (s, t) · σst (v). We will first show a series of equations that show how
to compute χsv . Afterwards we will give reasoning for equalities (1) and (2).
X
f (s, t) · σst (v)
χsv =
t∈V (G)

=

X

f (s, t)

t∈V (G)

=

X 

w∈Ss (v)

=

X 

w∈Ss (v)

=

X 

w∈Ss (v)

X

σst (v, w) =

t∈V (G)\{w}

X

f (s, t) · σst (v, w)

(30)



f (s, t) · σst (v, w) + f (s, w) · σsw (v, w)
f (s, t) · σst (w) ·

t∈V (G)\{w}

χsw ·

X

w∈Ss (v) t∈V (G)

w∈Ss (v)

X

X


σsv
+ f (s, w) · σsv
σsw


σsv 
+ f (s, w) · σsv
σsw

(31)

We will now show that Equations (30) and (31) are correct. All other equalities are simple arithmetics. To see that Equation (30) is correct, observe that each shortest path from s to any other
vertex t that contains v either ends in v, that is, t = P
v, or contains P
exactly
Pone edge {v, w},
where w ∈ Ss (v). If t = v, then σst (v) = 0 and therefore t∈V σst (v) = t∈V w∈Ss (v) σst (v, w).
To see that Equation (31) is correct, observe the following: First, that the number of shortest
paths from s to t that contain a vertex v is
(
0,
if dG (s, v) + dG (v, t) > dG (s, t);
σst (v) =
σsv · σvt , otherwise;
second, that the number of shortest st-paths that contain an edge {v, w}, w ∈ Ss (v), is
(
0,
if dG (s, v) + dG (w, t) + 1 > dG (s, t);
σst (v, w) =
σsv · σwt , otherwise;
and third, that the number of shortest sw-paths that contain v is equal to the number of shortest svpaths. Combining these two results yields σst (v, w) = σsv · σwt = σsv · σst (w)/σsw .
We next show how to compute χsv for each v ∈ V in overall O(m + n · τ ) time. First, order the vertices in non-increasing distance to s and compute the set of all successors of each
vertex in O(m) time using breadth-first search. Notice that the number of successors of all vertices is at most m since each edge defines at most one successor-predecessor relation. Then
compute χsv for each vertex by a dynamic program that
 iterates over the ordered list of verP
σsv
tices and computes w∈Ss (v) χsw · σsw + f (s, w) · σsv in overall O(m + n · τ ) time. This can
be done by first computing σst for all t ∈ V in overall O(m) time by Brandes [4, Corollary 4]
and f (s, t) for all t ∈ V (G) in O(n · τ ) 
time, and then using the already
computed values Ss (v)

P
σsv
χ
·
and χsw to compute χsv =
in
O(|S
+
f
(s,
w)
·
σ
sw
s (v)|) time. Notice
sv
w∈Ss (v)
σsw
P
that v∈V |Ss (v)| ≤ O(m). This concludes the proof.
We are now ready to combine all parts and prove our main theorem.
22

Theorem 4 (Restated). Betweenness Centrality can be solved in O(kn) time, where k is
the feedback edge number of the input graph.
Proof. We show that Algorithm 1 computes
X

CB (v) =

Pen[s] · Pen[t] ·

s,t∈V (G)

σst (v)
=
σst

X

γ(s, t, v)

s,t∈V (G)

for all v ∈ V (G) in O(kn) time. To this end, we use Observation 3 to split the sum as follows.
X
X
X
γ(s, t, v) =
γ(s, t, v) +
γ(t, s, v)
s∈V ≥3 (G),t∈V (G)

s∈V (G),t∈V (G)

s∈V =2 (G),t∈V ≥3 (G)

X

+

γ(s, t, v) +

X

γ(s, t, v).

s,t∈V =2 (P max )
P max ∈P max

s∈V =2 (P1max ),t∈V =2 (P2max )
P1max 6=P2max ∈P max

By Propositions 6 and 7, we can compute the third and fourth summand in O(kn) time provided that the term Inc[s, t] · σst (v) will be computed for every s, t ∈ V ≥3 (G) and v ∈ V (G) in a
postprocessing step (see Lines 22 to 27). We incorporate this postprocessing into the computation
of the first two summands in the equation, that is, we next show that for all v ∈ V (G) the following
value can be computed in overall O(kn) time:
X
X
X
γ(s, t, v) +
γ(s, t, v) +
Inc[s, t] · σst (v)
s∈V =2 (G)
t∈V ≥3 (G)

s∈V ≥3 (G)
t∈V (G)

To this end, observe that
X
γ(s, t, v) +
s∈V ≥3 (G)
t∈V (G)

=

X

γ(s, t, v) +

s∈V =2 (G)
t∈V ≥3 (G)

X

Pen[s] · Pen[t] ·

X

Inc[s, t] · σst (v)

X


(2

s∈V ≥3 (G)
t∈V (G)

+

s∈V ≥3 (G)
t∈V ≥3 (G)

σst (v)
+
σst

X

Inc[s, t] · σst (v)

s∈V ≥3 (G)
t∈V ≥3 (G)

X

Pen[s] · Pen[t] ·

s∈V ≥3 (G)
t∈V =2 (G)

σst (v)
σst

s∈V ≥3 (G)
t∈V ≥3 (G)

=

s∈V ≥3 (G)

X

t∈V =2 (G)

Pen[s] Pen[t]


X
Pen[s] Pen[t]
σst (v)
σst (v)(
)+
+ Inc[s, t])
σst
σst
≥3
t∈V

Notice that we initialize Inc[s, t] in Lines 16 and 17 in Algorithm 1 with 2 · Pen[s] Pen[t]/σst
and Pen[s] Pen[t]/σst respectively. Thus we can use the algorithm described in Lemma 3 for each
vertex s ∈ V ≥3 (G) with X(s, t) = Inc[s, t].
Since Pen[s], Pen[t], σst and Inc[s, t] can all be looked up in constant time, the algorithm only
takes O(n + m) time for each vertex s (see Lines 28 and 29). By Lemma 1 there are O(min{k, n})
vertices of degree at least three. Thus the algorithm altogether takes O(min{n, k}·m) = O(min{n, k}·
(n + k)) = O(kn) time.

5

Conclusion

Lifting the processing of degree-one vertices due to Baglioni et al. [3] to a technically much more
demanding processing of degree-two vertices, we derived a new algorithm for Betweenness Centrality running in O(kn) worst-case time (k is the feedback edge number of the input graph).
23

Our work focuses on algorithm theory; in a follow-up step empirical work with implementing and
testing our algorithm should be done. Given the practical success of Baglioni et al. [3] in accelerating the algorithm of Brandes [4], we expect this to be a fruitful line of future research. In
this context, also the use of further data reduction techniques should be investigated. Moving
back to theory, it would be of high interest to identify parameterizations “beyond” feedback edge
number that might help to get more results in the spirit of our work. Indeed, our work can be
seen as a further systematic contribution in making use of parameterized complexity analysis for
polynomial-time solvable problems as advocated by Giannopoulou et al. [8].

References
[1] Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences
between graph centrality problems, APSP and diameter. In Proceedings of the 26th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1681–1697. SIAM, 2015.
1
[2] David A Bader, Shiva Kintali, Kamesh Madduri, and Milena Mihail. Approximating betweenness centrality. In Proceedings of the 5th International Workshop on Algorithms and Models
for the Web-Graph (WAW 2007), pages 124–137. Springer, 2007. 1
[3] Miriam Baglioni, Filippo Geraci, Marco Pellegrini, and Ernesto Lastres. Fast exact computation of betweenness centrality in social networks. In Proceedings of the 4th International
Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), pages
450–456. IEEE Computer Society, 2012. 2, 3, 4, 5, 11, 23, 24
[4] Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177, 2001. 1, 2, 7, 11, 22, 24
[5] Dóra Erdős, Vatche Ishakian, Azer Bestavros, and Evimaria Terzi. A divide-and-conquer algorithm for betweenness centrality. In Proceedings of the 15th SIAM International Conference
on Data Mining (SDM 2015), pages 433–441. SIAM, 2015. 1
[6] Linton Freeman. A set of measures of centrality based on betweenness. Sociometry, 40:35–41,
1977. 1
[7] Robert Geisberger, Peter Sanders, and Dominik Schultes. Better approximation of betweenness centrality. In Proceedings of the Meeting on Algorithm Engineering & Expermiments
(ALENEX 2008), pages 90–100. SIAM, 2008. 1
[8] Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixedparameter algorithms: A case study for longest path on interval graphs. Theoretical Computer
Science, 689:67–95, 2017. 24
[9] Oded Green, Robert McColl, and David A Bader. A fast algorithm for streaming betweenness
centrality. In International Conference on Privacy, Security, Risk and Trust (PASSAT 2012),
pages 11–20. IEEE, 2012. 1
[10] Ali Khazaee, Ata Ebrahimzadeh, and Abbas Babajani-Feremi. Identifying patients with
Alzheimer’s disease using resting-state fMRI and graph theory. Clinical Neurophysiology, 126
(11):2132–2141, 2015. 1
[11] John D. Medaglia. Graph theoretic analysis of resting state functional MR imaging. Neuroimaging Clinics of North America, 27(4):593–607, 2017. 1
[12] George B. Mertzios, André Nichterlein, and Rolf Niedermeier. The power of linear-time data
reduction for maximum matching. In Proceedings of the 42nd International Symposium on
Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of LIPIcs, pages
46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. 2
24

[13] Meghana Nasre, Matteo Pontecorvi, and Vijaya Ramachandran. Betweenness centrality –
incremental and faster. In Proceedings of the 39th International Symposium on Mathematical
Foundations of Computer Science (MFCS 2014), volume 8634 of L, pages 577–588. Springer,
2014. 1
[14] Matteo Riondato and Evgenios M Kornaropoulos. Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 30(2):438–475, 2016. 1
[15] Ahmet Erdem Sariyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek. Graph manipulations for fast centrality computation. ACM Transactions on Knowledge Discovery from
Data, 11(3):26:1–26:25, 2017. 1
[16] Guangming Tan, Dengbiao Tu, and Ninghui Sun. A parallel algorithm for computing betweenness centrality. In Proceedings of the 38th International Conference on Parallel Processing
(ICPP 2009), pages 340–347. IEEE Computer Society, 2009. 1
[17] Wei Wang and Choon Yik Tang. Distributed computation of node and edge betweenness on
tree graphs. In Proceedings of the 52nd IEEE Conference on Decision and Control (CDC
2013), pages 43–48. IEEE, 2013. 1, 2

25

