2015 International Symposium on Nonlinear Theory and its Applications
NOLTA2015, Kowloon, Hong Kong, China, December 1-4, 2015

Proposal of a Truly Decentralized Algorithm for Estimating
Algebraic Connectivity of Multi-Agent Networks
Kazuma Yamane and Norikazu Takahashi†Graduate School of Natural Science and Technology, Okayama University
3–1–1 Tsushima-naka, Kita-ku, Okayama, 700–8530 Japan
Email: yamane@momo.cs.okayama-u.ac.jp, takahashi@cs.okayama-u.ac.jp
Abstract—Algebraic connectivity, the second smallest
eigenvalue of the Laplacian matrix, of a network is an important quantity that represents how well the network isconnected. In this paper, we propose a novel method foreach agent in a network to estimate the algebraic connectivity of the network. The proposed method is truly decentralized because each agent updates the state value by using
the information obtained from only agents in the neighborhood. The validity of the proposed method is confirmed bytheoretical analysis and numerical experiments.

show the validity from both theoretical and experimental
points of view. The proposed algorithm is a combinationof the one given by Yang et al. [3] and a dynamic averageconsensus algorithm. Here, by dynamic average consensus, we mean that the state value of each agent tracks theaverage of multiple time-varying reference signals [6, 7].
Because each agent updates the state value by using the information obtained from only agents in the neighborhood,the proposed algorithm is truly distributed.

1. Introduction

2. Conventional Algorithm

One of the fundamental issues in mobile agent networks
is how to keep the connectivity [1]. A promising approachto this problem is to make use of the algebraic connectivity, which is defined as the second smallest eigenvalue ofthe Laplacian matrix [2]. The algebraic connectivity is an
important measure that represents how well the network isconnected. In particular, it takes a positive value if andonly if the network is connected. However, it is not so easy
for agents to compute or estimate the algebraic connectivity because each agent in general cannot communicate withall agents in the network.
Recently, Yang et al. [3] proposed a continuous-time algorithm for agents to estimate the algebraic connectivity of
the network. They also proved analytically that the valueof the algebraic connectivity estimated by each agent converges to the true one for almost all initial conditions. A
few years later, Fukami and Takahashi [4] proposed a modified algorithm, which is more suitable for hardware implementation, and proved that the algebraic connectivity canbe estimated by their algorithm too. However, these twoalgorithms are not decentralized in a strict sense, because
they are based on a strong assumption that each agent cancompute the average of the state values of all agents instantaneously. Yang et al. claim that the computation of theaverage can be done quickly by using some average consensus algorithm [5] with a very small time constant, but it
is not clear how to initialize the consensus algorithm.
In this paper, we propose a novel continuous-time algorithm for the estimation of the algebraic connectivity, andLet us consider a network of n agents labeled from 1 ton that communicate with each other. Throughout this paper, we assume that the communication topology is staticand symmetric, that is, if agent i can communicate withagent j then agent j can communicate with agent i. Under these assumptions, the communication between agentsis expressed by an undirected graph G = (V, E) whereV = {1, 2, . . . , n} is the set of vertices representing agentsand E is the set of undirected edges such that {i, j} ∈ E
if and only if agents i and j can communicate with eachother. The set of all vertices adjacent to vertex i is called
the neighborhood of vertex i and denoted by Ni . The adjacency matrix is denoted by A = (ai j ) ∈ {1, 0}n×n whereai j = 1 if and only if {i, j} ∈ E. The degree matrix is denoted by D = diag(d1 , d2 , . . . , dn ) ∈ Zn×n
where Z+ is the+set of nonnegative integers and di = |Ni | for i = 1, 2, . . . , n.
The Laplacian matrix is defined by L = D − A. Let
λ1 , λ2 , . . . , λn be n eigenvalues of L. Because L is a real
symmetric matrix, its eigenvalues are real. Hence we assume without loss of generality that λ1 ≤ λ2 ≤ · · · ≤ λn .
Also, it is well known that λ1 is always zero and λ2 isnonzero if and only if G is connected. Let pi be a normalized eigenvector associated with λi for i = 1, 2, . . . , n.
Because L1 = 0, where 1 and 0 are vectors of all 1 and all0, respectively, p1 is either √1n 1 or − √1n 1.

