2019 International Symposium on Nonlinear Theory and Its Applications
NOLTA2019, Kuala Lumpur, Malaysia, December 2-6, 2019.

A Genetic Algorithm for Maximizing Algebraic Connectivity of Graphs by
Adding Multiple Edges
Hiroki Tajiri, Tsuyoshi Migita and Norikazu Takahashi
Graduate School of Natural Science and Technology, Okayama University
3-1-1 Tsushima-naka, Kita-ku, Okayama 700–8530, Japan
Email: tajiri@momo.cs.okayama-u.ac.jp, migita@cs.okayama-u.ac.jp, takahashi@cs.okayama-u.ac.jp
Abstract—The second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, of agraph represents how well the graph is connected. This
paper considers the problem of maximizing the algebraic
connectivity of graphs by adding a prescribed number ofedges. We propose a genetic algorithm for this problem
and evaluate its performance through experiments.
1. Introduction
Distributed computation is an important technique for
network systems such as the Internet, sensor networks andmultirobot systems. Some distributed algorithms over network systems are characterized by the algebraic connectivity [1, 2], the second smallest eigenvalue of the Laplacianmatrix. For example, the convergence speed of a consensus
algorithm is determined by the algebraic connectivity [3].
Thus, in order to achieve fast convergence, we need to design the network with a high algebraic connectivity [4].
Recently, Li et al. considered the problem of maximizing
the algebraic connectivity of undirected graphs by adding
one edge, and proposed a simple algorithm called the
Minimum Degree and Maximum Distance (MDMD) [5].
Roughly speaking, this algorithm ﬁrst selects one vertex
i with the minimum degree, then selects another vertex jhaving the maximum distance from i, and ﬁnally adds theedge connecting i and j. The MDMD algorithm has a very
low computational cost because the computation of the algebraic connectivity is not needed. Nevertheless, it can obtain high algebraic connectivity values as reported in [5].
In this paper, we consider a more general form of theabove-mentioned problem, in which the number of edges to
add is not restricted to one, and propose a genetic algorithm
for ﬁnding an approximate solution. Genetic algorithms
have proved to be powerful tools for various combinatorial
optimization problems [6]. We show through experiments
using small graphs that the proposed algorithm can achieve
higher algebraic connectivity values than a simple extension of the MDMD algorithm.
2. Notations and Problem Statement
Let G = (V, E) be a simple undirected graph with thevertex set V = {1, 2, . . . , n} and the edge set E. The undirected edge connecting vertices i and j is denoted by {i, j}.

Let A = (ai j ) ∈ {0, 1}n×n be the adjacency matrix of G.
Then ai j (= a ji ) takes 1 if {i, j} ∈ E and 0 otherwise. Notethat aii = 0 for all i ∈ {1, 2, . . . , n} because G is simple.
Let D = diag(d1 , d2 , . . . , dn ) be the degree matrix of G,∑
where di is the degree of vertex i and thus equal to nj=1 ai j .
The Laplacian matrix L = (ℓi j ) ∈ Zn×n of G is deﬁned by
L = D − A. Because L is positive-semi deﬁnite, all eigenvalues of L are nonnegative real numbers. In addition, because L1 = 0 where 1 is the vector of all ones, the smallest
eigenvalue of L is 0. The eigenvalues of L are denoted by
λ1 (= 0) ≤ λ2 ≤ λ3 ≤ · · · ≤ λn . The second smallest eigenvalue λ2 is called the algebraic connectivity of G [1, 2].
In what follows, by a graph, we always mean a simple
undirected graph. For a graph G = (V, E) and a positive
integer k, the set of all graphs obtained from G by adding kedges is denoted by G(G, k). In other words,
G(G, k) ≜ {G′ = (V, E ∪ E + ) | E ∩ E + = ∅, |E + | = k}. (1)The problem we consider in this paper is stated as follows.
Problem 1 Given a graph G = (V, E) and an integer k satisfying 1 ≤ k ≤ |V|(|V|−1)/2−|E|, ﬁnd a graph G∗ ∈ G(G, k)that maximizes the algebraic connectivity among all graphsin G(G, k).
Problem 1 is a generalization of the problem consideredin [5] because the latter corresponds to the special case of
the former where the value of k is restricted to 1. The
simplest approach to Problem 1 is the brute-force search,
but the time complexity of this algorithm is very high evenwhen k = 1 [5]. So we need to develop eﬃcient approximation algorithms.
3. Sequential MDMD Algorithm
In this section, we ﬁrst review the Min-Degree and MaxDistance (MDMD) algorithm developed by Li et al. [5] forsolving the special case of Problem 1 where k = 1. We thenpresents a simple method called the sequential MDMD algorithm for solving Problem 1.
The MDMD algorithm chooses an edge to be added to G
based on the degrees of vertices, the distance between two
vertices, and the Extendibility Centralities (EC) deﬁned by- 138 -

