# On Consensus of Star-Composed Networks with an Application of Laplacian Spectrum

Authors: Da Huang; Haijun Jiang; Zhiyong Yu; Qiongxiang Huang; Xing Chen
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

In this paper, we mainly study the performance of star-composed networks which can achieve consensus. Specifically, we investigate the convergence speed and robustness of the consensus of the networks, which can be measured by the smallest nonzero eigenvalueλ2 of the Laplacian matrix and the H2 norm of the graph, respectively. In particular, we introduce the notion of the corona of two graphs to construct star-composed networks and apply the Laplacian spectrum to discuss the convergence speed and robustness for the communication network. Finally, the performances of the star-composed networks have been compared, and we find that the network in which the centers construct a balanced complete bipartite graph has the most advantages of performance. Our research would provide a new insight into the combination between the field of consensus study and the theory of graph spectra.


---

## Body

## 1. Introduction

The research on consensus problems of networks has received much attention in the last decade. There are many potential applications in several aspects related to consensus such as sensor networks, formation control, and decision-making. It is well known that the first milestone of development for network study is related to the famous Euler graph, and then the application of graph theory came into many fields of network study in the past decades. One advantage of studying network through abstract graph is that it can let us compare the differences of properties of topologies between different networks in a more convenient way.For the purpose of achieving consensus, much of the relationships among agents are encoded by the communication graph of the system, and it is well known that the coordination problem can be connected with the Laplacian matrix of the communication graph ([1–3]). This fact can let us take graph theory as a more efficiency tool to study the consensus problem. Recently, there are many articles on consensus or other network properties related to the eigenvalue of Laplacian matrix of graph ([1, 2, 4–8]).The network coherence of fractal network is studied in [6] by using properties of Laplacian eigenvalues. Reference [7] has studied consensus problems in a family of tree networks and investigated first- and second-order consensus characterized by Laplacian spectrum. In [5], the authors have studied the Laplacian spectra of recursive treelike small-world polymer networks and analysed the solution with some related application. In [2], the authors have investigated how the robustness depends on the properties of the Laplacian eigenvalues of graphs and give a derivation for the convergence speed and the H2 norms of some specific graphs.In [1], Olfati-Saber and Murray have showed that the Fiedler eigenvalue λ2 of an undirected (or directed) graph can characterize the convergence speed of consensus problem. The article gives an idea that a network with dense interconnections solves an agreement problem faster than a connected but sparse network is briefly considered and can be further discussed. Since most Laplacian eigenvalues of graphs can not be determined precisely, we can not analyse the convergence speed or other network performances of most graphs in a quantitative way. It is well known that the Laplacian spectrum of star graph has already been determined, and star networks are one of the most common computer network topologies. Star-related structure of network are widely considered in many fields like the consensus problem and synchronization problem, and so on ([2, 9–15]).Inspired by this notion, we consider some meaningful specific networks of certain topologies that are related to star graphs. The star network can be viewed as point-to-multipoint communication system, and the star-composed network can be comprehended as adding communication links among centers on the basis of star networks. It makes sense that all the star topologies have connection with each other only through their center nodes because of the role of their position, and it is natural that the leaf nodes do not have the authorities to communicate among themselves.The consensus in this article means that each agent reaches an agreement by local communication. Our findings bring a better perspective into the combination between consensus problems and the field of graph theory, and our work makes further efforts to use the theory of graph spectra for studying performance of consensus, where the “performance” in this article mainly refers to the convergence speed and robustness of consensus. Due to the chosen undirected graphs, we study the convergence speed and robustness of consensus to communication noise with an application of Laplacian spectrum of corona ([16, 17]) of two graphs, and find that the method of constructing networks by using the notion of corona of two graphs can generate a class of polymer small-world network ([5]).The paper is organized as follows. In Section2, some notations on graph theory are summarized and the relations between performance and Laplacian eigenvalues are explained. In Section 3, the constructions of star-composed networks and main results on Laplacian eigenvalues are given. In Section 4, combined with theorem of algebraic graph theory, we analyse the simulation results in Section 3 and make the comparison of performances for the three classes of networks.


## 2. Preliminaries

### 2.1. Graph Theory and Notations

