# Quantitative Controllability Index of Complex Networks

Authors: Lifu Wang; Yali Zhang; Jingxiao Han; Zhi Kong
Journal: Advances in Mathematical Physics
 (2018)

---

## Abstract

In this paper, the controllability issue of complex network is discussed. A new quantitative index using knowledge of control centrality and condition number is constructed to measure the controllability of given networks. For complex networks with different controllable subspace dimensions, their controllability is mainly determined by the control centrality factor. For the complex networks that have the equal controllable subspace dimension, their different controllability is mostly determined by the condition number of subnetworks’ controllability matrix. Then the effect of this index is analyzed based on simulations on various types of network topologies, such as ER random network, WS small-world network, and BA scale-free network. The results show that the presented index could reflect the holistic controllability of complex networks. Such an endeavour could help us better understand the relationship between controllability and network topology.


---

## Body

## 1. Introduction

In recent years, the study of complex networks has drawn the attention of many scholars from both the science and the engineering communities [1–5]. Studies of theirs impact our understanding and control of a wide range of systems, from the Internet and the power-grid to cellular and ecological networks. While there are many challenges in the process of research due to the diversity of complex networks, one most challenging issue in modern science and engineering networks is the control of complex networks [6, 7]. The controllability of a dynamical system reflects the ability of external input information to influence the motion of the overall system. A complex network is controllable if, imposing appropriate external signals, the system can be driven from any initial state to any final state in finite time [8–10]. Although great effort has been devoted to understanding the interplay between complex networks and dynamical processes taking place on them in various natural and technological systems [11–17], the control of complex dynamical networks remains to be an outstanding problem. The Kalman controllability formed the foundation of the controllability theory by a set of algebraic criteria to check whether or not a given system is controllable. However, the Kalman controllability is qualitative; we cannot know how it is difficult or easy to control, that is, cannot know the size of network controllability for one network system. Therefore, it is necessary to find a method that can quantitatively measure controllability of a given system.With deeper understanding of the controllability of complex networks [18–26], more scholars have begun to explore the ability to control complex networks through various indicators. For example, Liu et al. [18] addressed the structural controllability of arbitrary complex directed networks, identifying a minimal set of driver nodes that can guide the system to any desired state. They selected an index denoted by Nd to quantitatively measure the extent of controllability of complex networks. Liu et al. [19] propose the concept of node control centrality to quantify the ability of a single node of complex network and calculate the distribution of control centrality for some networks. Jia et al. [20] proposed the concept of node control capability in the further study; that is, the possibility of node becoming a driving node was calculated. Many research works have been published under the theoretical framework of structural controllability [21–26]. However, these quantitative controllability methods only roughly measure the dimensionality of controllable subsystems; they could not better distinguish the controllability of systems with the same number of dimensions of controllable subsystems. Cai Ning [27] studied a way to quantitatively measure the extent of controllability of any given controllable network. This method is based on fully controllable networks; for uncontrollable networks, it could not make a judgement.In the current paper, we will try to explore the possible ways to quantitatively measure the extent of controllability of any given network. An index will be proposed to assess the controllability of a dynamical network, that is, the network whether or not being easily or difficulty controlled via the input information. While the previous Kalman controllability index is qualitative, only defining whether or not a system is controllable, the one in our paper is quantitative. Particularly, for a not completely controllable system, we can quantitative measure controllability of the controllable subsystem by decomposing the network into a controllable subsystem and an uncontrollable subsystem, so that we can measure how far the network is from being uncontrollable. Such a route may be called quantitative index measure controllability of complex network. Then simulations will be performed to show the effect of controllability index between different network topologies on three distinct types of model networks, namely, the random networks, the small-world networks, and the BA scale-free networks. Through simulation results, it can be found that controllability of given network is related to their topologies, such as the number of nodes and edges and edge density, so it is possible to improve the controllability of the network by adjusting certain parameters, such as the connectivity probabilityp and the number of nodes N.


## 2. Controllability of Complex Networks