ci ≜

n
∑
k=1

aik dk ,i = 1, 2, . . . , n.

(2)

Algorithm 1 MDMD Algorithm [5]Input: G = (V, E)
Output: Gout = (V, Eout )1: Set I ← {i ∈ V | di ≤ di′ for all i′ ∈ V}.
2: Select one i∗ ∈ I such that ci∗ ≤ ci for all i ∈ I.
3: Set J ← { j | j has the maximum distance from i∗ }.
4: Select one j∗ ∈ J such that c j∗ ≤ c j for all j ∈ J.
5: Set E out ← E ∪ {{i∗ , j∗ }} and return G out = (V, E out ).
Algorithm 2 SMDMD Algorithm
Input: G = (V, E), k ∈ N
Output: Gout = (V, Eout )1: Set G 0 ← G and m = 0.
2: Apply the MDMD algorithm (Algorithm 1) to G m toget a new graph Gm+1 .
3: Set m ← m + 1.
4: If m = k then return G m and stop. Otherwise go backto Step 2.
It ﬁrst selects one vertex i∗ which has the minimum degree
and the minimum EC among all vertices with the same degree. It then selects another vertex j∗ which has the maximum distance from i∗ and the minimum EC among all vertices with the same distance from i∗ . It ﬁnally returns theedge {i∗ , j∗ }. The main advantage of the MDMD algorithm
is its low computational cost because the computation of
the algebraic connectivity is not needed. The MDMD algorithm is formally described as Algorithm 1.
Although the MDMD algorithm was developed for the
special case of Problem 1 where k = 1, we can easily extend it to obtain a new algorithm that can be used for thegeneral case. The idea is to apply the MDMD algorithm sequentially. We thus call this new algorithm the sequential
MDMD (SMDMD) algorithm. The SMDMD algorithm isformally described as Algorithm 2.
4. Proposed Genetic Algorithm
In this section, we propose a genetic algorithm for ﬁnding an approximate solution of Problem 1.
4.1. Overview of Algorithm
In the proposed algorithm, each graph is encoded intoa binary sequence called a chromosome by concatenatingrows in the strict upper triangular part of the adjacency matrix, as shown in Fig. 1. Also, the ﬁtness value of eachchromosome is deﬁned by the algebraic connectivity of thecorresponding graph.
Given a graph G = (V, E) and an integer k satisfying
1 ≤ k ≤ |V|(|V| − 1)/2 − |E|, the algorithm ﬁrst generates a population of M chromosomes corresponding to M
graphs selected at random from G(G, k). Each chromosome
can be easily generated by randomly selecting k bits with avalue of 0 in the chromosome sG corresponding to G and

Figure 1: Encoding a graph into a chromosome (upper:
graph, middle: adjacency matrix, lower: chromosome).
then ﬂipping the selected bits to 1. Once the initial population of chromosomes is generated, the algorithm theniteratively updates the population in the way explained in
the next subsection until some stopping condition is met. In
what follows, each iteration is called a generation, and the
population in the t-th generation is denoted by P(t) (P(1)
is the initial population). Finally the algorithm returns thegraph corresponding to the chromosome with the highest
ﬁtness value in the ﬁnal population.
4.2. How to Update Population
Given the population P(t) of M chromosomes, the proposed algorithm performs the following three steps to obtain P(t + 1) of M chromosomes: selection, crossover andmutation. The algorithm also uses the elitist selection.
In the selection step, a new population P1 (t) of M chromosomes is generated from P(t). Suppose that P1 (t) is initialized to ∅. First, one chromosome with the highest ﬁtness
value is selected from P(t) and added to P1 (t) . Next, M − 1chromosomes are selected (with repetition allowed) from
P(t) by a tournament selection rule and added to P1 (t). The
tournament selection rule used in our algorithm is to select one chromosome with the highest ﬁtness value amongℓ chromosomes selected at random from P(t).
In the crossover step, a new population P2 (t) of M chromosomes is generated from P1 (t). Suppose that P2 (t) is
initialized to ∅. First, the chromosome ﬁrst added to P1 (t)is selected and added to P2 (t). Next, ⌊(M − 1)/2⌋ pairsof chromosomes are randomly made from the remaining
M−1 chromosomes. For each pair, a single-point crossoveris performed with probability pc ∈ (0, 1). However, thecrossover point cannot be chosen freely because the resulting two chromosomes must have the same number ofones as their parents. So Algorithm 3 is used to perform asingle-point crossover and the obtained two chromosomes
are added to P2 (t). If M is even then the chromosome inP1 (t) that was not used to make a pair is added to P2 (t).
In the mutation step, a new population P3 (t) = P(t +1) of M chromosomes is generated from P2 (t). Supposethat P3 (t) is initialized to ∅. Let sG be the chromosome- 139 -