Throughout this paper, we consider only simple undirected graphs even if without special explanation, where simple graph means the graph has no self-loops or parallel edges ([18]). It is well known to us that the networked system comprises mainly two factors, which are the dynamics of agents and the interaction topology among the nodes. Thus, when the dynamics are given, the network can be simplified as a graph. For convenience of expression, the terms, topology, and graph, vertex, and node will be used without distinction in this paper. We denote a complete graph of n vertices by Kn and denote a star graph with k leaves by Sk, where the leaf refers to the vertex of degree one. Pk is defined to be the empty graph with k vertices, where empty graph refers to the graph without edges among all the nodes of the graph. Let G be a graph with vertex set V={v1,v2,…,vN}, and the edge set of G is defined to be E={i,j∣i,j=1,2,…,N;i≠j}. The adjacency matrix of G, denoted by A(G), is defined as A(G)=[aij]N, where aij is the weight of the edge (i,j). An undirected graph is a graph in which edges have no orientation. To an undirected graph, we can see that (i,j) and (j,i) are the same edge in E, and aij=aji. An edge (i,j) in a weighted undirected graph denotes that the information transmission between two connected nodes is bidirectional. Since we consider mainly the influence of network structure, all the edges in our networks are supposed to have 0-1 weights; that is, aij=1,(i,j)∈E;0,(i,j)∉E.. The Laplacian matrix of G, denoted by L(G), is defined as D(G)-A(G) and can be simplified by L=D-A, where D(G) is the diagonal degree matrix of G defined by DG=diag(d1,d2,…,dN) with di=∑j≠i‍aij. The degree of a node in an undirected graph G is the number of edges that link to the node. The minimum degree of G is the minimum number of degrees of all the nodes in G and is denoted by δ(G). Note that if a graph is undirected, then its adjacency matrix and Laplacian matrix are both symmetric. The Laplacian spectrum of G is defined as spec(L(G))=λ1(G)λ2(G)⋯λp(G)l1l2⋯lp, where λ1(G)<λ2(G)<⋯<λp(G) are the eigenvalues of L(G) and l1,l2,…,lp are the multiplicities of these eigenvalues. The spectrum can be also simply denoted by a sequence of eigenvalues (see [16, 17, 19]): S(L(G))=(λ1,λ2,…,λN), where λ1≤λ2≤⋯≤λN are the Laplacian eigenvalues of G. For any undirected graph, it is well known that λ1=0 is an eigenvalue of L(G) associated with the eigenvector 1=(1,1,…,1)T and L(G) is a positive semidefinite matrix.Definition 1 (see [1] (mirror graph)).
LetG=(V,E,A) be a weighted digraph. Let E¯ be the set of reverse edges of G obtained by reversing the order of nodes of all the pairs in E. The mirror of G denoted by G^ is an undirected graph in the form G^=(V,E^,A^) with the same set of nodes as G, the set of edges E^=E∪E¯, and the symmetric adjacency matrix A^=[a^ij] with elements(1)a^ij=a^ji=aij+aji2≥0.Definition 2 (see [1] (balanced graph)).
The nodevi of a digraph G=(V,E,A) is defined to be balanced if and only if its indegree and outdegree are equal. A graph G is called balanced if and only if all of its nodes are balanced, or(2)∑jaij=∑jaji∀i.Remark 3.
In graph theory, we know that an undirected connected graphG can be viewed as a directed graph through the operation of replacing each edge by two opposite arcs with same weight; therefore it is strongly connected and balanced. By Theorem 4 of [1], we know that any undirected connected graph can achieve consensus. In this article, all the graphs of networks we considered is undirected and 0-1 weighted; through (1), we have a^ij=a^ji=1 or a^ij=a^ji=0; one can see that the mirror of an undirected graph is itself. Let Ls=(L+LT)/2; since d^i=Σaij+aji/2=di, thus D^=D; therefore, Ls=1/2(L+LT)=D-(A+AT)/2=D^-A^=L^=L(G^).Definition 4 (see [16] (the corona of two graphs)).
LetG1 and G2 be two graphs on disjoint sets of n and k vertices, respectively. The corona G1∘G2 of G1 and G2 is defined as the graph obtained by taking one copy of G1 and n copies of G2 and then joining the ith vertex of G1 to every vertex in the ith copy of G2.Example 5.
LetG1=C5, the cycle of 5 nodes, and G2=K2. The two different coronas G1∘G2 and G2∘G1 are shown in Figures 1(c) and 1(d).Figure 1Lemma 6 (see [16, 17]).
LetG1 be any graph with n1 vertices and m1 edges and G2 be any graph with n2 vertices and m2 edges. Suppose that S(L(G1))=(μ1,μ2,…,μn1) and S(L(G2))=(δ1,δ2,…,δn2). Then the Laplacian spectrum of G1∘G2 is given by (i)
two multiplicity one eigenvalues(μi+n2+1)±(μi+n2+1)2-4μi/2∈S(L(G1∘G2)) for each eigenvalue μi(i=1,2,…,n1) of S(L(G1));(ii)
δj+1∈spec(L(G1∘G2)) with multiplicity n1 for every eigenvalue δj(j=2,…,n2) of S(L(G2)).Definition 7 (see [1] (communication cost)).
For 0-1 weighted undirected graphs, the communication cost is defined by(3)C=∑i,j=1Naij=E.Definition 8 (network density).
The densityρ of a network which contains N nodes is defined as the quotient of the number of edges M that exist in the network and the maximum possible number of edges in the network. For undirected network, we have(4)ρ=M1/2NN-1.


### 2.2. Relations between the Performance and Laplacian Spectrum