Consider a complex system described by a directed weighted network ofN nodes whose time evolution follows the linear time invariant dynamics [28].(1)x˙t=Axt+Butwhere x(t)=(x1(t),x2(t),…,xN(t))T∈RN is the state vector of each node at time t. A∈RN×N denotes the state matrix that depicts the linking strength between the state nodes. The matrix element aij gives the strength or weight that node xj can affect node xi. B∈RN×M is the input matrix, indicating the nodes that are controlled by the time-dependent input vector ut=(u1(t),u2(t),…,uM(t))T∈RM with independent signals imposed by an outside controller. The element bij represents the control strength from the control node uj to the state node xi. A system is controllable if we can drive it from any initial state to any desired final state in finite time; otherwise, it is uncontrollable.System (1), also denoted as (A,B), is controllable if and only if its controllability matrix C=BABA2B⋯AN-1B∈RN×NM has full rank; that is,(2)rankC=rankBABA2B⋯AN-1B=Nwhich are the criteria often called Kalman’s controllability rank condition [8].The rank of the controllability matrixC, denoted by rank(C), provides the dimension of the controllable subspace of system (A,B). The system is not completely controllable if rankC=N1<N. Then the system can be decomposed into a controllable subsystem and an uncontrollable subsystem through a linear transformation [29], which is(3)
x
^
˙
1
x
^
˙
2
=
A
^
11
A
^
12
0
A
^
22
x
^
1
x
^
2
+
B
^
1
0
uwhere x^˙1=A^11x^1+A^12x^2+B^1u is the controllable subsystem whose dimension is N1, and x^˙2=A12x^2 is the uncontrollable subsystem whose dimension is N-N1.When we control nodexi only (xi is theith node in the network), B reduces to the vector bi with a single nonzero entry, and we denote C with Ci. We can therefore use rank Ci as a natural measure of node xi’s ability to control the system: if rankCi=N, then node xi alone can control the whole system; that is, it can drive the system to travel between any points in the N-dimensional state space in finite time. Any value of rankCi less than N provides the dimension of the subspace that xi can control. In particular, if rankCi=1, then node xi can only control itself.Kalman controllability theory provides great convenience for checking whether or not a given network is controllable. However, from the point of view of Kalman controllability, there are some problems that restrict the study of the controllability of complex networks to some extent. First, almost any arbitrary system is completely controllable in the sense of Kalman controllability [27]. This fact reduces the significance of Kalman controllability theory. In addition, Kalman controllability of dynamical system is qualitative, which means that, in Kalman's theory, the system could be only defined as either controllable or uncontrollable. However, for many real-world network systems, people need to know more information about the controllability issue such as how much our control force should be to control the whole system or maybe part of the system. In the next section, one index is brought up with to measure the controllability of networks quantitatively.


## 3. Quantitative Index Measuring Controllability

Before we begin to analyze quantitative controllability, we first introduce the definition of conditional number.Definition 1 (see [30]).
The condition number of a square matrix is(4)condC=CC-1,where ∙ denotes 2-norm of the square matrix C.
The condition number can measure the nonsingularity of a matrix, with range of variation in1,∞. When C is identity matrix, condC=1. On the contrary, when C is nearly singular matrix, condC=∞. That is, the greater the condition number is, the closer the matrix C is to being singular.


### 3.1. Examples of Analysis Controllability

Let us start the analysis on quantitative index measuring controllability by investigating two typical examples.Consider two simple networks ofN=7 nodes with different structures. The controlled network has an input connecting to a state node x1. The network topology is shown in Figure 1. The controllability of node x1 to the whole network is analyzed as in Figure 1.Figure 1
There are two simple networks ofN=7 nodes with different structures. The controlled network has an input node connecting to state node x1.
(a) (b)For Figure1(a), the state matrix of the network is(5)A=0000000101000000010000100000100000000001000000100.When we control node x1 only, the input matrix is(6)B=1000000T.Then the controllability matrix C1 by controlling node x1 is(7)C1=BABA2B⋯A6B=1000000010010000010010010010010000000100000010000.Therefore, the rank of controllability matrix C1=rankC1=6<N=7, indicating that the whole system is not completely controllable by controlling node x1 only. Yet, there exists a controllable subsystem with 6 nodes, and these nodes can be found by all stem-cycle disjoints [18]. For example, x1,x2,x3,x4,x5,x6 constitute a controllable subsystem. In other words, by controlling node x1 with a time-dependent signal u1(t), we can drive the subsystem x1,x2,x3,x4,x5,x6 from any initial state to any final state in finite time. According to linear system theory, the network system (A,B) can be decomposed by linear transformation [31, 32]. We can get the controllable subsystem (A^1,B^1) as follows:(8)A^1=01.20000000.70000.8000.6000-0.4001.20000.7001.4000000,B^1=0000001T.Then the controllability matrix of the controllable subsystem (A^1,B^1) is(9)C~1=B^1A^1B^1A^12B^1⋯A^15B^=000000.800000.70000100001.7000.501.4000.70100000.Then subsystem (A^1,B^1) can be completely controllable after the structural decomposing. We can compute that cond(C~(1))=2.98, indicating that the distance from the controllable subsystem to the uncontrollable (C~(1) singular) is +∞-2.98.Similarly, for Figure1(b), we can get the state matrix of the network:(10)A=0000000100000001000001000100000001000010000001000.And when the node x1 is controlled only, the input matrix is(11)B=1000000T.Then the controllability matrix is(12)C1=1000000010000000100000100100000100100100100010010.So we also can get C1=rankC1=6<N=7 when we control node x1 only. Through structural decomposing, the controllable subsystem (A^1,B^1) is(13)A^1=01.20000000.70000.4000.60000.4001.20000.7001.4000000,B^1=0000001T.And the controllability matrix of the controllable subsystem is(14)C~1=000000.800000.70000100001.7001.101.4000.70100000.The controllable subsystem is also x1,x2,x3,x4,x5,x6. For the controllable subspace, we can get that cond(C~(1))=3.4, indicating that the distance from the controllable subsystem to the uncontrollable one (C~(1) singular) is +∞-3.4. By comparing Figures 1(a) and 1(b), both controllable subsystems with the same size, we can see that they do not have the same distances from being uncontrollable. In these two examples, the two controllable subsystems both are equally distant from being uncontrollable. However, there are some networks that are controllable but have a closer distance to being uncontrollable; that is, the value of their cond(C~(1)) is very large and C~(1) is really close to being singular.


