# Optimizing Pinned Nodes to Maximize the Convergence Rate of Multiagent Systems with Digraph Topologies

Authors: Yujuan Han; Wenlian Lu; Tianping Chen; Changkai Sun
Journal: Complexity
 (2019)

---

## Abstract

This paper investigates how to choose pinned node set to maximize the convergence rate of multiagent systems under digraph topologies in cases of sufficiently small and large pinning strength. In the case of sufficiently small pinning strength, perturbation methods are employed to derive formulas in terms of asymptotics that indicate that the left eigenvector corresponding to eigenvalue zero of the Laplacian measures the importance of node in pinning control multiagent systems if the underlying network has a spanning tree, whereas for the network with no spanning trees, the left eigenvectors of the Laplacian matrix corresponding to eigenvalue zero can be used to select the optimal pinned node set. In the case of sufficiently large pinning strength, by the similar method, a metric based on the smallest real part of eigenvalues of the Laplacian submatrix corresponding to the unpinned nodes is used to measure the stabilizability of the pinned node set. Different algorithms that are applicable for different scenarios are develped. Several numerical simulations are given to verify theoretical results.


---

## Body

## 1. Introduction

Control problems in multiagent systems and complex networks are widely studied in recent years. In multiagent systems, consensus means that all agents will converge to some common state. Many algorithms are proposed to assure consensus [1–9]. Among them, the following linear interaction rule is commonly used:(1)x˙it=∑j=1,j≠imaijxjt-xit,i=1,…,mwhere xi(t)∈R is the state of agent i and aij≥0 is the coupling strength from agent j to i. By graph theory, A=[aij] can be seen as the weight matrix of a weighted directed graph. In most of the existing literatures, the concept of spanning tree is widely used to describe the communicability among agents in networks that can guarantee consensus [5–7]. It was proven that when the underlying graph has a spanning tree, the agents will agree on a common value, which is a linear combination of the initial states of all agents [8, 9]. However, in some cases, it is desirable to steer the state to a prescribed value s. For this purpose, the pinning control strategy could be applied:(2)x˙it=∑j=1,j≠imaijxjt-xit-κdixit-s,i=1,…,mwhere κ is the pinning strength; di takes value 1 if agent i is pinned and 0 otherwise.In [10], it was proven that a pinned node set can stabilize a directed network to some unstable trajectories if and only if the pinned node set can access all the other vertices in the digraph. In [11], it was proven that a single controller can pin a coupled complex network to a homogenous solution.These studies mainly concern how to choose pinned node(s) to stabilize the network. However, the pinned node set that can stabilize the network is not unique, and the stability performance under various pinned node sets can be different. Therefore, the following question is raised: given the number of feedback controllers, which nodes should be pinned to stabilize the network best?Up unitl now, many centrality measures (see [12]), such as degree, closeness, betweenness, and eigenvector centrality, have been proposed to assess the influence of nodes in the network. In [13–15], it was concluded that, for heterogeneous networks, pinning nodes with high degree or betweenness centrality perform better than the randomly pinning scheme, whereas, for homogeneous networks, there is no significant difference between random pinning and selective pinning schemes.However, when the number of pinned nodes is sufficiently large, it was shown in [16] that pinning nodes that are adjacent to those with highest degree have good performance, whereas, for scale-free networks, it was observed in [15, 17] that pinning nodes with small degree centrality or randomly pinning perform better than pinning nodes with high degree centrality. In [18, 19], a metric based on the Laplacian eigenratio was proposed to quatify local controllability of the network. A similar metric was also used for pinning controllability of undirected and unweighted networks in [20], where, by sensitivity analysis of the eigenratio, it was shown that the magnitude of elements in the eigenvector corresponds to the largest eigenvalue of the Laplacian that can be used to assess the importance of nodes. In [21], a new centrality named ControlRank (CR) was proposed for strongly connected networks. The CR is a dual form of PageRank, which can be seen as a variation of eigenvector centrality. But, as pointed out in [21], such a centrality cannot be used for disconnected networks.In this paper, we search for the pinned nodes that maximize the convergence rate of multiagent systems in cases of sufficiently small and large pinning strength. In the case of sufficently small pinning strength, perturbation methods are employed for analysis; we show that the left eigenvector(s) corresponding to eigenvalue 0 of the Laplacian matrix can be used to select the optimal pinned node set. In the case of sufficiently large pinning strength, a metric based on the smallest real part of eigenvalues of the Laplacian submatrix corresponding to the unpinned nodes is used to measure the controllability of pinned node set, which leads to a strategy to obtain the optimal pinned node set.


## 2. Preliminary

Given a matrixA, denote aij as the element of A on the i-th row and j-th column. Let 1 and 0 denote the column vectors with each element being 1 and 0, respectively. For any vector x, diag(x) denotes the diagonal matrix with its i-th diagonal element being the i-th element of x; [x]i denotes the i-the element of x; x⊤ denotes the transpose of x. For a matrix A∈Rm×m, denote its i-th smallest eigenvalue (in real part) by λi(A),i=1,…,m. In denotes the n×n identity matrix.A weighted directed graphG consists of a node set V(G), numbered by {1,…,m}, a directed edge set E(G)⊆V(G)×V(G), where e(i,j)∈E(G) if and only if there exists an edge from node j to node i, and a weighted matrix A=[aij], where aij>0 denotes the weight of edge e(i,j). The graph is said to have a spanning tree if there is a node calledroot such that, for any other node j, there is a path from the root to j. Define L=[lij] by lij=-aij if i≠j and lii=-∑j=1,j≠imlij. We call L the Laplacian matrix of the graph G.Denoteyi=xi(t)-s, y=[y1(t),…,ym(t)]⊤, and D=diag([d1,…,dm]). System (2) can be rewritten as(3)y˙t=-L+κDyt.Denote by D the pinned node set in the following. Hence, i∈D is equivalent to di=1.Noting that pinning consensus is a special case of pinning synchronization, we can apply the result given in [10, 11] to system (3). Then we have the following Lemma.Lemma 1 (see [10, 11]).
All the eigenvalues of matrixL+κD have positive real parts if and only if the pinned node set D can access all the other vertices.In this paper, we aim to find a set ofp nodes whose pinning increases the convergence rate of the system maximally. It is known that the eigenvalue of L+κD with the smallest real part, denoted by λ1(L+κD), gives the lower bound of the convergence rate of system (3). Therefore, the optimization problem in this paper is formalized as follows:given the Laplacian matrixL, the pinning strengthκ, and the number of pinned nodesp, find a pinned node setDthat reaches the following maximum:(4)maxD:D=p⁡Reλ1L+κD.Our investigation considers two extreme situations when the pinning strengthκ is sufficiently small or sufficiently large.