When we discuss the convergence speed of consensus, the dynamic of each node in the network is defined as follows:(5)x˙=-Lx,where x˙i=∑vj∈Ni‍aij(xj-xi), Ni is the set of neighbours of vi, xi denotes the value of node of vi, x=(x1,x2,…,xN)T is the state vector of network, and L is the Laplacian matrix of graph. The value of node represents physical quantities like position, attitude, and so on. We can comprehend the graph of the network as an information flow. For an undirected connected graph G, the following well known property holds ([20]):(6)minx≠0,1Tx=0xTLxx2=λ2L.The relation between convergence speed of consensus andλ2 of Laplacian matrix of graph can be understood by the following derivation on protocol (5).By Theorem6 of [1], we know that, for networks with balanced information flow, since 1Tx′=-1TLx=0 and ∑i=1N‍xi=C is a constant, we have that α=Ave(x)=C/N is an invariant quantity, and x can be decomposed by the following equation:(7)x=α1+δ,where δ∈RN and δ is the disagreement vector which evolves according to the dynamic(8)δ˙=-Lδ.It follows from (7) that ∑i=1N‍xi=Nα+∑i=1N‍δi; therefore ∑i=1N‍δi=0.LetV(δ)=1/2δ2, by (6) and Remark 3, we have V˙=-δTLδ=-δTLsδ=-δTL^δ≤-λ2(L)δ2=-2κV(δ)<0, ∀δ≠0. And because ∫0t‍V′(δ)/V(δ)ds<∫0t‍-2κds, we can obtain that V(δ(t))<V(δ(0))e-2κt. Moreover, since δ≤(2V(0)e-2κt)1/2=|δ(0)|e-κt, δ(t) converges to 0 exponentially fast with speed κ as t→+∞; this means that consensus can be reached with a convergence speed of κ.When we analyse the robustness of the network, every agent is assumed to be affected independently by white noise of the same intensity; thus the dynamic of each node is given by(9)x˙t=-Lxt+ξt(see [2]) with x∈RN and where ξ(t)∈RN is a random signal with E[ξ(t)]=0, E[ξ(t)Tξ(τ)]=α/2INδ(t-τ), and E[x(0)ξT(τ)]=0. δ(t) is the Dirac delta function and α>0 is the intensity of the noise.Lety(t)=Qx, where Q satisfies Q1N=0, QQT=IN-1, and QTQ=IN-1/N1N1NT=R. A measure of the distance from consensus is the dispersion of the system y(t)=(yT(t)y(t))1/2. Differentiating y(t), we obtain(10)y˙t=-L¯yt+Qξt,where L¯=QLQT. Since the graph of networks we considered is undirected and connected, all the eigenvalues of L¯ are positive real, and hence -L¯ is Hurwitz; therefore, (10) convergences exponentially to zero. In [2], the fact that the speed of convergence will be determined by the eigenvalue of L¯ with the smallest real part, which is equivalent to the nonzero smallest eigenvalue λ2 of L, has been proved. Therefore, we can also use dynamic (10) to analyse the convergence speed. For better interpreting the relation between dynamic system and the convergence speed of consensus, in this article, we consider the convergence speed under dynamic (5) for each node.Definition 9 (see [2]).
The robustness of the consensus dynamics to white noise inputs is measured byH=limt→∞E(y(t))=limt→∞(tr(E[y(t)y(t)T]))1/2, where y(t) satisfies (10) and y(t) defines the distance to consensus.For the state-space system,y˙=Ay+Bu and z=Cy, where A is Hurwitz. And the H2 norm is [tr(CXCT)]1/2, where X is the solution of the Lyapunov equation AX+XAT+BBT=0. It is familiar to us that the definition of H is equal to the H2 norm of system (10) with output equation z(t)=Iy(t).Lemma 10.
SupposeL is a Laplacian matrix of a connected undirected graph with eigenvalues λ1=0<λ2≤λ3≤⋯≤λN. Then the H2 norm which characterizes the robustness of system (10) is(11)H=∑i=2N12λi1/2.Proof.
It is well known that any undirected graph will have a symmetric Laplacian matrix, which is trivially normal ([2]), and we have LT1N=0; then RL=(I-1/N1N1NT)L=L is normal. Since L is symmetric, by proposition of [16], the H2 norm of network under dynamic (10) is H=(∑i=2N‍1/2Re{λi})1/2=(∑i=2N‍1/2λi)1/2.Remark 11.
One well known property related to theH2 norm of undirected graph is the effective resistance Kf, where Kf denotes the Kirchhoff index (see [2, 21, 22]) and Kf=N∑j=2N‍1/λj; it can be related to the power dissipated by the graph. The relation between Kf and H2 norm is H=Kf/2N1/2.


## 2.1. Graph Theory and Notations

