# Algorithm for Identifying Minimum Driver Nodes Based on Structural Controllability

Authors: Reza Haghighi; HamidReza Namazi
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Existing methods on structural controllability of networked systems are based on critical assumptions such as nodal dynamics with infinite time constants and availability of input signals to all nodes. In this paper, we relax these assumptions and examine the structural controllability for practical model of networked systems. We explore the relationship between structural controllability and graph reachability. Consequently, a simple graph-based algorithm is presented to obtain the minimum driver nodes. Finally, simulation results are presented to illustrate the performance of the proposed algorithm in dealing with large-scale networked systems.


---

## Body

## 1. Introduction

Advances in communications technology have opened up new challenges in the area of networked systems. Controllability of multiagent networked systems as a fundamental concept in this field has received considerable attention. The pioneer work in analysing controllability of multiagent systems with leader-follower architecture had been carried out by Tanner [1], where controllability conditions were provided for multiagent systems with undirected graph topology based on eigenvectors of the Laplacian matrix. In further development, some algebraic conditions for controllability of multiagent systems are presented in [2, 3]. Ji and Egerstedt [4] introduced network equitable partitions to present a necessary condition for the controllability of leader-follower multiagent systems. Inspired by [4], Rahmani et al. [5] proposed the controllability of multiagent systems with multiple leaders. Liu et al. [6] derived a simple controllability condition for discrete-time single-leader switching networks, which was further extended to continuous-time single-leader switching networks [7]. Ji et al. [8] derived a necessary and sufficient condition for the controllability of leader-follower multiagent systems, by dividing the overall system into several connected components. The other related topics in this area are leader-follower consensus [9, 10], leader-follower formation control [11–13], containment control [14, 15], and pinning-controllability of networked systems [16, 17].The concept of structural controllability has been studied extensively since the classical work by Lin [18]. In [18], structural controllability of SISO linear systems was explored by introducing a notion of structured matrix whose elements are either fixed zeros or independent free parameters. Shields and Pearson [19] extended the results of  [18] to structural controllability of multiinput linear systems. Since then various works have been carried out on the structural controllability of linear systems [20–22]. Recently, structural controllability of networked systems has emerged as a major interest in the network sciences. A notable work in this area is carried out by Liu et al. [23] which addressed the structural controllability of complex networks. Jafari et al. [24] studied structural controllability of a leader-follower multiagent system with multiple leaders. Sundaram and Hadjicostis [25] developed a graph-theoretic characterization of controllability and observability of linear systems over finite fields. Haghighi and Cheah [26] employed the concept of structural observability to examine the weight-balanceability of networked systems.For large-scale networked systems, it is infeasible to apply input signals to all network nodes due to the high control cost and the difficulty of practical implementations. In this case, a fundamental problem is to identify a certain amount of nodes to be driven externally to bring the whole network under control. This problem was addressed in [23], where a theoretical framework was developed to solve the minimum input problem based on Lin’s structural controllability theorem [18]. As pointed out in [27], the results in [23] are based on the assumption that each node has an infinite time constant, which do not generally represent the dynamics of the physical and biological systems.Despite the model in [23], Cowan et al. [27] considered internal dynamics for all nodes of the network. Cowan’s result states that structural controllability does not depend on degree distribution. Hence, the structural controllability can always be conferred with a single independent control input. However, the result in [27] suffers from a drawback that each independent input is connected to all nodes in the network, which is practically infeasible.In this paper, we examined the structural controllability in networked systems by relaxing the critical assumptions in previous results. Consequently, we provide a graph-theoretic method to identify driver nodes. We present an algorithm to determine minimum driver nodes in networked systems. The contribution of this paper is twofold: (i) we relaxed the assumptions in existing methods, such as infinite time constant for each node, and having direct access to input signals by all nodes, on structural controllability of networked systems. (ii) We provide a simple algorithm to obtain minimum driver nodes in networked systems.The paper is organized as follows. Section2 presents some preliminaries in graph theory and controllability. Section 3 presents the model of the networked systems. Section 4 addresses the structural controllability in networked systems and presents the linkage between the structural controllability and the graph reachability in networked systems. An algorithm for identifying minimum driver nodes in networked systems is proposed in Section 5. Section 6 presents the simulation results and Section 7 concludes this paper.