## 3. Small Pinning Strength

### 3.1. Network Has a Spanning Tree

Suppose thatG has a spanning tree and L is the Laplacian matrix. By the Gerschgorin theorem [22] and the Perron-Frobenius theorem [23], we have that 0 is the smallest eigenvalue of L and its associated left eigenvector, denoted by ξ, is nonnegative or nonpositive. With loss of generality, we assume that ∑i=1m[ξ]i=1 and [ξ]i≥0 holds for ∀i. Moreover, it can be seen that 1 is the right eigenvector of L corresponding to eigenvalue 0. By the perturbation theory [24, 25], the smallest eigenvalue of L+κD has the form (5)λ1L+κD=0+κ·λ1D+κ2·λ2D+oκ2and its associated right eigenvector, denoted by η1(L+κD), satisfies(6)η1L+κD=1+κ·η1D+κ2·η2D+oκ2as κ→0, where o(s) denotes terms that satisfy lims→0|o(s)|/s=0. By (L+κD)·η1(L+κD)=λ1(L+κD)·η1(L+κD), we have (7)L1+κD1+Lη1D+κ2Dη1D+Lη2D+oκ2=κλ1D1+κ2λ1Dη1D+λ2D1+oκ2which leads to(8)D1+Lη1D=λ1D1,(9)Dη1D+Lη2D=λ1Dη1D+λ2D1.Multiplying the vector ξ⊤ from left to (8) on both sides leads to(10)ξ⊤D1=λ1Dξ⊤1since ξ⊤L=0⊤. Then we have that(11)λ1D=ξ⊤D1ξ⊤1=ξ⊤D1=∑i=1mξidi.Suppose that p is the number of feedback controllers and j1,…,jm is a permutation of 1,…,m such that [ξ]j1≥[ξ]j2≥⋯≥[ξ]jm. Then we get (12)λ1D=∑i=1mξidi≤∑k=1pξjkand the equality sign holds if D={j1,…,jp}. Let D0={j1,…,jp}. Apparently, if [ξ]jp>[ξ]jp+1, D0 is the unique set that maximizes λ(1)(D). However, if [ξ]jp=[ξ]jp+1, the set D1={j1,…,jp-1,jp+1} also maximizes λ(1)(D). Now we need to compare D0 with other sets that also maximize λ(1)(D) and find the unqiue one that maximizes Reλ(2)(D).Analogously, multiplying the vectorξ⊤ from left to (9) on both sides and employing the equalities ξ⊤L=0⊤,ξ⊤1=1, we get(13)λ2D=ξ⊤D-λ1Dξ⊤η1D.Next, we need to compute η(1)(D). Suppose that J=Q-1LQ is a Jordan form matrix of L with Q=[1,Q^] and J=diag{J1,J2,…,JK}, where Jk is a Jordan block, k=1,…,K. Notice that 0 is a simple eigenvalue of L; we get that J1=0 and J2,…,JK are nonsingular. Let Q-1=[ξ,P^⊤]⊤ and J=diag{0,J^}. It can be derived from (8) that(14)η1D=a1-Q^J^-1P^D1where a∈C is some constant number. Substituting (14) into (13), we get (15)λ2D=-ξ⊤DQ^J^-1P^D1.Now we have the following result.Theorem 2.
Suppose thatL has a spanning tree, ξ∈Rm with ∑i=1m[ξ]i=1 is the left eigenvector of L associated with eigenvalue 0, and p is the number of pinned nodes. Let j1,…,jm be a permutation of 1,…,m such that [ξ]j1≥⋯≥[ξ]jm. (1)
If[ξ]jp>[ξ]jp+1, (16)maxD:D=p⁡Reλ1L+κD=κ·maxD:D=p⁡λ1D+oκ=κ·∑k=1pξjk+oκasκ→0, and the maximum is reached when D={j1,…,jp} and it is the unique set that maximizes λ(1)D.(2)
If[ξ]jp=[ξ]jp+1, let (17)P=D:D=p,∑i∈Dξi=∑k=1pξjk.Then(18)maxD:D=p⁡Reλ1L+κD=κ·maxD:D=p⁡λ1D+κ·Reλ2D+oκ2=κ·∑k=1pξjk+κ2·maxD:D∈P⁡Re-ξ⊤DQ^J^-1P^D1+oκ2asκ→0, where J=Q-1LQ is a Jordan form matrix of L with Q=[1,Q^], P^=[0,Im-1]Q-1, and J^=[0,Im-1]J[0,Im-1]⊤.Remark 3.
Theorem2 indicates that the magnitude of elements in the left eigenvector corresponding to eigenvalue 0 of the Laplacian matrix can be used to measure pinned nodes’ effect on the convergence rate of the system as κ→0.


### 3.2. Network without Spanning Trees

