IEEE Circuits and Systems Magazine - Q2 2019 - 15

of leaders. This result is constructive in that it allows selecting leaders for the purpose of making a networked
multi-agent system to be state controllable.
3.2 Network Equitable Partitions
Although elegant, the conditions given in Theorem 3 are
not graph-theoretic in that the controllability could not
be directly determined based on the network topology.
Rahmani and Mesbahi [13] discussed an intricate relationship between the state controllability and the graph
symmetry, and then gave a sufficient graph-theoretic
condition for determining the uncontrollability. Subsequently, they explored the notion of leader symmetry
with respect to the graph automorphism [14].
The notion of graph symmetry is introduced as follows.
Definition 4 [14]
The system (10) is leader symmetric with respect to a
single leader if there exists a non-identical permutation
P such that
PL f = L f P.

An r- partition r of VG, with cells C 1, C 2, f, C r , is said
to be equitable if each node in C i has the same number
of neighbors in C j for all i, j. The cardinality of the partition r is denoted by r = ; r ;.
Let b ij be the number of neighbors in C j of a node in
C i . The directed graph with the cells of an equitable
r- partition r as its nodes, and with b ij edges from the i
th cell to the j th cell of r, is called the quotient of G over
r and is denoted by G/r. A trivial partition is the
N- partition, r = {{1}, {2}, f, {N}} . If an equitable partition contains at least one cell with more than one node,
it is called a nontrivial equitable partition (NEP), and the
adjacency matrix of a quotient is given by A (G/r) ij = b ij .
Example 4
In the undirected network shown in Fig. 5(a), one nontrivial equitable partition is r = {{1}, {2, 3}, {4}, {5}, {6}}. The
adjacency matrix of its quotient (see Fig. 5(b)) is given by
R0
S
S1
A (G/r) = SS0
S0
S1
T

(11)

A sufficient graph-theoretic condition for the uncontrollability is given below.
Theorem 4 [13], [14]
The multi-agent system (10) with a single leader is uncontrollable if it is leader symmetric.
Example 3
The network depicted in Fig. 4(a) is leader symmetric
with respect to {4} but asymmetric with respect to any
other leader node set (e.g., Fig. 4(b)). According to Theorem 4, the leader-follower network shown in Fig. 4(a) is
uncontrollable, which is consistent with the conclusion
given by Theorem 3.
■
Considering the case that some multi-agent systems
may require multiple leaders, Ji et al. used nontrivial
equitable partitions and interlacing theory to identify
controllable networks, generalizing some existing results to the multi-leader case [15], [16]. They provided a
more precise interpretation of the intrinsic relationship
between the controllability and the network topology.
The concept of equitable partition is rooted in the graph
symmetry with respect to a leader [13], [14].
To introduce the graph-theoretic characterization of
the controllability for multi-leader networks, some more
definitions are needed.

2
0
2
0
0

0
1
0
1
0

0
0
1
0
0

1VW
0W
0WW .
0W
0W
X

■
A necessary condition for a multi-leader networked
system to be controllable was established in [15], [16],
as follows.
Theorem 5 [15], [16]
Given a connected graph G with the induced follower
graph G f , a necessary condition for system (10) to be
state controllable is that no NEPs r and r f on G and G f ,
respectively, share a nontrivial cell.

2
1

6

4

5

3
(a)
5′

1

1′

1

2′

2

2

3′

1

4′

1
(b)

Definition 5 [15], [16]
A cell C 1 VG is a subset of the node set. A nontrivial
cell is a cell with more than one node. A partition of the
graph is a grouping of its node set into different cells.
sEcOnd QuartEr 2019

Figure 5. (a) the equitable partition r = {{1}, {2, 3}, {4}, {5}, {6}}
on a 2-leader network with the leader set {5, 6}, which are
marked in blue. (b) the quotient of the network over r.

IEEE cIrcuIts and systEms magazInE

15
IEEE Circuits and Systems Magazine - Q2 2019

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2019