5

corresponding to G and let IG = {i ∈ {1, 2, . . . , N} | sGi =1}. Let pm ∈ (0, 1) be the mutation probability. First thechromosome ﬁrst added to P2 (t) is added to P3 (t). Next,
for each of the remaining M − 1 chromosomes s in P2 (t), a
new chromosome s′ is obtained by Algorithm 4 and added
to P3 (t). Note here that s′ not only satisﬁes s′i = 1 for alli ∈ IG but also has the same number of ones as s.
5. Experiments
In order to evaluate the performance of the proposed
genetic algorithm in comparison with the SMDMD algorithm, we conducted experiments using 20 synthetic
graphs: 10 Watts-Strogatz models [7] with 10 vertices and
20 edges and 10 Barabási-Albert models [8] with 10 vertices and 12 edges. The parameters in the proposed algorithm were set as M = 50, ℓ = 5, pc = 0.8 and pm = 0.05.
Also, the proposed algorithm stops when the number ofgeneration t reaches 200. Both algorithms were imple-

3

2

1

0
1

2

3

4

5
6
Graph ID

7

8

9

10

Figure 2: Algebraic connectivity obtained by the two algorithms for Watts-Strogatz models with 10 vertices and 20
edges and k = 5. The plots show the average of 10 runs.
original
SMDMD
GA

2

Algebraic Connectivity

7: Return s′1 and s′2 and stop.

Algorithm 4 Mutation
Input: s = (s1 , . . . , sN ) ∈ {0, 1}N , IG ⊂ {1, 2, . . . , N}, pm ∈(0, 1)
Output: s′ = (s′1 , . . . , s′N ) ∈ {0, 1}N
1: Set s′ ← s.
2: Set f ← 0 and i ← 1.
3: If i ∈ IG then go to Step 7. Otherwise go to Step 4.
4: Pick a number r from a uniform distribution in [0, 1].
5: If r ≤ pm then set s′i ← 1 − s′i and f ← f + 1 and go to
Step 6. Otherwise go to Step 7.
6: Select j ∈ {1, 2, . . . , N} \ (IG ∪ {i}) such that s′j = s′i atrandom and then set s′j ← 1 − s′j .
7: Set i ← i + 1. If i = N + 1 or f = 2 then return s′ andstop. Otherwise go to Step 3.

original
SMDMD
GA

4
Algebraic Connectivity

Algorithm 3 Single-Point Crossover
Input: si = (si1 , . . . , siN ) ∈ {0, 1}N (i = 1, 2), pc ∈ (0, 1)
Output: s′i = (s′i1 , . . . , s′iN ) ∈ {0, 1}N (i = 1, 2)
1: Pick a number r from a uniform distribution in [0, 1].
2: If r > pc then set s′i ← si for i = 1, 2 and go to Step 5.
Otherwise go to Step 3.
3: Select j∗ uniformly at random from {1, 2, . . . , N}.
∑N
∑N
4: If
j= j∗ s1 j =j= j∗ s2 j then go to Step 6. Otherwise
go to Step 5.
5: Set j∗ ← j∗ + 1 and go to Step 4.
6: Set s1 j , if j ∈ {1, 2, . . . , j∗ − 1},′
s1 j ←  s2 j , if j ∈ { j∗ , j∗ + 1, . . . , N}, s2 j , if j ∈ {1, 2, . . . , j∗ − 1},′s2 j ←  s1 j , if j ∈ { j∗ , j∗ + 1, . . . , N}.

1.5

1

0.5

0
1

2

3

4

5
6
Graph ID

7

8

9

10