### 3.2. Introduction of New Index: Quantitative Measuring Controllability

In this subsection, a more precise index of evaluating the controllability is presented. More than just saying “controllable” or “uncontrollable” to a network system, it can quantify the controllability of the given network. Such a route may be called quantitative controllability index.Definition 2 (quantitative controllability index).
The quantitative index measuring controllability of single nodei can be computed by(15)Qi=Ci+ki,where C(i)=rankB(i)AB(i)A2B(i)⋯ANB(i) is the rank of controllability matrix by controlling node xi only; 1≤C(i)≤N; thus Ci provides the dimension of the subspace node xi can control; ki=1/cond(C~i); C~i is the controllability matrix of controllable subsystem by controlling node xi only; then ki can measure the distance from the controllable subsystem to the uncontrollable one. Thus, Q(i) captures the ability of node xi to control the whole network. In addition, Q(i) can continuously characterize the controllability of the given network, while Ci as a positive integer can only measure the dimension of the controllable subspace (the higher Ci is, the stronger controllability given network achieves). For controllable subspaces with the same dimension, their controllability size is the same when Ci is used to measure controllability (e.g., Figure 1), so this characterization is not perfect. Therefore, we measure the controllability with the index Qi which adds ki to the base of Ci and uses ki, which indicates how far the subsystem is away from being uncontrollable, to measure the controllability of subsytems with the same dimensional controllable subspace. When Ci is the same, ki plays a key role in measuring the controllability. The larger ki is, the further the subsystem is away from the fully uncontrollable point, which means that the controllability of this subsystem is stronger. Therefore, the greater value of Q(i) is, the stronger controllability the network achieves. In Figure 1(a), when the node x1 is controlled separately, we can get Qa1=Ca1+ka1=6+0.34=6.34. In Figure 1(b), similarly, when the node x1 is controlled separately, we can get Qb1=Cb1+kb1=6+0.29=6.29. Their controllable subspace is the same, but their distances from the fully uncontrollable point are different. Therefore, the network controllability of Figure 1(a) is stronger than the network controllability of Figure 1(b) by controlling node x1 only.By the above definition, we can calculate the controllability of each node for the given network. Then we can get the average quantitative controllability index of the whole network:(16)Q=1N∑i=1NQi.Therefore, Q can be used to quantitatively measure the controllability of the whole network system. For Figures 1(a) and 1(b), the quantitative measuring the controllability Q(i) of each node is shown in Table 1. Then, the average quantitative index measuring controllability of whole network is calculated: Qa=1/7∑i=17Qi=3.5774 and Qb=1/7∑i=17Qi=3.5837 as shown in Table 1. Thus, we can conclude that the average controllability of network in Figure 1(a) is slightly weaker than network in Figure 1(b); that is, the network shown in Figure 1(b) is easier to be controlled than the other one in Figure 1(a).Table 1
Quantitative controllability indexesQ of each node and their average in Figure 1.
Q ( 1 ) Q ( 2 ) Q ( 3 ) Q ( 4 ) Q ( 5 ) Q ( 6 ) Q ( 7 ) Q Figure1(a) 6.34 4 4 4 2.71 2 2 3.5774  Figure1(b) 6.29 3 2 3.71 3.71 4.38 2 3.5837The change of number of nodes does influence theQ performance, while the increase of edges has no influence on the Q performance. We have also analyzed the index, especially calculating its time complexity. We estimate the time complexity in (16). For any complex network with N nodes, when we use Q to calculate the controllability of the network, the time complexity of the algorithm is O(N2).The controllability indexQ(i) consists of two parts: one is the control centrality, and the distribution of the control centrality is mainly determined by the degree distribution [19]; and the other part is k taking condition number as a parameter with the range between 0 and 1, which is the indicator of controllability difference among networks with the same number of dimensions, and it acts more like a modifier in Q(i), having no decisive effect on distribution of Q(i). Therefore, we deduce that the distribution of Q(i) is mostly determined by the network’s degree distribution. We use averaging of all nodes to assess the controllability of the whole network and to quantify the network’s controllability entirely, just like using average degree to analyze the whole network.


