# Fast Consensus Seeking on Networks with Antagonistic Interactions

Authors: Jijun Qu; Zhijian Ji; Chong Lin; Haisheng Yu
Journal: Complexity
 (2018)

---

## Abstract

It is well known that all agents in a multiagent system can asymptotically converge to a common value based on consensus protocols. Besides, the associated convergence rate depends on the magnitude of the smallest nonzero eigenvalue of Laplacian matrixL. In this paper, we introduce a superposition system to superpose to the original system and study how to change the convergence rate without destroying the connectivity of undirected communication graphs. And we find the result if the eigenvector x of eigenvalue λ has two identical entries xi=xj, then the weight and existence of the edge eij do not affect the magnitude of λ, which is the argument of this paper. By taking advantage of the inequality of eigenvalues, conditions are derived to achieve the largest convergence rate with the largest delay margin, and, at the same time, the corresponding topology structure is characterized in detail. In addition, a method of constructing invalid algebraic connectivity weights is proposed to keep the convergence rate unchanged. Finally, simulations are given to demonstrate the effectiveness of the results.


---

## Body

## 1. Introduction

In recent years, many issues related to consensus have been studied [1–10]. This is due to the large number of potential applications of consensus, ranging from engineering and computer science to biology, ecology, and social science. In [1], Jadbabaie proposed a nearest neighbor law to coordinate the control of the whole system, so that agents can reach a common final value. Olfati-Saber and Murray proposed a simple consensus protocol to achieve average consensus for undirected graphs and balanced digraphs in [2]. Based on quasi-consensus, Cai proposed an approach for clustering in [3]. And Liu proposed several necessary and sufficient conditions for consensus of second-order multiagent systems under directed topologies [4]. For high-order linear time-invariant singular multiagent systems with constant time delays, admissible output consensus design problem was investigated in [5]. For hybrid multiagent systems, necessary and sufficient conditions were also developed for the consensus [6, 7].The smallest nonzero eigenvalueλ2(L) of Laplacian L is the algebraic connectivity, which was first proposed by Fiedler [11]. Olfati-Saber and Murray conducted a preliminary discussion on the convergence rate of consensus and proposed the concept of communication cost [2]. The algebraic connectivity increases as the communication cost goes up. An approach of minimizing the guaranteed cost was given in [12]. For a stable system, we always expect that the system has a larger convergence rate. Based on the consensus protocol, the convergence rate becomes larger as the algebraic connectivity of the system increases.The convergence rate problem of consensus had been studied in [13–20]. The fast consensus and the optimization problem of convergence rate have been studied extensively [13]. The convergence rate of consensus was studied under the condition of weighted average in [14]. Jin proposed a multihop relay protocol to make a larger algebraic connectivity [15]. In [16], Olfati-Saber studied the fast consensus for small-world networks through randomly rewiring edges. In [18], Yang studied the optimization problem of convergence rate for second-order systems with time delays by the frequency-domain method. Yang proposed a new variable not only to measure the situation of optimization, but also to cope with the tradeoff between λ2(L) and λn(L). Xiao developed the results of delay margin by analyzing λn(L) in [17]. An optimal consensus protocol minimizing team cost function was proposed in [19], and an optimal synchronization protocol was designed for the largest convergence rate and minimal steady state error when the protocol is perturbed by an additive noise in [20].To improve the convergence rate of consensus in multiagent systems, we need to change the algebraic connectivityλ2(L). The variation of algebraic connectivity depends on the variation of weights and topologies of communication graphs. The algebraic connectivity can be improved by taking advantage of algorithms and graph theory, which was explored in [21–24]. The convergence rate is susceptible to the perturbation, which will further affect the stability of the system [25–28]. Based on former researchers’ works [29–37], we propose a concept of invalid algebraic connectivity weights (IACW), which is shown not only to be resistant to the perturbation but also can avoid unnecessary waste of costs. There are three methods to get a larger convergence rate: (1) changing the protocol; (2) changing the weights of a system; (3) changing the topology of a system. In this paper, we take methods (2) and (3). In particular, we investigate how the convergence rate varies when a superposition system is joined to the original system and present a detailed characterization for the variation of convergence rate. The results are developed by analyzing the variation of eigenvalues and eigenvectors of Laplacian matrix. Under fixed costs, we give the most optimal case, which can make the convergence rate and delay margin the largest. For a complete graph, if the cost is fixed, then λ2(L) reaches maximum and λn(L) reaches minimum. Thus, the convergence rate and delay margin achieve the biggest magnitude. Since the topology is unique, this achieves the optimization of convergence rate and delay margin. In addition, the method and conditions are put forward for the construction of invalid algebraic connectivity weights.In a multiagent network system, not all agents are cooperative. There are some agents which are competing. The cooperative and competitive relationship is represented, respectively, by positive weights and negative weights. Positive and negative weights have opposite effects on system performance. In some circumstances, negative weights are also needed. For example, in a system with time delay, the negative weights can reduce the magnitude ofλn(L^), which results in a larger delay margin. Hence, the fast consensus with antagonistic interactions is considered in the paper.The rest of the paper is organized as follows. In Section2, basic definitions, properties, and system model are addressed. In Section 3, we study the variation of convergence rate when a superposition system is superposed on the original system, and characterize the most optimal case of convergence rate under fixed cost. In Section 4, results are derived for the identification of invalid algebraic connectivity weights and the associated construction of IACW. In Section 5, simulation results are presented to show the effectiveness of the approach. Finally, conclusions are given in Section 6.


## 2. Consensus Protocol and Consensus State

LetG={V,E,A} be a weighted undirected graph, where V={v1,…,vn} denotes a set of n nodes, E⊆V×V denotes the set of edges, and A∈Rn×n is the adjacency matrix of undirected graph G. In this paper, if vi has a communication link with vj, then there is an edge eij∈E between nodes vi and vj, with aij=aji≠0, i,j∈{1,…,n}; and aij is the weight between nodes vi and vj. Here, the self-loop of V, under which aii=0,∀i=1,…,n, is not considered.The first-order multiagent system is given by(1)x˙i=-∑j∈Niaijxi-xjwhere xi denotes the state of agent i, which is the ith component of x; N(i) denotes the set of adjacent agents of agent i. The Laplacian matrix of G is represented by L=D-A, where D∈Rn×n is the diagonal connectivity degree matrix of A. So (1) can be written as(2)x˙=-LxThe entries of L can be written as (3)lij=-aiji≠j∑j∈Niaiji=j.D can be written as (4)D=diag∑j∈N1a1j,∑j∈N2a2j,…,∑j∈Nnanj.Assume that the communication graph consists ofn nodes, and the spectrum of eigenvalues is λ1(L)≤λ2(L)⋯≤λn(L). The spectrum means that the eigenvalues are arranged according to a certain order. Let S=span{u1,…,un} denote a vector space, in which any vector can be represented as a linear combination of u1,…,un; i.e., S={η∣η=k1u1+⋯+knun}. Below A∪A~ means that the entries of matrices A and A~ plus together. For A^=A∪A~, the entries of A^ are a^ij=aij+a~ij, where aij, a~ij are the entries of A, A~, respectively.Definition 1.
The system associated with graphG~={V,E~,A~}, which has the same node set V with the original graph G, is called a superposition system. Let G~ be superposed to G. We get a connected graph G^={V,E∪E~,A∪A~}. Then the system associated with G^ is called a superposed system.We give the definition of superposition system to represent the situation of the adding edges such asrank(L~), numbers, and weights of edges, so that we study the variation of superposed systems under different situations of adding edges.In this paper, graphG^ is connected and the spectrums of eigenvalues associated with both L~ and L^ are identical with L, where L~ denotes the Laplacian matrix of G~, 1≤rank(L~)≤n-1 and L^ denote the Laplacian matrix of G^. In what follows, L-L~≥0 means that L-L~ is positive semidefinite. Although there are negative weights, L~ can still be positive semidefinite or negative semidefinite.


## 3. Variation of Convergence Rate

The changing of algebraic connectivity relies on the variation of eigenvalues of LaplacianL. So the following lemma is introduced.Lemma 2 (Weyl theorem [38]).
LetA,B∈Rn×n be symmetric and the eigenvalues of A,B and A+B be ordered as that of L, respectively. Then(5)λiA+B≤λi+jA+λn-jB,j=0,1,…,n-ifor each i=1,…,n, with equality holding for some pair i,j if and only if there is a nonzero vector x such that Ax=λi+j(A)x,Bx=λn-j(B)x,(A+B)x=λi(A+B)x. Also,(6)λi-j+1A+λjB≤λiA+B,j=1,…,ifor each i=1,…,n, with equality holding for some pair i,j if and only if there is a nonzero vector x such that Ax=λi-j+1(A)x, Bx=λj(B)x, (A+B)x=λi(A+B)x. If A and B share no common eigenvectors, then (5) and (6) are strict inequalities.By Hermam Weyl theorem, some significant inequalities can be derived. This is essential to the development of results. In what follows, letA=L, B=L~, A+B=L^.


### 3.1. Convergence Rate of Undirected Graphs

