Efficient Computation of Betweenness Centrality
by Graph Decompositions and Their Applications
to Real-World Networks
メタデータ

言語: English
出版者: 電子情報通信学会
公開日: 2024-08-22
キーワード (Ja):
キーワード (En): BC-tree, Brandes' algorithm, centralityof networks, graph decomposition
作成者: Inoha, Tatsuya, Sadakane, Kunihiko, Uno,
Yushi, Yonebayashi, Yuma
メールアドレス:所属:

URL

http://hdl.handle.net/10466/0002001115

IEICE TRANS. INF. & SYST., VOL.E105–D, NO.3 MARCH 2022

451

PAPER

Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -Eﬃcient Computation of Betweenness Centrality by Graph
Decompositions and Their Applications to Real-World Networks
Tatsuya INOHA†∗ , Nonmember, Kunihiko SADAKANE††a) , Yushi UNO†b) , Members,
and Yuma YONEBAYASHI††∗∗c) , Nonmember

SUMMARY Betweenness centrality is one of the most significant andcommonly used centralities, where centrality is a notion of measuring theimportance of nodes in networks. In 2001, Brandes proposed an algorithm
for computing betweenness centrality eﬃciently, and it can compute thosevalues for all nodes in O(nm) time for unweighted networks, where n and mdenote the number of nodes and links in networks, respectively. However,even Brandes’ algorithm is not fast enough for recent large-scale real-world
networks, and therefore, much faster algorithms are expected. The objective of this research is to theoretically improve the eﬃciency of Brandes’
algorithm by introducing graph decompositions, and to verify the practicaleﬀectiveness of our approaches by implementing them as computer programs and by applying them to various kinds of real-world networks. A
series of computational experiments shows that our proposed algorithms
run several times faster than the original Brandes’ algorithm, which are
guaranteed by theoretical analyses.
key words: BC-tree, Brandes’ algorithm, centrality of networks, graphdecomposition

1.

Introduction

Network analysis has been a surprisingly active researcharea since the World Wide Web was invented. There area lot of significant topics of interest in this area (e.g., [1]),and among those computing “centrality” is one of such topics. When we model real-world networks as graphs, centrality is an index of the vertices of graphs that represents theimportance of each node in those networks. The notion ofcentrality itself has a long history in graph theory, but in thecontext of network analysis, some of them are rediscoveredand several notions are newly proposed due to their increasing importance in applications to real-world networks. They
include degree centrality, closeness centrality [2], PageRankcentrality [6], and so on, and used diﬀerently depending on
the purpose. Among those the betweenness centrality is oneof the most common centralities, and has attracted much atManuscript received March 24, 2021.
Manuscript revised July 15, 2021.
Manuscript publicized November 8, 2021.
†
The authors are with Graduate School of Engineering, Osaka
Prefecture University, Sakai-shi, 599–8531 Japan.
††
The authors are with Graduate School of Information Scienceand Technology, The University of Tokyo, Tokyo, 113–8656
Japan.
∗
Presently, with Fujitsu Broad Solution & Consulting Inc.,
Japan.
∗∗
Presently, with Marubeni Corporation, Japan.
a) E-mail: sada@mist.i.u-tokyo.ac.jpb) E-mail: uno@cs.osakafu-u.ac.jpc) E-mail: yuma.yonebayashi@gmail.com
DOI: 10.1587/transinf.2021FCP0003