Without loss of generality, we suppose thatL has the following form [26]: (19)L=L11⋯00⋯0⋮⋱⋮⋮⋯⋮0⋯LK1K10⋯0LK1+1,1⋯LK1+1,K1LK1+1,K1+1⋯LK1+1,K1+K2⋮⋱⋮⋮⋱⋮LK1+K2,1⋯LK1+K2,K1LK1+K2,K1+1⋯LK1+K2,K1+K2Here, each Lii∈Rli,li,i=1,…,K1 is a Laplacian matrix and its corresponding subgraph has a spanning tree (isolated node can be seen as a subgraph that has a spanning tree with itself being the root). In [26], the subgraphs corresponding to Lii,i=1,…,K1, were called primary layer subgraphs and an algorithm was given to extract them. Denote by ξ(i) the left eigenvector of Lii,i=1,…,K1, corresponding to 0 and ∑j[ξ(i)]j=1. Without loss of generality, we assume that [ξ(i)]1≥⋯≥[ξ(i)]li; otherwise, we can permutate the indices of nodes of the graph topology to get the above ordering.Meanwhile,∀i∈{K1+1,…,K1+K2}, the subgraph corresponding to Lii has a spanning tree and there exists j≠i such that Lij≠0. Denote (20)L^=LK1+1,K1+1⋯LK1+1,K1+K2⋮⋱⋮LK1+K2,K1+1⋯LK1+K2,K1+K2.By Gershgorin circle theorem [22], we get that all eigenvalues of L^ have positive real parts. Therefore, 0 is the smallest eigenvalue of L and has K1 different associated eigenvectors. Denote by {ηi,i=1,…,K1} and {ξi,i=1,…,K1} the right and left eigenspaces of L corresponding to eigenvalue 0. Suppose that(21)ηi=0l1+⋯+li-1⊤,1li⊤,0li+1+⋯,lK1⊤,#⊤,(22)ξi=0l1+⋯+li-1⊤,ξi⊤,0m-l1-⋯-lK1⊤⊤,i=1,…,K1.Denote byλ~iκ,D,i=1,…,K1, the K1 smallest eigenvalues of L+κD and by η~i(κ,D),i=1,…,K1, the associated right eigenvectors. For any fixed D, we regard λ~i(κ,D) and η~i(κ,D) as functions of κ with λ~i(0,D)=0,η~i(0,D)=ηi,i=1,…,K1. By a perturbation expansion [24, 25], we have(23)λ~iκ,D=0+κλi1+oκ,i=1,…,K1(24)η~iκ,D=ηi+κηi1+oκ,i=1,…,K1as κ→0. Then by(25)L+κD·ηi+κηi1+oκ=κλi1+oκ·ηi+κηi1+oκ,we have(26)Lηi1+Dηi=λi1ηi.Multiplyinig the vector ξi⊤ from left to the above equation, we have(27)ξi⊤Dηi=λi1ξi⊤ηisince ξi⊤L=0. According to the partition of L, we divide D as follows:(28)D=diagD11,…,DK1+K2,K1+K2,whereDii∈Rli,li,∀i.Then by (21), (22), and ξ(i)⊤·1=1, we have (29)λi1=ξi⊤Dηiξi⊤ηi=ξi⊤Dii1,i=1,…,K1.Substituting λi(1) into (23) gives(30)λ~iκ,D=κ·ξi⊤Dii1+oκ,i=1,…,K1.Apparently, the smallest eigenvalue λ1(L+κD) lies in λ~i(κ,D), i=1,…,K1. Hence, the optimal pinned node set can maximize (31)Reλ1L+κD=mini⁡Reλ~iκ,D=κ·mini⁡ξi⊤Dii1+oκ.Then we have the following result.Theorem 4.
Suppose thatL has the form in (19), ξ(i) is the left eigenvector of Lii corresponding to 0 with ∑jξij=1,i=1,…,K1, and p is the number of pinned nodes. Then (32)maxD:D=p⁡Reλ1L+κD=κ·maxD:D=p⁡mini=1,…,K1⁡ξi⊤Dii1+oκas κ→0, where D has the form in (28).Lemma1 implies that, to stabilize system (3), the pinned node set D should contain at least one root of every subgraph G(Lii),i=1,…,K1. Then we have the following lemma.Lemma 5.
Suppose thatL has the form in (19). Then maxD:|D|=p⁡mini=1,…,K1⁡ξ(i)⊤Dii1 is positive if and only if the number of pinned nodes satisfies p≥K1.Remark 6.
Assume that[ξ(i)]1≥⋯≥[ξ(i)]li,i=1,…,K1. If [ξ(i)]1>[ξ(i)]2 holds ∀i, then the optimal pinned node set should contain nodes 1,l1+1,l1+l2+1,…,∑k=1K1-1lk+1.In this section, we focus on the first-order approximation ofλ1(L+κD) and search for the pinned node set that maximizes the first-order term of the approximation.Remark 7.
Notice that the pinned node set that maximizesmini=1,…,K1⁡ξ(i)⊤Dii1 may not be unique; one may need to do the second-order approximation of λ1(L+κD) to find the optimal pinned node set. Specifically, among the sets that maximize mini=1,…,K1ξ(i)⊤Dii1, find the one that maximizes λ(2)(D), which is the second-order term of the approximation.Note that whenp>∑i=1Kli, all nodes in the primary layer subgraphs should be pinned to maximize mini=1,…,Kξ(i)⊤Dii1. But the selection of the rest of pinned nodes leads to a different optimization problem. Therefore, in this section, we focus on the case p≤∑i=1Kli. The investigation of the case p>∑i=1Kli is left as an open problem for future research.In this section, we need to solve the optimization problem:(33)maxD:D=p⁡mini=1,…,K1⁡ξi⊤Dii1.Based on the above theoretical analysis, Algorithm1 is presented to search for the pinned node set DO of cardinality p (p≥K1) that maximizes mini=1,…,K1ξ(i)⊤Dii1 when κ≪1.Algorithm 1:Searching for the pinned node set DO that maximizes mini=1,…,K1⁡ξ(i)ΤDii1.
Input: the Laplacian matrix L, the pinning strength κ, the number of pinned nodes p Output: the pinned node set DO; mini=1,…,K1ξ(i)ΤDii1 1: permute the indices of the nodes of graph G to transform L into the form (19) 2: compute the left eigenvectors ξ(i) of Lii,i=1,…,K1 corresponding to 0 and normalize them with 1-norm 3: permute the indices of the nodes in the subgraphs GLii to get [ξ(i)]1≥⋯≥[ξ(i)]li, i = 1 , … , K 1 4: initialize Di={li-1+1} and Si=ξili-1+1, i=1,…,K1 with l0=0 5: while  ∑i=1K1Di<p  do 6: find the smallest Si0=mini{Si} and add the node li0-1+|Di0|+1 to the node set D i 0: Di0←Di0∪{li0-1+|Di0|+1} 7: update Si0=Si0+[ξ(i0)]li0-1+|Di0|+1 8: end while 9: return  DO=⋃i=1K1Di, mini=1,…,K1ξ(i)ΤDii1


## 3.1. Network Has a Spanning Tree