For a systemx˙=-Lx which can achieve consensus, its eigenvalues satisfy λi(L)≥0 and are arranged in an increasing order, i=1,…,n. The solution of the system is x(t)=exp⁡(-Lt)x(0), where x(0) is the initial state of agents. Let -L=PJP-1, where J is the Jordan standard norm of -L, and the diagonal entries of J are the eigenvalues of -L. Then xt=exp⁡-Ltx0=Pexp⁡(Jt)P-1x(0). Let H=span{e-λ1(L)t,e-λ2(L)t,…,e-λn(L)t}. It follows that x∗∈H if the multiplicity of all eigenvalues of L is 1, where x∗ is the final value of the system. Therefore, the decay rate of the component e-λ2(L)tx2(0) in x(t) is less than or equal to the components of λ3(L),…,λn(L). If there is a repeated eigenvalue of L, x∗ is a nonlinear generation of H. Assume that the nonlinear generation of λ2(L) in x∗ is α1eλ2(L)t+α2teλ2(L)t+⋯+αntn-1eλ2(L)t, αi∈Rn. When t→∞, the derivative of its nonlinearity is less than or equal to the nonlinear generation corresponding to λ3(L),…,λn(L). Thus, the rate that x converges to a steady final value x∗ is determined by λ2(L).The superposition system has the same node set with the original system, and its edges can be constructed arbitrarily. We aim to analyze the variations of convergence rate after joining different superposition systems. For a system with undirected graphs, the following theorem can be achieved after joining a superposition system.Theorem 3.
For an undirected connected graphG, if L~ is a positive semidefinite matrix, then(7)λ2L≤λ2L^.If L~ is negative semidefinite, then(8)λ2L≥λ2L^.Only for λ2(L) with multiplicity 1, the necessary and sufficient condition for equalities in (7) and (8) to be true is that there is a vector x such that Lx=λ2(L)x, L~x=0, L^x=λ2(L^)x.Proof.
Letx1,…,xn; y1,…,yn; z1,…,zn, be the eigenvectors of L, L~, and L^, respectively, with xi2=yi2=zi2=1, i∈{1,…,n}. Denote S1=span{xi-j+1,…,xn}, S2=span{yj,…,yn}, S3=span{z1,…,zi},i∈{1,…,n},j∈{1,…,n}. Then (9)dim⁡S1+dimS2+dimS3=2n+1,which guarantees that there is a unit vector x∈S1∩S2∩S3. So we obtain the following inequality:(10)λi-j+1L+λjL~≤xTLx+xTL~x≤λiL^,j=1,…,n.For i=2,j=1, let L~ be positive semidefinite; it follows that (11)λ2L≤λ2L^.Denote S1=spanx1,…,xi+j, S2=span{y1,…,yn-j}, S3=span{zi,…,zn}, i∈{1,…,n}, j∈{0,1,…,n-i}. Then (12)dimS1+dimS2+dimS3=2n+1,which guarantees that there is a unit vector x∈S1∩S2∩S3. Thus,(13)λiL^≤xTLx+xTL~x≤λi+jL+λn-jL~,j=0,1,…,n-iFor i=2,j=0, let L~ be negative semidefinite; one has (14)λ2L^≤λ2L.
Ifλ2(L) is not a repeated eigenvalue, then λ2(L)=λ2(L~) only if there is an eigenvector x associated with λ2(L) satisfying L~x=0. In case that there is no eigenvector x satisfying L~x=0, then λ2(L^) is larger than λ2(L). So there are no vectors x,y,z with x=y=z such that xTLx+yTL~y=λ2(L)+0=λ2(L^). Thus the necessary and sufficient condition for equalities in (7) and (8) to be true is that there is a vector x satisfying Lx=λi(L)x, L~x=0, and L^x=λ2(L^)x.
Assume thatλ2(L) is a repeated eigenvalue with multiplicity p. If λ2(L) or λ1+p(L) changes and the other eigenvalues remain unchanged, L^ and L share p-1 eigenvalues, while the corresponding eigenvectors of L^ are different from those of L. Since L has p-1 identical eigenvalues with L^, there is an eigenvector z which has components satisfying zi=zj, such that L~z=0, i≠j, i,j∈{1,…,n}. In this case, however, the components of the corresponding eigenvector of L are different from each other. That is, there are different vectors x,y,z such that xTLx+yTL~y=λ2(L)+λ2(L~)=λ2(L^)=zTL^z.Theorem3 shows that the convergence rate of a system can be increased or decreased by adding a superposition system. This is always true for the positive semidefinite matrix L~ or negative semidefinite matrix L~, no matter what is the sign of the weights of L~. It is based on the analysis whether the equalities in (7) and (8) hold, we can figure out the variations of the convergence rate. In what follows, more specific instructions will be given on how to affect the convergence rate with respect to the problems and situations encountered during the process.In (10), take j=1, we see that λ1(L~)=0. Then(15)λiL≤λiL^,i=1,…,n.If L~ is positive semidefinite, (15) holds. Take j=0 in (13). Then, based on (15), if L~ is negative semidefinite, we have(16)λiL^≤λiL,i=1,…,n.Proposition 4.
For an undirected connected graphG, let X represent the set of eigenvectors corresponding to λp+1(L) with multiplicity p, p∈{1,…,n-1}. If rank(L~)=1, and there exists a vector xp∈X satisfying L~xp≠0, then the multiplicity of λp+1(L) corresponding to L^ is p-1.Proof.
LetL~ be a positive semidefinite matrix. For j=1 in (13), and λn-1(L~)=0, we have(17)λiL^≤λi+1L,i=1,…,n-1.By (15) and (17),(18)λiL≤λiL^≤λi+1L,i=1,…,n-1.Assume that there are repeated eigenvalues of Laplacian L associated with graph G, which are λi+1(L)=λi+2(L)=⋯=λi+p(L), i=1,…,n-p, and there exists one vector xp∈X satisfying L~xp≠0. Note that not for every vector x∈X, xTLx+xTL~x=xTLx holds. So there is one of repeated eigenvalues, the value of which is improved; i.e., λi+1(L^)=λi+2(L^)=⋯=λi+p-1(L^)<λi+p(L^), i∈{1,…,n-p}.
In caseL~ is negative semidefinite, the same line of arguments yields that λi+1(L^)<λi+2(L^)=⋯=λi+p-1(L^)=λi+p(L^), i∈{1,…,n-p}.Proposition4 shows if the eigenvector x of one eigenvalue λ has two identical entries xi=xj, adding an edge eij does not affect the eigenvalue λ, which means the weight, and even the existence of eij does not affect λ. For an eigenvalue λ with multiplicity p, the corresponding eigenvector has p-1 eigenvectors with two identical entries at any positions, so that if rank(L)=1, no matter the position of the adding edge, there is only one λ change; that is, the multiplicity of λ of superposed system is p-1. It is easy to know that if the multiplicity of λ is p, there is at least one eigenvector of λ that has p-1 pairs of identical entries; that is, if rank(L~)<p, the superposed system has the eigenvalue λ.Example 5.
The graph of the original system is shown as Figure1(a). Introducing the superposition system only establishes a connection between nodes 1 and 2. Thus, rank(L~)=1. The graph of the superposed system is shown as Figure 1(b). Below are L and L^.(19)L=4-1-1-1-1-14-1-1-1-1-17-50-1-1-512-5-1-10-57,L^=9-6-1-1-1-69-1-1-1-1-17-50-1-1-512-5-1-10-57.
The nonzero eigenvalues of the original system areλ2(L)=5, λ3(L)=5, λ4(L)=7, and λ5(L)=17, and the nonzero eigenvalues of the superposed system are λ2(L^)=5, λ3(L^)=7, λ4(L^)=15, and λ5(L^)=17. The multiplicity of eigenvalue 5 is 2. Let us join the superposition system with only one connection; i.e., rank(L~)=1. Since the eigenvector xp of the repeated eigenvalue satisfies L~xp≠0, the multiplicity of λ2(L^) is 1.Figure 1
(a) Original system; (b) superposed system.
(a)
G (b)
G ^


### 3.2. Changes of Convergence Rate

Definition 6.
For an entryaij of the adjacency matrix A, i,j∈{1,…,n}, if the increase of its value does not affect the algebraic connectivity of the communication graph, we call these weighted entries invalid algebraic connectivity weights (IACW).For an invalid algebraic connectivity weightaij, if there is a perturbation on one of associated nodes vi and vj so that the value of aij decreases, the magnitude of each eigenvalue except 0 and λ2(L) decreases firstly, while the delay margin of the system increases. Thus, in this case, the stability and the convergence of the system can be protected to a certain extent.If there is an invalid algebraic connectivity weight in the system, thenL~x=0, where x is an eigenvector of λ2(L) satisfying xTLx+xTL~x=λ2(L^)=xTL^x. All the eigenvector x′s corresponding to the smallest nonzero eigenvalue must contain two components xi and xj with xi=xj, i≠j, i,j∈{1,…,n}. Below is a further explanation.Due to the existence of repeated eigenvalue, the convergence rate does not necessarily change when a superposition system is superposed to the original system.Theorem 7.
If a superposition system related undirected graphG~ is superposed to an undirected connected graph G, a composite connected graph G^ is generated for the corresponding superposed system. Then the convergence rate of the superposed system changes as follows.(i)
If there are invalid algebraic connectivity weights inG, the adjacency matrix A~ of the superposition system only consists of invalid algebraic connectivity weights, and L~ is positive semidefinite, then the superposed system converges at a rate equal to the original system; i.e., λ2(L^)=λ2(L).(ii)
Ifλ2(L)≠λ3(L) and L~x≠0, where L~ is positive semidefinite and x is the eigenvector of λ2(L), then the superposed system converges faster than the original system; i.e., λ2(L^)>λ2(L).(iii)
Ifλ2(L)≠λ3(L), L~x≠0 and D-D~≥0, where L~ is negative semidefinite and x is the eigenvector of λ2(L), then the superposed system converges slower than the original system; i.e., λ2(L^)<λ2(L).Proof.
(i)
If a system associated with the original graphG has an invalid algebraic connectivity weight, then all the eigenvectors corresponding to the smallest nonzero eigenvalue of L contain two components xi, xj with xi=xj, i≠j, i,j∈{1,…,n}. A~ only consists of invalid algebraic connectivity weights if the superposition system only establishes a connection between vi and vj, such that there is an eigenvector x corresponding to λ2(L) with L~x=0, xTLx+xTL~x=λ2(L)+0=λ2(L^)=xTL^x. Therefore, the convergence rate of the superposed system remains unchanged.(ii)
Ifλ2(L)≠λ3(L) and L~x≠0, where L~ is positive semidefinite, then λ2(L)≠λ2(L^), the multiplicity of λ2(L) in L^ is 0. By (7), λ2(L^)>λ2(L) holds.(iii)
Ifλ2(L)≠λ3(L) and L~x≠0, where L~ is negative semidefinite, then λ2(L)≠λ2(L^) and the multiplicity of λ2(L) in L^ is 0. By (8), λ2(L^)<λ2(L) and D-D~≥0, which yields that L^ is positive semidefinite.Example 8.
The graph associated with the original system is shown as Figure2(e). The superposition system G~1 only establishes connections among nodes 3, 4, and 5. Thus, rank(L~1)=3. The superposed system G^1 is shown as Figure 2(b). Superpose another superposition system G~2 to G^1, where G~2 is shown as Figure 2(c) and only establishes the connection between nodes 1 and 2, which means rank(L~2)=1. The superposed system G^2 is shown as Figure 2(d). L, L^1, and L^2 are given as follows. (20)L=4-1-1-1-1-14-1-1-1-1-17-50-1-1-512-5-1-10-57,L^1=9-1-6-1-1-14-1-1-1-6-117-5-5-1-1-517-10-1-1-5-1017,L^2=14-6-6-1-1-69-1-1-1-6-117-5-5-1-1-517-10-1-1-5-1017.
The nonzero eigenvalues of the original system areλ2(L)=5, λ3(L)=5, λ4(L)=7, and λ5(L)=17, and the nonzero eigenvalues of the superposed system are λ2(L^1)=5, λ3(L^1)=9.5969, λ4(L^1)=22.4031, and λ5(L^1)=27. The invalid algebraic connectivity weights are a34(a43), a35(a53), and a45(a54). The established connections among nodes 1, 3, 4, and 5 mean rank(L~)=3. By Theorem 7, the convergence rate of the system still remains unchanged.
The nonzero eigenvalues of the superposed systemG2 are λ2(L^2)=7.4767, λ3(L^2)=15.7583, λ4(L^2)=23.765, and λ5(L^2)=27. Let the superposition system only establish a connection between nodes 1 and 2; that is, rank(L~2)=1. Then, there is no eigenvector x associated with λ2(L) satisfying L~x=0. Therefore, the superposed system converges faster than the original one.Figure 2
(a) Superposition systemG~1; (b) superposed system G^1; (c) superposition system G~2; (d) superposed system G^2; (e) original system.
(a)
G ~ 1 (b)
G ^ 1 (c)
G ~ 2 (d)
G ^ 2 (e)
GCorollary 9.
For an undirected connected graphG with the multiplicity of λ2(L) being r2, let r^2 represent the multiplicity of λ2(L) of L^, where the Laplacian L~ of the superposition system G~ is positive semidefinite and rank(L~)=q, q∈{1,…,n-1}. Thus, if r2-q=r^2=0, then λ2(L)≠λ2(L^), and accordingly the convergence rate of G^ is larger than the original system.Proof.
SetL~=L~1+L~2+⋯+L~q, rank(L~)=rank(L~1)+rank(L~2)+⋯+rank(L~q), where L~j are different matrices, rank(L~j)=1, j={1,…,q}, q∈{1,…,n-1}. If a superposition system L~j is superposed to the original system, and there is an eigenvector xj of λ2(L^j) associated with L^j satisfying L~j+1xj=0, then r2-j<r^2. Let xj be an eigenvector corresponding to λ2(L^j), j=1,…,q-1. If L~j+1xj=0 does not hold for every xj, and there is no eigenvector x corresponding to λ2(L) satisfying L^jx=0, then r2-j=r^2. Thus, if r2-q=r^2=0, then λ2(L) is not an eigenvalue of L^ anymore. So λ2(L)≠λ2(L^), and accordingly the convergence rate of G^ is larger than that of G.Remark 10.
For anyL~, if there is an eigenvector x of L such that L~x=0, the multiplicity of eigenvalue λi(L) associated with L^ satisfies r^≥1. That is to say, if x2=1, then xTLx+xTL~x=xTL^x=λi(L), i∈{1,2,…,n}.Because the same elements may exist in the eigenvectorx of λ2(L), superposition systems do not always enhance the convergence rate. In case r2>1, the convergence rate changes only if the entries of x associated with the edges of supposition system are not all equal. For example, if only the entries x3,x4,x5 of x are equal and the others are different from each other, then the superposition system with the connections among nodes 2, 3, 4, and 5 can enhance the convergence rate, while the superposition system with only the connections among nodes 3, 4, and 5 will not have such effect.Algorithm1 gives a method of finding a superposition system to enhance the convergence rate. In Algorithm, i=i+1 changes the label of node i, which makes different nodes connect to node j or nodes j, j+1,…,j+m-1 until xi≠xj; or until xi,xj,xj+1,…,xj+m-1 are not all equal. If r2=1, there exists at least one pair of entries xi,xj with xi≠xj in the eigenvector x corresponding to λ2(L). If r2=m, there exists a set of elements xi,xj,xj+1,…,xj+m-1 in eigenvector x that are not all equal; otherwise, x is a zero vector. So there is a superposition system that can increase the rate of convergence.Algorithm 1:Finding a superposition system to enhance the convergence rate.
r 2≔ the multiplicity of λ2(L) L ~≔ the Laplacian of superposition system x i , x j , … , x j + m - 1≔ the entries of the eigenvector of λ2L if r 2 = 1 then Connecting nodei to j in the superposition system whilexi=xjdo Connecting nodei=i+1 to j in the superposition system end while end if if r 2 = m > 1 then Connecting nodei to j, j+1,…,j+m in the superposition system whilexi=xj=xj+1=⋯=xj+m-1do Connecting nodei=i+1 to j,j+1,…,j+m in the superposition system end while end ifProposition 11.
For an undirected connected graphG, if the smallest nonzero eigenvalue of L is repeated, the invalid algebraic connectivity weights can be constructed in any two nodes.Proof.
The invalid algebraic connectivity weights exist if and only if, for an eigenvectorx corresponding to the smallest nonzero eigenvalue of L, there are two components xi,xj of x satisfying xi=xj, i≠j,i,j∈{1,…,n}.
For the positive semidefinite matrixL~+ or negative semidefinite matrix L~-, let rank(L~+)=rank(L~-)=1. If λ2(L) is a repeated eigenvalue, only one of repeated eigenvalues of L^ will change. Then for the superposition system, the nonzero entries of A~+ or A~- are invalid algebraic connectivity weights. All the eigenvectors corresponding to λ2(L) of L^ contain components xi,xj with xi=xj, where (i,j) represents the position of each nonzero weights associated with A~+ and A~-.