## 3.1. Examples of Analysis Controllability

Let us start the analysis on quantitative index measuring controllability by investigating two typical examples.Consider two simple networks ofN=7 nodes with different structures. The controlled network has an input connecting to a state node x1. The network topology is shown in Figure 1. The controllability of node x1 to the whole network is analyzed as in Figure 1.Figure 1
There are two simple networks ofN=7 nodes with different structures. The controlled network has an input node connecting to state node x1.
(a) (b)For Figure1(a), the state matrix of the network is(5)A=0000000101000000010000100000100000000001000000100.When we control node x1 only, the input matrix is(6)B=1000000T.Then the controllability matrix C1 by controlling node x1 is(7)C1=BABA2B⋯A6B=1000000010010000010010010010010000000100000010000.Therefore, the rank of controllability matrix C1=rankC1=6<N=7, indicating that the whole system is not completely controllable by controlling node x1 only. Yet, there exists a controllable subsystem with 6 nodes, and these nodes can be found by all stem-cycle disjoints [18]. For example, x1,x2,x3,x4,x5,x6 constitute a controllable subsystem. In other words, by controlling node x1 with a time-dependent signal u1(t), we can drive the subsystem x1,x2,x3,x4,x5,x6 from any initial state to any final state in finite time. According to linear system theory, the network system (A,B) can be decomposed by linear transformation [31, 32]. We can get the controllable subsystem (A^1,B^1) as follows:(8)A^1=01.20000000.70000.8000.6000-0.4001.20000.7001.4000000,B^1=0000001T.Then the controllability matrix of the controllable subsystem (A^1,B^1) is(9)C~1=B^1A^1B^1A^12B^1⋯A^15B^=000000.800000.70000100001.7000.501.4000.70100000.Then subsystem (A^1,B^1) can be completely controllable after the structural decomposing. We can compute that cond(C~(1))=2.98, indicating that the distance from the controllable subsystem to the uncontrollable (C~(1) singular) is +∞-2.98.Similarly, for Figure1(b), we can get the state matrix of the network:(10)A=0000000100000001000001000100000001000010000001000.And when the node x1 is controlled only, the input matrix is(11)B=1000000T.Then the controllability matrix is(12)C1=1000000010000000100000100100000100100100100010010.So we also can get C1=rankC1=6<N=7 when we control node x1 only. Through structural decomposing, the controllable subsystem (A^1,B^1) is(13)A^1=01.20000000.70000.4000.60000.4001.20000.7001.4000000,B^1=0000001T.And the controllability matrix of the controllable subsystem is(14)C~1=000000.800000.70000100001.7001.101.4000.70100000.The controllable subsystem is also x1,x2,x3,x4,x5,x6. For the controllable subspace, we can get that cond(C~(1))=3.4, indicating that the distance from the controllable subsystem to the uncontrollable one (C~(1) singular) is +∞-3.4. By comparing Figures 1(a) and 1(b), both controllable subsystems with the same size, we can see that they do not have the same distances from being uncontrollable. In these two examples, the two controllable subsystems both are equally distant from being uncontrollable. However, there are some networks that are controllable but have a closer distance to being uncontrollable; that is, the value of their cond(C~(1)) is very large and C~(1) is really close to being singular.


## 3.2. Introduction of New Index: Quantitative Measuring Controllability

