2016 International Symposium on Nonlinear Theory and Its Applications,
NOLTA2016, Yugawara, Japan, November 27th-30th, 2016

A Fast Method for Finding the Edge to be Added to Minimize
Betweenness Centrality of a Specified Vertex
Toshiyuki Namba, Tatsuki Kohno and Norikazu Takahashi
Graduate School of Natural Science and Technology, Okayama University
3–1–1 Tsushima-naka, Kita-ku, Okayama 700–8530, Japan
Email: {nanba,kono}@momo.cs.okayama-u.ac.jp, takahashi@cs.okayama-u.ac.jp
Abstract—Betweenness centrality is a measure that represents the importance of each vertex in a graph. From theviewpoint of the robustness against attacks and failures, it isdesired that all vertices take similar values of the betweenness centrality. In this paper, a fast algorithm for finding
the edge to be added to minimize the betweenness centrality of a specified vertex is developed. The eﬃciency of the
proposed algorithm is confirmed by some experiments on
random graphs and scale-free graphs. It is also shown experimentally that the proposed algorithm is useful for improving the robustness of the graph by an edge addition.

0.0

4.0

0.0

4.0

4

1

4

1

8.0
0.0 6

4.0

3

0.0 6

3

5

2

5

2

4.0

0.0

4.0

4.0

(a)

(b)

Figure 1: Eﬀect of an edge addition on betweenness centrality. The number beside each vertex represents the betweenness centrality of the vertex.

1. Introduction
Since the seminal paper by Watts and Strogatz [1], complex networks have attracted a great deal of attention fromresearchers in physics, engineering, economics, sociology,
and so on. When analyzing a network, it is often important to evaluate the importance of each node quantitatively.
Various measures of the importance have been proposed in
the literature. Among them, this paper focuses on the betweenness centrality [2] which is well known and widelyused in the analysis of complex networks.
From the viewpoint of the robustness against attacks andfailures, it is desired that all vertices take similar values ofthe betweenness centrality. A natural way to make a given
network more robust is to add a small number of edges todecrease the largest betweenness centrality of the network
as much as possible. As an example, let us consider thegraph shown in Fig. 1 (a). If we add an edge to connect vertices 2 and 5, the largest betweenness centrality decreases
from 8 to 4. However, finding edges to be added is computationally very expensive because, for each of the nonexisting edges, we have to compute the betweenness centrality
for all vertices assuming that the edge is added.
In this paper, we consider the problem of finding theedge to be added in order to minimize the betweenness centrality of a specified vertex. This problem is closely related
to the improvement of the robustness of a network mentioned above. If the betweenness centrality of the vertex
with the largest betweenness centrality can be greatly decreased by an edge addition, it is expected that the largest
betweenness centrality of the graph also decreases. We
first provide a few theoretical results about the eﬀect of anedge addition on the number and length of shortest paths
between any pair of vertices. We next propose an algorithm, which is based on these theoretical results, for solving the above-mentioned problem. We finally examine theeﬃciency of the proposed algorithm by some experiments
on random graphs and scale-free graphs, and show that the
proposed algorithm is much faster than a simple method
based on Brandes’s algorithm [3].
2. Betweenness Centrality
2.1. Mathematical Expression of Networks
Throughout this paper, a network is expressed as a simple connected undirected graph G = (V, E), where V ={1, 2, . . . , N} is the vertex set and E = {e1 , e2 , . . . , e M } is theedge set. Because G is simple and undirected, each member of E is an unordered pair of distinct vertices.
The set of all shortest paths from vertex s to vertex t (, s)in G is denoted by G st = (V st , E st ) where V st ⊆ V is the setof all vertices that appear in the shortest paths, and E st is
the set of all directed edges that appear in the shortest paths.
Note that, unlike E, each member of E st is an ordered pairof distinct vertices. The set of all shortest paths from vertex
s to all other vertices in G is denoted by G s = (V, E s ) whereE s is the set of all edges that appear in the shortest paths. It
is clear that E st is a subset of E s .
The number of shortest paths from vertex s to vertex t
and the length of these paths are denoted by σ st and d st , respectively. Because G is undirected, σ st = σts and d st = dts
for all pairs of s and t (, s). In the following discussions,- 614 -

