# Controllability of Weighted and Directed Networks with Nonidentical Node Dynamics

Authors: Linying Xiang; Jonathan J. H. Zhu; Fei Chen; Guanrong Chen
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The concept of controllability from control theory is applied to weighted and directed networks with heterogenous linear or linearized node dynamics subject to exogenous inputs, where the nodes are grouped into leaders and followers. Under this framework, the controllability of the controlled network can be decomposed into two independent problems: the controllability of the isolated leader subsystem and the controllability of the extended follower subsystem. Some necessary and/or sufficient conditions for the controllability of the leader-follower network are derived based on matrix theory and graph theory. In particular, it is shown that a single-leader network is controllable if it is a directed path or cycle, but it is uncontrollable for a complete digraph or a star digraph in general. Furthermore, some approaches to improving the controllability of a heterogenous network are presented. Some simulation examples are given for illustration and verification.


---

## Body

## 1. Introduction

Recent technological advances have stimulated broad interests in the notion of network controllability [1–12], which captures the ability to control aggregated dynamics of a networked system and guide it to a desired state by using limited external inputs [13, 14]. In most real dynamical networks, the nodes might have different dynamics. For example, the generators of a power network have different physical parameters and are certainly different from motors, which together form a heterogenous network with nonidentical node dynamics. Therefore, it is of both theoretical and practical importance to study the controllability of networked systems with nonidentical node dynamics, which can help develop a better understanding of the interplay between the complexity of the overall network topology and the collective dynamics of a networked system.The controllability problem for aleader-follower multiagent system was proposed by Tanner [1], who formulated it as the classical controllability of a single-input linear system and then derived a necessary and sufficient algebraic condition in terms of the eigenvalues and eigenvectors of a submatrix of the graph’s Laplacian matrix. Ji et al. [2] then gave a sufficient condition for multileader controllability based on the algebraic characteristics of a submatrix of the incidence matrix. Subsequently, Rahmani and Mesbahi [3, 4] discussed an intricate relationship between controllability and graph symmetry with respect to the leader and gave a sufficient condition for uncontrollability. Later, Ji et al. studied the controllability in the multileader setting via equitable partitions [5, 6]. It is worth noting that, in the above works [1–6], the interconnection graph is assumed to be connected. Ji et al. [7] introduced the concept of leader-follower connectedness and investigated the controllability of a multileader system that may not be connected. The work in [8] focused on the controllability of discrete-time single-leader switching networks, which was further extended to continuous-time single-leader switching networks [9]. Additionally, some sufficient algebraic conditions were derived for a multileader system with time delays in the states, where both single and double integrator dynamics were considered [10]. Moreover, Lou and Hong [11] employed a new equitable partition, that is, weight-balanced partition, to classify interconnection graphs. Zhang et al. [12] established a bound on the controllable subspace for a given multiagent system using an almost equitable partition.On the other hand, Liu et al. [15] developed some analytical tools to study the structural controllability of large-scale weighted and directed networks and solved the minimum input problem based on Lin’s structural controllability theorem [16]. Wang et al. [17] further proposed a general approach to optimizing the structural controllability of a complex network by judiciously perturbing the network structure. Cowan et al. [18] pointed out that the main results in [15] hinge on a critical modeling assumption: the results (implicitly) require that the “default” structures of the dynamical systems at the nodes of the network have infinite time constants, which do not reflect the dynamics of real physical and biological systems. It is important to emphasize that the controllability addressed in the present paper is fundamentally different from the “structural controllability” [15–18] and “pinning controllability” [19]. In fact, structural controllability is a weaker notion than the classical controllability, whereas pinning controllability discussed in [19] is essentially “synchronizability”.To summarize, the previous works [1–15, 17, 20], except for [18], did not consider the situation where the nodes have internal dynamics. However, many real networks including social networks, power grids, food webs, regulatory networks, and neuronal networks manifest intrinsic dynamics at each living node. Additionally, all the works in [1–12, 15, 17, 18] assumed that the dimension of the state of each node is one. Although Cai and Zhong [20] studied the controllability of a swarm system with higher-dimensional agent dynamics, they did not consider the nodal intrinsic dynamics. The introduction of higher-dimensional heterogenous node dynamics makes the controllability of the entire system more complicated since, apart from the complexity of the network structure, the complexity of the dynamics of the nodes has to be considered simultaneously.The contributions of this paper are as follows. The classic concept of controllability from control theory is extended to weighted and directed complex networks with nonidentical node dynamics in a systematic way. The leader-follower structure is introduced to characterize a network where a few nodes take a leader’s role and are subject to external signals while the remaining nodes simply follow the leaders. Necessary and/or sufficient conditions on node dynamics and network topology for controllability are given in either algebraic or graph-theoretic forms. Furthermore, some approaches to improving the controllability are presented.


## 2. Notation and Preliminaries

### 2.1. Notation

Throughout the paper,ℝ(ℂ) denotes the set of real (complex) numbers and ℝm(ℂm) the space of real (complex) m-vectors. The n×n unit (zero) matrix is denoted by In(0n). 1n denotes the n-dimensional column vector of ones and 0n the column vector of zeroes. The subscript n might be omitted if it is clear from the context. AT(aT) stands for the transpose (conjugate transpose) of matrix A∈ℝn×n (vector a∈ℂ). diag{a1,…,an} denotes the n×n diagonal matrix with its diagonal elements being a1,…,an. Re(·) is the real part of a complex number and Im(·) the imaginary part. ⊗ denotes the Kronecker product.Lemma 1 (see [21]).
For real matricesA, B, C, and D with compatible dimensions, one has the following.(i)
(A+B)⊗C=A⊗C+B⊗C.(ii)
(A⊗B)(C⊗D)=(AC)⊗(BD).(iii)
(A⊗B)T=AT⊗BT.(iv)
LetA be an m×m matrix with left eigenvectors α1,…,αm corresponding to its eigenvalues λ1,…,λm, and B an n×n matrix with left eigenvectors β1,…,βn corresponding to its eigenvalues μ1,…,μn. Then, αi⊗βj are left eigenvectors of A⊗B corresponding to its eigenvalues λiμj (i=1,…,m, j=1,…,n).


### 2.2.  Graphs and Their Algebraic Representations

