On Quantitatively Measuring Controllability of
Complex Networks

CAI, Ning1, 2
1

College of Electrical Engineering, Northwest University for Nationalities, Lanzhou, China
2
School of Automation, Hangzhou Dianzi University, Hangzhou, China
E-mail: caining91@tsinghua.org.cn

Abstract: This letter deals with the controllability issue of complex networks. An index
is chosen to quantitatively measure the extent of controllability of given network. The
effect of this index is observed based on empirical studies on various classes of network
topologies, such as random network, small-world network, and scale-free network.
Key Words: Controllability; Complex Network; Quantitative Measure

1. Introduction
The controllability of a dynamic system reflects the ability of influencing from
external input information to the motion of the overall system. Observability and
controllability are dual alternatives. Integrated with stability, they form the theoretical
foundation for most of the systems analysis and synthesis problems. Therefore,
controllability has been one of the most important concepts in modern control theory.
Since about a decade ago, the controllability problems of dynamic networked
large-scale systems have intrigued many scholars from both the control [1-7] and the
physics [8-13] community, and will surely continue to attract the attention from more
and more disciplines.

~1~

Tanner [1] earlier studied the controllability of systems with single leader and
conjectured that excessive connectivity might even be detrimental to controllability,
while giving a definition of graph controllability based on a partition of the associated
Laplacian matrix. Paying attention to the relationship between the extent of symmetry
of graph and controllability, Rahmani and Mesbahi [2] further extended the results in
[1]. Cai et al. addressed the controllability problems of a class of high-order systems,
proposing a scheme of controllability improvement [3-4]. Liu et al. [5] concerned the
controllability of discrete-time systems with switching graph topologies. Ji et al. [6-7]
dealt with the interactive protocols, endeavoring to integrate the influence of three
facets upon controllability, which are the protocol, the vertex dynamics and the
network topology, respectively.
Liu et al. [8] addressed the structural controllability of complex networks. They
selected an index denoted by ND to quantitatively measure the extent of controllability
of complex networks, namely the least amount of independent input signals required.
Along the route of [8], there have emerged plenty of researches from the physics
community, e.g. [9-13]. Particularly, Yan et al. [9] concentrated upon the problem of
minimal energy cost for maneuvering the nodes. Yuan et al. concerned the exact
controllability [10] of undirected networks with identical edge weights and discovered
certain consistency with [8].
The concept of controllability for dynamic systems was originally raised by
Kalman, with a set of algebraic criteria to check whether or not a given system is
exactly controllable. It has formed the foundation of the controllability theory.
However, there are two intrinsic problems limiting the study of the controllability of
complex networks from the viewpoint of exact controllability. The first problem is
that almost any arbitrary system is controllable in the sense of exact controllability.
This fact reduces the significance of being controllable. As the second problem, it is
rather difficult to translate those algebraic criteria into straightforward conditions for
the topologies of networks.
In comparison with exact controllability, the concept of structural controllability
possesses some advantages for coping with the controllability problems of networked
systems. First, it bears no ambiguity like almost exact controllability. Being
structurally controllable or not is essentially distinct for any system. Second, it is
possible to acquire concise and straightforward criteria about the topologies of
networks to check whether or not they are structurally controllable. Nevertheless, the
essence of structural controllability is a minimal requirement for the availability of

~2~

input information across the network, which is only a necessary prerequisite for
controlling, whereas it cannot facilitate to evaluate the efficiency of control. Therefore,
structural controllability is also restrictive.
In the current letter, a third angle on controllability is addressed, other than the
exact controllability and structural controllability. We shall endeavor to explore the
possible way to measure the extent of controllability of any given network,
quantitatively. It is motivated by a wish to overcome some of the limitations of exact
controllability and structural controllability, and to extend the methodology for
controllability analysis of networks, from qualitative to quantitative. An index will be
proposed for evaluating the ability of dynamic network to be easily controllable via
the input information, and simulations will be performed on three distinct types of
complex networks, namely the E-R networks, the WS small-world networks, and the
scale-free networks, to illustrate the diversity of controllability situations.
The remaining part of this letter is organized as follows. Section 2 introduces the
fundamental preliminaries about controllability of complex networks and describes
the model concerned. Section 3 endeavors to analyze the computational controllability
concept theoretically, based on some simple examples. Section 4 presents a series of
experimental results toward three typical complex networks. Finally, Section 5
concludes this letter.

