IEEE Circuits and Systems Magazine - Q2 2019 - 24

networked system (5) is state controllable if and only if
rank [sI N - A, B] = N, 6s ! C. According to the maximum
multiplicity theorem (Theorem 8), N D is determined by
the maximum geometric multiplicity n (m M ) of the eigenvalue m M . Therefore, the input matrix B used to ensure
the network controllability must satisfy the condition
that rank [m M I N - A, B] = N. Since the rank of the matrix
[m M I N - A, B] is contributed by the number of linearly
independent rows, employing the elementary column
transformation on the matrix m M I N - A (or A - m M I N ) will
yield a set of linearly dependent rows that violate the fullrank condition. The control signals located via B should
be imposed on the identical rows, so as to eliminate all
linear correlations and to ensure the full-rank condition.
The steps to identify the driver nodes to ensure exact
controllability are as follows: (i) for the given network,
compute the eigenvalues m of the matrix A and their
geometric multiplicities n (m), to find the eigenvalue m M
corresponding to the maximum geometric multiplicity
n (m M ); (ii) obtain the matrix A - m M I N ; (iii) perform an
elementary column transformation on A - m M I N to get
its column canonical form, which reveals the linear dependence among all rows. The rows that are linearly dependent on the others correspond to the driver nodes
with number N - rank (m M I N - A), which is the maximum
geometric multiplicity n (m M ).
Figure 11 shows a schematic example on the determination of driver nodes using the elementary column transformation. Note that the configuration of driver nodes is
not unique because it is determined by the order in operating the elementary column transformation and by the
different choices of the linearly dependent rows. However,
the minimum number of driver nodes is unique, which depends on the value of n (m M ). This approach to identifying
driver nodes is applicable to any network, including particularly networks characterized by structured matrices.

A - λMI N

4.2 Optimization Methods
Optimization of the network controllability is of great
importance in most real applications. To date, some representative methods of optimizing the network controllability can be classified as structure perturbations [62],
[63] and edge orientations [64].
Based on the minimum inputs theorem (Theorem 7),
Wang et al. [62] proposed a general approach to optimizing the structural controllability of complex networks
by minimum structure perturbations. The optimization
process involves three steps: (i) finding the minimum
number of independent matching paths using the maximum matching algorithm; (ii) randomly ordering all
found matching paths; (iii) linking the ending points of
each matching path to the starting nodes of the matching paths next to it in the above order. In operation, the
minimum number N D of driver nodes can be reduced to
one, maintaining the network connectivity. The principle
of the perturbation strategy is validated theoretically
and demonstrated numerically for both homogeneous
and heterogeneous random networks and for a number
of real networks from nature and society. It is found that,
for most real networks, about 5% of additional edges are
sufficient for optimizing the controllability. In [63], an
adding-edge strategy and a turning-edge strategy are proposed to optimize the controllability of switchboard edge
dynamics via minimum structural perturbations. Both
simulations and analysis indicate that the minimum number of adding-edges required for the optimal controllability is equal to the minimum number of turning-edges, and
networks with positively correlated in- and out-degrees
are easier to achieve optimal edge controllability.
Considering the difficulty and impracticality of changing the original network topology for a large-scale real
system, Xiao et al. [64] introduced an effective method
for enhancing the structural controllability of a complex

Column Canonical Form

-2

-1

λM = 0

µ(λM) = 2

λ=

Figure 11. Identifying the driver nodes based on elementary column transformation. For a general undirected network, the matrix
A - m M I N, the column canonical form of A - m M I N after an elementary column transformation, the eigenvalues m and the eigenvalue m M corresponding to the maximum geometric multiplicity n(m M) of A are given, respectively. the rows that are linearly
dependent on the others in the column canonical form are marked in red. the nodes corresponding to them are the driver nodes,
which are marked in purple in the original network. the set of driver nodes is not unique since it depends on the elementary column transformation, while the number of driver nodes is unique.
24

IEEE cIrcuIts and systEms magazInE

sEcOnd QuartEr 2019

IEEE Circuits and Systems Magazine - Q2 2019

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