### 3.3. Optimization of Convergence Rate

In a stable system, it is always expected that there is a larger convergence rate to take less time to get the stable state. In case all the weights of a communication graph are increased, the values of nonzero eigenvalues will be improved as a whole, and accordingly the stability can be achieved with a larger rate. From a practical point of view, however, this will increase the cost of realization. Even so, we still hope to achieve the rapidity of convergence under fixed cost. Below, lettr(L) denote the cost for achieving consensus. With tr(L) being fixed, we hope to find the most optimal topology to achieve the largest convergence rate.Theorem 12.
For a system with fixed cost∑i=1nlii=c>0, c∈R, if L(t) is time-varying and λ2(L)=∑i=1nlii/(n-1), then the system achieves the largest convergence rate.Proof.
Assumeλ2(L)=∑i=1nlii/(n-1) and the system does not achieve the largest convergence rate. If λ2(L)>∑i=1nlii/(n-1), then minλ2(L)+λ3(L)+⋯+λn(L)>∑i=1nlii, which is in contradiction with the known condition. If λ2(L)<∑i=1nlii/(n-1), it can be seen that the system does not achieve the largest convergence rate. The above arguments mean that the system achieves the largest convergence rate if λ2(L)=λ3(L)=⋯=λn(L)=∑i=1nlii/(n-1).For the communication delayτij between nodes vi and vj, we consider the case τij=τ. Then system (2) along with protocol (1) can be written as(21)x˙i=-∑j∈Niaijxit-τ-xjt-τ(22)x˙=-Lxt-τ.Lemma 13 (see [2]).
Consider a network of integrator agents with identical communication time delayτ in all links. Assume that the network topology is fixed, undirected, and connected. Then, protocol (22) with τij=τ globally asymptotically solves the average consensus problem if and only if either of the following equivalent conditions is satisfied.(i)
τ∈(0,τ∗) with τ∗=π/2λn.(ii)
The Nyquist plot ofΓ(s)=e-τs/s has a zero encirclement around -1/λk,∀k>1.By Theorem12, λ2(L) is determined as long as the system achieves the largest convergence rate under fixed cost. Since the value of λ2(L) is determined, it is expected to construct topologies to achieve the largest convergence rate, i.e., seeking Lopt, where Lopt is the Laplacian having an eigenvalue maxL⁡λ2(L). If the graph of a multiagent system is a complete graph and all of its weights are identical, then the system achieves the largest convergence rate under fixed cost ∑i=1nlii=c>0, λ2(L)=∑i=1nlii/(n-1). In this case, λ2(L) achieves the biggest magnitude and λn(L) achieves the smallest magnitude. By Lemma 13, the delay margin τ∗ is decided only by λn(L). If there is a communication delay in the system and the λn(L) achieves the smallest magnitude, then the delay margin achieves the biggest magnitude.The Laplacian transformation of (22) is(23)Xs=x0sI+e-τsLLet G(s)=sI+e-τsL. Then det(G(s))=det(sI+e-τsL)=s∏i=2n(s+λi(L)e-τs). In case s+λi(L)e-τs=0, we have seτs=-λi(L). Let F(s)=seτs. The partial derivation of F(s) is ∂F(s)/∂Re(s)=(1+τs)eτs. If F(s) is monotone for Re(s) in R, the root of det(G(s)) can only be one side of -1/τ. As a consequence, the rightmost root of a system with time delays is related to λ2(L) or λn(L).Corollary 14.
Iftr(L)=c>0, c∈R, and the communication topology is a complete graph with all weights being identical, then the delay margin τ∗ achieves the biggest magnitude, and the topology is unique. And the system achieves largest convergence rate, if F(s) is monotone for Re(s).Proof.
If the communication graph associated with the system is a complete graph, each node of the graph is connected with the others, and all the weights are identical. Hence,λi(L)=λj(L)=c/(n-1)=lii-lij, i,j∈{2,…,n}. Then λ2(L) achieves the biggest magnitude. Thus, λn(L) achieves the smallest magnitude; that is, τ∗=π/2λn(L) achieves the biggest magnitude.
IfF(s) is monotone increasing for Re(s), then ∂F(s)/∂Re(s)>0. Thus, the convergence rate is determined by the upper bound -λi(L); that is, -λ2(L), i={2,…,n}. min{|Re(s)∥Re(s)≠0} increases with λ2(L) increasing. If F(s) is monotone reducing for Re(s), then ∂F(s)/∂Re(s)<0. The convergence rate is determined by the lower bound -λi(L); that is, -λn(L), i={2,…,n}. min{|Re(s)∥Re(s)≠0} increases with λn(L) reducing. If λ2(L) achieves the biggest magnitude, λn(L) achieves the smallest magnitude, and F(s) is monotone for Re(s); then the system achieves the largest convergence rate.Remark 15.
If a nodevi is connected with all the other nodes, and the weights between vi and the others are identical, then λ=lii-lij is an eigenvalue of L.For a system with time delaysτ, the convergence rate is also affected by time delays τ.Corollary 16.
For a fixed topology, if the time delayτ increases and τ<τ∗, the convergence rate of the system reduces.Proof.
The characteristic polynomial of the system isdet(G(s))=det(sI+e-τsL)=s∏i=2n(s+λi(L)e-τs), i={2,…,n}. Let Re(s)=c, Im(s)=d; then the root of characteristic polynomial of the system can be solved from c+jd+λi(L)e-τ(c+jd)=0. Thus, c+λiLe-cτcos⁡dτ=0, b-λiLe-cτsin⁡dτ=0, λi(L)=-cecτ/cos⁡dτ=decτ/sin⁡dτ, such that c=-d/tan⁡dτ. ∂c/∂τ=d2/(tan2⁡dτ·cos2dτ)≥0, and then c increases with τ increasing; that is, convergence rate reduces with τ increasing for τ<τ∗.Example 17.
The original system is shown as Figure3(a), and the system with the largest convergence rate under the same cost is shown as Figure 3(b). The corresponding Laplacian matrices are (24)L=200-1-102-10-10-14-1-2-10-15-3-1-1-2-37,Lopt=4-1-1-1-1-14-1-1-1-1-14-1-1-1-1-14-1-1-1-1-14.For the eigenvalues of original system, λ2(L)=1.7273, λ5(L)=9.438, and the delay margin is τ∗=0.1661s. All the nonzero eigenvalues of the system with the largest convergence rate are 5, and the delay margin of this system is τ∗=0.3141s.Figure 3
(a) Original systemG; (b) the largest convergence rate system Gopt.
(a)
G (b)
G o p t


## 3.1. Convergence Rate of Undirected Graphs