Suppose thatG has a spanning tree and L is the Laplacian matrix. By the Gerschgorin theorem [22] and the Perron-Frobenius theorem [23], we have that 0 is the smallest eigenvalue of L and its associated left eigenvector, denoted by ξ, is nonnegative or nonpositive. With loss of generality, we assume that ∑i=1m[ξ]i=1 and [ξ]i≥0 holds for ∀i. Moreover, it can be seen that 1 is the right eigenvector of L corresponding to eigenvalue 0. By the perturbation theory [24, 25], the smallest eigenvalue of L+κD has the form (5)λ1L+κD=0+κ·λ1D+κ2·λ2D+oκ2and its associated right eigenvector, denoted by η1(L+κD), satisfies(6)η1L+κD=1+κ·η1D+κ2·η2D+oκ2as κ→0, where o(s) denotes terms that satisfy lims→0|o(s)|/s=0. By (L+κD)·η1(L+κD)=λ1(L+κD)·η1(L+κD), we have (7)L1+κD1+Lη1D+κ2Dη1D+Lη2D+oκ2=κλ1D1+κ2λ1Dη1D+λ2D1+oκ2which leads to(8)D1+Lη1D=λ1D1,(9)Dη1D+Lη2D=λ1Dη1D+λ2D1.Multiplying the vector ξ⊤ from left to (8) on both sides leads to(10)ξ⊤D1=λ1Dξ⊤1since ξ⊤L=0⊤. Then we have that(11)λ1D=ξ⊤D1ξ⊤1=ξ⊤D1=∑i=1mξidi.Suppose that p is the number of feedback controllers and j1,…,jm is a permutation of 1,…,m such that [ξ]j1≥[ξ]j2≥⋯≥[ξ]jm. Then we get (12)λ1D=∑i=1mξidi≤∑k=1pξjkand the equality sign holds if D={j1,…,jp}. Let D0={j1,…,jp}. Apparently, if [ξ]jp>[ξ]jp+1, D0 is the unique set that maximizes λ(1)(D). However, if [ξ]jp=[ξ]jp+1, the set D1={j1,…,jp-1,jp+1} also maximizes λ(1)(D). Now we need to compare D0 with other sets that also maximize λ(1)(D) and find the unqiue one that maximizes Reλ(2)(D).Analogously, multiplying the vectorξ⊤ from left to (9) on both sides and employing the equalities ξ⊤L=0⊤,ξ⊤1=1, we get(13)λ2D=ξ⊤D-λ1Dξ⊤η1D.Next, we need to compute η(1)(D). Suppose that J=Q-1LQ is a Jordan form matrix of L with Q=[1,Q^] and J=diag{J1,J2,…,JK}, where Jk is a Jordan block, k=1,…,K. Notice that 0 is a simple eigenvalue of L; we get that J1=0 and J2,…,JK are nonsingular. Let Q-1=[ξ,P^⊤]⊤ and J=diag{0,J^}. It can be derived from (8) that(14)η1D=a1-Q^J^-1P^D1where a∈C is some constant number. Substituting (14) into (13), we get (15)λ2D=-ξ⊤DQ^J^-1P^D1.Now we have the following result.Theorem 2.
Suppose thatL has a spanning tree, ξ∈Rm with ∑i=1m[ξ]i=1 is the left eigenvector of L associated with eigenvalue 0, and p is the number of pinned nodes. Let j1,…,jm be a permutation of 1,…,m such that [ξ]j1≥⋯≥[ξ]jm. (1)
If[ξ]jp>[ξ]jp+1, (16)maxD:D=p⁡Reλ1L+κD=κ·maxD:D=p⁡λ1D+oκ=κ·∑k=1pξjk+oκasκ→0, and the maximum is reached when D={j1,…,jp} and it is the unique set that maximizes λ(1)D.(2)
If[ξ]jp=[ξ]jp+1, let (17)P=D:D=p,∑i∈Dξi=∑k=1pξjk.Then(18)maxD:D=p⁡Reλ1L+κD=κ·maxD:D=p⁡λ1D+κ·Reλ2D+oκ2=κ·∑k=1pξjk+κ2·maxD:D∈P⁡Re-ξ⊤DQ^J^-1P^D1+oκ2asκ→0, where J=Q-1LQ is a Jordan form matrix of L with Q=[1,Q^], P^=[0,Im-1]Q-1, and J^=[0,Im-1]J[0,Im-1]⊤.Remark 3.
Theorem2 indicates that the magnitude of elements in the left eigenvector corresponding to eigenvalue 0 of the Laplacian matrix can be used to measure pinned nodes’ effect on the convergence rate of the system as κ→0.


## 3.2. Network without Spanning Trees