tention since its introduction by Freeman [10] in 1977. The
betweenness centrality of a vertex is defined by in how many
shortest paths between any two vertices the vertex is included, and considered to have a wide variety of potential
applications to real-world networks such as finding significant person (like terrorist) in social networks [8], or protein
structure analyses [9], and so on.
Computing centrality eﬃciently is an important issue
since the real-world networks are so enormous and evolving. For betweenness centrality, an algorithm proposed by
Brandes [4] in 2001 (the so-called Brandes’ algorithm) is
well-known as one of the most eﬃcient ways to computeits exact values. The algorithm is a kind of dynamic programming approach, and it first finds shortest paths fromeach starting vertex, and it computes and accumulates contributions to betweenness centrality of the other vertices by
traversing all the vertices in farthest-first order. The running
time of the algorithm is O(nm) for unweighted graphs andO(nm + n2 log n) for weighted graphs, where n and m are thenumber of vertices and edges of a graph, respectively. However, this implies that even Brandes’ algorithms is not fastenough for huge networks of the current era.
By this reason, many alternative approaches for computing betweenness centrality have been considered andproposed so far. One is to approximate them, instead ofto compute exact values. Brandes and Pich [5] proposed analgorithm of computing approximate values of centrality byderiving shortest paths for vertices in randomly sampled vertex subset. Another approach focuses on the dynamic aspectof real-world networks, that is, nodes and links are added
and/or deleted frequently. However, it is ineﬃcient and undesirable to compute centrality from scratch every time of
the change. Therefore, for those kind of networks it is useful if we can recompute them by their diﬀerences, and suchalgorithms have been studied extensively [3], [12], [15].
In view of this situation, the objective of this paper isto propose yet another approach of computing betweenness
centrality eﬃciently. We tackle this problem straightforwardly, that is, we are still trying to compute their exact
values of static networks based on Brandes’ algorithm. To
this end, we will fully exploit the decomposition structuresof networks. Specifically, our algorithm first prepares biconnectivity decompositions of input networks, and then applies Brandes’ algorithm on those decomposed graphs. This
may reduce the time for computation since the required information for computation is aggregated in decompositionc 2022 The Institute of Electronics, Information and Communication Engineers
Copyright ⃝IEICE TRANS. INF. & SYST., VOL.E105–D, NO.3 MARCH 2022

452

trees. We see that many of the real-world networks havesuch nice decomposition structures, and we show that our
proposed algorithm contributes greatly to the eﬀectiveness.

ineﬃciency, Brandes [4] introduced the following value:∑δ s• (v) =δ st (v).
(3)
t∈V\{s,v}

2.

Betweenness Centrality

2.1 Definition
We assume throughout the paper, that a graph G = (V, E)
is simple, undirected and connected, where V and E are its
vertex and edge sets, respectively, We denote n = |V| andm = |E|.
Let s and t be two distinct vertices in V, and consider
the shortest paths from s to t (s, t-shortest paths). Let σ st
be the number of distinct s, t-shortest paths, where σ ss isdefined to be 1. Among s, t-shortest paths, let σ st (v) denotethe number of those passing through v as a midpoint which
is diﬀerent from s and t. Now the betweenness centrality
g(v) of v (∈ V) is defined as follows:∑ σ st (v).
(1)g(v) =σ sts,t∈V\{v}In addition, by introducing a new variable δ st (v) ≜ σσst st(v) , we
can rewrite the definition formula (1) as∑
g(v) =
δ st (v).
(2)
s,t∈V\{v}Remark that this value of g(v) is often used by being normalized to fit in the range between 0 and 1. This can becomputed by dividing g(v) by (n − 1)(n − 2), since the possible maximum value of g(v) is achieved when v exists on the
shortest paths of all (n − 1)(n − 2) pairs of the vertices except
v itself. Figure 1 illustrates a graph and (normalized) valuesof betweenness centrality of each vertex.
2.2 Brandes’ Algorithm
In this subsection, we explain basic ideas of Brandes’ algorithm [4] that computes exact values of betweenness centrality for all vertices of an unweighted graph in O(nm) time.
The betweenness centrality of a single vertex v is computed simply according to formula (1) which is a direct definition of the notion. However, when we compute the value
for all the vertices, applying formula (1) may contain repeated computation of similar shortest path length manytimes due to the double summation on vertices, and thus,
this naive approach is quite ineﬃcient. Then, to avoid this

The value δ s• (v) defined in this way has the following property, where P s (u) is a set of vertices that precede u (predecessor of u) in the shortest path starting at s.
Theorem 2.1 [4] For all s, v ∈ V, it holds that∑ σ svδ s• (v) =· (1 + δ s• (u)).
σ
u:v∈P (u) su

To compute the betweenness centrality for all the vertices eﬃciently, Brandes’ algorithm pre-computes, by using
the property of Theorem 2.1, the order of vertices in theirdistances (farthest first) and the set of predecessors for eachstarting vertex s by traversing their shortest paths. We show
Brandes’ algorithm as Algorithm 1 in the appendix for convenience since we utilize its basic ideas for the further discussions in the subsequent sections. The time complexity ofsuch Brandes’ algorithm is stated as follows.
Theorem 2.2 [4] The betweenness centrality of all vertices
can be computed in O(nm) time for unweighted graphs andO(nm + n2 log n) time for weighted graphs both in O(n + m)
space.
As we see in the theorem, the notion of betweenness
centrality is defined not only on unweighted graphs but onedge-weighted graphs. However, since the way of computing the centrality for unweighted graphs can be generalized
into weighted ones relatively in a straightforward manner,
we only focus on unweighted graphs in this paper. We also
remark here that any path-comparison based algorithm cannot compute the betweenness centrality for all the vertices
faster than O(nm) time [14].
3. Graph Decompositions
The main objective of the paper is an attempt to accelerate Brandes’ algorithm by running it on small graphs after
decomposing input graphs. Therefore, in this section, we
introduce some notions of graph decompositions, that is, biconnectivity decompositions and BC-trees. We remark that
we will use the terms vertex (and edge) for input graphs, andnode (and edge) for BC-trees from now on.
3.1