2. Problem Description and Preliminaries
2.1 Exact Controllability
The dynamics of a network concerned with N f followers and N l leaders is
described by the following equation:

  Aff   Afl
where the vector  (t )  R

Nf

(1)

represents the states of the follower vertices;  (t )  R Nl

represents the states of the leader vertices, which can be determined externally; and

A  R N N is the weighted adjacency matrix of the overall network topology, which is
decomposed as follows according to the leader-follower distribution
 Aff
A
 Alf

Afl 
All 

The network is exactly controllable if the state values of the followers can be

~3~

fully controlled via appropriately selected state values of leaders, otherwise, it is
uncontrollable. This

conforms

to

the conventional

definition

of Kalman

controllability.
Definition 1: A dynamic network (1) is exactly controllable if for any initial
values of follower states

1 (0), 2 (0),...,  N (0)  R
f

there exist    and proper leader signals

1 (t ),2 (t ),...,N (t ) ( t [0, ] )
l

such that 1 ( )  2 ( )  ...   Nl ( )  0 .
Lemma 1 below provides the most fundamental criterion to check controllability,
known as the rank test.
Lemma 1 [14]: A dynamic network (1) is exactly controllable if and only if the
controllability matrix is of full rank, which is
   Afl

Aff Afl

A2ff Afl

N 1
Aff f Afl 

Remark 1: If the number of leader Nl  1 , then the controllability matrix  is
square. In this case, the network is controllable if and only if  is nonsingular.
2.2 Almost Exact Controllability
The classic notion of exact controllability of dynamic systems is qualitative, and
could answer only “Yes” or “No”. However, it is well-known by the control theory
community that almost any linear system is controllable, i.e. the probability for any
system (1) to be exactly controllable is 1, so long as the matrix A is continuous-valued;
whilst the uncontrollable cases are just the rare exceptions [4, 15-16]. In this sense,
the exact controllability is less significant, whereas a better way to evaluate the extent
of controllability should be to measure how far a given network is from being
uncontrollable [15-16]. Such a route may be called computational controllability.
The main connotation behind the concept of computational controllability can be
illustrated by Fig. 1.

~4~

Uncontrollable
Set

Overall
Network
Space

0

Measure of
Controllability

Particular
Network

Fig. 1. Network space of R N  N .
Solid curves represent the set of networks that cannot be exactly
controlled.

In Fig. 1, any network is represented by a point in the space. Almost all the
networks are exactly controllable. If a particular network happens to locate at the
uncontrollable set, then any infinitesimal perturbation could let it leave this set and
become controllable.

3. Computational Controllability of Complex Networks: Theoretical Analysis
3.1 Introduction of Concept
Almost all the dynamic networks are controllable. Nevertheless, the relative
controllability should be different for various network topologies. Some may possess
relatively higher controllability, whereas some others may be less controllable as
being very close to an uncontrollable network.
According to Lemma 1, controllability is determined by the rank of  . If the
rank is nearly reduced, then the controllability of the associated network should be
low. If  is square as the single leader case, it is expected to be away from being
singular for higher controllability. Thus, it should be meaningful to measure the extent
of its nonsingularity. In this paper, we choose the conditional number of  as this
measure.
Definition 2: The conditional number of a square matrix  is
cond ()    1

~5~

Conditional number can be regarded as a measure of nonsingularity, which varies
within [1, ] . cond ()  1 if  is identity matrix, with the maximal possible
nonsingularity. Oppositely, if  is nearly singular, then cond () must be large
because  1 is large. The greater the conditional number, the closer the matrix 
is to be singular, till cond ()   as the rank of  becomes reduced. A definition
of computational controllability hereby arises, based on conditional number of
controllability matrix.
Definition 3: The computational controllability of a dynamic complex network (1)
can be measured by