Without loss of generality, we suppose thatL has the following form [26]: (19)L=L11⋯00⋯0⋮⋱⋮⋮⋯⋮0⋯LK1K10⋯0LK1+1,1⋯LK1+1,K1LK1+1,K1+1⋯LK1+1,K1+K2⋮⋱⋮⋮⋱⋮LK1+K2,1⋯LK1+K2,K1LK1+K2,K1+1⋯LK1+K2,K1+K2Here, each Lii∈Rli,li,i=1,…,K1 is a Laplacian matrix and its corresponding subgraph has a spanning tree (isolated node can be seen as a subgraph that has a spanning tree with itself being the root). In [26], the subgraphs corresponding to Lii,i=1,…,K1, were called primary layer subgraphs and an algorithm was given to extract them. Denote by ξ(i) the left eigenvector of Lii,i=1,…,K1, corresponding to 0 and ∑j[ξ(i)]j=1. Without loss of generality, we assume that [ξ(i)]1≥⋯≥[ξ(i)]li; otherwise, we can permutate the indices of nodes of the graph topology to get the above ordering.Meanwhile,∀i∈{K1+1,…,K1+K2}, the subgraph corresponding to Lii has a spanning tree and there exists j≠i such that Lij≠0. Denote (20)L^=LK1+1,K1+1⋯LK1+1,K1+K2⋮⋱⋮LK1+K2,K1+1⋯LK1+K2,K1+K2.By Gershgorin circle theorem [22], we get that all eigenvalues of L^ have positive real parts. Therefore, 0 is the smallest eigenvalue of L and has K1 different associated eigenvectors. Denote by {ηi,i=1,…,K1} and {ξi,i=1,…,K1} the right and left eigenspaces of L corresponding to eigenvalue 0. Suppose that(21)ηi=0l1+⋯+li-1⊤,1li⊤,0li+1+⋯,lK1⊤,#⊤,(22)ξi=0l1+⋯+li-1⊤,ξi⊤,0m-l1-⋯-lK1⊤⊤,i=1,…,K1.Denote byλ~iκ,D,i=1,…,K1, the K1 smallest eigenvalues of L+κD and by η~i(κ,D),i=1,…,K1, the associated right eigenvectors. For any fixed D, we regard λ~i(κ,D) and η~i(κ,D) as functions of κ with λ~i(0,D)=0,η~i(0,D)=ηi,i=1,…,K1. By a perturbation expansion [24, 25], we have(23)λ~iκ,D=0+κλi1+oκ,i=1,…,K1(24)η~iκ,D=ηi+κηi1+oκ,i=1,…,K1as κ→0. Then by(25)L+κD·ηi+κηi1+oκ=κλi1+oκ·ηi+κηi1+oκ,we have(26)Lηi1+Dηi=λi1ηi.Multiplyinig the vector ξi⊤ from left to the above equation, we have(27)ξi⊤Dηi=λi1ξi⊤ηisince ξi⊤L=0. According to the partition of L, we divide D as follows:(28)D=diagD11,…,DK1+K2,K1+K2,whereDii∈Rli,li,∀i.Then by (21), (22), and ξ(i)⊤·1=1, we have (29)λi1=ξi⊤Dηiξi⊤ηi=ξi⊤Dii1,i=1,…,K1.Substituting λi(1) into (23) gives(30)λ~iκ,D=κ·ξi⊤Dii1+oκ,i=1,…,K1.Apparently, the smallest eigenvalue λ1(L+κD) lies in λ~i(κ,D), i=1,…,K1. Hence, the optimal pinned node set can maximize (31)Reλ1L+κD=mini⁡Reλ~iκ,D=κ·mini⁡ξi⊤Dii1+oκ.Then we have the following result.Theorem 4.
Suppose thatL has the form in (19), ξ(i) is the left eigenvector of Lii corresponding to 0 with ∑jξij=1,i=1,…,K1, and p is the number of pinned nodes. Then (32)maxD:D=p⁡Reλ1L+κD=κ·maxD:D=p⁡mini=1,…,K1⁡ξi⊤Dii1+oκas κ→0, where D has the form in (28).Lemma1 implies that, to stabilize system (3), the pinned node set D should contain at least one root of every subgraph G(Lii),i=1,…,K1. Then we have the following lemma.Lemma 5.
Suppose thatL has the form in (19). Then maxD:|D|=p⁡mini=1,…,K1⁡ξ(i)⊤Dii1 is positive if and only if the number of pinned nodes satisfies p≥K1.Remark 6.
Assume that[ξ(i)]1≥⋯≥[ξ(i)]li,i=1,…,K1. If [ξ(i)]1>[ξ(i)]2 holds ∀i, then the optimal pinned node set should contain nodes 1,l1+1,l1+l2+1,…,∑k=1K1-1lk+1.In this section, we focus on the first-order approximation ofλ1(L+κD) and search for the pinned node set that maximizes the first-order term of the approximation.Remark 7.
Notice that the pinned node set that maximizesmini=1,…,K1⁡ξ(i)⊤Dii1 may not be unique; one may need to do the second-order approximation of λ1(L+κD) to find the optimal pinned node set. Specifically, among the sets that maximize mini=1,…,K1ξ(i)⊤Dii1, find the one that maximizes λ(2)(D), which is the second-order term of the approximation.Note that whenp>∑i=1Kli, all nodes in the primary layer subgraphs should be pinned to maximize mini=1,…,Kξ(i)⊤Dii1. But the selection of the rest of pinned nodes leads to a different optimization problem. Therefore, in this section, we focus on the case p≤∑i=1Kli. The investigation of the case p>∑i=1Kli is left as an open problem for future research.In this section, we need to solve the optimization problem:(33)maxD:D=p⁡mini=1,…,K1⁡ξi⊤Dii1.Based on the above theoretical analysis, Algorithm1 is presented to search for the pinned node set DO of cardinality p (p≥K1) that maximizes mini=1,…,K1ξ(i)⊤Dii1 when κ≪1.Algorithm 1:Searching for the pinned node set DO that maximizes mini=1,…,K1⁡ξ(i)ΤDii1.
Input: the Laplacian matrix L, the pinning strength κ, the number of pinned nodes p Output: the pinned node set DO; mini=1,…,K1ξ(i)ΤDii1 1: permute the indices of the nodes of graph G to transform L into the form (19) 2: compute the left eigenvectors ξ(i) of Lii,i=1,…,K1 corresponding to 0 and normalize them with 1-norm 3: permute the indices of the nodes in the subgraphs GLii to get [ξ(i)]1≥⋯≥[ξ(i)]li, i = 1 , … , K 1 4: initialize Di={li-1+1} and Si=ξili-1+1, i=1,…,K1 with l0=0 5: while  ∑i=1K1Di<p  do 6: find the smallest Si0=mini{Si} and add the node li0-1+|Di0|+1 to the node set D i 0: Di0←Di0∪{li0-1+|Di0|+1} 7: update Si0=Si0+[ξ(i0)]li0-1+|Di0|+1 8: end while 9: return  DO=⋃i=1K1Di, mini=1,…,K1ξ(i)ΤDii1


## 4. Large Pinning Strength