Figure 3: Algebraic connectivity obtained by the two algorithms for Barabási-Albert models with 10 vertices and 12
edges and k = 5. The plots show the average of 10 runs.
mented in Scilab 5.5.2 and executed on a PC with Intel
Core i5-4670 and 8GB RAM.
In the ﬁrst experiment, we applied the two algorithms
to the problem of maximizing the algebraic connectivity ofWatts-Strogatz models with 10 vertices and 20 edges byadding ﬁve edges. The results are summarized in Fig. 2. It
is easy to see that both algorithms increased the algebraic
connectivity by about two times and that the proposed algorithm achieved a higher algebraic connectivity than the
SMDMD algorithm for all graphs.
In the second experiment, we applied the two algorithms
to the problem of maximizing the algebraic connectivity of
Barabási-Albert models with 10 vertices and 12 edges byadding ﬁve edges. The results are summarized in Fig. 3.
The proposed algorithm achieved a higher algebraic connectivity than the SMDMD algorithm for all graphs. In particular, the algebraic connectivity obtained by the former isnearly two times higher than the latter for some graphs. An
example is shown in Fig. 4.
In the third and fourth experiments, we applied the twoalgorithms to the problem of maximizing the algebraic connectivity of Watts-Strogatz models with 10 vertices and 20
edges by adding 15 edges, and the problem of maximizing
the algebraic connectivity of Barabási-Albert models with- 140 -

5

5

5

6

4

6

6

4

4

7

3

7

3

7

3

8

2

8

2

8

2

9

1

9

9

1

1

10

10

10

(a)

(b)

(c)

Figure 4: Comparison of the graphs obtained by the two algorithms. (a) Input (λ2 = 0.2881471). (b) Graph obtained by
the SMDMD algorithm (λ2 = 0.887342). (c) Graph obtained by the proposed algorithm (λ2 = 1.592531).

original
SMDMD
GA

8

Algebraic Connectivity

Algebraic Connectivity

7

original
SMDMD
GA

5

6
5
4
3

4

3

2

2
1
1
0

0
1

2

3

4

5
6
Graph ID

7

8

9

10

1

2

3

4

5
6
Graph ID

7

8

9

10

Figure 5: Algebraic connectivity obtained by the two algorithms for Watts-Strogatz models with 10 vertices and 20
edges and k = 15. The plots show the average of 10 runs.

Figure 6: Algebraic connectivity obtained by the two algorithms for Barabási-Albert models with 10 vertices and 12
edges and k = 15. The plots show the average of 10 runs.

10 vertices and 12 edges by adding 15 edges, respectively.
The results are summarized in Figs. 5 and 6. Both algorithms increased the algebraic connectivity by more than
three times for all graphs. Also, the proposed algorithm
achieved a higher algebraic connectivity than the SMDMD
algorithm for all graphs.

[2] C. Godsil and G. Royle, Algebraic Graph Theory,
Springer New York, 2001.

6. Conclusions
We proposed a genetic algorithm for solving the problem of maximizing the algebraic connectivity of a given
graph by adding a prescribed number of edges. We thenshowed experimentally that the proposed algorithm is superior to the SMDMD algorithm in terms of the algebraic
connectivity value. However, because only a small numberof graphs was used in the experiments, we need to evaluate
the performance of the proposed algorithm through further
experiments using graphs of various types and sizes. Also,
we need to decrease the computational cost of the proposed
algorithm so that it can be applied to large graphs.

[3] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol.95, no.1, pp.215–
233, January 2007.
[4] K. Ogiwara, T. Fukami and N. Takahashi, “Maximizing algebraic connectivity in the space of graphs with aﬁxed number of vertices and edges, IEEE Transactions
on Control of Network Systems, vol.4, no.2, pp.359–
368, June 2017.
[5] G. Li, Z. F. Hao, H. Huang and H. Wei, “Maximizing
algebraic connectivity via minimum degree and maximum distance,” IEEE Access, vol.6, pp.41249–41255,
2018.
[6] D. E. Goldberg, Genetic Algorithms, Pearson Educational India, 2006.

References[7] D. J. Watts and S. H. Strogatz, “Collective dynamics
of ‘small-world‘ networks,” Nature, vol.393, no.6684,
pp.440–442, 1998.

[1] M. Fiedler, “Algebraic connectivity of graphs,”
Czechoslovak Mathematical Journal, vol.23, no.98,
pp.298–305, 1973.

[8] A. L. Barabási and R. Albert, “Emergence of scaling in
random networks,” Science, vol.286, no.5439, pp.509–
512, 1999.

- 141 -