## 2. Preliminaries

The communication between nodes can be expressed by a weighted directed graphG(V,E,A), such that V=v1,v2,…,vN represents the set of nodes, E⊆V×V is the edge set, and A=[aij] is the weighted adjacency matrix where aij>0 if (i,j)∈E and aij=0 otherwise. A graph H is said to be a subgraph of a graph G if V(H)⊆V(G) and E(H)⊆E(G).A directed path in a digraph is an ordered sequence of nodes so that any two consecutive nodes in the sequence are an edge of the digraph. An undirected graph is a tree if and only if, for any two nodes, there is a unique path connecting them. A directed spanning tree or arborescence is a digraph such that there is a unique directed path from a designated root node to every other node.Definition 1.
A digraphG is called an arborescence diverging from node u, if there is only one directed path between root u and any other node of G. If G is an arborescence diverging from u, then its reverse digraph (i.e., all edges of G are reversed) is called an arborescence converging to u [28].If there is an arborescence subdigraph diverging from an arbitrary nodeu, then u is called a globally reachable node.Definition 2.
Driver nodes are nodes in a network that have to be controlled in order to completely control the entire network.Definition 3.
A matrixAs is said to be a structured matrix if its elements are either fixed zeros or independent free parameters [29].Definition 4.
Two dynamical systems are called structurally equivalent, if their interconnection structures are identical. Hence, we can say(A,B) has the same structure as (A1,B1), if for every fixed zero entry of the matrix AB, the corresponding entry of the matrix A1B1 is fixed zero and vice versa.Definition 5.
The structural rank (srank) of a matrix is the maximum rank of all structurally equivalent matrices [30].Theorem 6 (controllability test [31]).
(
A
n
×
n
,
B
n
×
m
) is controllable if and only if there is no left eigenvector of A that is orthogonal to B; that is,(1)∀wwherewTA=λwT⟹wTB≠0.Theorem 7 (Popov-Belevitch-Hautus controllability test [32]).
(
A
n
×
n
,
B
n
×
m
) is controllable if and only if(2)
R
a
n
k
⁡
λ
I
-
A
B
=
n
,where λ is an eigenvalue of A.


## 3. Model of Interconnected Networks

We consider each node in the network corresponding to a dynamical system, governed by the following equation:(3)x˙i=-aiixi+∑j=1j≠iNaijxj+biui,where xi∈R denotes the state of node i, N is the total number of nodes, and ui denotes an external input.Interconnected system (3) can be represented in matrix form(4)x˙=Ax+Bu,where x=[x1,x2,…,xN]T, u=[u1,u2,…,um]T, B∈RN×m is input matrix, and A∈Rn×n is defined as A=A-D, where A is the adjacency matrix and D=diag⁡{a11,a22,…,aNN}.


## 4. Controllability and Graph Reachability

According to classical control theory, a dynamical system is controllable if for any initial state there exists an input that can drive the system to any final state in a finite time. It is well known that the system (A,B) is controllable if and only if the following controllability matrix:(5)C=B,AB,…,AN-1Bhas full rank. Even though a system with a pair of (A,B) might be uncontrollable, it can be controllable for another structurally equivalent pair (A∗,B∗) [18].Definition 8.
A dynamical system(A,B) is structurally controllable if there exists a structurally equivalent system (A∗,B∗) that is controllable [33].In what follows, we first consider network with single driver node and present the relation between graph reachability and controllability.


### 4.1. Controllability of Networks with Single Driver Node