For a systemx˙=-Lx which can achieve consensus, its eigenvalues satisfy λi(L)≥0 and are arranged in an increasing order, i=1,…,n. The solution of the system is x(t)=exp⁡(-Lt)x(0), where x(0) is the initial state of agents. Let -L=PJP-1, where J is the Jordan standard norm of -L, and the diagonal entries of J are the eigenvalues of -L. Then xt=exp⁡-Ltx0=Pexp⁡(Jt)P-1x(0). Let H=span{e-λ1(L)t,e-λ2(L)t,…,e-λn(L)t}. It follows that x∗∈H if the multiplicity of all eigenvalues of L is 1, where x∗ is the final value of the system. Therefore, the decay rate of the component e-λ2(L)tx2(0) in x(t) is less than or equal to the components of λ3(L),…,λn(L). If there is a repeated eigenvalue of L, x∗ is a nonlinear generation of H. Assume that the nonlinear generation of λ2(L) in x∗ is α1eλ2(L)t+α2teλ2(L)t+⋯+αntn-1eλ2(L)t, αi∈Rn. When t→∞, the derivative of its nonlinearity is less than or equal to the nonlinear generation corresponding to λ3(L),…,λn(L). Thus, the rate that x converges to a steady final value x∗ is determined by λ2(L).The superposition system has the same node set with the original system, and its edges can be constructed arbitrarily. We aim to analyze the variations of convergence rate after joining different superposition systems. For a system with undirected graphs, the following theorem can be achieved after joining a superposition system.Theorem 3.
For an undirected connected graphG, if L~ is a positive semidefinite matrix, then(7)λ2L≤λ2L^.If L~ is negative semidefinite, then(8)λ2L≥λ2L^.Only for λ2(L) with multiplicity 1, the necessary and sufficient condition for equalities in (7) and (8) to be true is that there is a vector x such that Lx=λ2(L)x, L~x=0, L^x=λ2(L^)x.Proof.
Letx1,…,xn; y1,…,yn; z1,…,zn, be the eigenvectors of L, L~, and L^, respectively, with xi2=yi2=zi2=1, i∈{1,…,n}. Denote S1=span{xi-j+1,…,xn}, S2=span{yj,…,yn}, S3=span{z1,…,zi},i∈{1,…,n},j∈{1,…,n}. Then (9)dim⁡S1+dimS2+dimS3=2n+1,which guarantees that there is a unit vector x∈S1∩S2∩S3. So we obtain the following inequality:(10)λi-j+1L+λjL~≤xTLx+xTL~x≤λiL^,j=1,…,n.For i=2,j=1, let L~ be positive semidefinite; it follows that (11)λ2L≤λ2L^.Denote S1=spanx1,…,xi+j, S2=span{y1,…,yn-j}, S3=span{zi,…,zn}, i∈{1,…,n}, j∈{0,1,…,n-i}. Then (12)dimS1+dimS2+dimS3=2n+1,which guarantees that there is a unit vector x∈S1∩S2∩S3. Thus,(13)λiL^≤xTLx+xTL~x≤λi+jL+λn-jL~,j=0,1,…,n-iFor i=2,j=0, let L~ be negative semidefinite; one has (14)λ2L^≤λ2L.
Ifλ2(L) is not a repeated eigenvalue, then λ2(L)=λ2(L~) only if there is an eigenvector x associated with λ2(L) satisfying L~x=0. In case that there is no eigenvector x satisfying L~x=0, then λ2(L^) is larger than λ2(L). So there are no vectors x,y,z with x=y=z such that xTLx+yTL~y=λ2(L)+0=λ2(L^). Thus the necessary and sufficient condition for equalities in (7) and (8) to be true is that there is a vector x satisfying Lx=λi(L)x, L~x=0, and L^x=λ2(L^)x.
Assume thatλ2(L) is a repeated eigenvalue with multiplicity p. If λ2(L) or λ1+p(L) changes and the other eigenvalues remain unchanged, L^ and L share p-1 eigenvalues, while the corresponding eigenvectors of L^ are different from those of L. Since L has p-1 identical eigenvalues with L^, there is an eigenvector z which has components satisfying zi=zj, such that L~z=0, i≠j, i,j∈{1,…,n}. In this case, however, the components of the corresponding eigenvector of L are different from each other. That is, there are different vectors x,y,z such that xTLx+yTL~y=λ2(L)+λ2(L~)=λ2(L^)=zTL^z.Theorem3 shows that the convergence rate of a system can be increased or decreased by adding a superposition system. This is always true for the positive semidefinite matrix L~ or negative semidefinite matrix L~, no matter what is the sign of the weights of L~. It is based on the analysis whether the equalities in (7) and (8) hold, we can figure out the variations of the convergence rate. In what follows, more specific instructions will be given on how to affect the convergence rate with respect to the problems and situations encountered during the process.In (10), take j=1, we see that λ1(L~)=0. Then(15)λiL≤λiL^,i=1,…,n.If L~ is positive semidefinite, (15) holds. Take j=0 in (13). Then, based on (15), if L~ is negative semidefinite, we have(16)λiL^≤λiL,i=1,…,n.Proposition 4.
For an undirected connected graphG, let X represent the set of eigenvectors corresponding to λp+1(L) with multiplicity p, p∈{1,…,n-1}. If rank(L~)=1, and there exists a vector xp∈X satisfying L~xp≠0, then the multiplicity of λp+1(L) corresponding to L^ is p-1.Proof.
LetL~ be a positive semidefinite matrix. For j=1 in (13), and λn-1(L~)=0, we have(17)λiL^≤λi+1L,i=1,…,n-1.By (15) and (17),(18)λiL≤λiL^≤λi+1L,i=1,…,n-1.Assume that there are repeated eigenvalues of Laplacian L associated with graph G, which are λi+1(L)=λi+2(L)=⋯=λi+p(L), i=1,…,n-p, and there exists one vector xp∈X satisfying L~xp≠0. Note that not for every vector x∈X, xTLx+xTL~x=xTLx holds. So there is one of repeated eigenvalues, the value of which is improved; i.e., λi+1(L^)=λi+2(L^)=⋯=λi+p-1(L^)<λi+p(L^), i∈{1,…,n-p}.
In caseL~ is negative semidefinite, the same line of arguments yields that λi+1(L^)<λi+2(L^)=⋯=λi+p-1(L^)=λi+p(L^), i∈{1,…,n-p}.Proposition4 shows if the eigenvector x of one eigenvalue λ has two identical entries xi=xj, adding an edge eij does not affect the eigenvalue λ, which means the weight, and even the existence of eij does not affect λ. For an eigenvalue λ with multiplicity p, the corresponding eigenvector has p-1 eigenvectors with two identical entries at any positions, so that if rank(L)=1, no matter the position of the adding edge, there is only one λ change; that is, the multiplicity of λ of superposed system is p-1. It is easy to know that if the multiplicity of λ is p, there is at least one eigenvector of λ that has p-1 pairs of identical entries; that is, if rank(L~)<p, the superposed system has the eigenvalue λ.Example 5.
The graph of the original system is shown as Figure1(a). Introducing the superposition system only establishes a connection between nodes 1 and 2. Thus, rank(L~)=1. The graph of the superposed system is shown as Figure 1(b). Below are L and L^.(19)L=4-1-1-1-1-14-1-1-1-1-17-50-1-1-512-5-1-10-57,L^=9-6-1-1-1-69-1-1-1-1-17-50-1-1-512-5-1-10-57.
The nonzero eigenvalues of the original system areλ2(L)=5, λ3(L)=5, λ4(L)=7, and λ5(L)=17, and the nonzero eigenvalues of the superposed system are λ2(L^)=5, λ3(L^)=7, λ4(L^)=15, and λ5(L^)=17. The multiplicity of eigenvalue 5 is 2. Let us join the superposition system with only one connection; i.e., rank(L~)=1. Since the eigenvector xp of the repeated eigenvalue satisfies L~xp≠0, the multiplicity of λ2(L^) is 1.Figure 1
(a) Original system; (b) superposed system.
(a)
G (b)
G ^


## 3.2. Changes of Convergence Rate