Now, we consider the case of very large pinning strengthκ. Let ϵ=1/κ; L+κD=κϵL+D. Notice that D is a diagonal matrix with diagonal elements being 0 or 1. Hence, D has eigenvalues 0 and 1, and the smallest eigenvalue (in real part) of ϵL+D is a perturbation near zero eigenvalues of D in terms of ϵ. Let u be a right eigenvector of D corresponding to 0 and let λ(ϵ) and η(ϵ) be the perturbed eigenvalue and the associated right eigenvector of ϵL+D with λ(0)=0,η(0)=u. By a perturbation expansion, we have (34)λϵ=ϵλ1+oϵηϵ=u+ϵη1+oϵand(35)ϵL+D·u+ϵη1+oϵ=ϵλ1+oϵ·u+ϵη1+oϵas ϵ→0. By comparing the coefficients of ϵ in (35), we have(36)Lu+Dη1=λ1uas ϵ→0. Suppose that P is the permutation matrix such that(37)P⊤DP=ID0.By Du=0, we have 0=P⊤Du=P⊤DP·P⊤u, which implies that P⊤u=[0|D|⊤,u1⊤]⊤ for some u1∈Rm-|D|. Denote(38)P⊤LP=L11DL12DL21DL22D.Multiplying the permutation matrix P⊤ from left to (36) on both sides, we have (39)P⊤LP·P⊤u+P⊤DP·P⊤η1=λ1P⊤uas ϵ→0. Substituting (37) and (38) into the above equation, we get(40)L22D·u1=λ1·u1as ϵ→0, which implies that λ(1) is an eigenvalue of L22D as ϵ→0. Then we get that the smallest eigenvalue of ϵL+D satisfies (41)λ1ϵL+D=ϵ·λ1L22D+oϵas ϵ→0. Multiplying κ=1/ϵ on both sides of the above inequality yields (42)λ1L+κD=λ1L22D+o1as κ→+∞, where o(1) denotes terms that satisfy limκ→∞o(1)=0. In other words, in the limit of large pinning strength, the real part of λ1L22D, which is used to measure the stabilizability of the pinned network in [10], gives the lower bounds of the convergence rate of the pinned network.Hence, we have the following result.Theorem 8.
Suppose thatp is the number of pinned nodes. Then(43)maxD:D=p⁡Reλ1L+κD=maxD:D=p⁡Reλ1L22D+o1holds as κ→+∞, where L22D satisfies (38) and λ1L22D denotes the eigenvalue of L22D with the smallest real part.Remark 9.
For pinning synchronization problem of linearly coupled complex networks, the smallest eigenvalue ofL+κD also plays a dominate role in the stability analysis [10, 11]. Therefore, our theoretical results can be generalized to pinning synchronization problem.Remark 10.
In [25], the stability of multiagent systems with transimission and pinning delays was studied. The dominant eigenvalue was estimated in the limit of small and large pinning strengths, when the underlying graph was strongly connected. From our analysis and [25], one can reveal the dependence of the dominant eigenvalue on the pinned node set and generalize Theorems 2, 4, and 8 to time-delayed systems in [25].Inspired by [27, 28], we employ generic algorithm to solve the optimization problem (43) and search for the optimal node set. The algorithm contains mutation, crossover, and selection operations. Firstly, after initializing the population size and individual vectors, mutation operation is employed to generate a mutation vector associated with each individual. Mutation is applied to the current best individual vector and realized by randomly picking elements with probability 0.5 and replacing them by other randomly selected elements. Secondly, crossover is realized by randomly picking elements from each individual and its mutation vector to generate a new trial vector. At last, fitness of the generated trial vector is calculated and compared to that of its associated individual vector. Choose the vector with better fitness to be the individual vector of the next generation. At each generation, its best individual vector is the one with best fitness value. Here the fitness is defined by Reλ1L22D.The specific algorithm is presented in Algorithm2.Algorithm 2:Searching for the pinned node set DO that maximizes Reλ1L22D.
Input: the Laplacian matrix L, the pinning strength κ, the cardinality of pinned node set p, the generation number G0, the population size NP Output: the pinned node set DO, Reλ1L22DO 1: initialize G=0 and individuals Qi,G=[Qi,G1,…,Qi,Gp], i=1,…,NP as p∗1 vectors by randomly choosing p integers from {1…,m}, where m is the network size 2: for  G=1:G0  do 3: mutation step: generate a mutated vector Vi,G for each individual i, i=1,…,NP 4: crossover step: generate a trial vector Ui,G for each individual i, i=1,…,NP 5: selection step: Let Qi,G+1=Ui,G if Reλ1L22Ui,G>Reλ1L22Qi,G, otherwise Qi,G+1=Qi,G, i = 1 , … , N P. 6: end for 7: set i0=argmaxi=1,…,NP⁡Reλ1L22Qi,G0 8: return  DO={Qi0G0j,j=1…,p}, Reλ1L22DO


## 5. Numerical examples

In this section, we compare the proposed pinning strategies with the following ones: (i) pinning nodes with highest outdegrees, (ii) pinning nodes with highest hub centraility, and (iii) randomly selecting nodes to be pinned.In the following, the left eigenvector index algorithm applies the strategy of pinning nodes with the largest magnitude of elements in the left eigenvector corresponding to 0 of the Laplacian matrix.Denote byER(n,p1) an Erdös-Rényi random network with n nodes and linking probability p1. For each added linking, its direction is randomly chosen. Denote by BA(n,m,n0) a weighted Barabási-Albert scale-free network of n nodes. The network begins with a complete connected network of n0 nodes and m new edges are added at each time step. Inspired by the method to generate the asymmetry of the coupling matrix in [29], here we let lij=1 for i>j and lji=2 for i<j in BA networks if there is a linking between i and j. In this section, pinning consensus is measured by the variance(44)Errt=∑i=1mxit-s.


### 5.1. Strongly Connected Networks