In this subsection, a more precise index of evaluating the controllability is presented. More than just saying “controllable” or “uncontrollable” to a network system, it can quantify the controllability of the given network. Such a route may be called quantitative controllability index.Definition 2 (quantitative controllability index).
The quantitative index measuring controllability of single nodei can be computed by(15)Qi=Ci+ki,where C(i)=rankB(i)AB(i)A2B(i)⋯ANB(i) is the rank of controllability matrix by controlling node xi only; 1≤C(i)≤N; thus Ci provides the dimension of the subspace node xi can control; ki=1/cond(C~i); C~i is the controllability matrix of controllable subsystem by controlling node xi only; then ki can measure the distance from the controllable subsystem to the uncontrollable one. Thus, Q(i) captures the ability of node xi to control the whole network. In addition, Q(i) can continuously characterize the controllability of the given network, while Ci as a positive integer can only measure the dimension of the controllable subspace (the higher Ci is, the stronger controllability given network achieves). For controllable subspaces with the same dimension, their controllability size is the same when Ci is used to measure controllability (e.g., Figure 1), so this characterization is not perfect. Therefore, we measure the controllability with the index Qi which adds ki to the base of Ci and uses ki, which indicates how far the subsystem is away from being uncontrollable, to measure the controllability of subsytems with the same dimensional controllable subspace. When Ci is the same, ki plays a key role in measuring the controllability. The larger ki is, the further the subsystem is away from the fully uncontrollable point, which means that the controllability of this subsystem is stronger. Therefore, the greater value of Q(i) is, the stronger controllability the network achieves. In Figure 1(a), when the node x1 is controlled separately, we can get Qa1=Ca1+ka1=6+0.34=6.34. In Figure 1(b), similarly, when the node x1 is controlled separately, we can get Qb1=Cb1+kb1=6+0.29=6.29. Their controllable subspace is the same, but their distances from the fully uncontrollable point are different. Therefore, the network controllability of Figure 1(a) is stronger than the network controllability of Figure 1(b) by controlling node x1 only.By the above definition, we can calculate the controllability of each node for the given network. Then we can get the average quantitative controllability index of the whole network:(16)Q=1N∑i=1NQi.Therefore, Q can be used to quantitatively measure the controllability of the whole network system. For Figures 1(a) and 1(b), the quantitative measuring the controllability Q(i) of each node is shown in Table 1. Then, the average quantitative index measuring controllability of whole network is calculated: Qa=1/7∑i=17Qi=3.5774 and Qb=1/7∑i=17Qi=3.5837 as shown in Table 1. Thus, we can conclude that the average controllability of network in Figure 1(a) is slightly weaker than network in Figure 1(b); that is, the network shown in Figure 1(b) is easier to be controlled than the other one in Figure 1(a).Table 1
Quantitative controllability indexesQ of each node and their average in Figure 1.
Q ( 1 ) Q ( 2 ) Q ( 3 ) Q ( 4 ) Q ( 5 ) Q ( 6 ) Q ( 7 ) Q Figure1(a) 6.34 4 4 4 2.71 2 2 3.5774  Figure1(b) 6.29 3 2 3.71 3.71 4.38 2 3.5837The change of number of nodes does influence theQ performance, while the increase of edges has no influence on the Q performance. We have also analyzed the index, especially calculating its time complexity. We estimate the time complexity in (16). For any complex network with N nodes, when we use Q to calculate the controllability of the network, the time complexity of the algorithm is O(N2).The controllability indexQ(i) consists of two parts: one is the control centrality, and the distribution of the control centrality is mainly determined by the degree distribution [19]; and the other part is k taking condition number as a parameter with the range between 0 and 1, which is the indicator of controllability difference among networks with the same number of dimensions, and it acts more like a modifier in Q(i), having no decisive effect on distribution of Q(i). Therefore, we deduce that the distribution of Q(i) is mostly determined by the network’s degree distribution. We use averaging of all nodes to assess the controllability of the whole network and to quantify the network’s controllability entirely, just like using average degree to analyze the whole network.


## 4. Empirical Analysis of Quantitative Controllability Index

The controllability of complex networks is related to their network topology. Therefore, it is significant to find the relationship between quantitative index measuring controllability and the structure parameters of complex network. In this section, we will conduct a series of simulation analyses for three different typical complex network models to observe the regularity with which the network controllability changes with the variations of parameters.


### 4.1. ER Network