Throughout this paper, we consider only simple undirected graphs even if without special explanation, where simple graph means the graph has no self-loops or parallel edges ([18]). It is well known to us that the networked system comprises mainly two factors, which are the dynamics of agents and the interaction topology among the nodes. Thus, when the dynamics are given, the network can be simplified as a graph. For convenience of expression, the terms, topology, and graph, vertex, and node will be used without distinction in this paper. We denote a complete graph of n vertices by Kn and denote a star graph with k leaves by Sk, where the leaf refers to the vertex of degree one. Pk is defined to be the empty graph with k vertices, where empty graph refers to the graph without edges among all the nodes of the graph. Let G be a graph with vertex set V={v1,v2,…,vN}, and the edge set of G is defined to be E={i,j∣i,j=1,2,…,N;i≠j}. The adjacency matrix of G, denoted by A(G), is defined as A(G)=[aij]N, where aij is the weight of the edge (i,j). An undirected graph is a graph in which edges have no orientation. To an undirected graph, we can see that (i,j) and (j,i) are the same edge in E, and aij=aji. An edge (i,j) in a weighted undirected graph denotes that the information transmission between two connected nodes is bidirectional. Since we consider mainly the influence of network structure, all the edges in our networks are supposed to have 0-1 weights; that is, aij=1,(i,j)∈E;0,(i,j)∉E.. The Laplacian matrix of G, denoted by L(G), is defined as D(G)-A(G) and can be simplified by L=D-A, where D(G) is the diagonal degree matrix of G defined by DG=diag(d1,d2,…,dN) with di=∑j≠i‍aij. The degree of a node in an undirected graph G is the number of edges that link to the node. The minimum degree of G is the minimum number of degrees of all the nodes in G and is denoted by δ(G). Note that if a graph is undirected, then its adjacency matrix and Laplacian matrix are both symmetric. The Laplacian spectrum of G is defined as spec(L(G))=λ1(G)λ2(G)⋯λp(G)l1l2⋯lp, where λ1(G)<λ2(G)<⋯<λp(G) are the eigenvalues of L(G) and l1,l2,…,lp are the multiplicities of these eigenvalues. The spectrum can be also simply denoted by a sequence of eigenvalues (see [16, 17, 19]): S(L(G))=(λ1,λ2,…,λN), where λ1≤λ2≤⋯≤λN are the Laplacian eigenvalues of G. For any undirected graph, it is well known that λ1=0 is an eigenvalue of L(G) associated with the eigenvector 1=(1,1,…,1)T and L(G) is a positive semidefinite matrix.Definition 1 (see [1] (mirror graph)).
LetG=(V,E,A) be a weighted digraph. Let E¯ be the set of reverse edges of G obtained by reversing the order of nodes of all the pairs in E. The mirror of G denoted by G^ is an undirected graph in the form G^=(V,E^,A^) with the same set of nodes as G, the set of edges E^=E∪E¯, and the symmetric adjacency matrix A^=[a^ij] with elements(1)a^ij=a^ji=aij+aji2≥0.Definition 2 (see [1] (balanced graph)).
The nodevi of a digraph G=(V,E,A) is defined to be balanced if and only if its indegree and outdegree are equal. A graph G is called balanced if and only if all of its nodes are balanced, or(2)∑jaij=∑jaji∀i.Remark 3.
In graph theory, we know that an undirected connected graphG can be viewed as a directed graph through the operation of replacing each edge by two opposite arcs with same weight; therefore it is strongly connected and balanced. By Theorem 4 of [1], we know that any undirected connected graph can achieve consensus. In this article, all the graphs of networks we considered is undirected and 0-1 weighted; through (1), we have a^ij=a^ji=1 or a^ij=a^ji=0; one can see that the mirror of an undirected graph is itself. Let Ls=(L+LT)/2; since d^i=Σaij+aji/2=di, thus D^=D; therefore, Ls=1/2(L+LT)=D-(A+AT)/2=D^-A^=L^=L(G^).Definition 4 (see [16] (the corona of two graphs)).
LetG1 and G2 be two graphs on disjoint sets of n and k vertices, respectively. The corona G1∘G2 of G1 and G2 is defined as the graph obtained by taking one copy of G1 and n copies of G2 and then joining the ith vertex of G1 to every vertex in the ith copy of G2.Example 5.
LetG1=C5, the cycle of 5 nodes, and G2=K2. The two different coronas G1∘G2 and G2∘G1 are shown in Figures 1(c) and 1(d).Figure 1Lemma 6 (see [16, 17]).
LetG1 be any graph with n1 vertices and m1 edges and G2 be any graph with n2 vertices and m2 edges. Suppose that S(L(G1))=(μ1,μ2,…,μn1) and S(L(G2))=(δ1,δ2,…,δn2). Then the Laplacian spectrum of G1∘G2 is given by (i)
two multiplicity one eigenvalues(μi+n2+1)±(μi+n2+1)2-4μi/2∈S(L(G1∘G2)) for each eigenvalue μi(i=1,2,…,n1) of S(L(G1));(ii)
δj+1∈spec(L(G1∘G2)) with multiplicity n1 for every eigenvalue δj(j=2,…,n2) of S(L(G2)).Definition 7 (see [1] (communication cost)).
For 0-1 weighted undirected graphs, the communication cost is defined by(3)C=∑i,j=1Naij=E.Definition 8 (network density).
The densityρ of a network which contains N nodes is defined as the quotient of the number of edges M that exist in the network and the maximum possible number of edges in the network. For undirected network, we have(4)ρ=M1/2NN-1.


## 2.2. Relations between the Performance and Laplacian Spectrum

When we discuss the convergence speed of consensus, the dynamic of each node in the network is defined as follows:(5)x˙=-Lx,where x˙i=∑vj∈Ni‍aij(xj-xi), Ni is the set of neighbours of vi, xi denotes the value of node of vi, x=(x1,x2,…,xN)T is the state vector of network, and L is the Laplacian matrix of graph. The value of node represents physical quantities like position, attitude, and so on. We can comprehend the graph of the network as an information flow. For an undirected connected graph G, the following well known property holds ([20]):(6)minx≠0,1Tx=0xTLxx2=λ2L.The relation between convergence speed of consensus andλ2 of Laplacian matrix of graph can be understood by the following derivation on protocol (5).By Theorem6 of [1], we know that, for networks with balanced information flow, since 1Tx′=-1TLx=0 and ∑i=1N‍xi=C is a constant, we have that α=Ave(x)=C/N is an invariant quantity, and x can be decomposed by the following equation:(7)x=α1+δ,where δ∈RN and δ is the disagreement vector which evolves according to the dynamic(8)δ˙=-Lδ.It follows from (7) that ∑i=1N‍xi=Nα+∑i=1N‍δi; therefore ∑i=1N‍δi=0.LetV(δ)=1/2δ2, by (6) and Remark 3, we have V˙=-δTLδ=-δTLsδ=-δTL^δ≤-λ2(L)δ2=-2κV(δ)<0, ∀δ≠0. And because ∫0t‍V′(δ)/V(δ)ds<∫0t‍-2κds, we can obtain that V(δ(t))<V(δ(0))e-2κt. Moreover, since δ≤(2V(0)e-2κt)1/2=|δ(0)|e-κt, δ(t) converges to 0 exponentially fast with speed κ as t→+∞; this means that consensus can be reached with a convergence speed of κ.When we analyse the robustness of the network, every agent is assumed to be affected independently by white noise of the same intensity; thus the dynamic of each node is given by(9)x˙t=-Lxt+ξt(see [2]) with x∈RN and where ξ(t)∈RN is a random signal with E[ξ(t)]=0, E[ξ(t)Tξ(τ)]=α/2INδ(t-τ), and E[x(0)ξT(τ)]=0. δ(t) is the Dirac delta function and α>0 is the intensity of the noise.Lety(t)=Qx, where Q satisfies Q1N=0, QQT=IN-1, and QTQ=IN-1/N1N1NT=R. A measure of the distance from consensus is the dispersion of the system y(t)=(yT(t)y(t))1/2. Differentiating y(t), we obtain(10)y˙t=-L¯yt+Qξt,where L¯=QLQT. Since the graph of networks we considered is undirected and connected, all the eigenvalues of L¯ are positive real, and hence -L¯ is Hurwitz; therefore, (10) convergences exponentially to zero. In [2], the fact that the speed of convergence will be determined by the eigenvalue of L¯ with the smallest real part, which is equivalent to the nonzero smallest eigenvalue λ2 of L, has been proved. Therefore, we can also use dynamic (10) to analyse the convergence speed. For better interpreting the relation between dynamic system and the convergence speed of consensus, in this article, we consider the convergence speed under dynamic (5) for each node.Definition 9 (see [2]).
The robustness of the consensus dynamics to white noise inputs is measured byH=limt→∞E(y(t))=limt→∞(tr(E[y(t)y(t)T]))1/2, where y(t) satisfies (10) and y(t) defines the distance to consensus.For the state-space system,y˙=Ay+Bu and z=Cy, where A is Hurwitz. And the H2 norm is [tr(CXCT)]1/2, where X is the solution of the Lyapunov equation AX+XAT+BBT=0. It is familiar to us that the definition of H is equal to the H2 norm of system (10) with output equation z(t)=Iy(t).Lemma 10.
SupposeL is a Laplacian matrix of a connected undirected graph with eigenvalues λ1=0<λ2≤λ3≤⋯≤λN. Then the H2 norm which characterizes the robustness of system (10) is(11)H=∑i=2N12λi1/2.Proof.
It is well known that any undirected graph will have a symmetric Laplacian matrix, which is trivially normal ([2]), and we have LT1N=0; then RL=(I-1/N1N1NT)L=L is normal. Since L is symmetric, by proposition of [16], the H2 norm of network under dynamic (10) is H=(∑i=2N‍1/2Re{λi})1/2=(∑i=2N‍1/2λi)1/2.Remark 11.
One well known property related to theH2 norm of undirected graph is the effective resistance Kf, where Kf denotes the Kirchhoff index (see [2, 21, 22]) and Kf=N∑j=2N‍1/λj; it can be related to the power dissipated by the graph. The relation between Kf and H2 norm is H=Kf/2N1/2.