Fig. 1
tices.

A small graph and normalized betweennes centrality of its ver-(4)s

Biconnectivity Decomposition and BC-Tree

For a connected graph G = (V, E), a vertex v ∈ V is a cutvertex if its removal makes G disconnected, and a block is
a (inclusion-)maximal subgraph of G without cut-vertices.
Let B and C be families of blocks and cut-vertices of G,
respectively. Then the block graph of G is a graph whose
node set is B ∪ C and there is an edge (b, c) (b ∈ B, c ∈ C)
if a cut-vertex c belongs to a block b. A BC-tree is a blockINOHA et al.: BETWEENNESS CENTRALITY BY GRAPH DECOMPOSITIONS AND THEIR APPLICATIONS

453

Fig. 2 A graph and its BC-tree. B and C stand for B-node and C-node,
respectively.

graph rooted at an arbitrary node b ∈ B. For more details of
BC-trees and related notions, see [11], for example.
In a BC-tree, a node b ∈ B, which represents a block, iscalled a B-node, and a node c ∈ C, which represents a cutvertex, is called a C-node. By definition, no two B-nodes
can be adjacent and no two C-nodes either. For a graph, its
BC-tree is uniquely determined, and it shows how the graphis decomposed into biconnected components. Figure 2 illustrates an example of a graph and its BC-tree.
4.

Computing Betweenness Centrality by Biconnectivity Decompositions

Decomposed structures of graphs may help computing various network invariants since such computation could bedone separately within each decomposed component andmerged appropriately. In this section, we propose a new approach to compute betweenness centrality eﬃciently by decomposing a graph into biconnected components. The idea
is firstly to construct the BC-tree after biconnectivity decomposition, and then to apply Brandes’ algorithm to eachB-node.
To this end we introduce some values that are used during the computation. For any node x ∈ B ∪ C in a BC-tree
and a node y adjacent to x, we denote a block or a cut-vertex
corresponding to x by S x , a cut-vertex or a block corresponding to y, respectively, by S y , and a unique vertex thatbelongs to both S x and S y by c xy . Let w(x, y) be the numberof vertices except c xy in block y and its descendant blocks
when regarding x as a root node of a BC-tree.
Now we can describe our algorithm of computing betweenness centralities in detail.
1. For a given graph, construct its BC-tree by executing asingle depth-first search.
2. Select an arbitrary B-node as a root of the BC-tree, andapply the following procedure to all nodes except theroot by the post-order of a depth-first search on the BCtree.
Let q be a node where the depth-first search is now visiting, p be the parent of q, qc be the children of q, andnq be the number of vertices except c pq in S q . Since
all the child nodes of q have been processed due to thepost-order visit, a breadth-first search can compute nq
and thus we can compute w(p, q) by the following formula:Fig. 3 Shortest paths between two end vertices 1 and 6 (drawn in grey)that belong to diﬀerent biconnected components (1, 6-shortest paths areshown by bold edges). Any 1, 6-path goes through a cut-vertex that belongs
to both biconnected components, one containing 1 and the other containing 6.

w(p, q) =∑w(q, r) + nq .

(5)

r∈qc