we assume for the sake of convenience that σ ss = 1 andd ss = 0 for all s ∈ V.
2.2. Betweenness Centrality
The betweenness centrality of vertex i, which is denotedby Bi , is defined byBi =∑ ∑ σ st (i)s,i t,i,s

σ st

(1)

where σ st (i) is the number of shortest paths from vertex s
to vertex t that pass through vertex i. In other words, thebetweenness centrality of vertex i is the sum of the ratio of
the number of shortest paths from s to t passing through ito the number of all shortest paths from s to t over all pairsof s and t. Therefore, a vertex with a high betweenness
centrality is a key for many pairs of vertices because all or
many of the shortest paths between these two vertices passthrough the vertex.
2.3. Brandes’s Algorithm for Computing Betweenness
Centrality
A simple method for computing Bi for all i ∈ V is asfollows. First, for s = 1, 2, . . . , N, one finds all shortest
paths from vertex s to all other vertices by using, for example, the breadth-first search algorithm. During this process,d st and σ st can be found for all pairs of distinct verticess and t, and σ st (i) can be found for all triples of distinct
vertices s, t and i. Next, one computes Bi by using (1)for i = 1, 2, . . . , N. The computational complexity of thismethod is O(N 3 ), which becomes very large as the numberof vertices increases.
The most widely used algorithm for computing the betweenness centrality is the one proposed by Brandes [3]. It
is described as follows.
Algorithm 1 (Brandes’s Algorithm)
Input: A simple connected undirected graph G = (V, E)
Output: B1 , B2 , . . . , BN

2. Find G s = (V, E s ) by using the breadth-first search. In
so doing, find also d si and σ si for i = 1, 2, . . . , N.

4. Update the value of δ s (i) byδ s (i) ←∑σ si(1 + δ s ( j)),σsj
j:(i, j)∈E

Let us consider the computational complexity of this algorithm. Step 2 can be done in O(M) time, where M is thenumber of edges. Step 4 can be done in O(M) too, becauseN
we can update the values of {δ s (i)}i=1
while traversing thevertices once in non-increasing order of their distance froms [3]. Therefore, the total computational complexity of Algorithm 1 is O(N M), which is in general lower than O(N 3 ).
In particular, the former is much lower than the latter if
M ≪ N 2 , that is, the graph is sparse.
3. Theoretical Analysis of the Eﬀect of One Edge Addition on Betweenness Centrality
Let G′ = (V, E ′ ) be the graph obtained from a graph
G = (V, E) by adding an edge e = {α, β} < E. The setof all shortest paths from vertex s to vertex t (, s) in G′ isdenoted by the directed graph G′st = (V st′ , E ′st ). The set of
all shortest paths from s to all other vertices in G′ is denoted by G′s = (V, E ′s ). The number of shortest paths froms to t and the length of these paths are denoted by σ′st andd′st , respectively. The number of shortest paths from s to tthat pass through i is denoted by σ′st (i).
In this section, we show that the values of σ′st , σ′st (i) and′d st can be computed from {σ pq }Np,q=1 and {d pq }Np,q=1 . We
hereafter assume without loss of generality thatd sα ≤ d sβ .

′We also assume for convenience that V ss = V ss
= {s}, E ss =′′′E ss = ∅, σ ss = σ ss = 1 and d ss = d ss = 0 for all s ∈ V.

Theorem 1 Under the assumption (2), the following statements hold true.

2. If d sα < d sβ and d sα + dβt + 1 = d st then i) G′st consistsof G st , G sα , the directed edge (α, β), and Gβt , ii) σ′st =σ st + σ sα σβt , and iii) d′st = d st .
3. If d sα = d sβ and d sα + dβt + 1 > d st then i) G′st = G st ,ii) σ′st = σ st , and iii) d′st = d st .
Theorem 2 Under the assumption (2), the following statements hold true.

si = 1, 2, . . . , s − 1, s + 1, s + 2, . . . , N.

1. If d sα < d sβ and d sα + dβt + 1 < d st thenσ σ σ , if i ∈ V sα , si iα βt
σσ′st (i) = sα σβi σit , if i ∈ Vβt , 0,
if i < V sα ∪ Vβt .

5. Update the value of Bi by
Bi ← Bi + δ s (i),(2)

1. If d sα < d sβ and d sα +dβt +1 < d st then i) G′st consists of
G sα , the directed edge (α, β) and Gβt , ii) σ′st = σ sα σβt ,and iii) d′st = d sα + 1 + dβt .