Liu et al. [18] proved that the minimum number of nodes that the input signals are injected into, called driver nodes, could be determined by detecting the “maximum matching” in the network. A maximum matching is the maximum set of links that do not share start or end nodes. A node is said to be matched if a link of the maximum matching points at it; otherwise, it is unmatched. If the nodes in a network are all matched, then the network is perfectly matched and the number of driver nodes Nd is 1; otherwise, Nd=N-NM, where NM is the number of matched nodes. The ratio of driving nodes to total number of nodes can be used to measure controllability of the network. Here, we compare the quantitative indexQ with that of the number of driver nodes Nd as shown in Figure 2.Figure 2
Trend of controllability and drive nodes of ER network with connectivity probabilityp varying across 0,1.Consider the ER network with twenty nodes,N=20; each time one of the nodes is controlled separately. Let the connectivity probabilityp vary across [0,1]. Here we show the variation of controllability indexQ with connection probability p in Figure 2. Every data in the figure has been calculated 1000 times and we took the average value.We can see from Figure2 that, for small connecting probability p<0.2, controllability index Q increases with p and reaches the maximum at around p≈0.2. Meanwhile, for higher link density p>0.2,Q begins to decrease with connection probabilityp. However, according to the red line in Figure 2, when p<0.2, the number of driver nodes decreases and the connection possibilityp increases. The number of drive nodes is larger for smaller connection probability p, indicating the weak controllability of the network because more nodes need to be controlled. When 0.2<p<0.8, the number of driver nodes basically remains the same when the connection possibility increases. And when p>0.8, the number of driver nodes increases with the increase of the connection possibilityp, which indicates that the controllability is weaker in the meantime. Besides, the closer the network is to the complete graph, the more nodes need to be controlled and then the lower the controllability is. From the comparison ofQ and Nd, it is not hard to find out that, for the same ER networks, the controllability variation trend is basically the same. IndexQ is positively correlated to the controllability, while Nd is a negative correlation coefficient of controllability.Then we fix the connection probabilityp=0.2 and let the number of nodes N vary across 20,21,…,70. The variation of controllability index Q with the number of nodes N is shown in Figure 3. We can see from Figure 3 that, for the ER network model, the controllability indexQ of the network decreases and the number of nodesN increases. In addition, the indexQ is very poor for the network with the large number of nodes, which indicates that when the number of the nodes of the network is huge, the controllability is low and the whole network is relatively hard to control. In this regard, it is consistent with our practical experience.Figure 3
Trend of controllability of ER network with the number of nodesN varying across 20,21,…,70.


### 4.2. WS Small-World Network

For comparison, we apply our controllability indexQ and driver nodes Nd to the other class of networks. The WS small-world model is one of complex networks with short average path lengths and high clustering [33]. The topology of the network is relatively homogeneous, meaning that all nodes are of similar degree. Roughly speaking, start with a nearest-neighbor coupled ring lattice withN nodes, in which each node is connected to its 2K neighboring nodes i±1,…,i±2,…,i±K,K on each side. Randomly rewire each link of the network with probabilityp such that self-connections and duplicated links are excluded.For WS small-world network model, it could been seen from Figure4 that when the number of nodesN and the coefficientK are fixed, the connectivity possibility varies from 0 to 1, which indicates that there is no direct relation between controllabilityQ andp. In other words, under this circumstance, the change of parameterp does not influence the controllability.Figure 4
Trend of controllability and drive nodes of WS small-world network withp varying across [0,1].SetN=30 and p=0.5, and letK change from 2 to 11. We can clearly see from the simulation results in Figure 5 thatK and controllability are negatively correlated. This means that the initial network with higher density edge and the controllability are relatively weak.Figure 5
Trend of controllability of WS small-world network withK varying across 2,2,…,11.Then we setK=2 and p=0.5. And whenN increases from 20 to 60, we can see from Figure 6 that the controllability decreases as the number of nodes increases. Therefore, we can conclude that the number of nodes and edges of this network are negatively correlated to the controllability.Figure 6
Trend of controllability of WS small-world network with the number of nodesN varying across 20,21,…,60.


### 4.3. BA Scale-Free Network

The algorithm of the BA scale-free model [34] is generated as follows. (1) Growth: starting with a small number (m0) of nodes, at every time step, add a new node with m (m<m0) edges that link the new node to m different nodes already presented in the network. (2) Preferential attachment: when choosing the nodes to which the new node connects, assume that the probability p(ki) that a new node will be connected to nodei depends on the degree ki of nodei, in such way that(17)pki=ki∑jkj.After t time steps, we get a network having N=t+m0 nodes andmtedges. This network evolves into a scale-invariant state with the probability that a node has edges following a power-law distribution. However, the degree distribution of BA model is heterogeneous.For the controllability of BA scale-free network model, firstly, let the start nodes numberm0=7; the connections of m0 nodes in the initial network are as follows: (1) both are isolated points; (2) constitute a complete graph; (3) randomly connect some edges. The number of new edges added to each node m varies across 2,3,…,6. When the number of added nodes t=8,10,12,14, the total numbers of nodesN are 15,17,19, and 21, respectively. The relationship between the controllability index of the network andmis shown in Figure 7.Figure 7
Trend of controllability of BA scale-free network with the number of new edges added to each nodem varying across 2,3,…,6. The controllability of the network when N=15,17,19,21.In Figure7, the simulation shows that when the number of nodesN is relatively small (N=15,17), the controllabilityQ is positively correlated tom (the number of new edges added when one node is connected to the previous network). However, as the number of added nodes (N=19,21) increases, the controllability becomes negatively correlated with m as shown in Figure 7.When settingm0=10 and m=3, let the number of added nodes t change from 10 to 70. Thus, the number of nodes N in the BA scale-free network varies across 20,21,…,80. For each case, the average controllability index of 1000 trials is recorded and shown in Figure 8. As can be seen from the simulation results, as the number of nodes increases (i.e., the size of the network increases), the controllability index Q decreases. This indicates that the controllability of large-scale networks is quite weak.Figure 8
Trend of controllability of BA scale-free network with the number of nodesN varying across 20,21,…,80.