Definition 6.
For an entryaij of the adjacency matrix A, i,j∈{1,…,n}, if the increase of its value does not affect the algebraic connectivity of the communication graph, we call these weighted entries invalid algebraic connectivity weights (IACW).For an invalid algebraic connectivity weightaij, if there is a perturbation on one of associated nodes vi and vj so that the value of aij decreases, the magnitude of each eigenvalue except 0 and λ2(L) decreases firstly, while the delay margin of the system increases. Thus, in this case, the stability and the convergence of the system can be protected to a certain extent.If there is an invalid algebraic connectivity weight in the system, thenL~x=0, where x is an eigenvector of λ2(L) satisfying xTLx+xTL~x=λ2(L^)=xTL^x. All the eigenvector x′s corresponding to the smallest nonzero eigenvalue must contain two components xi and xj with xi=xj, i≠j, i,j∈{1,…,n}. Below is a further explanation.Due to the existence of repeated eigenvalue, the convergence rate does not necessarily change when a superposition system is superposed to the original system.Theorem 7.
If a superposition system related undirected graphG~ is superposed to an undirected connected graph G, a composite connected graph G^ is generated for the corresponding superposed system. Then the convergence rate of the superposed system changes as follows.(i)
If there are invalid algebraic connectivity weights inG, the adjacency matrix A~ of the superposition system only consists of invalid algebraic connectivity weights, and L~ is positive semidefinite, then the superposed system converges at a rate equal to the original system; i.e., λ2(L^)=λ2(L).(ii)
Ifλ2(L)≠λ3(L) and L~x≠0, where L~ is positive semidefinite and x is the eigenvector of λ2(L), then the superposed system converges faster than the original system; i.e., λ2(L^)>λ2(L).(iii)
Ifλ2(L)≠λ3(L), L~x≠0 and D-D~≥0, where L~ is negative semidefinite and x is the eigenvector of λ2(L), then the superposed system converges slower than the original system; i.e., λ2(L^)<λ2(L).Proof.
(i)
If a system associated with the original graphG has an invalid algebraic connectivity weight, then all the eigenvectors corresponding to the smallest nonzero eigenvalue of L contain two components xi, xj with xi=xj, i≠j, i,j∈{1,…,n}. A~ only consists of invalid algebraic connectivity weights if the superposition system only establishes a connection between vi and vj, such that there is an eigenvector x corresponding to λ2(L) with L~x=0, xTLx+xTL~x=λ2(L)+0=λ2(L^)=xTL^x. Therefore, the convergence rate of the superposed system remains unchanged.(ii)
Ifλ2(L)≠λ3(L) and L~x≠0, where L~ is positive semidefinite, then λ2(L)≠λ2(L^), the multiplicity of λ2(L) in L^ is 0. By (7), λ2(L^)>λ2(L) holds.(iii)
Ifλ2(L)≠λ3(L) and L~x≠0, where L~ is negative semidefinite, then λ2(L)≠λ2(L^) and the multiplicity of λ2(L) in L^ is 0. By (8), λ2(L^)<λ2(L) and D-D~≥0, which yields that L^ is positive semidefinite.Example 8.
The graph associated with the original system is shown as Figure2(e). The superposition system G~1 only establishes connections among nodes 3, 4, and 5. Thus, rank(L~1)=3. The superposed system G^1 is shown as Figure 2(b). Superpose another superposition system G~2 to G^1, where G~2 is shown as Figure 2(c) and only establishes the connection between nodes 1 and 2, which means rank(L~2)=1. The superposed system G^2 is shown as Figure 2(d). L, L^1, and L^2 are given as follows. (20)L=4-1-1-1-1-14-1-1-1-1-17-50-1-1-512-5-1-10-57,L^1=9-1-6-1-1-14-1-1-1-6-117-5-5-1-1-517-10-1-1-5-1017,L^2=14-6-6-1-1-69-1-1-1-6-117-5-5-1-1-517-10-1-1-5-1017.
The nonzero eigenvalues of the original system areλ2(L)=5, λ3(L)=5, λ4(L)=7, and λ5(L)=17, and the nonzero eigenvalues of the superposed system are λ2(L^1)=5, λ3(L^1)=9.5969, λ4(L^1)=22.4031, and λ5(L^1)=27. The invalid algebraic connectivity weights are a34(a43), a35(a53), and a45(a54). The established connections among nodes 1, 3, 4, and 5 mean rank(L~)=3. By Theorem 7, the convergence rate of the system still remains unchanged.
The nonzero eigenvalues of the superposed systemG2 are λ2(L^2)=7.4767, λ3(L^2)=15.7583, λ4(L^2)=23.765, and λ5(L^2)=27. Let the superposition system only establish a connection between nodes 1 and 2; that is, rank(L~2)=1. Then, there is no eigenvector x associated with λ2(L) satisfying L~x=0. Therefore, the superposed system converges faster than the original one.Figure 2
(a) Superposition systemG~1; (b) superposed system G^1; (c) superposition system G~2; (d) superposed system G^2; (e) original system.
(a)
G ~ 1 (b)
G ^ 1 (c)
G ~ 2 (d)
G ^ 2 (e)
GCorollary 9.
For an undirected connected graphG with the multiplicity of λ2(L) being r2, let r^2 represent the multiplicity of λ2(L) of L^, where the Laplacian L~ of the superposition system G~ is positive semidefinite and rank(L~)=q, q∈{1,…,n-1}. Thus, if r2-q=r^2=0, then λ2(L)≠λ2(L^), and accordingly the convergence rate of G^ is larger than the original system.Proof.
SetL~=L~1+L~2+⋯+L~q, rank(L~)=rank(L~1)+rank(L~2)+⋯+rank(L~q), where L~j are different matrices, rank(L~j)=1, j={1,…,q}, q∈{1,…,n-1}. If a superposition system L~j is superposed to the original system, and there is an eigenvector xj of λ2(L^j) associated with L^j satisfying L~j+1xj=0, then r2-j<r^2. Let xj be an eigenvector corresponding to λ2(L^j), j=1,…,q-1. If L~j+1xj=0 does not hold for every xj, and there is no eigenvector x corresponding to λ2(L) satisfying L^jx=0, then r2-j=r^2. Thus, if r2-q=r^2=0, then λ2(L) is not an eigenvalue of L^ anymore. So λ2(L)≠λ2(L^), and accordingly the convergence rate of G^ is larger than that of G.Remark 10.
For anyL~, if there is an eigenvector x of L such that L~x=0, the multiplicity of eigenvalue λi(L) associated with L^ satisfies r^≥1. That is to say, if x2=1, then xTLx+xTL~x=xTL^x=λi(L), i∈{1,2,…,n}.Because the same elements may exist in the eigenvectorx of λ2(L), superposition systems do not always enhance the convergence rate. In case r2>1, the convergence rate changes only if the entries of x associated with the edges of supposition system are not all equal. For example, if only the entries x3,x4,x5 of x are equal and the others are different from each other, then the superposition system with the connections among nodes 2, 3, 4, and 5 can enhance the convergence rate, while the superposition system with only the connections among nodes 3, 4, and 5 will not have such effect.Algorithm1 gives a method of finding a superposition system to enhance the convergence rate. In Algorithm, i=i+1 changes the label of node i, which makes different nodes connect to node j or nodes j, j+1,…,j+m-1 until xi≠xj; or until xi,xj,xj+1,…,xj+m-1 are not all equal. If r2=1, there exists at least one pair of entries xi,xj with xi≠xj in the eigenvector x corresponding to λ2(L). If r2=m, there exists a set of elements xi,xj,xj+1,…,xj+m-1 in eigenvector x that are not all equal; otherwise, x is a zero vector. So there is a superposition system that can increase the rate of convergence.Algorithm 1:Finding a superposition system to enhance the convergence rate.
r 2≔ the multiplicity of λ2(L) L ~≔ the Laplacian of superposition system x i , x j , … , x j + m - 1≔ the entries of the eigenvector of λ2L if r 2 = 1 then Connecting nodei to j in the superposition system whilexi=xjdo Connecting nodei=i+1 to j in the superposition system end while end if if r 2 = m > 1 then Connecting nodei to j, j+1,…,j+m in the superposition system whilexi=xj=xj+1=⋯=xj+m-1do Connecting nodei=i+1 to j,j+1,…,j+m in the superposition system end while end ifProposition 11.
For an undirected connected graphG, if the smallest nonzero eigenvalue of L is repeated, the invalid algebraic connectivity weights can be constructed in any two nodes.Proof.
The invalid algebraic connectivity weights exist if and only if, for an eigenvectorx corresponding to the smallest nonzero eigenvalue of L, there are two components xi,xj of x satisfying xi=xj, i≠j,i,j∈{1,…,n}.
For the positive semidefinite matrixL~+ or negative semidefinite matrix L~-, let rank(L~+)=rank(L~-)=1. If λ2(L) is a repeated eigenvalue, only one of repeated eigenvalues of L^ will change. Then for the superposition system, the nonzero entries of A~+ or A~- are invalid algebraic connectivity weights. All the eigenvectors corresponding to λ2(L) of L^ contain components xi,xj with xi=xj, where (i,j) represents the position of each nonzero weights associated with A~+ and A~-.


## 3.3. Optimization of Convergence Rate

In a stable system, it is always expected that there is a larger convergence rate to take less time to get the stable state. In case all the weights of a communication graph are increased, the values of nonzero eigenvalues will be improved as a whole, and accordingly the stability can be achieved with a larger rate. From a practical point of view, however, this will increase the cost of realization. Even so, we still hope to achieve the rapidity of convergence under fixed cost. Below, lettr(L) denote the cost for achieving consensus. With tr(L) being fixed, we hope to find the most optimal topology to achieve the largest convergence rate.Theorem 12.
For a system with fixed cost∑i=1nlii=c>0, c∈R, if L(t) is time-varying and λ2(L)=∑i=1nlii/(n-1), then the system achieves the largest convergence rate.Proof.
Assumeλ2(L)=∑i=1nlii/(n-1) and the system does not achieve the largest convergence rate. If λ2(L)>∑i=1nlii/(n-1), then minλ2(L)+λ3(L)+⋯+λn(L)>∑i=1nlii, which is in contradiction with the known condition. If λ2(L)<∑i=1nlii/(n-1), it can be seen that the system does not achieve the largest convergence rate. The above arguments mean that the system achieves the largest convergence rate if λ2(L)=λ3(L)=⋯=λn(L)=∑i=1nlii/(n-1).For the communication delayτij between nodes vi and vj, we consider the case τij=τ. Then system (2) along with protocol (1) can be written as(21)x˙i=-∑j∈Niaijxit-τ-xjt-τ(22)x˙=-Lxt-τ.Lemma 13 (see [2]).
Consider a network of integrator agents with identical communication time delayτ in all links. Assume that the network topology is fixed, undirected, and connected. Then, protocol (22) with τij=τ globally asymptotically solves the average consensus problem if and only if either of the following equivalent conditions is satisfied.(i)
τ∈(0,τ∗) with τ∗=π/2λn.(ii)
The Nyquist plot ofΓ(s)=e-τs/s has a zero encirclement around -1/λk,∀k>1.By Theorem12, λ2(L) is determined as long as the system achieves the largest convergence rate under fixed cost. Since the value of λ2(L) is determined, it is expected to construct topologies to achieve the largest convergence rate, i.e., seeking Lopt, where Lopt is the Laplacian having an eigenvalue maxL⁡λ2(L). If the graph of a multiagent system is a complete graph and all of its weights are identical, then the system achieves the largest convergence rate under fixed cost ∑i=1nlii=c>0, λ2(L)=∑i=1nlii/(n-1). In this case, λ2(L) achieves the biggest magnitude and λn(L) achieves the smallest magnitude. By Lemma 13, the delay margin τ∗ is decided only by λn(L). If there is a communication delay in the system and the λn(L) achieves the smallest magnitude, then the delay margin achieves the biggest magnitude.The Laplacian transformation of (22) is(23)Xs=x0sI+e-τsLLet G(s)=sI+e-τsL. Then det(G(s))=det(sI+e-τsL)=s∏i=2n(s+λi(L)e-τs). In case s+λi(L)e-τs=0, we have seτs=-λi(L). Let F(s)=seτs. The partial derivation of F(s) is ∂F(s)/∂Re(s)=(1+τs)eτs. If F(s) is monotone for Re(s) in R, the root of det(G(s)) can only be one side of -1/τ. As a consequence, the rightmost root of a system with time delays is related to λ2(L) or λn(L).Corollary 14.
Iftr(L)=c>0, c∈R, and the communication topology is a complete graph with all weights being identical, then the delay margin τ∗ achieves the biggest magnitude, and the topology is unique. And the system achieves largest convergence rate, if F(s) is monotone for Re(s).Proof.
If the communication graph associated with the system is a complete graph, each node of the graph is connected with the others, and all the weights are identical. Hence,λi(L)=λj(L)=c/(n-1)=lii-lij, i,j∈{2,…,n}. Then λ2(L) achieves the biggest magnitude. Thus, λn(L) achieves the smallest magnitude; that is, τ∗=π/2λn(L) achieves the biggest magnitude.
IfF(s) is monotone increasing for Re(s), then ∂F(s)/∂Re(s)>0. Thus, the convergence rate is determined by the upper bound -λi(L); that is, -λ2(L), i={2,…,n}. min{|Re(s)∥Re(s)≠0} increases with λ2(L) increasing. If F(s) is monotone reducing for Re(s), then ∂F(s)/∂Re(s)<0. The convergence rate is determined by the lower bound -λi(L); that is, -λn(L), i={2,…,n}. min{|Re(s)∥Re(s)≠0} increases with λn(L) reducing. If λ2(L) achieves the biggest magnitude, λn(L) achieves the smallest magnitude, and F(s) is monotone for Re(s); then the system achieves the largest convergence rate.Remark 15.
If a nodevi is connected with all the other nodes, and the weights between vi and the others are identical, then λ=lii-lij is an eigenvalue of L.For a system with time delaysτ, the convergence rate is also affected by time delays τ.Corollary 16.
For a fixed topology, if the time delayτ increases and τ<τ∗, the convergence rate of the system reduces.Proof.
The characteristic polynomial of the system isdet(G(s))=det(sI+e-τsL)=s∏i=2n(s+λi(L)e-τs), i={2,…,n}. Let Re(s)=c, Im(s)=d; then the root of characteristic polynomial of the system can be solved from c+jd+λi(L)e-τ(c+jd)=0. Thus, c+λiLe-cτcos⁡dτ=0, b-λiLe-cτsin⁡dτ=0, λi(L)=-cecτ/cos⁡dτ=decτ/sin⁡dτ, such that c=-d/tan⁡dτ. ∂c/∂τ=d2/(tan2⁡dτ·cos2dτ)≥0, and then c increases with τ increasing; that is, convergence rate reduces with τ increasing for τ<τ∗.Example 17.
The original system is shown as Figure3(a), and the system with the largest convergence rate under the same cost is shown as Figure 3(b). The corresponding Laplacian matrices are (24)L=200-1-102-10-10-14-1-2-10-15-3-1-1-2-37,Lopt=4-1-1-1-1-14-1-1-1-1-14-1-1-1-1-14-1-1-1-1-14.For the eigenvalues of original system, λ2(L)=1.7273, λ5(L)=9.438, and the delay margin is τ∗=0.1661s. All the nonzero eigenvalues of the system with the largest convergence rate are 5, and the delay margin of this system is τ∗=0.3141s.Figure 3
(a) Original systemG; (b) the largest convergence rate system Gopt.
(a)
G (b)
G o p t