This work was supported by JSPS KAKENHI Grant Number
15K00035.

The second smallest eigenvalue λ2 of L, which is called
the algebraic connectivity, reflects how well the graph isconnected. Yang et al. [3] proposed a continuous-time algorithm for agents to estimate the algebraic connectivity of
the graph representing the communication between agents.
Their algorithm is expressed by the following system of- 277 -

x̂i (0)diﬀerential equations:
 n 
 n

∑
 1 ∑ 
 1 ∑
ẋi = −k1 x j  −k2(xi − x j )−k3 x2j − 1 xi ,
n j=1
n j=1
j∈N
i

i = 1, 2, . . . , n (1)where xi (t) is the state value of agent i at time t andki (i = 1, 2, 3) are positive constants. By introducing x =(x1 , x2 , . . . , xn )T , (1) can be rewritten in a vector form as
follows:
)
(
)
(
1 T
1 T
(2)
ẋ = −k1 1 x 1 − k2 Lx − k3 x x − 1 x .
nnYang et al. analyzed the dynamical behavior of (2) and
derived the following theorem.
Theorem 1 (Yang et al. [3]) Suppose that the network isconnected and the initial value x(0) satisfies pT2 x(0) , 0.
Then any solution x(t) of (2) converges to either µp2 or−µp2 where µ is a positive constant given by√n(k3 − k2 λ2 )µ=k3
if and only if k1 > λ2 k2 and k3 > λ2 k2 .
From Theorem 1 we can easily see that∑
(Lx(t))i (L(µp2 ))ij∈Ni (xi (t) − x j (t))
lim
= lim
=
= λ2
t→∞
t→∞
xi (t)xi (t)µp2i(3)which means that the algebraic connectivity λ2 can be obtained from the solution x(t) of (1). However, it is assumed∑∑in (1) that the values of nj=1 x j (t) and nj=1 xi (t)2 can becomputed instantaneously. This assumption cannot be met
in general because each agent does not necessarily communicate with all other agents. Yang et al. claim that the∑∑values of nj=1 x j (t) and nj=1 xi (t)2 can be computed almost
instantaneously by using some consensus algorithm, suchas the one proposed by Olfati-Saber and Murray [5], witha much smaller time constant than the main algorithm (1).
However, there still remain some problems to be solved,
such as how to set the initial value of the consensus algorithm.

=

3.1. Dynamic Average Consensus Algorithm
In order to develop a truly decentralized algorithm forthe estimation of the algebraic connectivity of the network,a dynamic average consensus algorithm is needed. We propose to use the continuous-time algorithm given byxi (t) =x̂˙i =x̂i (t) + ri (t), i = 1, 2, . . . , n ,∑α(x j − xi ), i = 1, 2, . . . , n ,
j∈Ni

(4)
(5)

i = 1, 2, . . . , n ,(6)where ri (t) is the time-varying input signal given to agent
i, and (xi (t), x̂i (t)) is the state vector of agent i at time t.
This algorithm is based on the one proposed by Chen etal. [6], but diﬀerent from it because the signum function is
not used in (5).
Theorem 2 Suppose that the network is connected andthere exist positive constants C and b such that∥ṙ(t)∥ ≤ Ce−bt∀t ≥ 0,(7)

where r(t) = (r1 (t), r2 (t), . . . , rn (t))T . Then the algorithm
given by (4)–(6) satisfies


n


1∑

lim  xi (t) −r j (t) = 0, i = 1, 2, . . . , n . (8)
t→∞
n j=1
Proof: Eliminating x̂1 (t), x̂2 (t), . . . , x̂n (t) from (4)–(6), we
have
=
=

ẋ
x(0)

−αLx + ṙ ,r(0) ,(9)(10)

where x(t) = (x1 (t), x2 (t), . . . , xn (t))T and L is the Laplacian matrix of the graph. Note that L is decomposed
as L = P ΛP T where P = (p1 , p2 , . . . , pn ) andΛ = diag(λ1 , λ2 , . . . , λn ) with λ1 = 0. Note also that
λ2 , λ3 , . . . , λn are positive because the network is assumed
to be connected. Multiplying P T from the left to bothsides of (9) and (10), and putting P T x(t) = y(t) =(y1 (t), y2 (t), . . . , yn (t))T , we haveẏ=−αΛy + P T ṙ ,

(11)

y(0)

=

P T r(0) .

(12)The solution of this diﬀerential equation is given byy1 (t) = pT1 r(t)

(13)

and
−αλi tyi (t) = e∫ t
0

3. Proposed Algorithm0,eαλi s pTi ṙ(s)ds+yi (0)e−αλi t , i = 2, 3, . . . , n .

(14)
From (14), we have∫ t
−αλi t|yi (t)| ≤ eeαλi s ∥pi ∥∥ṙ(s)∥ds + yi (0)e−αλi t0∫ t−αλi t≤ eeαλi sCe−bs ds + yi (0)e−αλi t
0∫ t= Ce−αλi te(αλi −b)s ds + yi (0)e−αλi t0if αλi = b ,Cte−αλi t ,−αλi t= yi (0)e+ C (e−bt − e−αλi t ), if αλi , b .
αλi −b- 278 -

Because λ2 , λ3 , . . . , λn are positive, we have
lim yi (t) = 0,i = 2, 3, . . . , n .

t→∞

11

(15)

7

3

10

1

9

It follows from (13) and (15) that the solution of (11) and(12) satisfies()
lim y(t) − (pT1 r(t), 0, 0, . . . , 0)T = 0 .

4
1

4

2

2
5

5

6

8

3

t→∞

12

(a)

Multiplying P from the left to both sides of this equation,
we havelim (x(t) − p1 pT1 r(t)) = 0

6
7

t→∞

3

14
1

5

2
18

3.2. Algebraic Connectivity Estimation Algorithmj∈Niyi (t) =ŷ˙ i (t) =8−k3 (zi (t) − 1)xi (t), i = 1, 2, . . . , n (16)ŷi (t) + xi (t), i = 1, 2, . . . , n(17)∑α(y j (t) − yi (t)), i = 1, 2, . . . , n (18)

10

16
9

We now propose a new continuous-time algorithm which
is obtained from (1) by replacing the computations of
1 ∑n
1 ∑n
2
j=1 x j (t) and n
j=1 x j (t) with the dynamic averagenconsensus algorithm given by (4)–(6). It is expressed by
the following system of diﬀerential equations:∑ẋi (t) = −k1 yi (t) − k2
(x j (t) − xi (t))

12

4

□

which is equivalent to (8).

(b)

11

13
15

17

20

19

(c)
Figure 1: Networks used in numerical experiments. Algebraic connectivities are: (a) 0.5188057, (b) 0.1794688, and(c) 0.4165522.
4. Numerical Experimentsj∈Niŷi (0)=zi (t) =ẑ˙i (t) =0,

i = 1, 2, . . . , nẑi (t) + xi2 (t),
α

∑

(19)

i = 1, 2, . . . , n(20)(z j (t) − zi (t)),

i = 1, 2, . . . , n (21)i = 1, 2, . . . , n

(22)

j∈Ni

ẑi (0)=0,where (xi (t), yi (t), ŷi (t), zi (t), ẑi (t))T is the state vector ofagent i at time t. The first element xi (t) represents the estimated value of the algebraic connectivity. The second element yi (t) and the fourth element zi (t) represent the esti∑∑
mated values of 1n nj=1 x j (t) and 1n nj=1 x j (t)2 , respectively.
Because each agent only needs information of itself and its
neighbors in order to update the state vector, the proposed
algorithm is truly decentralized.
If the network is connected and x(t) satisfies∀t ≥ 0,∥ẋ(t)∥ ≤ Ce−bt(23)

for some positive constants C and b, then it follows from∑
Theorem 2 that yi (t) − 1n nj=1 x j (t) converges to 0 for all∑i and zi (t) − 1n nj=1 x j (t)2 converges to 0 for all i. In thiscase, it is expected that x(t) converges to an eigenvectorof L associated with λ2 and that the algebraic connectivity
can be estimated by (3). However, it is not clear whether(23) is true or false because the behavior of x(t) depends
on y1 (t), y2 (t), . . . , yn (t) and z1 (t), z2 (t), . . . , zn (t). Theoretical analysis of the convergence property of the proposed
algorithm is a future problem.

In order to examine the validity of the proposed method,
we conducted some numerical experiments. To be more
specific, for each of the three networks shown in Fig.1, we
found the solution x(t) of the system of diﬀerential equations described by (16)–(22) numerically by using Euler’s
method with a step size of 0.005, and then checked whether
x(t) converged to an eigenvector of L associated with λ2
and whether λ2 was correctly estimated by (3). The valuesof positive constants k1 , k2 , k3 and α were set to 1, and theinitial value x(0) was determined randomly.
Results are shown in Figs.2–5. Fig.2 shows the waveforms of | cos θ(t)| = |x(t)T p2 |/∥x(t)∥ and ∥x(t)∥ for the
network shown in Fig.1(a). Because | cos θ(t)| converges to
1 and ∥x(t)∥ converges to a positive constant, we can conclude that x(t) converges to an eigenvector of L associatedwith λ2 . Fig.3 shows the waveforms of the values of thealgebraic connectivity estimated by the five agents in thesame network. We see there that all of the five estimatedvalues converge to the true value. From these observations,
we can conclude that the proposed algorithm works properly for the network shown in Fig.1(a). We also see from
Figs.4 and 5 that the proposed algorithm works for othertwo networks in Fig.1.
5. Conclusion
We have proposed a new continuous-time algorithm forthe estimation of the algebraic connectivity of multi-agent- 279 -

2
estimated value of algebraic connectivity

1.2

and

1.5

1

0.5

1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6

0
0

10

20

30

40

50

60

70

0

80

Figure 2: Waveforms of | cos θ(t)| = |x(t)T p2 |/∥x(t)∥ and∥x(t)∥ for the network shown in Fig.1(a).
agent 1
agent 2
agent 3
agent 4
agent 5

1

20

30

40

50

60

70

80

∑
Figure 4: Waveforms of j∈Ni (xi (t) − x j (t))/xi (t) (i =1, 2, . . . , 12) for the network shown in Fig.1(b).
1.2
estimated value of algebraic connectivity

estimated value of algebraic connectivity

1.5

10

0.5

0

1
0.8
0.6
0.4
0.2
0
-0.2
-0.4

-0.5
0

10

20

30

40

50

60

70

80

0

10

20

30

40

50

60

70

80

∑
Figure 3: Waveforms of j∈Ni (xi (t) − x j (t))/xi (t) (i =1, 2, 3, 4, 5) for the network shown in Fig.1(a).

∑Figure 5: Waveforms of j∈Ni (xi (t) − x j (t))/xi (t) (i =1, 2, . . . , 20) for the network shown in Fig.1(c).

networks. The validity of the the proposed algorithm has
been confirmed by numerical experiments with three networks consisting of 5, 12 and 20 agents. However, it remains an open question whether the solution of the system of diﬀerential equations described by (16)–(22) always
converges to an eigenvector of the Laplacian matrix associated with the algebraic connectivity. This question will beanswered in future studies.

[4] T. Fukami and N. Takahashi, “A new continuoustime algorithm for calculating algebraic connectivityof multi-agent networks,” in Proceedings of 2012 International Symposium on Nonlinear Theory and its
Applications, 2012, pp. 45–48.

References[1] M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in Multiagent Networks. Princeton: Princeton
University Press, 2010.
[2] M. Fiedler, “Algebraic connectivity of graphs,”
Czechoslovak Mathematical Journal, vol. 23, no. 98,
pp. 298–305, 1973.
[3] P. Yang, R. Freeman, G. Gordon, K. Lynch, S. Srinivasa, and R. Sukthankar, “Decentralized estimationand control of graph connectivity for mobile sensor
networks,” Automatica, vol. 46, pp. 390–396, 2010.

[5] R. Olfati-Saber and R. M. Murray, “Consensus protocols for networks of dynamic agents,” in Proceedingsof the 2003 American Control Conference, June 2003,
pp. 951–956.
[6] F. Chen, Y. Cao, and W. Ren, “Distributed average
tracking of multiple time-varying reference signals
with bounded derivatives,” IEEE Transactions on Automatic Control, vol. 57, no. 12, pp. 3169–3174, December 2012.
[7] S. S. Kia, J. Cortés, and S. Martı́nez, “Dynamic average consensus under limited control authority andprivacy requirements,” International Journal of Robustand Nonlinear Control, vol. 25, pp. 1941–1966, 2015.

- 280 -