## 4.1. ER Network

Liu et al. [18] proved that the minimum number of nodes that the input signals are injected into, called driver nodes, could be determined by detecting the “maximum matching” in the network. A maximum matching is the maximum set of links that do not share start or end nodes. A node is said to be matched if a link of the maximum matching points at it; otherwise, it is unmatched. If the nodes in a network are all matched, then the network is perfectly matched and the number of driver nodes Nd is 1; otherwise, Nd=N-NM, where NM is the number of matched nodes. The ratio of driving nodes to total number of nodes can be used to measure controllability of the network. Here, we compare the quantitative indexQ with that of the number of driver nodes Nd as shown in Figure 2.Figure 2
Trend of controllability and drive nodes of ER network with connectivity probabilityp varying across 0,1.Consider the ER network with twenty nodes,N=20; each time one of the nodes is controlled separately. Let the connectivity probabilityp vary across [0,1]. Here we show the variation of controllability indexQ with connection probability p in Figure 2. Every data in the figure has been calculated 1000 times and we took the average value.We can see from Figure2 that, for small connecting probability p<0.2, controllability index Q increases with p and reaches the maximum at around p≈0.2. Meanwhile, for higher link density p>0.2,Q begins to decrease with connection probabilityp. However, according to the red line in Figure 2, when p<0.2, the number of driver nodes decreases and the connection possibilityp increases. The number of drive nodes is larger for smaller connection probability p, indicating the weak controllability of the network because more nodes need to be controlled. When 0.2<p<0.8, the number of driver nodes basically remains the same when the connection possibility increases. And when p>0.8, the number of driver nodes increases with the increase of the connection possibilityp, which indicates that the controllability is weaker in the meantime. Besides, the closer the network is to the complete graph, the more nodes need to be controlled and then the lower the controllability is. From the comparison ofQ and Nd, it is not hard to find out that, for the same ER networks, the controllability variation trend is basically the same. IndexQ is positively correlated to the controllability, while Nd is a negative correlation coefficient of controllability.Then we fix the connection probabilityp=0.2 and let the number of nodes N vary across 20,21,…,70. The variation of controllability index Q with the number of nodes N is shown in Figure 3. We can see from Figure 3 that, for the ER network model, the controllability indexQ of the network decreases and the number of nodesN increases. In addition, the indexQ is very poor for the network with the large number of nodes, which indicates that when the number of the nodes of the network is huge, the controllability is low and the whole network is relatively hard to control. In this regard, it is consistent with our practical experience.Figure 3
Trend of controllability of ER network with the number of nodesN varying across 20,21,…,70.


## 4.2. WS Small-World Network

For comparison, we apply our controllability indexQ and driver nodes Nd to the other class of networks. The WS small-world model is one of complex networks with short average path lengths and high clustering [33]. The topology of the network is relatively homogeneous, meaning that all nodes are of similar degree. Roughly speaking, start with a nearest-neighbor coupled ring lattice withN nodes, in which each node is connected to its 2K neighboring nodes i±1,…,i±2,…,i±K,K on each side. Randomly rewire each link of the network with probabilityp such that self-connections and duplicated links are excluded.For WS small-world network model, it could been seen from Figure4 that when the number of nodesN and the coefficientK are fixed, the connectivity possibility varies from 0 to 1, which indicates that there is no direct relation between controllabilityQ andp. In other words, under this circumstance, the change of parameterp does not influence the controllability.Figure 4
Trend of controllability and drive nodes of WS small-world network withp varying across [0,1].SetN=30 and p=0.5, and letK change from 2 to 11. We can clearly see from the simulation results in Figure 5 thatK and controllability are negatively correlated. This means that the initial network with higher density edge and the controllability are relatively weak.Figure 5
Trend of controllability of WS small-world network withK varying across 2,2,…,11.Then we setK=2 and p=0.5. And whenN increases from 20 to 60, we can see from Figure 6 that the controllability decreases as the number of nodes increases. Therefore, we can conclude that the number of nodes and edges of this network are negatively correlated to the controllability.Figure 6
Trend of controllability of WS small-world network with the number of nodesN varying across 20,21,…,60.