1
cond ( )

where  is the controllability matrix.
Remark 2: For any network,  [0,1] . The greater this value, the higher
controllability a network achieves. A network is uncontrollable if   0 , otherwise, it
is controllable. However, if  is very small, the controllability is still quite weak
although the network is thought to be controllable in the conventional sense.
3.2 Basic Analysis
Let us start the theoretical analysis on computational controllability from
investigating several concrete typical instances.
Example 1: Consider the path PN . For simplicity, let N  5 and let the fifth
agent be the only leader. It is always controllable in the sense of exact controllability.
The network topology is illustrated in Fig. 2.

Fig. 2. Fifth order path P5 with default arc weight 1.

If this network is directed, its adjacency matrix is
0 1 0 0 0 
0 0 1 0 0 


A  0 0 0 1 0 


0 0 0 0 1 
0 0 0 0 0 

~6~

which is already decomposed by dotted lines. The controllability matrix  is just
the identity matrix, with   1 , indicating a maximal controllability.
If this network is undirected with the adjacency matrix
0 1 0 0 0 
1 0 1 0 0 


A  0 1 0 1 0 


0 0 1 0 1 
0 0 0 1 0 
the controllability matrix is

0
0

0

1

0 0 1
0 1 0 
1 0 2

0 1 0

The nonsingularity of this matrix is also quite satisfactory with cond ()  5.8284
and   0.1716 , indicating a rather high controllability.
Example 2: Consider the complete network C5 . The adjacency matrix is
0 1 1 1 1 
1 0 1 1 1 


A  1 1 0 1 1 


1 1 1 0 1 
1 1 1 1 0 
with the corresponding controllability matrix being

1
1

1

1

3 9 27 
3 9 27 
3 9 27 

3 9 27 

It is singular with the rank being only 1. Thus,  is definitely zero.
Example 3: Consider the random weighted directed network, which is known to
be almost controllable in the conventional sense. A random network of 8th order is
generated, with the last agent assigned as the leader. The resulted controllability
matrix is

~7~

0.1897
 0.1934

 0.6822

   0.3028
0.5417

 0.1509
 0.6979


0.8962 2.7716

8.6052

27.0802

84.4664

1.9397 5.3306 17.1429 53.1950 166.8824
1.0615 3.9149 12.0033 37.6166 117.6977
1.0436 2.9809

9.6179

29.8652

93.5949

1.1522 3.9331 11.9725 37.7541 117.8886
1.5067 3.9574 12.9025 39.9819 125.3981
1.0432 4.1353 12.2815 38.9403 121.4206

264.5718
521.6511
368.1719 

292.6930 
368.9820 

392.0307 
380.1693 

(2)

In this case, cond ()  1.5075 106 , and   6.6335 107 . Such a network
obviously holds a lower controllability.
The controllability of a network is closely relational to its spectral distribution, by
which the reason for lower controllability of Example 3 could partially be explained.
Note that the average values of column elements keep on increasing from left to
right in (2). Such a phenomenon will greatly deteriorate the nonsingularity of the
overall matrix, according to the following lemma.
Lemma 2: The infinite conditional number of square matrix A  [aij ]  R N  N is
generally greater than  N , with   1 being the ratio between the maximal and
minimal row/column sum of absolute values of elements.
Proof: If A is singular, cond ( A) is infinite. Consider the case that A is
nonsingular. Without loss of generality, let the rows be sorted according to the sums of
absolute values of elements, with the first row possessing the minimal sum, and
1
N
a11   j 1 a1 j
N
Now consider the matrix A / a11 , which has obviously the same conditional number
with A. Because the sum of absolute values of elements in the first row of A / a11 is



N
j 1

( a1 j / a11 )  N