Consider a network of nodes with single driver node,i, which is expressed as follows:(6)x˙=Ax+Bu,where B=0,…,0,bi,0,…,0︸ithelementT. To examine the controllability, we form the following zero-state response:(7)xt=∫0teAt-τBuτdτ.The term eA(t-τ)B refers to the ith column of the matrix eA(t-τ) multiplied by bi. Using Cayley-Hamilton theorem, eA(t-τ) can be expanded as follows:(8)eAt-τ=∑i=0N-1αit-τAi,where αi(·) are scalar functions. We state the following theorem.Theorem 9.
Consider the network expressed by (6). The network is structurally controllable if and only if there is an arborescence subdigraph diverging from driver node i.Proof (necessity condition).
According to LemmaA.1 in the Appendix, the (j,i)th element of matrix series (8) is zero, if there is no path from node i to node j. In this case, the jth element of the eA(t-τ)B is zero and remains zero for all values of the network link weights; therefore at least x∗=0,…,0,α,0,…,0︸jthelementT is an uncontrollable state of the system.
Sufficiency Condition. We show that a network, which contains an arborescence subdigraph diverging from its driver node, is structurally controllable. Without loss of generality, we assume that node 1 is the driver node. In structural controllability, independent nonzero parameters can take any values including zero. Hence, we zero out the weights for redundant links in such a way that the digraph associated with the network becomes an arborescence diverging from the driver node.
MatricesA and B in (4) for an arborescence diverging from driver node can be expressed as follows:(9)A=-a110⋯0a21-a22⋮⋮⋮⋱0aN1aN2⋯-aNN,B=b10⋯0T.Let wi=w1i,…,wNiT be the left eigenvector associated with eigenvalue λi. Using Theorem 6, we have(10)wiTB≠0⟺w1ib1≠0⟺w1i≠0.Therefore, to show that the network is structurally controllable, we need to prove the existence of weights such that w1i≠0, for i=1,…,N. To do so, let aii be a strictly monotonic sequence for i=1,…,N. Since A is triangular matrix with distinct diagonal entries, eigenvalues of A are its diagonal entries; that is, λi=-aii for i=1,…,N. Therefore, we obtain w1i by solving wiTA=λiwi as follows:(11)λ1=-a11⟹w11=1,λ2=-a22⟹w12=a21a11-a22,λ3=-a33⟹w13=a31a11-a33+a32a21a22-a33a11-a33⋮λN=-aNN⟹w1N=aN1a11-aNN+∑l1=2N-1aNl1al11al1l1-aNNa11-aNN+∑l1=3N-1∑l2=2l1-1aNl1al1l2al21al1l1-aNNal2l2-aNNa11-aNN⋮+∑l1=N-1N-1⋯∑lN-1=2lN-2-1aNl1al1l2⋯alN-11al1l1-aNN⋯alN-1lN-1-aNNa11-aNN.Since all the denominators of (11) have the same sign and w1i for i=1,…,N can be expressed as(12)w1i=α11ai1+∑l1=1i-1α2l1ail1al11︸path  of  length2  from  1  toi+∑l1=1i-1∑l2=1l1-1α3l1l2ail1al1l2al21︸path  of  length3  from  1  toi+⋯+∑l1=i-1i-1⋯∑li-1=2li-2-1αi-11ail1al1l2⋯ali-11︸pathoflengthi-1from1toi,where αkl are same sign scalars for different values of k and l. Existence of arborescence diverging from node 1 guarantees that w1i≠0. Hence, wiB≠0 for i=1,…,N.
Since an arborescence diverging from the driver node is structurally controllable, we can conclude that any networked system which contains an arborescence subdigraph diverging from the driver node is structurally controllable.Corollary 10.
A network with a globally reachable driver node is structurally controllable.In the above, we examine networks with single driver node. In what follows, we generalize the result for networks with multiple driver nodes.


### 4.2.  Controllability of Networks with Multiple Driver Nodes