Although graphs are assumed to be undirected, wecannot compute w(q, p) within the above procedure ofcomputing w(p, q). For this reason, we need to compute w for all pairs of vertices. This will be done in thenext step (Step 3).
3. By a depth-first search starting at q, compute value w
in pre-order, and apply Brandes’ algorithm to each Bnode in post-order. (This will be explained in detailbelow.)
Step 3 is the main part for making Brandes’ algorithm
more eﬃcient by biconnectivity decomposition. This isachieved by a simple observation that any (shortest) path
between two vertices in diﬀerent biconnected components
must go through the cut-vertices between them. To exploit
this property in Brandes’ algorithm and to make it work correctly, we have to give some modifications to formula (4)of the original algorithm, depending on if s or v is a cutvertex. These are to compute the contribution (value) of end
vertices, which are not contained in the currently visiting
B-node, of shortest paths to the centrality value at the sametime of applying Brandes’ algorithm to the current B-node.
Figure 3 shows an example of such shortest paths.
We have the following four cases depending onwhether s or v is a cut-vertex or not.
(i) Neither s nor v is a cut-vertex.
We do not need any change in this case.
(ii) Only s is a cut-vertex.
We need to consider the contributions of v to the betweenness centrality by the shortest paths between the vertices that are reachable to s and are outside of the current
B-node, and the vertices in the currently visiting B-node.
Those shortest paths always go through s, and thus traverse
the same route within the current B-node. This implies thatδ s• (v) increases, for each u, by the ratio of shortest paths
passing through v, out of all the shortest paths starting at
outside vertices that are reachable to s (Fig. 4). Therefore,
in this case, we can change formula (4) as follows:)∑ ( σ sv
σ sv
· (1+δ s• (u))+· w(q, p) .
δ s• (v) =σσ su
u:v∈P (u) sus(iii) Only v is a cut-vertex.

IEICE TRANS. INF. & SYST., VOL.E105–D, NO.3 MARCH 2022

454

Fig. 4 Each white vertex denotes a cut-vertex, and q is the current Bnode, s is a cut-vertex, and p is a C-node that shares the cut-vertex s withq. The contributions of v to the centrality by x, u-shortest paths starting at
x, which is reachable to s and is in a descendant B-node of p rooted at q, isalso computed.

Fig. 5 Each white vertex denotes a cut-vertex, and p is the current Bnode, v is a cut-vertex, and r is a C-node that shares the cut-vertex v withp. The contributions of v to the centrality by s, y-shortest paths ending at y,which is reachable from v and is in a descendant B-node of r when rooted
at p, is also computed.

We need to consider the contributions of v to the betweenness centrality by the shortest paths between s andthe vertices that are reachable from v and are outside of thecurrent B-node. Those shortest paths always go through v,
which forms a C-node r, and they traverse the same route
within the current B-node in case that v is the end vertex(Fig. 5). Therefore, since δ s• (v) increases by the number ofvertices reachable from v and outside of the current B-node,
we need to change formula (4) as follows:∑ σ sv· (1 + δ s• (u)).
δ s• (v) = w(q, r) +σu:v∈P (u) sus(iv) Both s and v are cut-vertices.
In addition to cases (ii) and (iii), we need to consider
the contributions of v to the betweenness centrality by theshortest paths between the vertices that are reachable tos and are outside of the current B-node, and the vertices
that are reachable from v and outside of the current B-node(Fig. 6). Therefore, δ s• (v) increases not only by cases (ii)and (iii) but the number of vertices reachable to s (and outside of the current B-node) for each vertex that is reachable
from v (and outside of the current B-node). Thus, we needto change formula (4) as follows:

Fig. 6 Each white vertex denotes a cut-vertex, and q is the current Bnode, s and v are cut-vertices, p is a C-node that shares the cut-vertex s withq, and r is a C-node that shares the cut-vertex v with q. In addition to theshortest paths of Figs. 4 and 5, the contributions of v to the centrality by x, yshortest paths, starting at x which is reachable to s and is in a descendant
B-node of p and ending at y which is reachable from v and is in a descendant
B-node of r, is also computed.

Procedure 1 W-Calculation function
1: N[vBC]: the number of vertices in a node vBC of theBC-tree of an input graph2:
3: function WCALC(v′ , s′ )4:visit[v′ ] = 1;
5:
for neighbor w′ of v′ do
6:
if visit[w′ ] = 0 then7:
p[w′ ] = v′ ;8:
WCALC(w′ , s′ );9:end if
10:
end for11:
if v′ , s′ then12:
for neighbor w′ of v′ do
13:
if w′ , p[v′ ] then14:
W[p[v′ ]][v′ ] ← W[p[v′ ]][v′ ]+W[v′ ][w′ ];15:
end if16:
end for17:
W[p[v′ ]][v′ ] ← W[p[v′ ]][v′ ] + N[v′ ] − 1;18:
end if
19: end function

We finally discuss the computational complexity of our
proposed algorithm. This is estimated as follows.
Theorem 4.1 Let nb and mb be the number of vertices andedges contained in each biconnected component b ∈ B, respectively. Then we can compute the betweenness centrality g(v) for all the ∑vertices v ∈ V of an unweighted graph
G = (V, E) in time b∈B O(nb mb ).

δ s• (v) = w(q, r)+w(q, r) · w(q, p))∑ ( σ sv
σ sv·(1+δ s• (u))+·w(q, p) .
+
σ su
σ su
u:v∈P (u)Proof. In the algorithm, we spend O(n+m) time for a depthfirst search to decompose a graph into biconnected components and to construct a BC-tree as a preprocess. Then it′
requires O(|B|∑+ |C|) time for computing w and w values andO(|B|+|C|)+ b∈B O(nb mb ) time
∑ for computing betweenness
centralities. Altogether, since b∈B O(nb mb ) is dominant theresult follows.
□

As we analyzed so far, we can compute exact betweenness centrality values correctly only by using vertices within
a B-node, once we have computed w values beforehand. The
following Procedure 1 illustrates a function WCALC thatcomputes w values in a post-order of a depth-first search.
The overall algorithm of our proposed approach is presented
as Algorithm 2 in the Appendix.

Observe in the theorem that if we let NB = maxb∈B nb ,then
∑ the total computational time could be rephrased byb∈B O(nb mb ) = O(NB m). This observation implies that if
an input graph has a biconnectivity decomposition whose
size of its maximum component is relatively small, then thecomputational time can be much smaller compared to O(nm)of the original Brandes’ algorithm. This suggests that wesINOHA et al.: BETWEENNESS CENTRALITY BY GRAPH DECOMPOSITIONS AND THEIR APPLICATIONS

455
Table 1 Fundamental information about selected networks, and their biconnectivity decompositions:n and m are the number of vertices and edges of networks, respectively; B, NB and MB are the number ofbiconnected components, the number of vertices and edges of the maximum biconnected components,
respectively.
Network (abbreviation)category

n

m

B

NB

MB

U.Rovira i Virgili (U.R)
Facebook(NIPS) (Fa)US power grid (US)Pretty Good Privacy (PGP)CAIDA (CA)Douban (Do)communication
online social
infrastructure
online contact
computeronline social

1,133
2,888
4,941
10,68026,475
154,908

5,451
2,981
6,594
24,31653,381
327,162

157
2,798
1,688
5,992
10,195103,265

976
69
3,040
3,670
16,264
51,634

5,293
140
4,555
15,91043,155
223,878can expect the algorithm to work faster in practice when thereal networks are decomposed well.

BC-trees optimally in linear time, based on the theoreticalresults (such as [13], and so on).

5.

5.2

Application to Real-World Networks

In this section, we verify the eﬀectiveness of our proposed
approaches for computing betweenness centralities based ongraph decompositions. We are also interested in the properties about how the real-world networks are decomposed. To
this end, we implement those ideas as computer programs
and performed a series of computational experiments by applying them to real-world network benchmark data. The environment of computational experiments is as follows: OS:
openSUSE 12.3 64bit, Memory: 32GB, CPU: Intel Core i74771 CPU @ 3.50Hz x 8, compiler: g++ 4.7.2.
Benchmark network data are taken from KONECT –The Koblenz Network Collection (http://konect.uni-koblenz.
de/), which maintains a large collection of network datasetsfrom many diﬀerent application areas. Among those, we
selected undirected, connected and unweighted networks.
5.1 OGDF
In implementing our proposed ideas as computer programs,
we used OGDF: The Open Graph Drawing Framework(http://www.ogdf.net/) libraries. This is a C++ library toprovide algorithms and data structures for graph drawing
purposes and has been developed by Chimani et al. [7]. In
addition to the functions specific to graph drawing, various
kinds of classes that are related to processing graphs areavailable, from fundamental to advanced ones: data structures such as arrays, stacks; algorithms such as Dijkstra’s,planarizations, decompositions, and so on. It greatly facilitated our programming and made programs succinct. Below
we list some of its functions that we used in our implementation:• input/output functions for graph (network) data,• fundamental classes that manipulate graphs, vertices,
edges, etc.,• data structures necessary for implementing Brandes’
algorithm such as arrays, stacks, queues, lists, etc.,• hashes to store w values in biconnectivity decompositions, and• BC-tree classes.
Remark that BC-tree classes are implemented to construct

Decomposition Structures of Real-World Networks

We first show the results of biconnectivity decompositionsof some networks in Table 1.
From this table, we can see that the biconnectivity decomposition structures greatly depend on each network. For
example, Facebook(NIPS) is decomposed into extremely
many components and its maximum size is small; it is only
about 2.39% of the entire network. On the other hand,
U.Rovira i Virgili is decomposed into relatively small number of components but the maximum size is large; it occupies about 86.1% of the total number of vertices. Similar
observation can be seen in US power grid, that is, it is decomposed into relatively small number of components andthe maximum component size is about 61.5% of the total
number of vertices. We could see that these phenomena are
due to the category of networks; virtual networks (such as
online social) are known to have many low-degree vertices(e.g., pendant vertices) on its fringe, and thus easily to be decomposed into a single edge component. In contrast, physical networks (such as infrastructure) usually avoid to havecut-vertices, and thus easy to form a big component.
It is hard to find any common properties of decompositions shared by all networks, but at least we could say thatmost of the networks are decomposed into “small number oflarge biconnected components” and “large number of smallbiconnected components”. We also remark that, to the bestof our knowledge, there are quite few observations about
decomposition structures of real-world networks, so theseresults are valuable on their own.
5.3

Computational Results for Biconnectivity Decompositions

We now show in Table 2 the experimental results of computing betweenness centralities by implementing (a) naive
Brandes’ algorithm (for comparison purpose), and (b) our
proposed algorithm by biconnectivity decompositions. For
the proposed algorithm, we measured the computationaltime for constructing BC-trees and applying Brandes’ algorithm after decompositions, separately.
We have the following observations from Table 2.

IEICE TRANS. INF. & SYST., VOL.E105–D, NO.3 MARCH 2022

456
Table 2 Computational time (in seconds) by (a) Brandes’ algorithm and (b) the proposed algorithm
by biconnectivity decompositions. We did multiple (five) trials for each network. For (a), we take theiraverage. For (b), we take the median in terms of the total time, and BC-tree and Brandes are the timesof that trial. We did so so that the sum of BC-tree and Brandes coincides with the total time.
Network
Brandes
Biconnectivity decomposition
BC-tree
Brandes
total
U.R
Fa
US
PGP
CA
Do

0.199294
0.332757
1.95956
13.1339
115.075
10, 083.6

0.001451
0.001698
0.003268
0.012537
0.030944
0.253606

1. It takes almost no time (within a second) for biconnectivity decompositions and obtaining BC-trees, for any
types of networks.
2. For all networks except one (U.R), the proposed algorithm runs faster than a naive application of Brandes’
algorithm.
3. The eﬀectiveness of the proposed algorithm depends
on the property of decompositions of networks.
We verify the third point in detail. For example, U.Rovira
i Virgili (U.R), which is not well decomposed into biconnected components, takes almost as much time as for Brandes’ algorithm, and thus the proposed algorithm has disadvantage in spending time for decompositions. On the other
hand, Facebook(NIPS) (Fa), which is decomposed into somany small components, can receive the advantage of thedecomposition, and the proposed algorithm outperforms anaive application of Brandes’ algorithm without decompositions. It runs about 20 times faster than a naive implementation.
We can conclude that using biconnectivity decompositions shows great advantage for computing betweenness
centralities as expected.
6.

Discussions and Conclusion

In this paper, we studied the problem of computing betweenness centralities of all vertices of a given network.
Especially, we focused on the well-known Brandes’ algorithm and proposed an approach of exploiting decomposition structures of networks to make Brandes’ algorithm
work more eﬃciently. Furthermore, we implemented theseideas as computer programs and verified the eﬀectiveness ofthe proposed algorithm by performing computational experiments on real-world networks.
As a result, we confirmed that using biconnectivity decompositions (applying Brandes’ algorithm after biconnectivity decompositions) has great advantage in the computational time. We also observed that real-world networks
have various types of biconnectivity decomposition structures and the eﬀectiveness of proposed approach depends on
those structures. However, the proposed algorithm performs
much better than a naive algorithm (i.e., without using decompositions) for large-scale networks, so we claim that we
could always prefer our proposed algorithm for computing

0.199611
0.0152210.994061
2.82199
92.2047
2, 574.98

0.201062
0.016919
0.997329
2.83453
92.2356
2, 575.23

exact betweenness centrality values.
Computing betweenness centrality eﬃciently is an important task by its own, but it has great spreading eﬀect.
For future work, we can incorporate our proposed approach
into other algorithms that use centrality computation as subroutines, such as Girvan-Newman algorithm for community
detection in social networks. We can expect that they will
be greatly accelerated by our proposed algorithm.
Acknowledgments
We express our hearty gratitude for anonymous refrees fortheir careful reading and helpful comments.
This work is partially supported by JST CREST
Grant Number JPMJCR1402, Japan. This work is also
partially supported by JSPS KAKENHI Grant Numbers
JP17K00017, 20H05964 and 20H05967.
References[1] A.-L. Barabási, Network Science, Cambridge University Press,
2016.
[2] A. Bavelas, “Communication patterns in task-oriented groups,” J.
Acoust. Soc. Am., vol.22, no.6, pp.725–730, 1950.
[3] E. Bergamini, H. Meyerhenke, and C.L. Staudt, “Approximating
betweenness centrality in large evolving networks,” In the 17th
Meeting on Algorithm Engineering and Experiments (ALENEX),
pp.133–146, 2015.
[4] U. Brandes, “A faster algorithm for betweenness centrality,” J. Mathematical Sociology, vol.25, no.2, pp.163–177, 2001.
[5] U. Brandes and C. Pich, “Centrality estimation in large networks,”
Int. J. Bifurcation and Chaos, vol.17, no.07, pp.2303–2318, 2007.
[6] S. Brin and L. Page, “The anatomy of a large-scale hypertextual
web search engine,” Computer Networks and ISDN Systems, vol.33,
no.1-7, pp.107–117, April 1998.
[7] M. Chimani, C. Gutwenger, M. Jünger, G.W. Klau, K. Klein, and P.
Mutzel, The Open Graph Drawing Framework (OGDF). Chapter 17
in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp.543–569, 2014.
[8] T. Coﬀman, S. Greenblatt, and S. Marcus, “Graph-based technologies for intelligence analysis,” Communications of the ACM, vol.47,
no.3, pp.45–47, March 2004.
[9] A. Del Sol, H. Fujihashi, and P. O’Meara, “Topology of smallworld networks of protein-protein complex structures,” Bioinformatics, vol.vol.21, no.8, pp.1311–1315, Jan. 2005.
[10] L.C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol.40, no.1, pp.35–41, 1977.
[11] C. Gutwenger, “Application of SPQR-trees in the planarization approach for drawing graphs,” Ph. D Thesis, Dortmund University ofTechnology, 2010.

INOHA et al.: BETWEENNESS CENTRALITY BY GRAPH DECOMPOSITIONS AND THEIR APPLICATIONS

457[12] T. Hayashi, T. Akiba, and Y, Yoshida, “Fully dynamic betweenness
centrality maintenance on massive networks,” In the 42nd Int. Conf.
the Very Large Data Bases Endowment (VLDB), vol.9, no.2, pp.48–
59, Oct. 2015.
[13] J. Hopcroft and R.E. Tarjan, “Dividing a graph into triconnectedcomponents,” SIAM J. Comput., vol.2, no.3, pp.135–158, 1973.
[14] S. Kintali, “Betweenness centrality: algorithms and lower bounds,”
arXiv: 0809.1906v2, 2008.
[15] M.-J. Lee, J. Lee, J.Y. Park, R.H. Choi, and C.-W. Chung, “QUBE:
a quick algorithm for updating betweenness centrality,” In the 21stInternational World Wide Web Conference (WWW), pp.351–360,
April 2012.

Appendix A: Brandes’ algorithm
Algorithm 1 Brandes’ algorithm
1: g[v] ← 0, v ∈ V;
2: for s ∈ V do3:
S ← empty stack;4:
P[w] ← empty list, w ∈ V;5:
σ[t] ← 0, t ∈ V; σ[s] ← 1;
6:
d[t] ← −1, t ∈ V; d[s] ← 0;
7:
Q ← empty queue;
8:
enqueue s → Q;
9:while Q not empty do
10:dequeue v ← Q;
11:
push v → S ;12:for neighbor w o f v do
13:
if d[w] < 0 then14:
enqueue w → Q;
15:d[w] ← d[v] + 1;
16:
end if17:
if d[w] = d[v] + 1 then18:
σ[w] ← σ[w] + σ[v];19:append v → P[w];20:
end if21:
end for22:
end while23:
δ[v] ← 0, v ∈ V;
24:
while S not empty do
25:
pop w ← S ;26:
for v ∈ P[w] do
σ[v]27:
δ[v] ← δ[v] + σ[w]· (1 + δ[w]);28:
end for29:
if w , s then30:g[w] ← g[w] + δ[w];31:
end if32:
end while
33: end forAppendix B: Brandes’ algorithm with BC-tree
Algorithm 2 Brandes’ algorithm with BCTree
1: O[vB]: vertices of an input graph corresponding to a Bnode vB
2: C[vO]: a C-node corresponding to a cut-vertex vO of an
input graph3:
4: p[v′ ] ← 0, v′ ∈ V ′ ;5: visit[t′ ] ← 0, t′ ∈ V ′ ;6: for e′ ∈ E ′ do7:v′ , w′ ← endpoint of e′8:
W[v′ ][w′ ] = 0;
9: end for
10: WCALC(s′ , s′ );11:
12: g[v] ← 0, v ∈ V;
13: visit[t′ ] ← 0, t′ ∈ V ′ ;14: S ′ ← empty stack;
15: push s′ → S ′ ;16: while S ′ not empty do
17:
pop v′ ← S ′ ;18:visit[v′ ] ← 1;
19:
if N[v′ ] > 1 then20:
for s ∈ V[v′ ] do21:
S ← empty stack;22:
P[w] ← empty list, w ∈ V[v′ ];23:
σ[t] ← 0, t ∈ V[v′ ]; σ[s] ← 1;
24:
d[t] ← −1, t ∈ V[v′ ]; d[s] ← 0;25:
Q ← empty queue;
26:
enqueue s → Q;
27:
while Q not empty do
28:dequeue v ← Q;
29:
push v → S ;30:
for neighbor w o f v do
31:
if d[w] < 0 then32:
enqueue w → Q;
33:
d[w] ← d[v] + 1;
34:
end if35:
if d[w] = d[v] + 1 then36:
σ[w] ← σ[w] + σ[v];37:append v → P[w];38:
end if
39:
end for40:
end while41:
δ[v] ← 0, v ∈ V[v′ ];42:while S not empty do
43:
pop w ← S ;44:
if O[w] cut-vertex then45:
δ[w] ← δ[w] + W[v′ ][C[w]];46:
if O[s] cut-vertex then47:
δ[w] ← δ[w] + W[v′ ][C[w]] ·W[v′ ][C[s]];

48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:

end ifend iffor v ∈ P[w] do
σ[v]· (1 + δ[w]);δ[v] ← δ[v] + σ[w]if O[s] cut-vertex thenσ[v]· W[v′ ][C[s]];δ[v] ← δ[v] + σ[w]end ifend for
if w , s theng[w] ← g[w] + δ[w];end ifend while
end forend iffor neighbor w′ o f v′ doif visit[w′ ] = 0 thenfor neighbor x′ o f v′ do
if x′ , w′ thenW[w′ ][v′ ] ← W[w′ ][v′ ] + W[v′ ][x′ ];end ifend forIEICE TRANS. INF. & SYST., VOL.E105–D, NO.3 MARCH 2022

458
69:
W[w′ ][v′ ] ← W[w′ ][v′ ] + N[v′ ] − 1;
70:
push w′ → S ′ ;71:
end if72:
end for73: end while

Tatsuya Inoha
received the M.S. degree
in Engineering from Osaka Prefecture University in 2017. Currently, he is working at Fujitsu
Broad Solutions & Consulting Inc., Nagoya,Japan.

Kunihiko Sadakane
received B.S., M.S.,
and Ph.D. degrees from Department of Information Science, University of Tokyo in 1995, 1997
and 2000, respectively. He was a research associate at Graduate School of Information Sciences, Tohoku University from 2000 to 2003,
an associate professor at Faculty of Information Science and Electrical Engineering, Kyushu
University from 2003 to 2009, an associate professor at National Institute of Informatics from2009 to 2014. Since 2014, he has been a professor at Graduate School of Information Science and Technology, The University of Tokyo. His research interest includes information retrieval, data
structures, and data compression.

Yushi Uno
received the B.E., M.E. and
Ph.D. degrees from Kyoto University, in 1987,
1989 and 1995, respectively. Currently, he isworking at Graduate School of Science, Osaka
Prefecture University, Sakai, 599–8531 Japan.
His research interests include combinatorial optimization, algorithmic graph theory, discrete
mathematics, operations research, design andanalysis of algorithms, and network analysis.
He is a member of Association for Computing Machinery, Operations Research Society ofJapan and Information Processing Society of Japan.

Yuma Yonebayashi
received B.S. and M.S.
degrees from Faculty of Engineering and Graduate School of Information Science and Technology, The University of Tokyo, Japan, respectively. Currently, he is working at Marubeni
Corporation, Japan.