the sum of absolute values of elements in the last row of A / a11 is  N and as a
result
A / a11



 N

The inverse of matrix A / a11 can be computed through a series of elementary row
transformations to the following augmented matrix:

~8~

 a11 / a11

 a21 / a11


 aN 1 / a11

a12 / a11
a22 / a11

a1N / a11
a2 N / a11

1 0
0 1

aN 2 / a11

aNN / a11

0 0

0

0


1 

Evidently, the absolute value of the element of ( A / a11 )1 with index (1, 1) is 1, and
it follows that
( A / a11 )1



1 □

Remark 3: The bound  N given in Lemma 2 is quite conservative. Usually, the
conditional number of a matrix is far greater than this bound. Besides, although there
are different definitions of conditional number, generally their trends are consistent. It
is not possible that the conditional number is very large by one definition but very
small by another.
The spectrum of Aff in Example 3 is
{3.1285, 0.4372  0.445i, 0.3542  0.2556i, 0.7864, 0.7592}

Such a distribution is typical for the class of random networks in Example 3, with one
largest eigenvalue and the remaining being very smaller.
It is known that any random matrix is almost diagnolizable [17]. Suppose that

Aff could be diagnolized as
1

P 1 Aff P  






N f 

It follows that
1k

Akff  P 




 1
P
k 
N f 

The magnitude of Akff of Example 3 increases with k because 1 is much larger
than 1.
The controllability can be changed by scaling the spectral radius through zooming
the topology of network, without affecting the structure.
Consider the controllability of A /  , where   0 is the zoom factor. Take the
data in Example 3 and let the zoom factor  vary across [1, 4] ; the corresponding
controllability variation forms a quite smooth curve, as shown in Fig. 3. One can see
that, at first, the controllability increases as  increases, and it reaches a maximum

~9~

when   2.4 ; then the controllability keeps on decreasing because the magnitude of

Akff decreases with k if 1 is less than 1.
Intuitively speaking, the controllability of a network should generally be better if
the eigenvalues locate nearby the unit circle. The spectral radius being either greatly
larger or less than 1 will deteriorate the controllability.
-5.3
-5.4
-5.5
-5.6
-5.7
-5.8
-5.9
-6
-6.1

1

1.5

2

2.5

3

3.5

4

ZoomFactor

Fig. 3. Trend of controllability in Example 3 with zoom factor varying across [1, 4]

4. Computational

Controllability

of

Complex

Networks:

Empirical Analysis
This section will manifest a series of empirical analysis on computational
controllability for the three typical classes of complex networks.
4.1 E-R Network
Consider the E-R networks comprising of 15 followers and 1 leader. Let the
connectivity probability p vary across [0, 0.9]. The value of each data point is the
average of 2000 random trials. The variation of controllability is shown in Fig. 4. One
can see that the logarithm variation trend could be fitted into two straight lines.
It is worth mentioning that throughout this section, the edge weights are mounted
with noises uniformly distributed within [-0.025, 0.025], which are relatively rather
weak.

~ 10 ~

-14

-16

-18

-20

-22

-24

-26

-28

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

p

Fig. 4. Trend of controllability of E-R network with connectivity probability
varying across [0, 0.9]

The controllability achieves a maximum when about p  0.15 . If the value of p
is too low, the network lacks sufficient connectivity to guarantee controllability.
However, the controllability keeps on decreasing as p is large enough. The more a
network approximates a complete graph, the less controllable it would be.
Now fix the connectivity probability p to 0.15 and let the number of leaders N l
vary across 1, 2, …, 15. The variation of controllability is shown in Fig. 5. There is a
positive correlation between the controllability and N l . However, such a correlation
becomes weak as the number of leaders is sufficiently large. For this example,
log( ) seems to approach a limit being less than 10.
-10
-10.5
-11
-11.5
-12
-12.5
-13
-13.5
-14
-14.5
-15

0

5

10

15

Nl

Fig. 6. Trend of controllability of E-R network with number of leaders varying
across 1, 2, …, 15