Consider a network of nodes with multiple driver nodes, which is expressed as follows:(13)x˙=Ax+Bu,where B=rdiag⁡{b1,b2,…,bm}∈RN×m, where rdiag⁡{·} refers to the rectangular diagonal matrix and br are positive scalars. The following theorem expresses the controllability condition in networks with multiple driver nodes.Theorem 11.
Consider the network expressed by (13) which consists of multiple driver nodes. The network is structurally controllable if and only if there is a path from at least one driver node to any arbitrary node.Proof.
For simplicity, we assume that nodesi=1,…,m are driver nodes of the network. Hence matrix B can be expressed as follows:(14)B=b10⋯00b2⋮⋮⋱00⋯0bm0N-m×m.
Necessity Condition. We assume that there is node j and that there is no path from any input node to that node. According to Lemma A.1 in the Appendix, matrix series (8) has zero elements in columns 1 to m of row j. Therefore, eA(t-τ)B has zero row j, which yields existence of x∗=0,…,0,α,0,…,0︸jthelementT as an uncontrollable state of the system.
Sufficiency Condition. We assume that the network contains m driver nodes. By zeroing out the weights of redundant links, we decompose the network into m components such that driver node k controls over nodes of component k. Hence, matrices A and B can be expressed as follows:(15)A=A10⋱0Am,B=B10⋱0Bm.If lth node in kth component is driver node, we have Bk=[0,…,0,bk,0,…,0︸lthelement]T for k=1,…,N. Using Theorem 7, we obtain(16)
R
a
n
k
λ
I
-
A
B
=
R
a
n
k
λ
I
1
-
A
1
B
1
0
⋱
0
λ
I
m
-
A
m
B
m
,where Ik are identity matrices with the same size as Ak for k=1,…,N. Using Theorem 9, for an arbitrary component k, λIk-AkBk is full row-rank. Since λI-AB is block diagonal matrix with full row-rank block matrices, therefore(17)
R
a
n
k
⁡
λ
I
-
A
B
=
N
.For better underdressing, in what follows, we compare the proposed structural controllability condition and Liu’s structural controllability condition. An example of Liu’s structural controllability is presented in Figure1. It is shown that controlling node 1 is not sufficient for full control (see Figure 1(a)). To gain full control, we must simultaneously control node 1 and any node among x2,x3 (see Figure 1(b)). In contrast, in the proposed structural controllability (see Figure 2), controlling node 1 is sufficient for full control over the networked system.Figure 1
An example of Liu’s structural controllability.
(a)
(b)Figure 2
An example of the proposed structural controllability.


## 4.1. Controllability of Networks with Single Driver Node