## 4.3. BA Scale-Free Network

The algorithm of the BA scale-free model [34] is generated as follows. (1) Growth: starting with a small number (m0) of nodes, at every time step, add a new node with m (m<m0) edges that link the new node to m different nodes already presented in the network. (2) Preferential attachment: when choosing the nodes to which the new node connects, assume that the probability p(ki) that a new node will be connected to nodei depends on the degree ki of nodei, in such way that(17)pki=ki∑jkj.After t time steps, we get a network having N=t+m0 nodes andmtedges. This network evolves into a scale-invariant state with the probability that a node has edges following a power-law distribution. However, the degree distribution of BA model is heterogeneous.For the controllability of BA scale-free network model, firstly, let the start nodes numberm0=7; the connections of m0 nodes in the initial network are as follows: (1) both are isolated points; (2) constitute a complete graph; (3) randomly connect some edges. The number of new edges added to each node m varies across 2,3,…,6. When the number of added nodes t=8,10,12,14, the total numbers of nodesN are 15,17,19, and 21, respectively. The relationship between the controllability index of the network andmis shown in Figure 7.Figure 7
Trend of controllability of BA scale-free network with the number of new edges added to each nodem varying across 2,3,…,6. The controllability of the network when N=15,17,19,21.In Figure7, the simulation shows that when the number of nodesN is relatively small (N=15,17), the controllabilityQ is positively correlated tom (the number of new edges added when one node is connected to the previous network). However, as the number of added nodes (N=19,21) increases, the controllability becomes negatively correlated with m as shown in Figure 7.When settingm0=10 and m=3, let the number of added nodes t change from 10 to 70. Thus, the number of nodes N in the BA scale-free network varies across 20,21,…,80. For each case, the average controllability index of 1000 trials is recorded and shown in Figure 8. As can be seen from the simulation results, as the number of nodes increases (i.e., the size of the network increases), the controllability index Q decreases. This indicates that the controllability of large-scale networks is quite weak.Figure 8
Trend of controllability of BA scale-free network with the number of nodesN varying across 20,21,…,80.


## 5. Conclusions and Further Work

In this paper, we mainly discussed the problem of quantitative measurement controllability for arbitrary given network. A quantitative index is presented based on the control centrality and conditional number of the controllability matrix of controllable network (or subnetwork) system. And the index can quantitatively measure the controllability of each node in a given network. The effect of this controllability index is observed and discussed mainly by a series of experiments on various types of networks, namely, E–R networks, WS small-world networks, and BA scale-free networks. For ER networks, the controllability of networks increases with the increase of connection probability p; however, when p reached a certain value, the controllability will decrease with the increase of connection probability. Besides, the controllability of the network is negatively correlated with the number of nodes when the connectivity probability is fixed, so the controllability of the large-scale network is poor. For WS small-world network model, the controllability of the network is negatively correlated to both K and the number of nodes. For the BA scale-free network, due to the different number of new edges added when one node is trying to connect to the previous network, the controllability of the network presents different trends, and specific reasons of this phenomenon need to be further studied. These findings can help us better understand the relationship between controllability and network topology.Much work still remains to be done concerning the controllability issue of complex networks. There still exist abundant potential future extensions:(1) How to apply this index to larger network? Our method has been estimated using MATLAB R2014a, which can execute the network with 1000 nodes for an hour. When the number of nodes in the network increases to a large complex network with millions of nodes, it is necessary to further optimize the algorithm and rewrite programs in C language or any other language to reduce the complexity of the algorithm and improve the computing speed. (2) The measuring controllability index of this paper proposed is mainly based on given complex networks and linear time-invariant dynamic systems. It cannot be directly applied to the time-dynamic complex networks. Should this index be used on time-variant networks, we need to consider whether under this circumstance the “control centrality” could reflect the dimensional change of controllable subsystems and whether conditional number can still measure the singularity of matrix. These questions need further consideration. (3) Further research can be made to compare the controllability between complex networks with different topology. (4) More experiments can be conducted to discover more empirical regularities of real-world networks. (5) Certain phenomenon observed could be explained analytically or even mathematically. To be brief, the current complex network research continues to develop, but it also faces many problems that needed to be solved. How to apply these theoretical concepts and equations into practice is also of great significance in future studies.



---

*Source: 2586536-2018-10-22.xml*