## 3. Network Construction and Main Results

As we mentioned in the introduction part, the star-composed network of this paper is a kind of network in which all nodes have identical dynamics, and it has the topology composed of linking the center nodes among basic star topologies. The links between two nodes mean that they have communication for information. The star-composed structures in this article are all undirected and connected; therefore, by Remark3, we know that they can achieve consensus. The following procedures (A), (B), and (C) are given to define the three classes of networks.(A) Construction of Star-Composed Network (
1)Step 1.
Given a star topology withk leaves, each node in the star represents an agent. The node with largest degree in the star has the role of communication center, which is called “center node.” The node with degree one in the star is called leaf node.Step 2.
Maken copies of the given star topology. The leaf nodes in each star topology exchange information with the center node of the same star.Step 3.
Link every two of all the center nodes of then star topologies with each other. It makes the centers in the communication network compose a complete graph.The topology can be characterized byKn∘Pk, and we denote it bynetwork (1). We can see that n and k are both positive integers with n≥2 and k≥2; this condition holds for all the networks we constructed in our article. Figure 2 is an example of network (1).Figure 2
The communication topologyK5∘P3.Theorem 12.
LetPk be empty graphs with k nodes and Kn be a complete graph with n nodes. If the network has the topology of network(1), then the convergence speed of consensus is λ2=n+k+1-(n+k+1)2-4n/2, and the H2 norm of the network is H=(1/2(k+1)+(n-1)(n+k+1)/2n+n(k-1)/2)1/2.Proof.
S
p
e
c
(
L
(
K
n
)
)
=
0
n
1
n
-
1 (see [19]), and 0 is the eigenvalue of Pk with multiplicity k.
By Lemma6, we have (i)
0+k+1±(k+1)2-4×0/2∈spec(L(Kn∘Pk)); it follows that 0 and k+1∈spec(L(Kn∘Pk)) with multiplicity 1; we can also acquire that n+k+1±(n+k+1)2-4n/2∈spec(L(Kn∘Pk)) with multiplicity (n-1);(ii)
1∈spec(L(Kn∘Pk)) with multiplicity n(k-1); then the total number of eigenvalues of the Laplacian matrix is 2+2(n-1)+n(k-1)=n+nk, which equals the number of nodes of Kn∘Pk.
Sinceλ2 is the smallest nonzero Laplacian eigenvalue and the eigenvalues of L are nonnegative, λ2=min{n+k+1-(n+k+1)2-4n/2,1}. Due to the theorem that λ2≤δ(G) (see [23]), where δ(G) is the minimum degree of graph G, and since the minimum degree of graph of the network is 1, and it can be proved that n+k+1-(n+k+1)2-4n/2<1, therefore, λ2=n+k+1-(n+k+1)2-4n/2.
Since the graphs of the networks are undirected, their Laplacian matrix is symmetric; by Lemma10, the H2 norm of the network is (12)H=∑i=2N12λi1/2=12k+1+n-1n+k+1+k+1+n2-4n+n-1n+k+1-k+1+n2-4n+nk-121/2=12k+1+n-1n+k+12n+nk-121/2.Remark 13.
Now we discuss the monotonicity ofλ2 and the H2 norm of network (1) when one of n and k is fixed.
The Variance of
λ
2
(i)
Ifk is fixed as a constant, which means the number of leaves of each star is fixed, then let f(x)=x+k+1-(x+k+1)2-4x/2 be a continuously differentiable function; it can be derived that f′(x)>0; therefore λ2=n+k+1-(n+k+1)2-4n/2 increases as the number of center nodes n increases.
(ii)
If the number of center nodesn is fixed, then let g(x)=n+x+1-(n+x+1)2-4n/2 be a continuously differentiable function; it can be derived that g′(x)<0; therefore, λ2=n+k+1-(n+k+1)2-4n/2 decrease as the number of leaf nodes k increases.The Variance of
H
2
Norm
(i)
Ifk is fixed as a constant, let H(x)=(1/2(k+1)+(x-1)(x+k+1)/2x+x(k-1)/2)1/2 be a continuously differentiable function; it can be derived that H′(x)>0; therefore, the H2 norm increases as the number of center nodes increases.
(ii)
Ifn is fixed as a constant, let H(x)=(1/2(x+1)+(n-1)(n+x+1)/2n+n(x-1)/2)1/2; it can be derived that H′(x)>0; therefore, in this case, the H2 norm increases as the number of leaf nodes of each star increases.We give examples for the variance ofλ2 and H2 norm of the above cases in Figures 3, 4, 5, and 6.Figure 3
The variance ofλ2 for Kn∘P5.Figure 4
The variance ofλ2 for K3∘Pk.Figure 5
TheH2 norm for topology Kn∘P3.Figure 6
TheH2 norm for topology K3∘Pk.(B) Construction of Star-Composed Network (
2)Step 1.
Given a star topology withk leaves, each node in the star represents an agent. The node with the largest degree in the star has the role of communication center, which is named center node. The node of degree one in the star is called leaf node.Step 2.
Maken identical copies of the star; separate all the center nodes into two parts such that the center nodes in the same part have no connection with each other.Step 3.
Link each center node in one part to every center node in the other part in order that the center nodes in the same part have the same degree.The topology which the above procedure made can be characterized byKa,b∘Pk (see Figure 7). It can be seen that the topology composed only of the centers of the above procedure is a complete bipartite graph.Figure 7
The communication topologyK2,3∘P3.For the simplicity and practical meaning of result (see Remark15), we consider the special case that the number of center nodes in the two parts are equal, and the topology of the special case is denoted bynetwork (2).Theorem 14.
LetKa,b be a complete bipartite graph, where a,b is the number of nodes of each part, and a,b≥2. Let Pk be an empty graph with k nodes. If a≤b, then the convergence speed of the topology Ka,b∘Pk is λ2=a+k+1-(a+k+1)2-4a/2, and the H2 norm which characterizes the robustness is H=(1/2(k+1)+(b-1)(a+k+1)/2a+(a-1)(b+k+1)/2b+(a+b+k+1)/2(a+b)+1/2(a+b)(k-1))1/2.Proof.
Since the Laplacian spectrum of complete bipartite graph is (see [7])(13)specLKa,b=0aba+b1b-1a-11,by Lemma 6, we have(i)
k+1±(k+1)2/2∈spec(Ka,b∘Pk); it follows that 0 and k+1∈spec(Ka,b∘Pk) with multiplicity 1, a+k+1±(a+k+1)2-4a/2∈spec(Ka,b∘Pk) with multiplicity (b-1), b+k+1±(b+k+1)2-4b/2∈spec(Ka,b∘Pk) with multiplicity (a-1), and a+b+k+1±(a+b+k+1)2-4(a+b)/2∈spec(Ka,b∘Pk) with multiplicity 1;(ii)
1∈spec(Ka,b∘Pk) with multiplicity (a+b)(k-1).
SetF(x)=(x+k+1)-(x+k+1)2-4x/2; we can acquire that F′(x)>0; therefore, to derive the smallest nonzero eigenvalue λ2 of L, we only need to make the comparison between a+k+1-(a+k+1)2-4a/2, b+k+1-(b+k+1)2-4b/2, and 1. Thus, the convergence speed of consensus of our network is λ2=min⁡{1,a+k+1-(a+k+1)2-4a/2,b+k+1-(b+k+1)2-4b/2}. Since the algebraic connectivity λ2 is always less than or equal to the smallest degree, that is, λ2≤δ(G), it is obvious that in our star-composed topology δ(G)=1; thus we have λ2≤1; therefore, λ2=a+k+1-(a+k+1)2-4a/2. By Lemma 10, the H2 norm which characterizes the robustness of our network is (14)H=∑i=2N12λi1/2=12k+1+b-1a+k+1+a+k+12-4a+b-1a+k+1-a+k+12-4a+a-1b+k+1+b+k+12-4b+a-1b+k+1-b+k+12-4b+1a+b+k+1+a+b+k+12-4a+b+1a+b+k+1-a+b+k+12-4a+b+12a+bk-11/2=12k+1+b-1a+k+12a+a-1b+k+12b+a+b+k+12a+b+12a+bk-11/2.Remark 15.
It is well known that the complete graph has the structure that every node has the same degree, which means each center node has the same communication role of the network. It is familiar to us that each node of undirected cycle has the degree two, and the spectrum of the cycle has already been determined; therefore it has accurate eigenvalues; we can acquireλ2 from its spectrum.
According to this fact, a natural question arises that if the topology of the regular graph of networks may have the similar analysis of determiningλ2, which can characterize the convergence speed? However, it is a pity that the spectrum of general k-regular graph ([18]) has not been determined by anyone yet, where k≥2 can be any positive integer. We know that the structure of bipartite graph has many applications in the network science ([24]), such as man cooperative network, student course selection network, and online community network. It is interesting to see that the structure which procedure (B) made can be viewed as adhering each node of bipartite graph with a star topology.
Based on the above understanding, to derive a more simple solution of the performance, we consider the case that the linking relations among the centers have the structure of balanced complete bipartite graph, in which each part of the structure has the same number of nodes, which meansa=b, and we denote this kind of network by network (2). In this special case, all center nodes in the network have the same degree; thus, the following corollary can be derived.Corollary 16.
When the two parts of the network have the same number of center nodes, that is,a=b, we have spec(L(Ka,a))=0a2a12(a-1)1, and the convergence speed for the consensus of network(2) with topology Ka,a∘Pk equals λ2=a+k+1-(a+k+1)2-4a/2. Its robustness can be determined by H=(1/2(k+1)+(a-1)(a+k+1)/a+a(k-1)+(2a+k+1)/4a)1/2, where a≥1, k≥2.Remark 17.
With the similar analysis of Theorem12, it can be deduced that the λ2 increases as a increases and it decreases as the number of leaves of each star k increases; besides, 1 is an upper bound of λ2. Next, we discuss the monotonicity of H2 norm: (i)
Ifk is fixed, then let H(x)=(1/2(k+1)+(x-1)(x+k+1)/x+x(k-1)+(2x+k+1)/4x)1/2. It can be derived that H′(x)>0; therefore, in this case, the H2 norm increases as a increase.(ii)
Ifa is fixed, let H(x)=(1/2(x+1)+(a-1)(a+x+1)/a+a(x-1)+(2a+x+1)/4a)1/2. We can derived that H′(x)>0; therefore, the H2 norm increases as k increases.
Numerical examples for the variance ofλ2 and H2 norm are given in Figures 8, 9, 10, and 11.Figure 8
The variance ofλ2 for Ka,a∘P3.Figure 9
The variance ofλ2 for K3,3∘Pk.Figure 10
The variance ofH2 norm for Ka,a∘P3.Figure 11
The variance ofH2 norm for K3,3∘Pk.(C) Construction of Star-Composed Network (
3)Step 1.
With the same operation of constructions (A) and (B), givenn copies of the given star topology, each star has k leaves.Step 2.
Comprehend each center node of the given stars as an agent of signal center; then choose one of all the centers arbitrarily as the general communication center of the whole network.Step 3.
Link all the other centers to the general center of the network.The topology can be constructed by the operation of corona and can be expressed bySn-1∘Pk, where Sn-1 is a star with n-1 leaves; we denoted the network bynetwork (3). An example of the network is shown in Figure 12.Figure 12
The communication topologyS4∘P3.Theorem 18.
The network(3) which is characterized by Sn-1∘Pk has the convergence speed λ2=2+k-(k+2)2-4/2, and the H2 norm equals H=(1/2(k+1)+(n+k+1)/2n+(n-2)(k+2)+n(k-1)/2)1/2.Proof.
It is obvious thatSn-1=K1∘Pn-1. By Lemma 6, we have (i)
0+(n-1)+1±n2-4×0/2∈Spec(L(K1∘Pn-1)); it follows that n and 0∈Spec(L(K1∘Pn-1)) with multiplicity 1;(ii)
1∈spec(L(Sn-1)) with multiplicity n-2; therefore, (15)specLSn-1=01n1n-21.Next, we calculate the Laplacian spectrum of Sn-1∘Pk. Again, by Lemma 6, we have(iii)
k+1±(k+1)2-4×0/2∈spec(L(Sn-1∘Pk)) with multiplicity 1; it follows that 0 and k+1∈Spec(L(Sn-1∘Pk)) with multiplicity 1, n+k+1±(n+k+1)2-4×n/2∈spec(L(Sn-1∘Pk)) with multiplicity 1, and 2+k±(k+2)2-4/2∈spec(L(Sn-1∘Pk)) with multiplicity (n-2).(iv)
1∈Spec(L(Sn-1∘Pk)) with multiplicity n(k-1); similar to the analysis of Theorem 12, set F(x)=(x+k+1)-(x+k+1)2-4x/2; since Fx′>0, and k is an positive integer, we have that 2+k-(k+2)2-4/2 is the minimum nonzero Laplacian eigenvalue of the graph except 1. Let g(y)=2+y-(y+2)2-4/2; it can be derived that gy′<0; therefore, the maximum value of λ2 equals g(2)=2-3<1; it accords with the result of algebraic graph theory that λ2≤δ(G)=1, where δ(G) is the minimum degree of graph G. Therefore, λ2=2+k-(k+2)2-4/2.
Due to the eigenvalues derived above, theH2 norm of the network equals (16)H=12k+1+1n+k+1+n+k+12-4n+1n+k+1-n+k+12-4n+n-2k+2+k+22-4+n-2k+2-k+22-4+nk-121/2=12k+1+n+k+12n+n-2k+2+nk-121/2.Remark 19.
Through the derivation of Theorem18, we can obtain that λ2 is monotonically decreasing as k increases.
The variance ofH2 norm is discussed as follows:(i)
Ifk is fixed, let H(x)=(1/2(k+1)+(x+k+1)/2x+((x-2)(k+2)+x(k-1))/2)1/2; then we can derive that Hx′>0; therefore, the H2 norm increases as the number of center nodes increases.(ii)
Ifn is fixed, let H(x)=(1/2(x+1)+(n+x+1)/2n+((n-2)(x+2)+n(x-1))/2)1/2; then we have Hx′>0; therefore, the H2 norm increases as k increase.
Examples of variance for convergence speed and robustness are given in Figures13, 14, and 15.Figure 13
The convergence speed forSn-1∘Pk.Figure 14
The variance ofH2 norm for Sn-1∘P3 (n≥3).Figure 15
The variance ofH2 norm for S3∘Pk (k≥2).Remark 20.
In Theorem18, if there exist k+1 identical star topologies, which equal the number of center nodes of the network, that is, n=k+1 (see Figure 16), from Example 5 and Figure 16, we find that the network construction method of corona of two graphs can generate a class of small-world polymer networks (see [5]), and Figure 16 is an example of the 2 iterations of the network construction method in [5]. The following corollary can be derived.Figure 16
The communication topologyS4∘S4 (n=5, k=4).Corollary 21.
Under the network topology of Remark20, the convergence speed equals λ2=1+n-(n+1)2-4/2, and the H2 norm is H=(1/2n+1+(n-2)(1+2n)/2)1/2.Proof.
By Lemma6, with the similar analysis of the above theorem, we have(i)
n±n2/2∈spec(L(Sk∘Pk)); it follows that 0 and n∈spec(L(Sk∘Pk)) with multiplicity 1; 2n±(2n)2-4n/2∈spec(L(Sk∘Pk)) with multiplicity 1; 1+n±(n+1)2-4/2∈spec(L(Sk∘Pk)) with multiplicity (n-2);(ii)
1∈spec(L(Sk∘Pk)) with multiplicity n(n-2); since there exist at least two star clusters, which means n≥2, and because 1+n+(n+1)2-4>2, let f(x)=2x-4x2-4x; we can derive that fx′>0; thus 2n-4n2-4n≥2; therefore (17)2n-4n2-4n/21+n-n+12-4/2=2n-4n2-4n1+n+n+12-44>1.Then letg(x)=1+x-(x+1)2-4, gx′<0; therefore 1+n-(n+1)2-4/2<1; it accords with the theorem of algebraic theory that λ2≤δ(G)=1. Hence, we have λ2=1+n-(n+1)2-4/2. We can see that λ2 decreases as the number of center nodes increases. The H2 norm of this case equals (18)H=12n+12n+4n2-4n+12n-4n2-4n+n-21+n+n+12-4+n-21+n-n+12-4+nn-221/2=12n+1+n-21+2n21/2.Remark 22.
LetF(x)=(1/2x+1+(x-2)(1+2x)/2)1/2; we can derive that F′(x)>0; therefore, the H2 norm increases as the number of center nodes increases. Due to the proof of Corollary 21, it can be seen that λ2 decreases as n increases. The variance of λ2 and H2 norm (when n=2,…,50; k=2,…,49) is showed in Figures 17 and 18.Figure 17
λ
2 of Sn-1∘Pn-1 (n≥3, k=n-1).Figure 18
TheH2 norm of Sn-1∘Pn-1 (n≥3).