Consider a network of nodes with single driver node,i, which is expressed as follows:(6)x˙=Ax+Bu,where B=0,…,0,bi,0,…,0︸ithelementT. To examine the controllability, we form the following zero-state response:(7)xt=∫0teAt-τBuτdτ.The term eA(t-τ)B refers to the ith column of the matrix eA(t-τ) multiplied by bi. Using Cayley-Hamilton theorem, eA(t-τ) can be expanded as follows:(8)eAt-τ=∑i=0N-1αit-τAi,where αi(·) are scalar functions. We state the following theorem.Theorem 9.
Consider the network expressed by (6). The network is structurally controllable if and only if there is an arborescence subdigraph diverging from driver node i.Proof (necessity condition).
According to LemmaA.1 in the Appendix, the (j,i)th element of matrix series (8) is zero, if there is no path from node i to node j. In this case, the jth element of the eA(t-τ)B is zero and remains zero for all values of the network link weights; therefore at least x∗=0,…,0,α,0,…,0︸jthelementT is an uncontrollable state of the system.
Sufficiency Condition. We show that a network, which contains an arborescence subdigraph diverging from its driver node, is structurally controllable. Without loss of generality, we assume that node 1 is the driver node. In structural controllability, independent nonzero parameters can take any values including zero. Hence, we zero out the weights for redundant links in such a way that the digraph associated with the network becomes an arborescence diverging from the driver node.
MatricesA and B in (4) for an arborescence diverging from driver node can be expressed as follows:(9)A=-a110⋯0a21-a22⋮⋮⋮⋱0aN1aN2⋯-aNN,B=b10⋯0T.Let wi=w1i,…,wNiT be the left eigenvector associated with eigenvalue λi. Using Theorem 6, we have(10)wiTB≠0⟺w1ib1≠0⟺w1i≠0.Therefore, to show that the network is structurally controllable, we need to prove the existence of weights such that w1i≠0, for i=1,…,N. To do so, let aii be a strictly monotonic sequence for i=1,…,N. Since A is triangular matrix with distinct diagonal entries, eigenvalues of A are its diagonal entries; that is, λi=-aii for i=1,…,N. Therefore, we obtain w1i by solving wiTA=λiwi as follows:(11)λ1=-a11⟹w11=1,λ2=-a22⟹w12=a21a11-a22,λ3=-a33⟹w13=a31a11-a33+a32a21a22-a33a11-a33⋮λN=-aNN⟹w1N=aN1a11-aNN+∑l1=2N-1aNl1al11al1l1-aNNa11-aNN+∑l1=3N-1∑l2=2l1-1aNl1al1l2al21al1l1-aNNal2l2-aNNa11-aNN⋮+∑l1=N-1N-1⋯∑lN-1=2lN-2-1aNl1al1l2⋯alN-11al1l1-aNN⋯alN-1lN-1-aNNa11-aNN.Since all the denominators of (11) have the same sign and w1i for i=1,…,N can be expressed as(12)w1i=α11ai1+∑l1=1i-1α2l1ail1al11︸path  of  length2  from  1  toi+∑l1=1i-1∑l2=1l1-1α3l1l2ail1al1l2al21︸path  of  length3  from  1  toi+⋯+∑l1=i-1i-1⋯∑li-1=2li-2-1αi-11ail1al1l2⋯ali-11︸pathoflengthi-1from1toi,where αkl are same sign scalars for different values of k and l. Existence of arborescence diverging from node 1 guarantees that w1i≠0. Hence, wiB≠0 for i=1,…,N.
Since an arborescence diverging from the driver node is structurally controllable, we can conclude that any networked system which contains an arborescence subdigraph diverging from the driver node is structurally controllable.Corollary 10.
A network with a globally reachable driver node is structurally controllable.In the above, we examine networks with single driver node. In what follows, we generalize the result for networks with multiple driver nodes.


## 4.2.  Controllability of Networks with Multiple Driver Nodes

Consider a network of nodes with multiple driver nodes, which is expressed as follows:(13)x˙=Ax+Bu,where B=rdiag⁡{b1,b2,…,bm}∈RN×m, where rdiag⁡{·} refers to the rectangular diagonal matrix and br are positive scalars. The following theorem expresses the controllability condition in networks with multiple driver nodes.Theorem 11.
Consider the network expressed by (13) which consists of multiple driver nodes. The network is structurally controllable if and only if there is a path from at least one driver node to any arbitrary node.Proof.
For simplicity, we assume that nodesi=1,…,m are driver nodes of the network. Hence matrix B can be expressed as follows:(14)B=b10⋯00b2⋮⋮⋱00⋯0bm0N-m×m.
Necessity Condition. We assume that there is node j and that there is no path from any input node to that node. According to Lemma A.1 in the Appendix, matrix series (8) has zero elements in columns 1 to m of row j. Therefore, eA(t-τ)B has zero row j, which yields existence of x∗=0,…,0,α,0,…,0︸jthelementT as an uncontrollable state of the system.
Sufficiency Condition. We assume that the network contains m driver nodes. By zeroing out the weights of redundant links, we decompose the network into m components such that driver node k controls over nodes of component k. Hence, matrices A and B can be expressed as follows:(15)A=A10⋱0Am,B=B10⋱0Bm.If lth node in kth component is driver node, we have Bk=[0,…,0,bk,0,…,0︸lthelement]T for k=1,…,N. Using Theorem 7, we obtain(16)
R
a
n
k
λ
I
-
A
B
=
R
a
n
k
λ
I
1
-
A
1
B
1
0
⋱
0
λ
I
m
-
A
m
B
m
,where Ik are identity matrices with the same size as Ak for k=1,…,N. Using Theorem 9, for an arbitrary component k, λIk-AkBk is full row-rank. Since λI-AB is block diagonal matrix with full row-rank block matrices, therefore(17)
R
a
n
k
⁡
λ
I
-
A
B
=
N
.For better underdressing, in what follows, we compare the proposed structural controllability condition and Liu’s structural controllability condition. An example of Liu’s structural controllability is presented in Figure1. It is shown that controlling node 1 is not sufficient for full control (see Figure 1(a)). To gain full control, we must simultaneously control node 1 and any node among x2,x3 (see Figure 1(b)). In contrast, in the proposed structural controllability (see Figure 2), controlling node 1 is sufficient for full control over the networked system.Figure 1
An example of Liu’s structural controllability.
(a)
(b)Figure 2
An example of the proposed structural controllability.