~ 11 ~

Fix the connectivity probability p to 0.15 and the number of leaders N l to 1. Let
the number of followers vary across 5, 6, …, 104, 105. According to the result, the
controllability is negatively correlated to the number of followers, as shown in Fig. 6.
One can see that the controllability of a network with large-scale is quite weak.
0
-20
-40
-60
-80
-100
-120
-140
-160

0

20

40

60

80

100

120

Nf

Fig. 7. Trend of controllability of E-R network with number of followers
varying across 5, 6, …, 104, 105

4.2 WS Small-World Network
Consider the WS small-world networks containing 16 followers, with K  2 .
First, let the switching probability p vary across [0, 0.9]. However, no direct
relationship can be seen between the controllability and p, according to the simulation
result.
Set the switching probability p to 0.5 and successively increase the quantity of
leaders N l from 1 to 15, with the quantity of followers N f being fixed. A resulted
relationship between the controllability and N l is shown in Fig. 8. It can be seen that
more leaders are generally beneficial to the controllability, although this effect is less
prominent if Nl  1 .

~ 12 ~

-8

-9

-10

-11

-12

-13

-14

-15

0

5

10

Nl

15

Fig. 8. Trend of controllability of WS small-world network with number of
leaders varying across 1, 2, …, 15

Let p  0.5 , Nl  1 , and the quantity of followers be 5, 6, …, 85. The
relationship between the controllability and N f is illustrated in Fig. 9, which may be
approximately fitted into a straight line.
0

-10

-20

-30

-40

-50

-60

0

10

20

30

40

50

60

70

80

90

Nf

Fig. 9. Trend of controllability of WS small-world network with number of
followers varying across 5, 6, …, 85

Let p  0.5 , Nl  1 , and N f  30 ; successively increase the K from 2 to 15. It
should be interesting to see that although being independent of p, the controllability is
negatively correlated to K, as shown in Fig. 10.

~ 13 ~

-20

-25

-30

-35

-40

-45

2

4

6

8

10

12

14

16

K

Fig. 10. Trend of controllability of WS small-world network with K varying
across 2, 3, …, 15

4.3 BA Scale-Free Network
Consider the controllability of BA scale-free networks. First, let the order of the
original complete graph m0  7 , the number of added vertices t  8 , and the number
of new edges per vertex m  3 . The resulted network topology is illustrated in Fig. 11,
with the indices of vertices sorted by degree.
11
1

5
10

3

12

9

2

8

15

14
13

4

7
6

Fig. 11. BA scale-free network with m0 = 7, m = 3, and t = 8

Select each vertex as the single leader, one by one, with the computed controllability
of network successively shown in Fig. 12. A slight tendency of positive correlation
between the controllability and the degree of leader vertex can be observed.

~ 14 ~

-14

7

x 10

6

5

4

3

2

1

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

indexof leader

Fig. 12. Trend of controllability of BA scale-free network with degree of
leader decreasing

Fix m0  7 and t  8 ; meanwhile, let m vary across 1, 2, …, 6. For each case,
the average controllability of 2000 trials is recorded and displayed in Fig. 13.
Evidently, the controllability is positively correlated to m.
-10

-15

-20

-25

1

2

3

m

4

5

6

Fig. 13. Trend of controllability of BA scale-free network with m varying
across 1, 2, …, 6

5. Conclusion
Considering the fact that weighted real-world networks are almost controllable in
the sense of exact controllability, this letter addresses the problem of measuring the

~ 15 ~

controllability of complex networks quantitatively. For this end, an index is selected,
based on the conditional number of controllability matrix. The effect of this index is
observed and discussed, mainly by a series of experiments on various types of
complex networks, e.g. the E-R networks, the WS small-world networks, and the BA
scale-free networks.
Studies along this route could enable the comparisons of controllability between
complex networks with different topologies. The current letter just takes a first step.
There exist abundant directions of potential future extensions, for instance: 1) Other
indices beside the one here can be sought; 2) More experiments can be conducted to a
broader range of networks, for the sake of discovering more empirical regularities; 3)
Certain phenomena observed could be explained analytically. 4) The network model
concerned can take other forms, e.g. being represented by Laplacian matrix.