## 4. Construction of Invalid Algebraic Connectivity Weights

Definition 18.
π = { C 1 , … , C r } is called an equitable weights partition if each node in cell Ci has the same weight with the nodes in Cj, ∀i,j∈{1,…,r}. If each node in Ci has the same weight with the nodes in Cj the partition π is called an almost equitable weights partition, where ∀i≠j,i,j∈{1,…,r}. We denote the cardinality of cell Cr with |Cr|.A cellCr is nontrivial if it contains more than one node; otherwise it is trivial. Equitable weights partition can be used in what follows to analyze the convergence rate of consensus, and we can construct the nontrivial cells to get the IACWs.


### 4.1. Convergence Rate under Equitable Weights Partition

For a nontrivial cellCr in an equitable weights partition, suppose that the number of nodes in Cr is |Cr|=m. We have the following lemma.Lemma 19.
IfL~ij,L~kj are superposition systems only constructed, respectively, by vi and vj and vk and vj; then λ2(L^ij)=λ2(L^kj), where vi,vk∈Cr, and vj∈V is a node given in advance, i≠k,j≠i,j≠k.Proof.
Since there is a nontrivial cell withm nodes and vj∈V is fixed, we construct the superposition system by selecting any node vi in the nontrivial cell to establish one communication link with the given vj. The dynamic equations of the nodes in the nontrivial cell are(25)x˙l+1x˙l+2⋮x˙l+m=lr1Lrlr2x,where the entries of the columns in lr1∈Rm×l and lr2∈Rm×(n-m-l) are all equal. In the superposition system, an arbitrary node vi∈Cr is selected to establish one communication link with the fixed vj. Then the dynamic equations remain unchanged when the positions of xl+1,…,xl+m are exchanged, and the positions of x˙l+1,…,x˙l+m remain unchanged. In this situation, the topology of the system remains unchanged. The discussion above means that the variations of eigenvalues associated with L are equal since there is only one link between vj and any node of Cr in the superposition system. Note that the variation of algebraic connectivity is also identical. Then, if vi∈Cr, the variation of the algebraic connectivity is unrelated to the choosing of vi. Thus, if vk∈Cr is selected to construct a superposition system, its convergence rate is identical with L~ij, and accordingly λ2(L^ij)=λ2(L^kj), where i≠k,j≠i,j≠k.Example 20.
A graph with two nontrivial cells is shown as Figure4. The corresponding Laplacian L is(26)L=6-2-2-1-1-25-1-1-1-2-15-1-1-1-1-15-2-1-1-1-25.
The expression of LaplacianL implies that there is a partition C1={1}, C2={2,3}, C3={4,5}. Consider the case that rank(L~)=1, which means that there is an edge with weight 1 in the graph associated with the superposition system. Let us establish the connection between any two nodes, and let L~ij denote the corresponding matrix which has only one link between nodes vi and vj. L^ij denotes the Laplacian matrix of the superposed system corresponding to L~ij. Then, λ2(L^12)=λ2(L^13)=5, λ2(L^14)=λ2(L^15)=5.5188, λ2(L^24)=λ2(L^25)=λ2(L^34)=λ2(L^35)=5.382. The variations of the other eigenvalues of L^ij are the same.Figure 4
A graph with nontrivial cells.Letλij denote an eigenvalue of a submatrix which is generated by selecting the rows and columns corresponding to the nodes of the nontrivial cell Cr. λij=lii-lij=ljj-lji, with i,j indicating that λij only relies on Cr,i,j∈Cr. The Fariavector denotes the vector which only contains two nonzero entries, and the two entries are opposite from each other.Corollary 21.
For an equitable weights partitionπ with a nontrivial cell Cr, the multiplicity of λij satisfies r(λij)=n-rank(λijI-L), m-1≤r(λij), |Cr|=m.Proof.
Since LaplacianL is symmetric, the geometrical and algebraic multiplicity of each eigenvalue of L is equal to each other. Hence, the number of linearly independent eigenvectors x of λij is the multiplicity of λij. Note that n-rank(λijI-L) is equal to the number of linearly independent solutions of (λijI-L)x=0. It follows that n-rank(λijI-L) is equal to the number of linearly independent vectors x which satisfies Lx=λijx, r(λij)=n-rank(λijI-L). The structure form of λijI-L implies that the row entries of L corresponding to the nodes in Cr are equal. Therefore, m-1≤r(λij).Remark 22.
The number of eigenvaluesλij is no less than the number of the nontrivial cells Cr.It is worth mentioning that, for an equitable weights partition, the submatrix corresponding to a nontrivial cellCr consisting of m nodes only has the eigenvalue λij with its multiplicity satisfying r(λij)=m-1. There, however, will be such a situation r(λij)>m-1, which is the consequence of the nontrivial cell Cr working with the other cells.Proposition 23.
For an equitable weights partition, if there is a nontrivial cell withm nodes, the number of linearly independent Fariavectors in the eigenvectors corresponding to λij is m-1.Proof.
For a nontrivial cell withm nodes, the number of Fariavectors is Cm2. Let XCm2={x1,x2,…,xCm2}, where xi denotes a Fariavector, i∈{1,2,…,Cm2}, and the nonzero entries in xi is corresponding to the nodes in Cr. Since XCm2 consists of Cm2Fariavectors, then rank(XCm2)≤m. Let Xm-1={x1,x2,x3,…,xm-1}, where x1=e1-e2={1,-1,0,0,…,0}, x2=e1-e3={1,0,-1,0,…,0}, x3=e1-e4={1,0,0,-1,…,0}, ⋯, xm-1=e1-em={1,0,0,0,…,0,-1,0,…,0}, and ei∈Rn denotes a vector with the ith entry taking 1 and the others taking 0. XCm2∖Xm-1 can be represented as a linear combination of e1,e2,…,em-1, and the other Cm2-(m-1)Fariavectors all can be represented by vectors x1, x2, x3, ⋯, xm-1. Hence, the number of linearly independent Fariavectors in the eigenvectors set of λij is m-1.Example 24.
A graph with two nontrivial cells is shown in Figure5. The corresponding Laplacian L is (27)L=11-1-1-3-3-3-18-1-2-2-2-1-18-2-2-2-3-2-211-2-2-3-2-2-211-2-3-2-2-2-211,V=10300411-30011-1-300110111-2101-10-21010-1-2=v1,v2,v3,v4,v5,v6,Dλ=diag0,9,10,13,13,15.
The expression ofL implies that there is a partition π with C1={1}, C2={2,3}, C3={4,5,6}. The entries of diagonal matrix Dλ are the eigenvalues of L, and the columns of V are the eigenvectors corresponding to Dλ. Note that v4 and v5 are Fariavectors. It can be seen that 9 is an eigenvalue of the submatrix obtained by selecting the rows and columns corresponding to the nodes in C2, and its corresponding eigenvector is aFaria vector. The eigenvalue 10 is not associated with any submatrix corresponding to any cell. The second and third entry of the eigenvector corresponding to eigenvalue 10 are equal, and the same thing happens to the fourth, fifth, and sixth entry. It is the same situation to eigenvalue 15 with the second and third entry of its eigenvector being equal as well as the fourth, fifth, and sixth entry. The two eigenvectors of eigenvalue 13 are both Fariavectors.Figure 5
A graph with nontrivial cells.Lemma 25.
For a connected graphG, if there exists a nontrivial cell Cr with m nodes, then the following claims hold under equitable weights partition.(i)
Ifn-rank(λijI-L)=m-1, the eigenvectors of λij are all Fariavectors.(ii)
Ifn-rank(λijI-L)>m-1, the entries in the eigenvector x of λij corresponding to any other nontrivial cell Cr-1 are equal to each other as long as the eigenvector is not a Fariavetor.(iii)
Ifλ(L)≠λij, the entries in the eigenvectors of λ(L) corresponding to the nontrivial cell Cr are equal to each other.Proof.
(i)
If there is a nontrivial cellCr containing nodes vi and vj, let us set λij=lii-lij. Then rank(λijI-L)<n, that is, λijI-L=0, where λij is an eigenvalue of Laplacian L. In case x={0,…,0,dith,0…,0, -djth,0,…,0}T, Lx=λijx, where dith=djth, dith and djth are nonzero constants, which denote the ith and jth entries of vector x, respectively. If n-rank(λijI-L)=m-1, it follows from Lemma 19 that the position exchanging of nodes in the nontrivial cell does not affect the structure of L. As a consequence, the eigenvectors of λij are also unaffected. Thus, when dith exchanges its position with -djth, the original eigenvector x is replaced by -x, and the entries except the ith and jth entries in eigenvectors x are 0. That is, there are m-1 linearly independent eigenvectors of Fariavector corresponding to the m-1 eigenvalues λij.(ii)
Ifn-rank(λijI-L)≥m, and the entries in eigenvector x corresponding to Cr-1 are equal, then, there are more than m-1Fariavectors. Thus the entries of x’s of λij are equal.(iii)
Ifλ(L)≠lii-lij, let us consider the entries of x’s of λ(L), where these entries correspond to the nodes in Cr. Assume that these entries are not equal. Then vectors xe are still eigenvectors associated with λ(L) after the positions of these unequal entries are exchanged. Let xlc denote the linear combination of x and xe. The entries of xlc corresponding to the nodes in the nontrivial cell Cr are equal, and the others corresponding to the trivial cell C¬r are 0, which contradicts with the assumption. Therefore, the entries in the eigenvectors corresponding to λ(L)≠lii-lij are equal.The equitable weights partition leads to some special perspectives on the eigenvalues and eigenvectors of Laplacian matrix, which allows us to propose an explicit method for constructing IACW.Theorem 26.
For an equitable weights partition of graphG, suppose that there is a nontrivial cell Cr with m nodes. Then the following statements hold for IACW.(i)
Ifλ2(L)≠λij, the weights between the nodes in Cr are IACW.(ii)
Ifλ2(L)=λij, and n-rank(λijI-L)=m-1, the weights except those between the nodes in the nontrivial cell Cr are IACW.Proof.
By Lemma25, if λ2(L)≠λij, the entries in the eigenvector x of λ2(L) corresponding to the nodes in Cr are equal, and accordingly the weights between the nodes in Cr are IACW. If λ2(L)=λij, and n-rank(λijI-L)=m-1, then Lemma 25 means that the ith and the jth entry in the eigenvectors of λ2(L) are opposite, and the others are 0. Thus the weights except those in the nontrivial cell Cr are IACW.


### 4.2. Convergence Rate under Almost Equitable Weights Partition