## 5. Algorithm for Identifying Minimum Driver Nodes

We have shown the relationship between the structural controllability and graph reachability. Thus the problem of examining the structural controllability of the networked systems described by (5) can be converted into graph reachability problem. Here, we are interested in determining the minimum number of driver nodes in a directed network, denoted by ND, to obtain controllability over the networked systems. However, difficulties in identifying minimum number of driver nodes in large-scale networks lead to the requirement for a simple systematic method. In what follows, we propose a simple algorithm to determine the minimum number of driver nodes using graph reachability approach.To check the graph reachability between each two arbitrary nodes, we present the following theorem.Theorem 12.
Consider a network of nodes with an associated structured adjacency matrixAs. For any two arbitrary nodes i and j, if (j,i)th element of the matrix I-Ast-1 is zero, then there is no path from node i to node j, where I is an identity matrix and t is a positive constant such that the spectral radius of Ast is less than 1.Proof.
To prove this theorem, we first use the Taylor series expansion of the matrix inverse (see LemmaA.3 in the Appendix). Consider(18)I-Ast-1=∑i=0∞tiAsi.Using Lemma A.2, Askji for k=1,2,…,∞ is zero if and only if there is no path from node i to node j. Hence, the zeroness of the (j,i)th entry of Ask for k=1,2,…,∞ leads to the zeroness of the (j,i)th entry of I-Ast-1.Remark 13.
Using Gershgorin’s theorem [34], the suitable t which satisfies the condition in Theorem 12 is obtained as follows:(19)t=maxi∑j=1j≠iNaij-1-ɛ,where ɛ is a small number.To illustrate the result in Theorem12, let us consider the network in Figure 3.Figure 3
An example of a network with 4 nodes.The associated structured matrix can be defined as Boolean matrix as follows:(20)As=0111000111010100.From (19), we obtain t=0.1. Therefore, matrix I-Ast-1 is obtained in structured format as follows:(21)∗∗∗∗0∗0∗∗∗∗∗0∗0∗,where ∗ represents nonzero parameters such that in matrix (21), for example, entry (4,1) is zero, which means that there is no path from node 1 to node 4. Since the network is small, driver nodes in Figure 3 can be easily identified, which are either node 2 or node 4. The same result can be obtained by examining I-Ast-1. In matrix (21), columns full of nonzero elements represent globally reachable nodes. For columns which contain zero elements, we definegraph reachability index as follows.Definition 14.
Nodeu is said to have graph reachability index r, if there are paths from u to maximum r, other nodes of the network.Therefore, we can express the following corollary.Corollary 15.
In matrixI-At-1, columns with higher nonzero elements represent nodes with higher graph reachability index.We can deduce that nodes with higher graph reachability index are suitable to be assigned as driver nodes.Remark 16.
To find the minimum driver nodes to obtain a structurally controllable network, we start by assigning the node with the highest graph reachability index as the driver node. Then, we remove all the nodes that are in the path rooted for the assigned driver node. We repeat the above procedure for the remaining network till the condition in Theorem11 is satisfied.Using the above mentioned results, we present a systematic algorithm to identify the minimum driver nodes in a networked system such that the structural controllability of the network is guaranteed. The algorithm for determining the minimum driver nodes of the network is described as follows.Consider graphG with the associated structured adjacency matrix As,Step 1.
Compute graph reachability matrixS=IN-Ast-1.Step 2.
Identify the node with the highest graph reachability index by finding the columns of matrixS with the largest nonzero elements. If there is more than one node with the highest graph reachability index, we can randomly choose one of them.Step 3.
Assign that node as the driver node and zero out all the rows with the nonzero elements in the column associated with that driver node.Step 4.
Go back to Step2 and repeat the procedure till all elements of matrix S are zero.The above procedure is expressed in Algorithm1.Algorithm 1:Finding driver nodes in each connected component.
Input:As;
Method:
(1) Compute t from (19);
(2) Compute graph reachability matrix S=IN-Ast-1;
(3) k=0;
(4) whilemax⁡(any(S))≠0do
(5) k=k+1;             %k represents the number of driver nodes.
(6) v=sum(S≠0,1);       %v represents the vector of the number of nonzero elements in each column.
(7) [value,ind]=max⁡(v);     %ind represents the column with the largest graph reachability index.
(8) Dnode(k)=ind;       %Dnode represents the array of driver nodes.
(9) w=find(S(:,ind));     %w represents the rows with nonzero elements in the driver node column.
(10)   S(w,:)=0;
(11) end whileRemark 17.
It should be noted that the set of minimum driver nodes is usually not unique depending on the network configurations, and one can determine other sets with the same number of driver nodes.