1. Set s ← 1 and Bi ← 0 for i = 1, 2, . . . , N.

3. Set δ s (i) ← 0 for i = 1, 2, . . . , N.

6. If s = N then return B1 , B2 , . . . , BN and stop. Otherwise set s ← s + 1 and go to Step 3.

i = 1, 2, . . . , N.

- 615 -

2. If d sα < d sβ and d sα + dβt + 1 = d st thenTable 1: Computation time for random graphs.
N
M
Proposed (sec) Simple (sec)
70
387
0.062
12.453
100
873
0.265
96.812150 1867
1.281
986.25200 3317
4.031
5910.172250 5083
9.968
23525.422
σ (i) + σ si σiα σβt , if i ∈ V sα , st
σ st (i) + σ sα σβi σit , if i ∈ Vβt ,σ′st (i) =  σ (i),
if i < V sα ∪ Vβt .
st
3. If d sα = d sβ or d sα + dβt + 1 > d st then σ′st (i) = σ st (i).
We omit the proofs of these theorems due to space constraints.
Note that we need to check the conditions i ∈ V sα andi ∈ Vβt in order to compute σ′st (i). However, this is easily
done because it is well known that i ∈ V pq if and only if
d pq = d pi + diq . Note also that the value of σ st (i) is required
for the computation of σ′st (i). However, σ st (i) can be easily
obtained by{σ si σit , if d si + dit = d st ,σ st (i) =0,
if d si + dit , d st .
Thus σ′st (i) can be computed from {σ pq }Np,q=1 and {d pq }Np,q=1 .

Table 2: Computation time for scale-free graphs.
N
M
Proposed (sec) Simple (sec)
70 204
0.094
7.203
100 294
0.328
40.891150 4441.609
302.077
200 594
4.968
1197.421
250 744
11.8903520.593
2. If s = i then go to Step 8. Otherwise go to Step 3.
3. Set t ← 1.

4. Proposed Algorithm

4. If t ∈ {i, s} then go to Step 7. Otherwise go to Step 5.

We consider in this section the problem of finding theedge to be added to minimize the betweenness centralityof a specified vertex. For this problem, the following algorithm is easily derived from the theoretical results in theprevious section.

5. Compute σ st and σ st (i) by Theorem 1 and Theorem 2,
respectively.

Algorithm 2
Input: G = (V, E) and i ∈ V.
Output: Edge {α, β} < E to be added.

7. If t = N then go to Step 8. Otherwise set t ← t + 1 andgo to Step 4.
8. If s = N then return B′i and stop. Otherwise set s ←s + 1 and go to Step 2.

1. Compute {σ pq }Np,q=1 and {d pq }Np,q=1 for G by thebreadth-first search algorithm.
2. Set Bmin ← ∞ and α ← 1.
3. Set β ← α + 1.
4. If {α, β} ∈ E then go to Step 7. Otherwise go to Step 5.
5. Compute B′i by Algorithm 3 given below.
6. If B′i < Bmin then set Bmin ← B′i , αmin ← α and βmin ←β.
7. If β = N then go to Step 8. Otherwise set β ← β + 1
and go to Step 4.
8. If α = N − 1 then return {αmin , βmin } and stop. Otherwise set α ← α + 1 and go to Step 3.
Algorithm 3
Input: G = (V, E), {σ pq }Np,q=1 , {d pq }Np,q=1 , {α, β} < E andi∈V
Output: B′i
1. Set s ← 1 and B′i ← 0.

6. B′i ← B′i + σ st (i)/σ st

Let us examine the computational complexity of Algorithm 2. Step 1 can be done in O(N M) time. Step 5, that
is, Algorithm 3 can be accomplished in O(N 2 ) time, andthere are N(N − 1)/2 − M candidates for the edge to be
added. Therefore, we can conclude that the computational
complexity of Algorithm 2 is O(N 4 ).
In Step 5 of Algorithm 2, we can employ Algorithm 1
instead of Algorithm 3. In this case, Step 1 can be skipped.
Also, unnecessary computations in Steps 4 and 5 of Algorithm 1 can be skipped too. Nevertheless, the computational complexity of this simple algorithm is O(N 3 M)
which is higher than O(N 4 ).
5. Application of the Proposed Algorithm to Vertex
with the Maximum Betweenness Centrality
In order to evaluate the eﬃciency of the proposed algorithm, the authors applied Algorithm 2 and the algorithm
mentioned in the last paragraph of the previous section,
which is hereafter called the simple algorithm, to randomgraphs [4] and scale-free graphs [5]. By a random graph,
we mean a graph such that each pair of vertices is connected with probability p. In the experiments, the value- 616 -

Table 3: The largest betweenness centrality before and afteran edge addition to random graphs.
N
M
Before
After
Diﬀ.
70
387
83.26176.778 −6.483
100
873 110.542 107.266 −3.276
150 1867 132.943 130.914 −2.029
200 3317 183.125 181.772 −1.353
250 5083 243.350 241.127 −2.223

1

6

4

2

7

5

3

9

8

10

11

Figure 2: A graph with 11 vertices and 16 edges.
Table 4: The largest betweenness centrality before and afteran edge addition to scale-free graphs.
N
M
BeforeAfter
Diﬀ.
70 2041327.625
1307.093 −20.532
100 2943330.202
3303.231 −26.971
150 4448228.860
8178.460 −50.400
200 594 15834.116 15776.048 −58.068
250 744 25438.355 25367.843 −70.512

11 vertices of the graph, vertex 3 has the largest betweenness centrality, which is 11.50. If Algorithm 2 is applied tovertex 3 of this graph, it returns edge {2, 10}. In fact, thisedge can decrease the betweenness centrality of vertex 3 to2.95. However, it also increases the betweenness centralityof vertex 2 from 10.75 to 14.50.
6. Conclusionof p was set to 0.1666. Scale-free graphs were generated
by the process proposed by Barabási and Albert [5]. To
be more specific, we start with the complete graph with m0
vertices, and then add new vertices one by one. When a
new vertex is added, it is connected to m (≤ m0 ) existingvertices with a probability that is proportional to their degrees. In the experiments, the values of m0 and m were set
to 4 and 3, respectively. For each of the graphs mentioned
above, the vertex with the largest betweenness centrality
was chosen as the specified vertex. All algorithms were
implemented with C language, complied with gcc version
5.3.0 and executed on a PC with Intel Core i5 4590 processor and 8GB RAM.
Computation time of the two algorithms is shown in Tables 1 and 2. In the case of random graphs, the proposed
algorithm is faster than the simple one by a factor of 200 to
2360 as shown in Table 1. In the case of scale-free graphs,
the proposed algorithm is faster than the simple one by afactor of 77 to 296 as shown in Table 2. These results suggest the eﬀectiveness of the proposed algorithm.
If the edge found by the proposed algorithm is added
to the graph, the betweenness centrality of the vertex having the largest betweenness centrality among all vertices isminimized. However, it is not guaranteed that the largest
betweenness centrality of the graph decreases. If the betweenness centrality of some vertex other than i, which isthe vertex having the largest betweenness centrality before
the edge is added, becomes greater than Bi by the additionof the edge, the largest betweenness centrality increases.
So let us examine whether or not the largest betweenness
centrality is decreased by the edge addition. Results areshown in Tables 3 and 4, from which we see that the largest
betweenness centrality decreases for all graphs used in theexperiments. However, this is not always true. To see
this, let us consider the graph shown in Fig. 2. Among

The problem of finding the edge to be added that minimizes the betweenness centrality of a specified vertex of agraph has been studied in this paper. We first analyzed theoretically the eﬀect of an edge addition on the number andlength of the shortest paths between each pair of vertices.
We then developed an algorithm, which is based on the theoretical analysis, for solving the problem and demonstrated
the eﬃciency by experiments.
Acknowledgement
This work was partially supported by JSPS KAKENHI
Grant Number JP15K00035.
References[1] D. J. Watts and S. H. Strogatz, “Collective dynamics
of ‘small-world’ networks,” Nature, vol.393, pp.440–
442, 1998.
[2] L. C. Freeman, “A set of measures of centrality basedon betweenness,” Sociometry, vol.40, no.1, pp.35–41,
1977.
[3] U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical Sociology, vol.25,
no.2, pp.163–177, 2001.
[4] E. N. Gilbert, “Random graphs,” The Annals of
Mathematical Statistics, vol.30, no.4, pp.1141–1144,
1959.
[5] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol.286, no.5439,
pp.509–512, 1999.

- 617 -