Different from the equitable weights partition, the weights in the nontrivial cellCr are not equal if the almost equitable weights partition is taken into account. So the latter makes a part of properties lost compared to the equitable weights partition. Thus, this case is more complex. For the almost equitable weights partition, since the weights between the nodes in nontrivial cell Cr are different, λij=lii-lij is no longer true. As a consequence, λij cannot be characterized exactly.Lemma 27.
For an undirected graphG, there is an eigenvector x of a nonzero eigenvalue of L so that xT1n=0, where 1n∈Rn denotes the column vector with all entries taking 1.Proof.
For an undirected connected graph, 0 is a simple eigenvalue ofL, and L1n=0. Let x denote an eigenvector of a nonzero eigenvalue of L; i.e., Lx=λ(L)x. The Laplacian L is symmetric. It follows that xTL=λ(L)xT, xTL1n=λ(L)xT1n=0. Thus, xT1n=0.In case there is a partition with a nontrivial cellCr, L can be decomposed in accordance with the nontrivial cell,(28)L=LrlrlrTL¬r,where Lr corresponds to the nodes in the nontrivial cell, which indicates the weights between nodes in Cr and its degree. Each column of lr is equal to the other columns, which indicates the weights between nodes in Cr and nodes in other cells. L¬r corresponds to the trivial cells.Remark 28.
For an equitable weights partition,Lr has an eigenvalue λij=lii-lij with multiplicity m-1 if there is a nontrivial cell. For an almost equitable weights partition, Lr only has an eigenvalue with multiplicity 1 which can be characterized.L r = l r 1 T 1 r I r + L r r, where lr1 denotes the first column of lr, and 1r is the vector with proper dimension and all entries taking 1. Lrr is the Laplacian matrix of a system constructed by the nodes in the nontrivial cell Cr. For almost equitable weights partitions, Lrr is the general Laplacian matrix. So the nonzero eigenvalues cannot be characterized. Because of the existence of lr1T1rIr, there is an eigenvalue lr1T1r associated with Lr, and the entries in the eigenvector of lr1T1r are all equal.Lemma 29.
For a matrixLr∈Rm×m, suppose that there is only one nontrivial cell associated with Lr. Then the Laplacian matrices L and Lr share m-1 common eigenvalues λij. Moreover, for matrix L, its x’s associated with λij take xr as a subvector, where xr is the eigenvector of λij associated with Lr; that is, xT={xrT,0,…,0}.Proof.
Assume that the nontrivial cellCr contains m nodes, and Lr=lr1T1rIr+Lrr. Then Lrxr=lr1T1rxr+λrrxr=λijxr, where Lrrxr=λrrxr, λij=lr1T1r+λrr. Let xT={xrT,0,…,0}, with the positions of entries 0 corresponding to the nodes in C¬r. Since xT1n=0, it follows that [Lr,lr]x=λijxr, [lr,L¬r]x=0¬r, Lx=λijx. If λrr=lr1T1r, we see that xr is a vector with all of its entries taking 1. Thus xrT1r≠0; that is, lrTxr≠0, [lr,L¬r]x≠0¬r. Therefore, Lr does not share the eigenvalue lr1T1r with L. So L and Lr share m-1 common eigenvalues, and xT={xrT,0,…,0}.Lemma29 explains the affections caused by nontrivial cells under equitable weights and almost equitable weights partition. The existence of nontrivial cells in Lr makes that part of eigenvalues and eigenvectors of L rely on Lr.Theorem 30.
For an almost equitable weights partition of graphG, suppose that there is a nontrivial cell Cr. If λ2(L)=λij, the weights except those in Cr are all IACW. If λ2(L)≠λij, the weights in Cr are IACW.Proof.
For an almost equitable weights partition with a nontrivial cellCr, λij is an eigenvalue of submatrix obtained by selecting the rows and columns corresponding to the nodes in Cr. By Lemma 29, if λ2(L)=λij, the entries of vector x except those corresponding to the nodes in Cr are 0, where x is the eigenvector corresponding to λij. Therefore, the weights of C¬r are IACW. Let xT=[xr,x¬r]T, where xr is the eigenvector of Lr. The entries of every column in lr are equal to the others. Then lrx¬r=c1r, where c is a constant. If λ2(L)≠λij, and the entries of xr are different, then [Lr,lr]x=Lrxr+c1r=λxr, Lrxr=λxr-c1r. If the entries of xr are different, the entries of λxr-c1r are also different. Thus λ=λij and λ2(L)≠λij yield that the weights between the nodes in the nontrivial cell Cr are IACW.When the nontrivial cells existed, there are IACWs in a system. Thus, we can construct the nontrivial cell to get the IACWs. And it is easy to know that the IACWs are changed, when the caseλ2(L)=λij transforms into λ2(L)≠λij. The cases of the IACWs are identical for equitable weights partition and almost equitable weights partition.


## 4.1. Convergence Rate under Equitable Weights Partition

For a nontrivial cellCr in an equitable weights partition, suppose that the number of nodes in Cr is |Cr|=m. We have the following lemma.Lemma 19.
IfL~ij,L~kj are superposition systems only constructed, respectively, by vi and vj and vk and vj; then λ2(L^ij)=λ2(L^kj), where vi,vk∈Cr, and vj∈V is a node given in advance, i≠k,j≠i,j≠k.Proof.
Since there is a nontrivial cell withm nodes and vj∈V is fixed, we construct the superposition system by selecting any node vi in the nontrivial cell to establish one communication link with the given vj. The dynamic equations of the nodes in the nontrivial cell are(25)x˙l+1x˙l+2⋮x˙l+m=lr1Lrlr2x,where the entries of the columns in lr1∈Rm×l and lr2∈Rm×(n-m-l) are all equal. In the superposition system, an arbitrary node vi∈Cr is selected to establish one communication link with the fixed vj. Then the dynamic equations remain unchanged when the positions of xl+1,…,xl+m are exchanged, and the positions of x˙l+1,…,x˙l+m remain unchanged. In this situation, the topology of the system remains unchanged. The discussion above means that the variations of eigenvalues associated with L are equal since there is only one link between vj and any node of Cr in the superposition system. Note that the variation of algebraic connectivity is also identical. Then, if vi∈Cr, the variation of the algebraic connectivity is unrelated to the choosing of vi. Thus, if vk∈Cr is selected to construct a superposition system, its convergence rate is identical with L~ij, and accordingly λ2(L^ij)=λ2(L^kj), where i≠k,j≠i,j≠k.Example 20.
A graph with two nontrivial cells is shown as Figure4. The corresponding Laplacian L is(26)L=6-2-2-1-1-25-1-1-1-2-15-1-1-1-1-15-2-1-1-1-25.
The expression of LaplacianL implies that there is a partition C1={1}, C2={2,3}, C3={4,5}. Consider the case that rank(L~)=1, which means that there is an edge with weight 1 in the graph associated with the superposition system. Let us establish the connection between any two nodes, and let L~ij denote the corresponding matrix which has only one link between nodes vi and vj. L^ij denotes the Laplacian matrix of the superposed system corresponding to L~ij. Then, λ2(L^12)=λ2(L^13)=5, λ2(L^14)=λ2(L^15)=5.5188, λ2(L^24)=λ2(L^25)=λ2(L^34)=λ2(L^35)=5.382. The variations of the other eigenvalues of L^ij are the same.Figure 4
A graph with nontrivial cells.Letλij denote an eigenvalue of a submatrix which is generated by selecting the rows and columns corresponding to the nodes of the nontrivial cell Cr. λij=lii-lij=ljj-lji, with i,j indicating that λij only relies on Cr,i,j∈Cr. The Fariavector denotes the vector which only contains two nonzero entries, and the two entries are opposite from each other.Corollary 21.
For an equitable weights partitionπ with a nontrivial cell Cr, the multiplicity of λij satisfies r(λij)=n-rank(λijI-L), m-1≤r(λij), |Cr|=m.Proof.
Since LaplacianL is symmetric, the geometrical and algebraic multiplicity of each eigenvalue of L is equal to each other. Hence, the number of linearly independent eigenvectors x of λij is the multiplicity of λij. Note that n-rank(λijI-L) is equal to the number of linearly independent solutions of (λijI-L)x=0. It follows that n-rank(λijI-L) is equal to the number of linearly independent vectors x which satisfies Lx=λijx, r(λij)=n-rank(λijI-L). The structure form of λijI-L implies that the row entries of L corresponding to the nodes in Cr are equal. Therefore, m-1≤r(λij).Remark 22.
The number of eigenvaluesλij is no less than the number of the nontrivial cells Cr.It is worth mentioning that, for an equitable weights partition, the submatrix corresponding to a nontrivial cellCr consisting of m nodes only has the eigenvalue λij with its multiplicity satisfying r(λij)=m-1. There, however, will be such a situation r(λij)>m-1, which is the consequence of the nontrivial cell Cr working with the other cells.Proposition 23.
For an equitable weights partition, if there is a nontrivial cell withm nodes, the number of linearly independent Fariavectors in the eigenvectors corresponding to λij is m-1.Proof.
For a nontrivial cell withm nodes, the number of Fariavectors is Cm2. Let XCm2={x1,x2,…,xCm2}, where xi denotes a Fariavector, i∈{1,2,…,Cm2}, and the nonzero entries in xi is corresponding to the nodes in Cr. Since XCm2 consists of Cm2Fariavectors, then rank(XCm2)≤m. Let Xm-1={x1,x2,x3,…,xm-1}, where x1=e1-e2={1,-1,0,0,…,0}, x2=e1-e3={1,0,-1,0,…,0}, x3=e1-e4={1,0,0,-1,…,0}, ⋯, xm-1=e1-em={1,0,0,0,…,0,-1,0,…,0}, and ei∈Rn denotes a vector with the ith entry taking 1 and the others taking 0. XCm2∖Xm-1 can be represented as a linear combination of e1,e2,…,em-1, and the other Cm2-(m-1)Fariavectors all can be represented by vectors x1, x2, x3, ⋯, xm-1. Hence, the number of linearly independent Fariavectors in the eigenvectors set of λij is m-1.Example 24.
A graph with two nontrivial cells is shown in Figure5. The corresponding Laplacian L is (27)L=11-1-1-3-3-3-18-1-2-2-2-1-18-2-2-2-3-2-211-2-2-3-2-2-211-2-3-2-2-2-211,V=10300411-30011-1-300110111-2101-10-21010-1-2=v1,v2,v3,v4,v5,v6,Dλ=diag0,9,10,13,13,15.
The expression ofL implies that there is a partition π with C1={1}, C2={2,3}, C3={4,5,6}. The entries of diagonal matrix Dλ are the eigenvalues of L, and the columns of V are the eigenvectors corresponding to Dλ. Note that v4 and v5 are Fariavectors. It can be seen that 9 is an eigenvalue of the submatrix obtained by selecting the rows and columns corresponding to the nodes in C2, and its corresponding eigenvector is aFaria vector. The eigenvalue 10 is not associated with any submatrix corresponding to any cell. The second and third entry of the eigenvector corresponding to eigenvalue 10 are equal, and the same thing happens to the fourth, fifth, and sixth entry. It is the same situation to eigenvalue 15 with the second and third entry of its eigenvector being equal as well as the fourth, fifth, and sixth entry. The two eigenvectors of eigenvalue 13 are both Fariavectors.Figure 5
A graph with nontrivial cells.Lemma 25.
For a connected graphG, if there exists a nontrivial cell Cr with m nodes, then the following claims hold under equitable weights partition.(i)
Ifn-rank(λijI-L)=m-1, the eigenvectors of λij are all Fariavectors.(ii)
Ifn-rank(λijI-L)>m-1, the entries in the eigenvector x of λij corresponding to any other nontrivial cell Cr-1 are equal to each other as long as the eigenvector is not a Fariavetor.(iii)
Ifλ(L)≠λij, the entries in the eigenvectors of λ(L) corresponding to the nontrivial cell Cr are equal to each other.Proof.
(i)
If there is a nontrivial cellCr containing nodes vi and vj, let us set λij=lii-lij. Then rank(λijI-L)<n, that is, λijI-L=0, where λij is an eigenvalue of Laplacian L. In case x={0,…,0,dith,0…,0, -djth,0,…,0}T, Lx=λijx, where dith=djth, dith and djth are nonzero constants, which denote the ith and jth entries of vector x, respectively. If n-rank(λijI-L)=m-1, it follows from Lemma 19 that the position exchanging of nodes in the nontrivial cell does not affect the structure of L. As a consequence, the eigenvectors of λij are also unaffected. Thus, when dith exchanges its position with -djth, the original eigenvector x is replaced by -x, and the entries except the ith and jth entries in eigenvectors x are 0. That is, there are m-1 linearly independent eigenvectors of Fariavector corresponding to the m-1 eigenvalues λij.(ii)
Ifn-rank(λijI-L)≥m, and the entries in eigenvector x corresponding to Cr-1 are equal, then, there are more than m-1Fariavectors. Thus the entries of x’s of λij are equal.(iii)
Ifλ(L)≠lii-lij, let us consider the entries of x’s of λ(L), where these entries correspond to the nodes in Cr. Assume that these entries are not equal. Then vectors xe are still eigenvectors associated with λ(L) after the positions of these unequal entries are exchanged. Let xlc denote the linear combination of x and xe. The entries of xlc corresponding to the nodes in the nontrivial cell Cr are equal, and the others corresponding to the trivial cell C¬r are 0, which contradicts with the assumption. Therefore, the entries in the eigenvectors corresponding to λ(L)≠lii-lij are equal.The equitable weights partition leads to some special perspectives on the eigenvalues and eigenvectors of Laplacian matrix, which allows us to propose an explicit method for constructing IACW.Theorem 26.
For an equitable weights partition of graphG, suppose that there is a nontrivial cell Cr with m nodes. Then the following statements hold for IACW.(i)
Ifλ2(L)≠λij, the weights between the nodes in Cr are IACW.(ii)
Ifλ2(L)=λij, and n-rank(λijI-L)=m-1, the weights except those between the nodes in the nontrivial cell Cr are IACW.Proof.
By Lemma25, if λ2(L)≠λij, the entries in the eigenvector x of λ2(L) corresponding to the nodes in Cr are equal, and accordingly the weights between the nodes in Cr are IACW. If λ2(L)=λij, and n-rank(λijI-L)=m-1, then Lemma 25 means that the ith and the jth entry in the eigenvectors of λ2(L) are opposite, and the others are 0. Thus the weights except those in the nontrivial cell Cr are IACW.