## 4. Simulation Analysis and Comparison

Now we make the comparison of performance for the star-composed networks(1)–(3). By the analysis of the above theorems, it can be derived that the monotonicity of function f(x)=x+k+1-(x+k+1)2-4x/2 is monotonically increasing. Therefore, when n and k of the three classes of networks are equal, the convergence speed of networks (1)–(3) has the relation λ2(1)≥λ2(2)>λ2(3), where λ2(i) denotes the smallest nonzero Laplacian eigenvalue of the graph of network (i), i=1,2,3. We can see that the network (1) has the largest convergence speed of the three, and λ2(3) is irrelevant with the number of center nodes n. Actually, we have the theorem in the algebraic graph theory that λ2(G)≤λ2(G′), where G′ is the graph obtained by adding an edge to graph G (see [23]). Hence, if the linking structure of center nodes of our network has less edges than complete graph Kn, then the convergence speed of the whole network is always smaller than network (1). The method of constructing the network topology in this article can obviously create a class of small-world networks by the corona of a sequence of graphs; for instance, the corona K1∘Pn∘Pn∘⋯∘Pn is a kind of small-world polymer network (see Figure 1 in [5]). We can view the corona of these graphs as a construction method of network grown.Due to the simulation data, it can be seen that the variance of theH2 norms of all our networks increases as the number of center nodes n or the number of leaf nodes k is fixed, and the monotonicity of H2 norm of Corollary 21 is similar to the linear relation. Through the construction of the networks, note that n and k satisfy the equation n(1+k)=N, where N is the number of nodes of the whole network. When N is fixed, for better comparing these different classes of networks, we describe their variance of H2 norm in the three-dimensional space in Figures 19 and 20.Figure 19
The variance ofH2 norm for network (i) when N=10000, i=1,2,3.Figure 20
The variance ofH2 norm for network (i) when N=100, i=1,2,3.Through the two numerical examples in Figures19 and 20, we find that when N=100, the H2 norm of network (1) is the smallest of the three. The H2 norm of network (1) and network (2) decreases as n increases. And with N increases, the H2 norm of network (1) and network (2) tend to be the same value. It tells us that when the number of the nodes of the whole network N is fixed, the robustness of network (1) and network (2) tend to be the same as n increase, and since the difference between the two networks is that network (2) has less edges than network (1), therefore, by (3), the cost of network (2) is less than network (1).WhenN is fixed, the H2 norm of network (3) increases as n increases. We can see that when n=2, the H2 norms of the three classes of star-composed networks are the same; it accords with the fact that they have the same topology when n=2 (Figure 21).Figure 21
Star-composed network (n=2, k=8).When then identical star topologies are given, by (4), we can obtain that ρ1=1/2n(n-1)/1/2n(n-1)=1, ρ2=n/2·n/2/1/2n(n-1) (here we suppose n/2 is an integer), and ρ3=n-1/1/2n(n-1), where ρi denotes the density of the graph composed only of the center nodes of network (i), i=1,2,3. It can be derived that ρ1>ρ2>ρ3. Due to the network construction and the simulation figures, we give a conjecture that the H2 norm of network (i) is relevant with the density ρi; that is, the H2 norm decreases as ρi increases when the same n copy of star clusters is fixed, which means the robustness becomes better as the density of the graph constructed by centers increases.


## 5. Conclusion

Consider synthetically the convergence speed, robustness, and the cost of the network, we find that the topology of network(3) has the largest H2 norm of the three; therefore its robustness is the worst of them; however, it has the smallest cost of the three. Network (2) has an advantage that it has relatively large convergence speed and its robustness is as good as network (1) when the size of the network increases, but its cost is relatively small. Therefore, network (2) has reference values for real applications.



---

*Source: 4619514-2017-03-05.xml*