## 6. Simulations

In this section, we present simulation results to illustrate the performance of the proposed method for networked systems of various sizes and topologies. For the numerical calculations and simulations, we used MATLAB software. For illustration purpose, we first consider a network with 30 nodes which are distributed randomly as depicted in Figure4. The weights of links are randomly selected from [0,1]. We compute I-At-1, where A is the associated Laplacian matrix. The sparsity pattern of matrix I-At-1 is plotted in Figure 5, where the blue solid circles represent nonzero elements of the matrix. Applying the proposed algorithm, the driver nodes of the network are identified by magenta circles in Figure 6. The result of the first simulation is summarized in Table 1, where N is the number of nodes, L is the number of links, ND is the computed number of driver nodes, and nd is the computed density of driver nodes obtained by nd=Nd/N.Table 1
The characteristics of the network represented in Figure6.
N
L
N
D
n
d
30
41
6
0.2Figure 4
An example of a network consisting of 30 nodes.Figure 5
The sparsity pattern of matrixI-At-1.Figure 6
Driver nodes of the network identified by magenta circles.To illustrate the capability of the purposed algorithm in dealing with large-scale networks, we consider a network of 1000 nodes which are distributed randomly within a square region as shown in Figure7. The communication links are generated between neighboring nodes with the probability of 0.5. The weights of links are randomly selected from [0,1]. The sparsity pattern of matrix I-At-1 is plotted for the network in Figure 8. Applying the proposed algorithm, the driver nodes of the network are identified by magenta circles in Figure 9. The result of the second simulation is summarized in Table 2.Table 2
The characteristics of the network represented in Figure9.
N
L
N
D
n
d
1000
1361
96
0.096Figure 7
An example of a network consisting of 1000 nodes.Figure 8
The sparsity pattern of matrixI-At-1.Figure 9
Driver nodes of the network identified by magenta circles.We applied the proposed algorithm on some randomly generated networks, and the results are illustrated in Table3.Table 3
The characteristics of some randomly generated networks.
N
L
N
D
n
d
2000
2929
128
0.0640
5000
6931
408
0.0816
10000
13951
748
0.0748


## 7. Conclusion

In this paper, we have addressed the structural controllability problem for networked systems. Despite the existing methods governed by some impractical assumptions on nodal dynamics and availability of input signals, we have examined structural controllability for networked systems in practical framework. Using controllability analysis, we have presented the connection between networks driver nodes and graph reachability. Consequently, based on results on graph reachability, we have put forward a simple algorithm to determine minimum driver nodes in networked systems. Finally, simulation results have been presented to illustrate the performance of the proposed methods.



---

*Source: 192307-2015-10-11.xml*