## 4.2. Convergence Rate under Almost Equitable Weights Partition

Different from the equitable weights partition, the weights in the nontrivial cellCr are not equal if the almost equitable weights partition is taken into account. So the latter makes a part of properties lost compared to the equitable weights partition. Thus, this case is more complex. For the almost equitable weights partition, since the weights between the nodes in nontrivial cell Cr are different, λij=lii-lij is no longer true. As a consequence, λij cannot be characterized exactly.Lemma 27.
For an undirected graphG, there is an eigenvector x of a nonzero eigenvalue of L so that xT1n=0, where 1n∈Rn denotes the column vector with all entries taking 1.Proof.
For an undirected connected graph, 0 is a simple eigenvalue ofL, and L1n=0. Let x denote an eigenvector of a nonzero eigenvalue of L; i.e., Lx=λ(L)x. The Laplacian L is symmetric. It follows that xTL=λ(L)xT, xTL1n=λ(L)xT1n=0. Thus, xT1n=0.In case there is a partition with a nontrivial cellCr, L can be decomposed in accordance with the nontrivial cell,(28)L=LrlrlrTL¬r,where Lr corresponds to the nodes in the nontrivial cell, which indicates the weights between nodes in Cr and its degree. Each column of lr is equal to the other columns, which indicates the weights between nodes in Cr and nodes in other cells. L¬r corresponds to the trivial cells.Remark 28.
For an equitable weights partition,Lr has an eigenvalue λij=lii-lij with multiplicity m-1 if there is a nontrivial cell. For an almost equitable weights partition, Lr only has an eigenvalue with multiplicity 1 which can be characterized.L r = l r 1 T 1 r I r + L r r, where lr1 denotes the first column of lr, and 1r is the vector with proper dimension and all entries taking 1. Lrr is the Laplacian matrix of a system constructed by the nodes in the nontrivial cell Cr. For almost equitable weights partitions, Lrr is the general Laplacian matrix. So the nonzero eigenvalues cannot be characterized. Because of the existence of lr1T1rIr, there is an eigenvalue lr1T1r associated with Lr, and the entries in the eigenvector of lr1T1r are all equal.Lemma 29.
For a matrixLr∈Rm×m, suppose that there is only one nontrivial cell associated with Lr. Then the Laplacian matrices L and Lr share m-1 common eigenvalues λij. Moreover, for matrix L, its x’s associated with λij take xr as a subvector, where xr is the eigenvector of λij associated with Lr; that is, xT={xrT,0,…,0}.Proof.
Assume that the nontrivial cellCr contains m nodes, and Lr=lr1T1rIr+Lrr. Then Lrxr=lr1T1rxr+λrrxr=λijxr, where Lrrxr=λrrxr, λij=lr1T1r+λrr. Let xT={xrT,0,…,0}, with the positions of entries 0 corresponding to the nodes in C¬r. Since xT1n=0, it follows that [Lr,lr]x=λijxr, [lr,L¬r]x=0¬r, Lx=λijx. If λrr=lr1T1r, we see that xr is a vector with all of its entries taking 1. Thus xrT1r≠0; that is, lrTxr≠0, [lr,L¬r]x≠0¬r. Therefore, Lr does not share the eigenvalue lr1T1r with L. So L and Lr share m-1 common eigenvalues, and xT={xrT,0,…,0}.Lemma29 explains the affections caused by nontrivial cells under equitable weights and almost equitable weights partition. The existence of nontrivial cells in Lr makes that part of eigenvalues and eigenvectors of L rely on Lr.Theorem 30.
For an almost equitable weights partition of graphG, suppose that there is a nontrivial cell Cr. If λ2(L)=λij, the weights except those in Cr are all IACW. If λ2(L)≠λij, the weights in Cr are IACW.Proof.
For an almost equitable weights partition with a nontrivial cellCr, λij is an eigenvalue of submatrix obtained by selecting the rows and columns corresponding to the nodes in Cr. By Lemma 29, if λ2(L)=λij, the entries of vector x except those corresponding to the nodes in Cr are 0, where x is the eigenvector corresponding to λij. Therefore, the weights of C¬r are IACW. Let xT=[xr,x¬r]T, where xr is the eigenvector of Lr. The entries of every column in lr are equal to the others. Then lrx¬r=c1r, where c is a constant. If λ2(L)≠λij, and the entries of xr are different, then [Lr,lr]x=Lrxr+c1r=λxr, Lrxr=λxr-c1r. If the entries of xr are different, the entries of λxr-c1r are also different. Thus λ=λij and λ2(L)≠λij yield that the weights between the nodes in the nontrivial cell Cr are IACW.When the nontrivial cells existed, there are IACWs in a system. Thus, we can construct the nontrivial cell to get the IACWs. And it is easy to know that the IACWs are changed, when the caseλ2(L)=λij transforms into λ2(L)≠λij. The cases of the IACWs are identical for equitable weights partition and almost equitable weights partition.


## 5. Simulation Results

When a superposition system is superposed to an original system, some weights of the original graph are changed accordingly. In order to verify the variation of the convergence rate on topologies and weights, we do simulations for Example8.The convergence rate of a system depends on the magnitude of the smallest nonzero eigenvalueλ2(L). When a system gets a larger λ2(L), it can converge faster. For the system in Example 8, we choose initial states x1(0)=-3, x2(0)=2, x3(0)=1.5, x4(0)=-2, x5(0)=-4. Therefore, x∗=-1.1 when the system achieves consensus. Figures 6–8 show the simulation results of G, G^1, G^2, respectively, which show that the system associated with graph G^2 achieves consensus faster than G and G^1. In addition, the system associated with G^1 converges as fast as G because of the identical λ2.Figure 6
States of graphG.Figure 7
States of graphG^1.Figure 8
States of graphG^2.Figures9, 10, and 11 are the simulations of Example 17, where the initial states are the same as Example 8. For τ=0.19s, the state response is shown in Figure 9. It can be seen that the system is unstable since the time delay τ is larger than the delay margin τ∗=0.1661s. For graph Gopt, however, the system can achieve consensus with τ=0.19s as shown in Figure 10, which means that the system with graph Gopt has a larger delay margin τ∗ than the system with graph G in Example 17. The corresponding topological structures in Figures 9 and 10 are, respectively, (a) and (b) in Figure 3. Precisely because the topology corresponding to Figure 9 is different from that corresponding to Figure 10, the system associated with Figure 9 is unstable at the delay τ while Figure 10 is stable at the same delay. When τ=0.14s, the system associated with graph Gopt achieves a faster consensus than the system at τ=0.19s, which is shown in Figure 11.Figure 9
Sates of graphG, τ=0.19s.Figure 10
Sates of graphGopt, τ=0.19s.Figure 11
Sates of graphGopt, τ=0.14s.


## 6. Conclusions and Future Work

In this paper, we proposed a superposition system which was superposed to the original system to explore the variation of convergence rate. By analyzing the eigenvector ofλ2(L), results were derived on checking whether the convergence rate can be changed. When the Laplacian L~ of the superposition system only consists of invalid algebraic connectivity weights, it was proven that the convergence rate remains unchanged. Otherwise, the convergence rate changes. We gave the most optimal case of the convergence rate under fixed cost, which makes the convergence rate the largest and the system more stable. Finally, we proposed a method of constructing invalid algebraic connectivity weights to make systems resistant in a certain extent to the perturbation. In addition, based on the equitable weights partition and almost equitable weights partition, we analyzed the changes of eigenvalues and eigenvectors to discover the variation of convergence rate. In future work, the optimization of convergence rate and convergence rate on directed graphs will be studied. Although, explicit results have been derived for the convergence rate by taking advantage of the proposed concept of superposition systems, the optimization of convergence rate still needs further study. In the future work, convergence rate on directed graphs will also be studied.



---

*Source: 7831317-2018-12-16.xml*