Figures1(a) and 1(b) plot the dynamics of Err(t) under different pinning algorithms. The numerical result shows a good agreement with our theoretical result that, in the case of sufficiently small pinning strength, the left eigenvector corresponding to eigenvalue 0 of the Laplacian matrix measures the importance of nodes best in comparison to other centrality algorithms.Figure 1
Dynamics ofErr(t) with different pinning algorithms. The left eigenvector index algorithm applies the strategy of pinning nodes associated with the largest elements in the left eigenvector corresponding to 0 of the Laplacian matrix. The pinned node number is fixed to be 3. Averaged over 50 times.
(a)
G 1 = E R 100,0.3 ,   κ = 0.1 (b)
G 2 = B A 100,10,1 ,   κ = 0.1 (c)
G 1 = E R 100,0.3 ,   κ = 100 (d)
G 2 = B A 100,10,1 ,   κ = 100Next, in order to verify the effectiveness of Algorithm2, Figures 1(c) and 1(d) plot the dynamics of Err(t) under different pinning algorithms in the case κ=100. The simulation result shows that Algorithm 2 performs best as compared to random pinning algorithm and other pinning algorithms based on centrality measures.To illustrate the effectiveness of our algorithm in real-word networks, we use Epinions dataset gathered from Stanford Large Network Dataset Collection (http://snap.stanford.edu/data/soc-Epinions1.html). Epinions.com is a general consumer review site and its members can decide whether to trust each other based upon their reviews. The members and their trust relationship specify a real-world trust network with 75879 nodes and 508837 edges. Since Epinions social network is not strongly connected, here we consider its subnetwork corresponding to the largest strongly connected component, which contains 32223 nodes and 443506 edges. In this example, p=1000 nodes are selected to be pinned. Figures 2(a) and 2(b) plot the dynamics of Err(t) under different pinning algorithms with pinning strength κ=0.1 and κ=100, respectively, which shows a good agreement with our theoretical result.Figure 2
Dynamics ofErr(t) with different pinning algorithms. The pinned node number is 1000.
(a)
Epinions social network,κ=0.1 (b)
Epinions social network,κ=100


### 5.2. Disconnected Networks

We firstly construct a disconnected networkER(n1,n2,p1,p2) by integrating two mutually independent ER random networks ER(n1,p1) and ER(n2,p2) into a larger one. Each ER random network is a strongly connected component of ER(n1,n2,p1,p2), and there is no linking between these two components. Similary, BA(n1,n2,m1,m2,n01,n02) represents a disconnected network that contains two mutually independent BA networks BA(n1,m1,n01) and BA(n2,m2,n02). We verify the effectiveness of Algorithms 1 and 2 by comparing them with other pinning algorithms. Figure 3 plots the dynamics of Err(t), which shows that the pinned node set obtained from Algorithms 1 or 2 performs best, as compared to other pinning algorithms.Figure 3
Dynamics ofErr(t) with different pinning algorithms. The pinned node number is fixed to be 5. Averaged over 20 times.
(a)
G 3 = E R 100,100,0.3,0.3 ,   κ = 0.1 (b)
G 3 = E R 100,100,0.3,0.3 ,   κ = 100Next, we consider the Enron email dataset collected from 1998 to 2002 and adopt the dataset downloaded fromhttp://www.cis.jhu.edu/~parky/Enron/, which considers 184 users by counting the number of unique addresses. Let Eij be the number of mails sent from user i to user j and let Cij be the number of mails cc-ed or bcc-ed to j from i. Define the weight of the edge from i to j as(45)aij=Eij+0.5∗Cij25.And remove the users who have no linkings with other users. Then we get a network with 136 nodes and 472 edges, denoted by G5. The pinned node number is 6 in this simulation.By the primary layer detection algorithm in [26], we find that there are 4 primary layer subgraphs in G5. Denote the root set of these 4 primary layer subgraphs by Si,i=1,2,3,4. As pointed out in Lemma 1, at least one root in every primary layer subgraph should be pinned to reach consensus. Therefore, in outdegree (or hub) centrality pinning algorithm, node with largest outdegree (or hub) centrality in each Si,i=1,…,4, is pinned, and 2 other nodes with highest outdegree (or hub) centrality are pinned. In random algorithm, one node in each Si,i=1,…,4, is randomly pinned, and the rest 2 nodes are pinned randomly in the network. Figure 4 plots the dynamics of Err(t), which shows that the pinned node set obtained from Algorithms 1 or 2 performs best, as compared to other pinning algorithms.Figure 4
Dynamics ofErr(t) with different pinning algorithms. The pinned node number is fixed to be 6.
(a)
Enron email network,κ=0.1 (b)
Enron email network,κ=100To further reveal the performance of different algorithms, Figures5 and 6 plot the value of Reλ1(L+κD) with respect to the pinning fraction and the pinning strength.Figure 5
Variation ofReλ1(L+κD) with respect to pinning fraction.
(a)
G 1 = E R 100,0.3 ,   κ = 0.1 (b)
G 1 = E R 100,0.3 ,   κ = 100 (c)
G 3 = E R 100,100,0.2,0.2 ,   κ = 0.1 (d)
G 3 = E R 100,100,0.2,0.2 ,   κ = 100Figure 6
Variation ofReλ1(L+κD) with respect to pinning strength. The solid red curve represents Algorithm 2, the dotted blue curve represents the outdegree centrality algorithm, the dashed green curve represents the hub centrality algorithm, and the dashed purple curve represents random algorithm. In (a), (b), and (c), the solid black curve represents the left eigenvector index pinning algorithm, whereas in (d), (e), and (f), it represents Algorithm 1.
(a)
G 1 = E R 100,0.1 ,   p = 5 (b)
G 2 = B A 100,10,1 ,   p = 5 (c)
Epinions social network,p=2000 (d)
G 3 = E R 100,100,0.2,0.2 ,   p = 5 (e)
G 4 = B A 100,100,10,10,1 , 1 ,   p = 5 (f)
Enron email network,p=5It can be seen from Figure6 that, even for the case of medium pinning strength, our algorithms perform dominantly better than the existing methods.


## 5.1. Strongly Connected Networks

Figures1(a) and 1(b) plot the dynamics of Err(t) under different pinning algorithms. The numerical result shows a good agreement with our theoretical result that, in the case of sufficiently small pinning strength, the left eigenvector corresponding to eigenvalue 0 of the Laplacian matrix measures the importance of nodes best in comparison to other centrality algorithms.Figure 1
Dynamics ofErr(t) with different pinning algorithms. The left eigenvector index algorithm applies the strategy of pinning nodes associated with the largest elements in the left eigenvector corresponding to 0 of the Laplacian matrix. The pinned node number is fixed to be 3. Averaged over 50 times.
(a)
G 1 = E R 100,0.3 ,   κ = 0.1 (b)
G 2 = B A 100,10,1 ,   κ = 0.1 (c)
G 1 = E R 100,0.3 ,   κ = 100 (d)
G 2 = B A 100,10,1 ,   κ = 100Next, in order to verify the effectiveness of Algorithm2, Figures 1(c) and 1(d) plot the dynamics of Err(t) under different pinning algorithms in the case κ=100. The simulation result shows that Algorithm 2 performs best as compared to random pinning algorithm and other pinning algorithms based on centrality measures.To illustrate the effectiveness of our algorithm in real-word networks, we use Epinions dataset gathered from Stanford Large Network Dataset Collection (http://snap.stanford.edu/data/soc-Epinions1.html). Epinions.com is a general consumer review site and its members can decide whether to trust each other based upon their reviews. The members and their trust relationship specify a real-world trust network with 75879 nodes and 508837 edges. Since Epinions social network is not strongly connected, here we consider its subnetwork corresponding to the largest strongly connected component, which contains 32223 nodes and 443506 edges. In this example, p=1000 nodes are selected to be pinned. Figures 2(a) and 2(b) plot the dynamics of Err(t) under different pinning algorithms with pinning strength κ=0.1 and κ=100, respectively, which shows a good agreement with our theoretical result.Figure 2
Dynamics ofErr(t) with different pinning algorithms. The pinned node number is 1000.
(a)
Epinions social network,κ=0.1 (b)
Epinions social network,κ=100


## 5.2. Disconnected Networks

We firstly construct a disconnected networkER(n1,n2,p1,p2) by integrating two mutually independent ER random networks ER(n1,p1) and ER(n2,p2) into a larger one. Each ER random network is a strongly connected component of ER(n1,n2,p1,p2), and there is no linking between these two components. Similary, BA(n1,n2,m1,m2,n01,n02) represents a disconnected network that contains two mutually independent BA networks BA(n1,m1,n01) and BA(n2,m2,n02). We verify the effectiveness of Algorithms 1 and 2 by comparing them with other pinning algorithms. Figure 3 plots the dynamics of Err(t), which shows that the pinned node set obtained from Algorithms 1 or 2 performs best, as compared to other pinning algorithms.Figure 3
Dynamics ofErr(t) with different pinning algorithms. The pinned node number is fixed to be 5. Averaged over 20 times.
(a)
G 3 = E R 100,100,0.3,0.3 ,   κ = 0.1 (b)
G 3 = E R 100,100,0.3,0.3 ,   κ = 100Next, we consider the Enron email dataset collected from 1998 to 2002 and adopt the dataset downloaded fromhttp://www.cis.jhu.edu/~parky/Enron/, which considers 184 users by counting the number of unique addresses. Let Eij be the number of mails sent from user i to user j and let Cij be the number of mails cc-ed or bcc-ed to j from i. Define the weight of the edge from i to j as(45)aij=Eij+0.5∗Cij25.And remove the users who have no linkings with other users. Then we get a network with 136 nodes and 472 edges, denoted by G5. The pinned node number is 6 in this simulation.By the primary layer detection algorithm in [26], we find that there are 4 primary layer subgraphs in G5. Denote the root set of these 4 primary layer subgraphs by Si,i=1,2,3,4. As pointed out in Lemma 1, at least one root in every primary layer subgraph should be pinned to reach consensus. Therefore, in outdegree (or hub) centrality pinning algorithm, node with largest outdegree (or hub) centrality in each Si,i=1,…,4, is pinned, and 2 other nodes with highest outdegree (or hub) centrality are pinned. In random algorithm, one node in each Si,i=1,…,4, is randomly pinned, and the rest 2 nodes are pinned randomly in the network. Figure 4 plots the dynamics of Err(t), which shows that the pinned node set obtained from Algorithms 1 or 2 performs best, as compared to other pinning algorithms.Figure 4
Dynamics ofErr(t) with different pinning algorithms. The pinned node number is fixed to be 6.
(a)
Enron email network,κ=0.1 (b)
Enron email network,κ=100To further reveal the performance of different algorithms, Figures5 and 6 plot the value of Reλ1(L+κD) with respect to the pinning fraction and the pinning strength.Figure 5
Variation ofReλ1(L+κD) with respect to pinning fraction.
(a)
G 1 = E R 100,0.3 ,   κ = 0.1 (b)
G 1 = E R 100,0.3 ,   κ = 100 (c)
G 3 = E R 100,100,0.2,0.2 ,   κ = 0.1 (d)
G 3 = E R 100,100,0.2,0.2 ,   κ = 100Figure 6
Variation ofReλ1(L+κD) with respect to pinning strength. The solid red curve represents Algorithm 2, the dotted blue curve represents the outdegree centrality algorithm, the dashed green curve represents the hub centrality algorithm, and the dashed purple curve represents random algorithm. In (a), (b), and (c), the solid black curve represents the left eigenvector index pinning algorithm, whereas in (d), (e), and (f), it represents Algorithm 1.
(a)
G 1 = E R 100,0.1 ,   p = 5 (b)
G 2 = B A 100,10,1 ,   p = 5 (c)
Epinions social network,p=2000 (d)
G 3 = E R 100,100,0.2,0.2 ,   p = 5 (e)
G 4 = B A 100,100,10,10,1 , 1 ,   p = 5 (f)
Enron email network,p=5It can be seen from Figure6 that, even for the case of medium pinning strength, our algorithms perform dominantly better than the existing methods.


## 6. Conclusion

We have discussed how to choose pinned node set to maximize the convergence rate of multiagent systems with digraph topologies in cases of sufficiently small and large pinning strength. We prove that when the pinning strength is sufficiently small, the left eigenvector(s) associated with eigenvalue 0 of the Laplacian matrix can be used to select the optimal pinned node set. In the case of sufficiently large pinning strength, nodes that increase the smallest eigenvalue of the Laplacian submatrix associated with unpinned nodes maximally should be pinned. Numerical simulations are given to illustrate the effectiveness of our theoretical results.There are several interesting problems for future research. First, our study mainly focuses on the cases where the pinning strength is very small or very large. The extreme assumption is necessary for employing the perturbation approach to estimate the dominant eigenvalue of the pinned system. Nevertheless, it is important to study the optimization problem for the case of medium pinning strength, which is left as an open problem for future research. Second, for networks without spanning trees, we mainly consider the first-order approximation of the smallest eigenvalue of the perturbed Laplacian matrix and search for the pinned node set that maximizes the first-order term in the approximation. Sometimes, however, the set that maximizes the first-order term is not unique. Therefore, it is a significant future work to study the second-order approximation to obtain the optimal pinned node set. Third, it is interesting to extend our theoretical results to more general systems, for example, systems with time-varying delays and dynamical topology. However, this will make the analysis difficult because the dominant eigenvalue becomes time-dependent. Fourth, the present study does not consider the cost of applying feedback controllers. It is an interesting future work to study the optimization problem while considering the control cost.



---

*Source: 4096981-2019-01-10.xml*