Aweighted digraph (or a weighted directed graph) [22] 𝒢=(𝒱,ℰ,𝒲) consists of a node set 𝒱={1,…,n}, an edge set ℰ⊂𝒱×𝒱, and a weight set 𝒲. An edge, denoted by (i,j), is an ordered pair of distinct nodes of 𝒱. (i,j)∈ℰ means that there is a direct edge from node i to node j. In this paper, simple weighted digraphs are considered. That is, self-loops and multiple edges are precluded.A sequence of edges, (vj,vj+1), j=1,…,k-1, is called a directed path and is denoted by 𝒫=v1→⋯→vk, where all the nodes v1,…,vk are distinct. Node v1 is called the beginning node and vk the end node of the path. In this case, node vk is said to be reachable from node v1. A directed cycle is a closed directed path of the form 𝒫c=v1→⋯→vk→v1, where the beginning node and end node are the same.If𝒱′⊂𝒱 and ℰ′⊂ℰ, then 𝒢′=(𝒱′,ℰ′) is called a subgraph of 𝒢=(𝒱,ℰ), written as 𝒢′⊂𝒢. In addition, if 𝒢′ contains all the edges (i,j)∈ℰ with i,j∈𝒱′, then 𝒢′ is called an induced subgraph of 𝒢. Graphs 𝒢1=(𝒱1,ℰ1) and 𝒢2=(𝒱2,ℰ2) are said to be disjoint if 𝒱1⋂𝒱2=∅.Theadjacency matrix of a weighted directed graph 𝒢, 𝒜(𝒢)∈ℝn×n is defined by [23]
(1)[𝒜(𝒢)]ij={ωij,(j,i)∈ℰ,0,otherwise,
where ωij>0 is the weight of edge (j,i).Remark 2.
An unweighted digraph (or digraph) is a weighted digraph withωij=1 for i,j=1,…,n.The graphLaplacian is defined by
(2)[ℒ(𝒢)]ij={∑j=1,j≠in‍ωij,i=j,-ωij,i≠j.
The sum of all entries in any row of ℒ(𝒢) is zero.


## 2.1. Notation

Throughout the paper,ℝ(ℂ) denotes the set of real (complex) numbers and ℝm(ℂm) the space of real (complex) m-vectors. The n×n unit (zero) matrix is denoted by In(0n). 1n denotes the n-dimensional column vector of ones and 0n the column vector of zeroes. The subscript n might be omitted if it is clear from the context. AT(aT) stands for the transpose (conjugate transpose) of matrix A∈ℝn×n (vector a∈ℂ). diag{a1,…,an} denotes the n×n diagonal matrix with its diagonal elements being a1,…,an. Re(·) is the real part of a complex number and Im(·) the imaginary part. ⊗ denotes the Kronecker product.Lemma 1 (see [21]).
For real matricesA, B, C, and D with compatible dimensions, one has the following.(i)
(A+B)⊗C=A⊗C+B⊗C.(ii)
(A⊗B)(C⊗D)=(AC)⊗(BD).(iii)
(A⊗B)T=AT⊗BT.(iv)
LetA be an m×m matrix with left eigenvectors α1,…,αm corresponding to its eigenvalues λ1,…,λm, and B an n×n matrix with left eigenvectors β1,…,βn corresponding to its eigenvalues μ1,…,μn. Then, αi⊗βj are left eigenvectors of A⊗B corresponding to its eigenvalues λiμj (i=1,…,m, j=1,…,n).


## 2.2.  Graphs and Their Algebraic Representations

Aweighted digraph (or a weighted directed graph) [22] 𝒢=(𝒱,ℰ,𝒲) consists of a node set 𝒱={1,…,n}, an edge set ℰ⊂𝒱×𝒱, and a weight set 𝒲. An edge, denoted by (i,j), is an ordered pair of distinct nodes of 𝒱. (i,j)∈ℰ means that there is a direct edge from node i to node j. In this paper, simple weighted digraphs are considered. That is, self-loops and multiple edges are precluded.A sequence of edges, (vj,vj+1), j=1,…,k-1, is called a directed path and is denoted by 𝒫=v1→⋯→vk, where all the nodes v1,…,vk are distinct. Node v1 is called the beginning node and vk the end node of the path. In this case, node vk is said to be reachable from node v1. A directed cycle is a closed directed path of the form 𝒫c=v1→⋯→vk→v1, where the beginning node and end node are the same.If𝒱′⊂𝒱 and ℰ′⊂ℰ, then 𝒢′=(𝒱′,ℰ′) is called a subgraph of 𝒢=(𝒱,ℰ), written as 𝒢′⊂𝒢. In addition, if 𝒢′ contains all the edges (i,j)∈ℰ with i,j∈𝒱′, then 𝒢′ is called an induced subgraph of 𝒢. Graphs 𝒢1=(𝒱1,ℰ1) and 𝒢2=(𝒱2,ℰ2) are said to be disjoint if 𝒱1⋂𝒱2=∅.Theadjacency matrix of a weighted directed graph 𝒢, 𝒜(𝒢)∈ℝn×n is defined by [23]
(1)[𝒜(𝒢)]ij={ωij,(j,i)∈ℰ,0,otherwise,
where ωij>0 is the weight of edge (j,i).Remark 2.
An unweighted digraph (or digraph) is a weighted digraph withωij=1 for i,j=1,…,n.The graphLaplacian is defined by
(2)[ℒ(𝒢)]ij={∑j=1,j≠in‍ωij,i=j,-ωij,i≠j.
The sum of all entries in any row of ℒ(𝒢) is zero.


## 3. Problem Description

Consider a weighted and directed networked system consisting ofn nodes with linear or linearized nonidentical dynamics, described by
(3)x˙i(t)=ciΓxi(t)+∑j=1n‍ℒijΓ(xi(t)-xj(t))+δiBui(t),i=1,…,n,
where xi∈ℝm is the state vector of the ith node, ui∈ℝp the control input of node i, and B∈ℝm×p the control input matrix. One has δi=1 if node i is subject to an exogenous control signal and δi=0 otherwise. Here, ciΓxi (ci∈ℝ and ci≠0) describes the intrinsic dynamics of node i, Γ=(γij)∈ℝm×m is a constant matrix indicating the inner-coupling between different components, and the Laplacian matrix ℒ=(ℒij)∈ℝn×n denotes the outer-coupling among the nodes, which contains all the weights of the network.Remark 3.
Network model (3) describes a generic networked system. Several models considered previously can be seen as special cases of (3). For example, in [1–7, 11, 12, 15, 17], ci=0, m=1, and Γ=B=1, in [18], m=1 and Γ=B=1, and in [20], ci=0.The nodes in the network can be divided into two different groups:leaders and followers, where external control inputs are injected only at the leaders. Denote the set of controlled nodes as the leader set, 𝒱l, and the remaining nodes as the follower set, 𝒱f. Herein, the subscripts l and f denote the leaders and followers, respectively. It follows that 𝒱l⋃‍𝒱f=𝒱 and 𝒱l⋂‍𝒱f=∅. Define the follower graph𝒢f to be the subgraph induced by 𝒱f and the leader graph𝒢l the subgraph induced by 𝒱l. Obviously, 𝒢l and 𝒢f are disjoint.Without loss of generality, one can reorganize the indices of the nodes in such a way that the firstq (1≤q<n) nodes are chosen to be controlled. That is, one can label the leaders from 1 to q and the followers from q+1 to n. The associated Laplacian matrix ℒ is thereby partitioned as
(4)ℒ=[LlLlfLflLf],
where Ll and Lf are q×q and (n-q)×(n-q) matrices, respectively. However, they generally no longer have the Laplacian matrix properties. Moreover, Lfl denotes the information flow from the leaders to the followers and Llf the flow from the followers to the leaders.DefiningX(t)=[x1T(t),…,xnT(t)]T∈ℝmn and U(t)=[u1T(t),…,uqT(t),0T,…,0T]T∈ℝpn, system (3) can be rewritten in a matrix form as
(5)X˙(t)=[(𝒞-ℒ)⊗Γ]X(t)+(Δ⊗B)U(t),
where 𝒞=diag{c1,…,cn} and Δ=diag{1,…,1︷q,0,…,0︷n-q}.Some definitions and lemmas are introduced below.Definition 4.
The system (5) is said to be controllable if, for any initial state X(0) and target state X(T) in the state space, there exists an input signal U(t) such that the driven system can be steered from X(0) to X(T) in finite time.The classical controllability theorem [24] asserts the equivalence of the following statements.Lemma 5.
Given systemx˙(t)=A0x(t)+B0u(t), where x∈ℝN, u∈ℝP, and A0 and B0 are matrices with appropriate dimensions, the following statements are equivalent.(i)
The system is completely controllable.(ii)
The controllability matrix(6)ℚ=[B0A0B0⋯A0N-1B0]
is of full row rank.(iii)
The relationshipνTA0=λνT implies νTB0≠0T, where ν is the nonzero left eigenvector of A0 corresponding to the eigenvalue λ.Conditions (ii) and (iii) in Lemma5 are referred to as the controllability rank criterion and PBH eigenvector test, respectively.


## 4. Controllability Analysis

In this section, the controllability of system (5) is analyzed in detail. Before proceeding, some definitions are given.Definition 6.
A graph𝒢 with the Laplacian matrix ℒ is said to be a controllable graph if and only if [LfLfl] is a controllable matrix pair.Definition 7.
Define the extended graph𝒢¯ as the graph with the extended Laplacian matrix
(7)ℒ¯=ℒ-𝒞=[Ll-𝒞lLlfLflLf-𝒞f],
where 𝒞l=diag{c1,…,cq} and 𝒞f=diag{cq+1,…,cn}. Moreover,
(8)Lf-𝒞f=Mℒ¯MT,Lfl=Mℒ¯N,
where M=[0(n-q)×qIn-q] and N=[Iq0q×(n-q)]T.A sufficient and necessary condition for the controllability of system (5) is now established.Theorem 8.
The system (5) is controllable if and only if the following two conditions are satisfied simultaneously:(i)
[ΓB] is a controllable matrix pair;(ii)
there exists no left eigenvector ofℒ¯ with the first q entries being all zeroes.Proof.
It follows from Lemma5(iii) that the system (5) is uncontrollable if and only if there exists a nonzero left eigenvector ν∈ℂmn of (𝒞-ℒ)⊗Γ such that νT(Δ⊗B)=0T. According to Lemma 1, there exist two nonzero vectors ν1∈ℂn and ν2∈ℂm, which are left eigenvectors of 𝒞-ℒ and Γ, respectively, such that ν=ν1⊗ν2 and (ν1T⊗ν2T)(Δ⊗B)=0T. Furthermore, one has
(9)(ν1TΔ)⊗(ν2TB)=0T.
It follows that (9) is true if and only if either(i)
ν1TΔ=0T, that is, there exists a left eigenvector of ℒ¯ with the first q elements being all zeroes, or(ii)
ν2TB=0T, that is, [ΓB] is an uncontrollable matrix pair.
The proof is thus completed.Remark 9.
By Theorem8, the controllability of system (5) is decoupled into two independent problems: one is to analyze the controllability of the isolated leader subsystem x˙=Γx+Bu, which depends only on the intrinsic dynamics of the isolated node, and the other is to identify whether there exists a left eigenvector of ℒ¯ with the first q entries being all zeroes, which is determined by 𝒢¯.


### 4.1. Controllability of the Isolated Leader Subsystem

Consider the system(10)x˙=Γx+Bu,
where Γ∈ℝm×m and B∈ℝm×p are defined in (3).In general, the controllability of system (10) can be derived by using the classic controllability rank criterion or PBH eigenvector test. In this subsection, two special cases of Γ are further discussed below, since it characterizes the inner-coupling among different components.First, consider the fully diagonal inner-couplingΓ=Im.Theorem 10.
The system (10) is controllable if and only if m≤p and rank(B)=m.Proof.
SinceΓ=Im, the controllability matrix of the pair [ΓB] is
(11)ℚ=[BΓB⋯Γm-1B]=[BB⋯B].
According to the second statement of Lemma 5, [ΓB] is controllable if and only if m≤p and rank(B)=m. The proof is thus completed.Remark 11.
From Theorem10, all the leaders’ states should be controlled in order to render the system controllable.Secondly, assumeΓ is symmetric and the sum of all entries in each row of Γ is zero.Theorem 12.
The system (10) is uncontrollable if 1mTB=0T.Proof.
SinceΓ is symmetric, for each eigenvalue, its left and right eigenvectors are the same. Additionally, the sum of all elements in any row of Γ is zero. Therefore, 0 is an eigenvalue of Γ associated with eigenvector 1m=[1,…,1]T. It follows from PBH eigenvector test that if 1mTB=0T, then [ΓB] is uncontrollable. The proof is thus completed.


### 4.2. Controllability of the Extended Graph

It follows from Theorem8 that if condition (i) of Theorem 8 is already satisfied, then the controllability of system (5) is reduced to the controllability of the extended graph 𝒢¯.Consider the system(12)x˙=(𝒞-ℒ)x,
or equivalently,
(13)[x˙lx˙f]=[𝒞l-Ll-Llf-Lfl𝒞f-Lf][xlxf],
where xl=[x1T,…,xqT]T denotes the states of the leaders and xf=[xq+1T,…,xnT]T those of the followers.From (13), the dynamics of the n-q followers can be rewritten as
(14)x˙f=(𝒞f-Lf)xf-Lflxl.Remark 13.
By Definitions6 and 7, that 𝒢¯ is controllable is equivalent to that the system (14) is controllable through xl. Therefore, the controllability of 𝒢¯ is reduced to the problem whether the leaders can drive the followers from any configuration to any other configuration in finite time. This question will be answered next. It should be emphasized that parameter ci of node i makes the controllability of 𝒢¯ more challenging than the question based on the original graph 𝒢.


#### 4.2.1. Algebraic Criteria

In this section, the controllability of𝒢¯ is discussed.Theorem 14.
𝒢
¯ is controllable if and only if there exists no left eigenvector of ℒ¯ with the first q entries being all zeroes.Proof.
This theorem reveals that𝒢¯ is uncontrollable if and only if there exists a left eigenvector of ℒ¯ with the first q entries being all zeroes.
Necessity. Let ν¯∈ℂn be a left eigenvector of ℒ¯ corresponding to the eigenvalue λ¯∈ℂ with the first q elements being zeros. From (7) and (8), one has Lf-𝒞f=Mℒ¯MT and Lfl=Mℒ¯N, where M=[0(n-q)×qIn-q] and NT=[Iq0q×(n-q)]. Since MTM=diag{0q,In-q}, it follows that MTMν¯=ν¯. From ν¯Tℒ¯=λ¯ν¯T, one has (Mν¯)T(Lf-𝒞f)=ν¯TMT(Mℒ¯MT)=λ¯(Mν¯)T and (Mν¯)TLfl=(Mν¯)TMℒ¯N=0T. Let ν=Mν¯. Then, νT(Lf-𝒞f)=λ¯νT and νTLfl=0T. According to (iii) of Lemma 5, 𝒢¯ is uncontrollable.
Sufficiency. Assume that 𝒢¯ is not controllable. By the PBH eigenvector criterion, 𝒢¯ is uncontrollable if there exist a nonzero eigenvector ν∈ℂn-q and a corresponding eigenvalue λ∈ℂ such that νT(Lf-𝒞f)=λνT and νTLfl=0T. Construct a new vector
(15)ν¯=[0ν].
Then, one has
(16)ν¯Tℒ¯=[0TνT][Ll-𝒞lLlfLflLf-𝒞f]=[νTLflνT(Lf-𝒞f)]=[0TλνT]=λν¯T.
This implies that ν¯ is a left eigenvector of ℒ¯ with the first q elements being zeros. The proof is thus completed.Theorem 15.
The system (14) is controllable if Lf-𝒞f and ℒ¯ have no common eigenvalues.Proof.
It suffices to prove that if the system is uncontrollable then there exists at least one common eigenvalue betweenLf-𝒞f and ℒ¯.
Assume that the system (14) is not controllable. From (iii) of Lemma 5, there exists a vector ν∈ℂn-q such that νT(Lf-𝒞f)=λνT for some λ∈ℂ, with νTLfl=0T. Moreover,
(17)[0TνT][Ll-𝒞lLlfLflLf-𝒞f]=[νTLflνT(Lf-𝒞f)]=λ[0TνT],
which implies that λ is also an eigenvalue of ℒ¯ with eigenvector [0TνT]T. The proof is thus completed.Note that Theorem15 is only a sufficient condition. Therefore, the system might be controllable even if Lf-𝒞f and ℒ¯ have common eigenvalues, which is different from the results for undirected graphs [5, 6]. This can be verified by a special case that there is no edge from the followers to the leaders. The following result is given for further explanation.Theorem 16.
If there is no edge from the followers to the leaders in the system (14), then Lf-𝒞f and ℒ¯ have common eigenvalues.Proof.
In this case,ℒ¯ can be rewritten as
(18)ℒ¯=[Ll-𝒞l0q×(n-q)LflLf-𝒞f].
Since Lf-𝒞f is a principal diagonal submatrix of ℒ¯, it can be described by MT(Lf-𝒞f)=ℒ¯MT, where M=[0(n-q)×qIn-q] is an (n-q)×n matrix. Let ν be the right eigenvector of Lf-𝒞f corresponding to λ. Then, one has ℒ¯(MTν)=(ℒ¯MT)ν=MT(Lf-𝒞f)ν=MT(λν)=λ(MTν). That is, MTν is the right eigenvector of ℒ¯ corresponding to the common eigenvalue λ. The proof is thus completed.


#### 4.2.2. Example 1

As shown in Figure1, node 1 is selected to be the leader and c2≠c3. It can be verified that ℒ¯ and Lf-𝒞f have two common eigenvalues 1-c2 and 1-c3, and the rank of the controllability matrix [Lfl(Lf-𝒞f)Lfl] is 2. By (ii) of Lemma 5, the graph is still controllable, although ℒ¯ and Lf-𝒞f have common eigenvalues.Figure 1
A digraph withc2≠c3.Now, consider the special case withc1=c2=⋯=cn=c.Corollary 17.
A directed path is controllable if the beginning node is selected to be the only leader.Proof.
The extended Laplacian matrix of a directed path (Figure2(a)) is given by
(19)ℒ¯=[-c00⋯0-11-c0⋯00-11-c⋯0⋮⋮⋱⋱⋮00⋯-11-c].
By direct calculation, the eigenvalues of ℒ¯ are -c and 1-c with the left eigenvectors [1,0,…,0]T and [1,-1,0,…,0]T, respectively. It follows from Theorem 14 that the graph is controllable.Illustration of network topologies.
(a)
A directed path
(b)
A directed cycleCorollary 18.
A directed cycle with a single leader is controllable.Proof.
For a directed cycle (Figure2(b)), the extended Laplacian matrix is given by
(20)ℒ¯=[1-c00⋯-1-11-c0⋯00-11-c⋯0⋮⋮⋱⋱⋮00⋯-11-c].
The real and imaginary parts of the eigenvalues λ satisfy the elliptic relationship [Re(λ)+c-1]2+[Im(λ)]2=1. However, all the eigenvalues of Lf-𝒞f are equal to 1-c. Thus, it follows from Theorem 15 that the graph is controllable.


#### 4.2.3. Graph Theoretical Criteria

So far, some sufficient and/or necessary conditions for network controllability have been derived. However, these conditions are basically algebraic, which remains elusive on the exact graphical interpretation. In fact, the study of the graph associated with a controlled system is equivalent to the study of the underlying algebraic system, which motivates us to study the controllability from a graph-theoretic perspective. It turns out that the graph-theoretic conditions are indeed more intuitive and easier to evaluate.First, some definitions are introduced.Definition 19.
A permutation matrixP∈ℝn×n is a 0-1 matrix with a single nonzero element in each row and column.Definition 20.
The system (14) is leader symmetric with respect to the leaders if there exists a nonidentity permutation matrix P such that
(21)P(Lf-𝒞f)=(Lf-𝒞f)P,PLfl=Lfl.Remark 21.
Definition20 is an extension of Definition  5.7 in [6]. The main differences are twofold.(i)
Definition  5.7 in [6] is applicable only to single-leader systems and unweighted graphs, whereas Definition 20 works also for multiple-leader systems and weighted digraphs.(ii)
Because of the nonidentical node dynamics,𝒞f must satisfy certain conditions in addition to that the original graph is leader symmetric.Some examples are given here for illustration.Example 22.
Figure3(a) shows a directed leader-follower network with 𝒱l={1} and 𝒱f={2,3,4}. It can be verified that
(22)ℒ¯=[-c1000-11-c2000-12-c3-1-1001-c4],
with
(23)Lf-𝒞f=[1-c200-12-c3-1001-c4],Lfl=[-10-1].
Assuming c2=c4, one can find a nonidentity permutation matrix
(24)P=[001010100],
satisfying (21). As a result, it is leader symmetric with respect to {1}. Likewise, the digraph of Figure 3(b) is leader symmetric about {1,2}.The digraphs that are leader symmetric: (a) with respect to node{1}, (b) with respect to nodes {1,2}.
(a)
c
2
=
c
4
(b)
c
4
=
c
5Theorem 23.
The system (14) is uncontrollable if it is leader symmetric.Proof.
If system (14) is leader symmetric, then there exists a nonidentity permutation matrix P such that P(Lf-𝒞f)=(Lf-𝒞f)P. Let λ and ν be the corresponding eigenvalue and left eigenvector of Lf-𝒞f, respectively, satisfying νT(Lf-𝒞f)=λνT. As a result, νT(Lf-𝒞f)P=λνTP=λ(PTν)T. Using (21), (PTν)T(Lf-𝒞f)=νTP(Lf-𝒞f)=νT(Lf-𝒞f)P=λ(PTν)T. This implies that PTν is also a left eigenvector of Lf-𝒞f corresponding to the eigenvalue λ. Furthermore, one has ν-PTν is also a left eigenvector of Lf-𝒞f. By (21), it follows that (ν-PTν)TLfl=νTLfl-νTPLfl=νTLfl-νTLfl=0T. This suggests that the eigenvector ν-PTν of Lf-𝒞f is orthogonal to Lfl, which does not satisfy the controllability condition in (iii) of Lemma 5. Therefore, the system (14) is uncontrollable. The proof is completed.Remark 24.
Theorem23 provides a graph-theoretic result for the uncontrollability of system (14). Note that leader symmetry is only a sufficient condition rather than a necessary one. For example, the graph shown in Figure 4 is asymmetric about the leader {1}, but it is uncontrollable.Figure 4
The digraph that is leader asymmetric with respect to node{1}: c2=c3≠c4.Consider the case ofc1=c2=⋯=cn=c. Some corollaries can be easily derived from Theorem 23.Corollary 25.
A complete digraph with a single leader is uncontrollable.Proof.
It is well known that each node in a complete digraph (Figure5(a)) has an in-degree (or out-degree) n-1. Corollary 25 is a direct consequence of Theorem 23 because of its leader symmetry.Illustration of network topologies.
(a)
A complete digraph
(b)
A star digraphCorollary 26.
A star digraph is uncontrollable with respect to the center node.Proof.
A star digraph is symmetric about the center node (Figure5(b)). If one chooses the center node as the leader, the graph is leader symmetric. It thus follows that a star digraph with the center node being the leader is uncontrollable.


## 4.1. Controllability of the Isolated Leader Subsystem

Consider the system(10)x˙=Γx+Bu,
where Γ∈ℝm×m and B∈ℝm×p are defined in (3).In general, the controllability of system (10) can be derived by using the classic controllability rank criterion or PBH eigenvector test. In this subsection, two special cases of Γ are further discussed below, since it characterizes the inner-coupling among different components.First, consider the fully diagonal inner-couplingΓ=Im.Theorem 10.
The system (10) is controllable if and only if m≤p and rank(B)=m.Proof.
SinceΓ=Im, the controllability matrix of the pair [ΓB] is
(11)ℚ=[BΓB⋯Γm-1B]=[BB⋯B].
According to the second statement of Lemma 5, [ΓB] is controllable if and only if m≤p and rank(B)=m. The proof is thus completed.Remark 11.
From Theorem10, all the leaders’ states should be controlled in order to render the system controllable.Secondly, assumeΓ is symmetric and the sum of all entries in each row of Γ is zero.Theorem 12.
The system (10) is uncontrollable if 1mTB=0T.Proof.
SinceΓ is symmetric, for each eigenvalue, its left and right eigenvectors are the same. Additionally, the sum of all elements in any row of Γ is zero. Therefore, 0 is an eigenvalue of Γ associated with eigenvector 1m=[1,…,1]T. It follows from PBH eigenvector test that if 1mTB=0T, then [ΓB] is uncontrollable. The proof is thus completed.


## 4.2. Controllability of the Extended Graph

It follows from Theorem8 that if condition (i) of Theorem 8 is already satisfied, then the controllability of system (5) is reduced to the controllability of the extended graph 𝒢¯.Consider the system(12)x˙=(𝒞-ℒ)x,
or equivalently,
(13)[x˙lx˙f]=[𝒞l-Ll-Llf-Lfl𝒞f-Lf][xlxf],
where xl=[x1T,…,xqT]T denotes the states of the leaders and xf=[xq+1T,…,xnT]T those of the followers.From (13), the dynamics of the n-q followers can be rewritten as
(14)x˙f=(𝒞f-Lf)xf-Lflxl.Remark 13.
By Definitions6 and 7, that 𝒢¯ is controllable is equivalent to that the system (14) is controllable through xl. Therefore, the controllability of 𝒢¯ is reduced to the problem whether the leaders can drive the followers from any configuration to any other configuration in finite time. This question will be answered next. It should be emphasized that parameter ci of node i makes the controllability of 𝒢¯ more challenging than the question based on the original graph 𝒢.


### 4.2.1. Algebraic Criteria

In this section, the controllability of𝒢¯ is discussed.Theorem 14.
𝒢
¯ is controllable if and only if there exists no left eigenvector of ℒ¯ with the first q entries being all zeroes.Proof.
This theorem reveals that𝒢¯ is uncontrollable if and only if there exists a left eigenvector of ℒ¯ with the first q entries being all zeroes.
Necessity. Let ν¯∈ℂn be a left eigenvector of ℒ¯ corresponding to the eigenvalue λ¯∈ℂ with the first q elements being zeros. From (7) and (8), one has Lf-𝒞f=Mℒ¯MT and Lfl=Mℒ¯N, where M=[0(n-q)×qIn-q] and NT=[Iq0q×(n-q)]. Since MTM=diag{0q,In-q}, it follows that MTMν¯=ν¯. From ν¯Tℒ¯=λ¯ν¯T, one has (Mν¯)T(Lf-𝒞f)=ν¯TMT(Mℒ¯MT)=λ¯(Mν¯)T and (Mν¯)TLfl=(Mν¯)TMℒ¯N=0T. Let ν=Mν¯. Then, νT(Lf-𝒞f)=λ¯νT and νTLfl=0T. According to (iii) of Lemma 5, 𝒢¯ is uncontrollable.
Sufficiency. Assume that 𝒢¯ is not controllable. By the PBH eigenvector criterion, 𝒢¯ is uncontrollable if there exist a nonzero eigenvector ν∈ℂn-q and a corresponding eigenvalue λ∈ℂ such that νT(Lf-𝒞f)=λνT and νTLfl=0T. Construct a new vector
(15)ν¯=[0ν].
Then, one has
(16)ν¯Tℒ¯=[0TνT][Ll-𝒞lLlfLflLf-𝒞f]=[νTLflνT(Lf-𝒞f)]=[0TλνT]=λν¯T.
This implies that ν¯ is a left eigenvector of ℒ¯ with the first q elements being zeros. The proof is thus completed.Theorem 15.
The system (14) is controllable if Lf-𝒞f and ℒ¯ have no common eigenvalues.Proof.
It suffices to prove that if the system is uncontrollable then there exists at least one common eigenvalue betweenLf-𝒞f and ℒ¯.
Assume that the system (14) is not controllable. From (iii) of Lemma 5, there exists a vector ν∈ℂn-q such that νT(Lf-𝒞f)=λνT for some λ∈ℂ, with νTLfl=0T. Moreover,
(17)[0TνT][Ll-𝒞lLlfLflLf-𝒞f]=[νTLflνT(Lf-𝒞f)]=λ[0TνT],
which implies that λ is also an eigenvalue of ℒ¯ with eigenvector [0TνT]T. The proof is thus completed.Note that Theorem15 is only a sufficient condition. Therefore, the system might be controllable even if Lf-𝒞f and ℒ¯ have common eigenvalues, which is different from the results for undirected graphs [5, 6]. This can be verified by a special case that there is no edge from the followers to the leaders. The following result is given for further explanation.Theorem 16.
If there is no edge from the followers to the leaders in the system (14), then Lf-𝒞f and ℒ¯ have common eigenvalues.Proof.
In this case,ℒ¯ can be rewritten as
(18)ℒ¯=[Ll-𝒞l0q×(n-q)LflLf-𝒞f].
Since Lf-𝒞f is a principal diagonal submatrix of ℒ¯, it can be described by MT(Lf-𝒞f)=ℒ¯MT, where M=[0(n-q)×qIn-q] is an (n-q)×n matrix. Let ν be the right eigenvector of Lf-𝒞f corresponding to λ. Then, one has ℒ¯(MTν)=(ℒ¯MT)ν=MT(Lf-𝒞f)ν=MT(λν)=λ(MTν). That is, MTν is the right eigenvector of ℒ¯ corresponding to the common eigenvalue λ. The proof is thus completed.


### 4.2.2. Example 1

As shown in Figure1, node 1 is selected to be the leader and c2≠c3. It can be verified that ℒ¯ and Lf-𝒞f have two common eigenvalues 1-c2 and 1-c3, and the rank of the controllability matrix [Lfl(Lf-𝒞f)Lfl] is 2. By (ii) of Lemma 5, the graph is still controllable, although ℒ¯ and Lf-𝒞f have common eigenvalues.Figure 1
A digraph withc2≠c3.Now, consider the special case withc1=c2=⋯=cn=c.Corollary 17.
A directed path is controllable if the beginning node is selected to be the only leader.Proof.
The extended Laplacian matrix of a directed path (Figure2(a)) is given by
(19)ℒ¯=[-c00⋯0-11-c0⋯00-11-c⋯0⋮⋮⋱⋱⋮00⋯-11-c].
By direct calculation, the eigenvalues of ℒ¯ are -c and 1-c with the left eigenvectors [1,0,…,0]T and [1,-1,0,…,0]T, respectively. It follows from Theorem 14 that the graph is controllable.Illustration of network topologies.
(a)
A directed path
(b)
A directed cycleCorollary 18.
A directed cycle with a single leader is controllable.Proof.
For a directed cycle (Figure2(b)), the extended Laplacian matrix is given by
(20)ℒ¯=[1-c00⋯-1-11-c0⋯00-11-c⋯0⋮⋮⋱⋱⋮00⋯-11-c].
The real and imaginary parts of the eigenvalues λ satisfy the elliptic relationship [Re(λ)+c-1]2+[Im(λ)]2=1. However, all the eigenvalues of Lf-𝒞f are equal to 1-c. Thus, it follows from Theorem 15 that the graph is controllable.


### 4.2.3. Graph Theoretical Criteria

So far, some sufficient and/or necessary conditions for network controllability have been derived. However, these conditions are basically algebraic, which remains elusive on the exact graphical interpretation. In fact, the study of the graph associated with a controlled system is equivalent to the study of the underlying algebraic system, which motivates us to study the controllability from a graph-theoretic perspective. It turns out that the graph-theoretic conditions are indeed more intuitive and easier to evaluate.First, some definitions are introduced.Definition 19.
A permutation matrixP∈ℝn×n is a 0-1 matrix with a single nonzero element in each row and column.Definition 20.
The system (14) is leader symmetric with respect to the leaders if there exists a nonidentity permutation matrix P such that
(21)P(Lf-𝒞f)=(Lf-𝒞f)P,PLfl=Lfl.Remark 21.
Definition20 is an extension of Definition  5.7 in [6]. The main differences are twofold.(i)
Definition  5.7 in [6] is applicable only to single-leader systems and unweighted graphs, whereas Definition 20 works also for multiple-leader systems and weighted digraphs.(ii)
Because of the nonidentical node dynamics,𝒞f must satisfy certain conditions in addition to that the original graph is leader symmetric.Some examples are given here for illustration.Example 22.
Figure3(a) shows a directed leader-follower network with 𝒱l={1} and 𝒱f={2,3,4}. It can be verified that
(22)ℒ¯=[-c1000-11-c2000-12-c3-1-1001-c4],
with
(23)Lf-𝒞f=[1-c200-12-c3-1001-c4],Lfl=[-10-1].
Assuming c2=c4, one can find a nonidentity permutation matrix
(24)P=[001010100],
satisfying (21). As a result, it is leader symmetric with respect to {1}. Likewise, the digraph of Figure 3(b) is leader symmetric about {1,2}.The digraphs that are leader symmetric: (a) with respect to node{1}, (b) with respect to nodes {1,2}.
(a)
c
2
=
c
4
(b)
c
4
=
c
5Theorem 23.
The system (14) is uncontrollable if it is leader symmetric.Proof.
If system (14) is leader symmetric, then there exists a nonidentity permutation matrix P such that P(Lf-𝒞f)=(Lf-𝒞f)P. Let λ and ν be the corresponding eigenvalue and left eigenvector of Lf-𝒞f, respectively, satisfying νT(Lf-𝒞f)=λνT. As a result, νT(Lf-𝒞f)P=λνTP=λ(PTν)T. Using (21), (PTν)T(Lf-𝒞f)=νTP(Lf-𝒞f)=νT(Lf-𝒞f)P=λ(PTν)T. This implies that PTν is also a left eigenvector of Lf-𝒞f corresponding to the eigenvalue λ. Furthermore, one has ν-PTν is also a left eigenvector of Lf-𝒞f. By (21), it follows that (ν-PTν)TLfl=νTLfl-νTPLfl=νTLfl-νTLfl=0T. This suggests that the eigenvector ν-PTν of Lf-𝒞f is orthogonal to Lfl, which does not satisfy the controllability condition in (iii) of Lemma 5. Therefore, the system (14) is uncontrollable. The proof is completed.Remark 24.
Theorem23 provides a graph-theoretic result for the uncontrollability of system (14). Note that leader symmetry is only a sufficient condition rather than a necessary one. For example, the graph shown in Figure 4 is asymmetric about the leader {1}, but it is uncontrollable.Figure 4
The digraph that is leader asymmetric with respect to node{1}: c2=c3≠c4.Consider the case ofc1=c2=⋯=cn=c. Some corollaries can be easily derived from Theorem 23.Corollary 25.
A complete digraph with a single leader is uncontrollable.Proof.
It is well known that each node in a complete digraph (Figure5(a)) has an in-degree (or out-degree) n-1. Corollary 25 is a direct consequence of Theorem 23 because of its leader symmetry.Illustration of network topologies.
(a)
A complete digraph
(b)
A star digraphCorollary 26.
A star digraph is uncontrollable with respect to the center node.Proof.
A star digraph is symmetric about the center node (Figure5(b)). If one chooses the center node as the leader, the graph is leader symmetric. It thus follows that a star digraph with the center node being the leader is uncontrollable.


## 4.2.1. Algebraic Criteria

In this section, the controllability of𝒢¯ is discussed.Theorem 14.
𝒢
¯ is controllable if and only if there exists no left eigenvector of ℒ¯ with the first q entries being all zeroes.Proof.
This theorem reveals that𝒢¯ is uncontrollable if and only if there exists a left eigenvector of ℒ¯ with the first q entries being all zeroes.
Necessity. Let ν¯∈ℂn be a left eigenvector of ℒ¯ corresponding to the eigenvalue λ¯∈ℂ with the first q elements being zeros. From (7) and (8), one has Lf-𝒞f=Mℒ¯MT and Lfl=Mℒ¯N, where M=[0(n-q)×qIn-q] and NT=[Iq0q×(n-q)]. Since MTM=diag{0q,In-q}, it follows that MTMν¯=ν¯. From ν¯Tℒ¯=λ¯ν¯T, one has (Mν¯)T(Lf-𝒞f)=ν¯TMT(Mℒ¯MT)=λ¯(Mν¯)T and (Mν¯)TLfl=(Mν¯)TMℒ¯N=0T. Let ν=Mν¯. Then, νT(Lf-𝒞f)=λ¯νT and νTLfl=0T. According to (iii) of Lemma 5, 𝒢¯ is uncontrollable.
Sufficiency. Assume that 𝒢¯ is not controllable. By the PBH eigenvector criterion, 𝒢¯ is uncontrollable if there exist a nonzero eigenvector ν∈ℂn-q and a corresponding eigenvalue λ∈ℂ such that νT(Lf-𝒞f)=λνT and νTLfl=0T. Construct a new vector
(15)ν¯=[0ν].
Then, one has
(16)ν¯Tℒ¯=[0TνT][Ll-𝒞lLlfLflLf-𝒞f]=[νTLflνT(Lf-𝒞f)]=[0TλνT]=λν¯T.
This implies that ν¯ is a left eigenvector of ℒ¯ with the first q elements being zeros. The proof is thus completed.Theorem 15.
The system (14) is controllable if Lf-𝒞f and ℒ¯ have no common eigenvalues.Proof.
It suffices to prove that if the system is uncontrollable then there exists at least one common eigenvalue betweenLf-𝒞f and ℒ¯.
Assume that the system (14) is not controllable. From (iii) of Lemma 5, there exists a vector ν∈ℂn-q such that νT(Lf-𝒞f)=λνT for some λ∈ℂ, with νTLfl=0T. Moreover,
(17)[0TνT][Ll-𝒞lLlfLflLf-𝒞f]=[νTLflνT(Lf-𝒞f)]=λ[0TνT],
which implies that λ is also an eigenvalue of ℒ¯ with eigenvector [0TνT]T. The proof is thus completed.Note that Theorem15 is only a sufficient condition. Therefore, the system might be controllable even if Lf-𝒞f and ℒ¯ have common eigenvalues, which is different from the results for undirected graphs [5, 6]. This can be verified by a special case that there is no edge from the followers to the leaders. The following result is given for further explanation.Theorem 16.
If there is no edge from the followers to the leaders in the system (14), then Lf-𝒞f and ℒ¯ have common eigenvalues.Proof.
In this case,ℒ¯ can be rewritten as
(18)ℒ¯=[Ll-𝒞l0q×(n-q)LflLf-𝒞f].
Since Lf-𝒞f is a principal diagonal submatrix of ℒ¯, it can be described by MT(Lf-𝒞f)=ℒ¯MT, where M=[0(n-q)×qIn-q] is an (n-q)×n matrix. Let ν be the right eigenvector of Lf-𝒞f corresponding to λ. Then, one has ℒ¯(MTν)=(ℒ¯MT)ν=MT(Lf-𝒞f)ν=MT(λν)=λ(MTν). That is, MTν is the right eigenvector of ℒ¯ corresponding to the common eigenvalue λ. The proof is thus completed.


## 4.2.2. Example 1

As shown in Figure1, node 1 is selected to be the leader and c2≠c3. It can be verified that ℒ¯ and Lf-𝒞f have two common eigenvalues 1-c2 and 1-c3, and the rank of the controllability matrix [Lfl(Lf-𝒞f)Lfl] is 2. By (ii) of Lemma 5, the graph is still controllable, although ℒ¯ and Lf-𝒞f have common eigenvalues.Figure 1
A digraph withc2≠c3.Now, consider the special case withc1=c2=⋯=cn=c.Corollary 17.
A directed path is controllable if the beginning node is selected to be the only leader.Proof.
The extended Laplacian matrix of a directed path (Figure2(a)) is given by
(19)ℒ¯=[-c00⋯0-11-c0⋯00-11-c⋯0⋮⋮⋱⋱⋮00⋯-11-c].
By direct calculation, the eigenvalues of ℒ¯ are -c and 1-c with the left eigenvectors [1,0,…,0]T and [1,-1,0,…,0]T, respectively. It follows from Theorem 14 that the graph is controllable.Illustration of network topologies.
(a)
A directed path
(b)
A directed cycleCorollary 18.
A directed cycle with a single leader is controllable.Proof.
For a directed cycle (Figure2(b)), the extended Laplacian matrix is given by
(20)ℒ¯=[1-c00⋯-1-11-c0⋯00-11-c⋯0⋮⋮⋱⋱⋮00⋯-11-c].
The real and imaginary parts of the eigenvalues λ satisfy the elliptic relationship [Re(λ)+c-1]2+[Im(λ)]2=1. However, all the eigenvalues of Lf-𝒞f are equal to 1-c. Thus, it follows from Theorem 15 that the graph is controllable.


## 4.2.3. Graph Theoretical Criteria

So far, some sufficient and/or necessary conditions for network controllability have been derived. However, these conditions are basically algebraic, which remains elusive on the exact graphical interpretation. In fact, the study of the graph associated with a controlled system is equivalent to the study of the underlying algebraic system, which motivates us to study the controllability from a graph-theoretic perspective. It turns out that the graph-theoretic conditions are indeed more intuitive and easier to evaluate.First, some definitions are introduced.Definition 19.
A permutation matrixP∈ℝn×n is a 0-1 matrix with a single nonzero element in each row and column.Definition 20.
The system (14) is leader symmetric with respect to the leaders if there exists a nonidentity permutation matrix P such that
(21)P(Lf-𝒞f)=(Lf-𝒞f)P,PLfl=Lfl.Remark 21.
Definition20 is an extension of Definition  5.7 in [6]. The main differences are twofold.(i)
Definition  5.7 in [6] is applicable only to single-leader systems and unweighted graphs, whereas Definition 20 works also for multiple-leader systems and weighted digraphs.(ii)
Because of the nonidentical node dynamics,𝒞f must satisfy certain conditions in addition to that the original graph is leader symmetric.Some examples are given here for illustration.Example 22.
Figure3(a) shows a directed leader-follower network with 𝒱l={1} and 𝒱f={2,3,4}. It can be verified that
(22)ℒ¯=[-c1000-11-c2000-12-c3-1-1001-c4],
with
(23)Lf-𝒞f=[1-c200-12-c3-1001-c4],Lfl=[-10-1].
Assuming c2=c4, one can find a nonidentity permutation matrix
(24)P=[001010100],
satisfying (21). As a result, it is leader symmetric with respect to {1}. Likewise, the digraph of Figure 3(b) is leader symmetric about {1,2}.The digraphs that are leader symmetric: (a) with respect to node{1}, (b) with respect to nodes {1,2}.
(a)
c
2
=
c
4
(b)
c
4
=
c
5Theorem 23.
The system (14) is uncontrollable if it is leader symmetric.Proof.
If system (14) is leader symmetric, then there exists a nonidentity permutation matrix P such that P(Lf-𝒞f)=(Lf-𝒞f)P. Let λ and ν be the corresponding eigenvalue and left eigenvector of Lf-𝒞f, respectively, satisfying νT(Lf-𝒞f)=λνT. As a result, νT(Lf-𝒞f)P=λνTP=λ(PTν)T. Using (21), (PTν)T(Lf-𝒞f)=νTP(Lf-𝒞f)=νT(Lf-𝒞f)P=λ(PTν)T. This implies that PTν is also a left eigenvector of Lf-𝒞f corresponding to the eigenvalue λ. Furthermore, one has ν-PTν is also a left eigenvector of Lf-𝒞f. By (21), it follows that (ν-PTν)TLfl=νTLfl-νTPLfl=νTLfl-νTLfl=0T. This suggests that the eigenvector ν-PTν of Lf-𝒞f is orthogonal to Lfl, which does not satisfy the controllability condition in (iii) of Lemma 5. Therefore, the system (14) is uncontrollable. The proof is completed.Remark 24.
Theorem23 provides a graph-theoretic result for the uncontrollability of system (14). Note that leader symmetry is only a sufficient condition rather than a necessary one. For example, the graph shown in Figure 4 is asymmetric about the leader {1}, but it is uncontrollable.Figure 4
The digraph that is leader asymmetric with respect to node{1}: c2=c3≠c4.Consider the case ofc1=c2=⋯=cn=c. Some corollaries can be easily derived from Theorem 23.Corollary 25.
A complete digraph with a single leader is uncontrollable.Proof.
It is well known that each node in a complete digraph (Figure5(a)) has an in-degree (or out-degree) n-1. Corollary 25 is a direct consequence of Theorem 23 because of its leader symmetry.Illustration of network topologies.
(a)
A complete digraph
(b)
A star digraphCorollary 26.
A star digraph is uncontrollable with respect to the center node.Proof.
A star digraph is symmetric about the center node (Figure5(b)). If one chooses the center node as the leader, the graph is leader symmetric. It thus follows that a star digraph with the center node being the leader is uncontrollable.


## 5. Controllability Improvement of Heterogenous Networked Systems

There exists a fundamental and yet challenging problem in the study of the controllability of complex networks: how to improve the controllability of an uncontrollable networked system? In this section, some approaches to improving the controllability are suggested.


### 5.1. Increasing the Number of Leaders

It can be verified thatleader reachable is a necessary condition for being controllable. That is, the graph is uncontrollable if there exist followers who are isolated or have no incoming edge from any leader or other follower. Therefore, the isolated nodes and the nodes without incoming edge should be first selected to be the leaders. As shown in Figure 3(a), node 1 has no incoming edge from other nodes and is thus chosen to be a leader. It follows that the graph is leader symmetric about the leader node 1 and is, therefore, uncontrollable when c2=c4. However, if node 2 or node 4 is also selected to be a leader, the leader symmetry property does not hold anymore. It follows from (ii) of Lemma 5 that the system becomes controllable. This example shows that increasing the number of leaders may improve the controllability.


### 5.2. Changing the Nodal Parameters

Nodal intrinsic dynamics is considered for the system (5). It follows that parameter ci of node i is an important quantity determining the controllability of the networked system. For example, in Figure 3(b), if c4≠c5, then the leader symmetry property is not satisfied. It follows from (ii) of Lemma 5 that the system is controllable, which implies that changing the nodal intrinsic parameters may improve the controllability.


### 5.3. Changing the Edge Weights

Note that the edge weights in the system (5) can be different, indicating that one can change the weights to possibly improve the controllability of the system. For instance, in Figure 3(b), by assigning different weights of the edges (2,4) and (2,5), the leader symmetry property is also violated so that the digraph becomes controllable.


### 5.4. Example 2

To verify the theoretical results, consider a directed and weighted network with four different nodes, as shown in Figure6. Let m=p=2, Γ=I2, and B=diag{1,2}. The local dynamics of the nodes are given by
(25)x˙1=1.5x1,x˙2=-10x2,x˙3=x3,x˙4=-2x4.Figure 6
Illustration of a network topology.Node 1 is selected to be a leader, so one has(26)ℒ=[20-1-1-1.51.5000-1.21.2000-11],Lf=[1.500-1.21.200-11].
It follows from Theorem 10 that [ΓB] is controllable. Furthermore, one can calculate the eigenvalues of Lf-𝒞f and ℒ¯, obtaining {0.2,3,11.5} and {-0.1263,0.8709,2.9681,11.4872}, respectively. By Theorem 15, the extended digraph is controllable.The evolution of the states of the network without control input is depicted in Figures7(a) and 7(b). The whole network is unstable. Design the control law u1=-10x1. Then, as shown in Figures 8(a) and 8(b), all the nodes are controlled to zeroes.The evolution of node states without control.
(a)
x
(
0
)
=
[
-
4
-
3
1
3
]
T
(b)
x
(
0
)
=
[
1
3.5
2
-
4
]
TThe evolution of node states under control.
(a)
x
(
0
)
=
[
-
4
-
3
1
3
]
T
(b)
x
(
0
)
=
[
1
3.5
2
-
4
]
T


## 5.1. Increasing the Number of Leaders

It can be verified thatleader reachable is a necessary condition for being controllable. That is, the graph is uncontrollable if there exist followers who are isolated or have no incoming edge from any leader or other follower. Therefore, the isolated nodes and the nodes without incoming edge should be first selected to be the leaders. As shown in Figure 3(a), node 1 has no incoming edge from other nodes and is thus chosen to be a leader. It follows that the graph is leader symmetric about the leader node 1 and is, therefore, uncontrollable when c2=c4. However, if node 2 or node 4 is also selected to be a leader, the leader symmetry property does not hold anymore. It follows from (ii) of Lemma 5 that the system becomes controllable. This example shows that increasing the number of leaders may improve the controllability.


## 5.2. Changing the Nodal Parameters

Nodal intrinsic dynamics is considered for the system (5). It follows that parameter ci of node i is an important quantity determining the controllability of the networked system. For example, in Figure 3(b), if c4≠c5, then the leader symmetry property is not satisfied. It follows from (ii) of Lemma 5 that the system is controllable, which implies that changing the nodal intrinsic parameters may improve the controllability.


## 5.3. Changing the Edge Weights

Note that the edge weights in the system (5) can be different, indicating that one can change the weights to possibly improve the controllability of the system. For instance, in Figure 3(b), by assigning different weights of the edges (2,4) and (2,5), the leader symmetry property is also violated so that the digraph becomes controllable.


## 5.4. Example 2

To verify the theoretical results, consider a directed and weighted network with four different nodes, as shown in Figure6. Let m=p=2, Γ=I2, and B=diag{1,2}. The local dynamics of the nodes are given by
(25)x˙1=1.5x1,x˙2=-10x2,x˙3=x3,x˙4=-2x4.Figure 6
Illustration of a network topology.Node 1 is selected to be a leader, so one has(26)ℒ=[20-1-1-1.51.5000-1.21.2000-11],Lf=[1.500-1.21.200-11].
It follows from Theorem 10 that [ΓB] is controllable. Furthermore, one can calculate the eigenvalues of Lf-𝒞f and ℒ¯, obtaining {0.2,3,11.5} and {-0.1263,0.8709,2.9681,11.4872}, respectively. By Theorem 15, the extended digraph is controllable.The evolution of the states of the network without control input is depicted in Figures7(a) and 7(b). The whole network is unstable. Design the control law u1=-10x1. Then, as shown in Figures 8(a) and 8(b), all the nodes are controlled to zeroes.The evolution of node states without control.
(a)
x
(
0
)
=
[
-
4
-
3
1
3
]
T
(b)
x
(
0
)
=
[
1
3.5
2
-
4
]
TThe evolution of node states under control.
(a)
x
(
0
)
=
[
-
4
-
3
1
3
]
T
(b)
x
(
0
)
=
[
1
3.5
2
-
4
]
T


## 6. Conclusions

In this paper, the controllability of a weighted and directed network with nonidentical node dynamics has been investigated, where the network has a leader-follower structure. The controllability of the controlled network is converted to two subproblems. The first subproblem is to analyze the controllability of the isolated leader subsystem. The second subproblem is to examine the controllability of the extended follower subgraph. A set of conditions for assessing network controllability and identifying nodes playing a key role in network controllability have been established based on matrix theory. Additionally, by using graph theory, several controllability properties have been translated into graph conditions, which are generally more intuitive and informative, therefore, easier to use for applications.It is found that the controllability of a controlled network with heterogeneous node dynamics is determined by both the node local dynamics and the graph topology including the number of leaders, the location of leaders, and the connection pattern among followers. This result is constructive since it allows for selecting leaders to render the system controllable. Under this framework, the notion of controllability of complex networks with various essentially different structures has been generalized. It has been shown that a single-leader network is controllable if it is a directed path or cycle, otherwise uncontrollable if it is a complete digraph or a star digraph. It has also been shown that the controllability of the system can be improved by increasing the number of leaders, changing the nodal local parameters, or assigning different weights to the edges.The main difference between our work and the previous works lies in the introduction of different kinetic constants for the uncoupled nodes. The results obtained here are merely the first step in the study on controllability of complex networks with heterogenous node dynamics. Future research along the same line might include the cases of noise, uncertainties, and time-varying topology. In addition, the dual property of the observability of complex networks is worthy of future investigation. The concept of “structural observability” [25] may help build up a general framework for future research on this topic.



---

*Source: 405034-2013-05-26.xml*