Acknowledgments
This work is supported by National Natural Science Foundation (NNSF) of China
(Grants 61263002 & 61374054), by Program for Young Talents of State Ethnic
Affairs Commission (SEAC) of China (Grant [2013] 231), and by the Zhejiang Open
Foundation of the Most Important Subjects.

References
[1] H. G. Tanner, “On the controllability of nearest neighbor interconnections”, Proc. 43rd IEEE
Conf. Decision and Control, vol. 3, pp. 2467-2472, 2004.
[2] A. Rahmani, M. Ji, and M. Mesbahi et al., “Controllability of multi-agent systems from a
graph-theoretic perspective”, SIAM J. Control Optim., vol. 48, no.1, pp. 162-186, 2009.
[3] N. Cai, J.-X. Xi, and Y.-S. Zhong et al., “Controllability improvement for linear
time-invariant dynamical multi-agent systems”, Int. J. Innov. Comput. I., vol. 8, no. 5a, pp.
3315-3328, 2012.
[4] N. Cai, J.-W. Cao, and M. J. Khan, “A controllability synthesis problem for dynamic
multi-agent systems with linear high-order protocol”, Int. J. Control Automat. Syst., vol. 12,
no. 6, pp. 1366-1371, 2014.
[5] B. Liu, T.-G. Chu, and L. Wang et al., “Controllability of a leader-follower dynamic network
with switching topology”, IEEE Trans. Autom. Control, vol. 53, no.4, pp. 1009-1013, 2008.
[6] Z.-J. Ji, H. Lin, and H.-S. Yu, “Leaders in multi-agent controllability under consensus
algorithm and tree topology”, Syst. Control Lett., vol. 61, no. 9, pp. 918-925, 2012.
[7] Z.-J. Ji, H. Lin, and H.-S. Yu, “Protocols design and uncontrollable topologies construction
for multi-agent networks”, IEEE Trans. Automat. Control, vol. 60, no. 3, pp. 781-786, 2015.

~ 16 ~

[8] Y.-Y. Liu, J. J. Slotine, and A. L. Barabási, “Controllability of complex networks”, Nature, vol.
473, pp. 167-173, 2011.
[9] G. Yan, J. Ren, and Y.-C. Lai et al., “Controlling complex networks: How much energy is
needed?”, Phys. Rev. Lett., vol. 108, 218703, 2012.

[10] Z.-Z. Yuan, C. Zhao, and Z.-R. Di et al., “Exact controllability of complex networks”, Nat.
Commn., vol. 4, 2013.
[11] T. Jia, Y.-Y. Liu, and E. Csóka et al., “Emergence of bimodality in controlling complex
networks”, Nat. Commun., vol. 4, 2002, 2013.
[12] Y.-Y. Liu, J. J. Slotine, and A. L. Barabási, “Control centrality and hierarchical structure in
complex networks”, PLoS ONE, vol. 7, no. 9, e44459, 2012.
[13] J. Ruths and D. Ruths, “Control profiles of complex networks”, Science, vol. 21, pp.
1373-1376, 2014.
[14] T. Kailath, Linear Systems, Englewood Cliffs: Prentice-Hall, 1980.
[15] C. C. Paige, “Properties of numerical algorithms relating to computing controllability”, IEEE
Trans. Automat. Control, vol. 26, no. 1, pp. 130-138, 1981.
[16] D. L. Boley and W.-S. Lu, “Measuring how far a controllable system is from an
uncontrollable one”, IEEE Trans. Automat. Control, vol. 31, no. 3, pp. 249-251, 1986.
[17] N. Cai, J.-W. Cao, and M. J. Khan, “Almost decouplability of any directed weighted network
topology”, Physica A, vol. 436, pp. 637-645, 2015.

~ 17 ~

