# Optimizing Network Controllability with Minimum Cost

Authors: Xiao Wang; Linying Xiang
Journal: Complexity
 (2021)

---

## Abstract

In this paper, the issue of optimally modifying the structure of a directed network to guarantee its structural controllability is investigated. Given a directed network, in order to obtain a structurally controllable system, a framework for finding the minimum number of directed edges that need to be added to the network is proposed. After we get these edge-addition configurations, we further calculate the network cost of each optimization scheme and choose the one with the minimum cost. Our main contribution is twofold: first, we provide an algorithm able to find all optimal network modifications in polynomial time; second, we provide a way to calculate the cost of optimizing the network based on the node betweenness. Numerical simulations are given to illustrate the theoretical results.


---

## Body

## 1. Introduction

The ultimate goal of complex network research is to find effective means to control network behavior and make it serve human beings. Controllability is a basic concept in control theory, which quantifies the ability to control a dynamical system from any initial state to any final state in finite time [1]. In the past decade, the issue of network controllability for complex dynamical systems has attracted increasing attention and becomes a focal topic in interdisciplinary research [2–30]. Numerous works have been reported from rather diverse perspectives on such topics as structural controllability [2, 3]; exact controllability [18]; edge dynamics [19–21]; optimization [22–24]; control energy [25, 26]; and robustness [27, 28].In the study of network controllability, we usually rely on the theory of structural controllability [31–37]. If there is a matrix pair that is controllable, all structurally equivalent matrix pairs are controllable except for special ill-conditioned cases [31]. Recently, those results have been applied to the controllability analysis of directed complex networks [2, 3, 16, 19, 22, 23] from a graph-theoretic perspective. Note that it is very effective to analyze network controllability by using tools developed under the background of structural control theory [31].Optimization of the network controllability is of prime importance in real applications. Generally speaking, given a network which is structurally uncontrollable, we can make it structurally controllable through two strategies: (i) add external input signals to the original network [16] and (ii) add new edges to the network topology [23]. Wang et al. provided a method to change the structure of a complex network to make the system structurally controllable when only a single driver node was considered [22]. Zhang and Zhou considered three related problems on determining the minimal cost structural perturbations, including edge additions, edge deletions, and input deletions to make a networked system structurally controllable/uncontrollable [24]. Chen et al. proposed an approach to adding minimum directed edges to the original network so as to ensure structural controllability [23].Motivated by the above discussions, a minimum-cost optimization method to guarantee structural controllability is investigated in this paper. It should be emphasized that, differing from [23], in this work, a new method is proposed to optimize network topology and thus to ensure the network controllability. Moreover, it also provides a way to calculate the total cost of optimizing the network. However, in [23], it only gives a method to optimize the network topology without considering the optimization cost. Note that calculating the optimization cost is exactly the major point in this work. In [27], Zhang et al. considered the problem of network cost. Although the measurement index of edge cost was given therein, it did not provide a simple and effective method to calculate the total network cost. Compared with the previous works, we not only address the problem of optimizing network controllability but also propose a way to calculate the cost of optimizing the network. The main contributions of this article are as follows. (i) We propose a new method to optimize the network topology so as to ensure the network controllability. (ii) We propose an algorithm to solve the optimal edge-addition configuration problem. (iii) After getting all the edge-addition configurations, we introduce network cost measurement indexes to calculate the cost of optimizing the network. Based on which, we can determine the optimal edge-addition configuration with minimum-cost. The results of this paper can provide both theoretical and technical guidance for the analysis and control of real complex networks. The obtained results shed some lights on the transformation of a structurally uncontrollable network to a structurally controllable one with a low cost. For example, in the power network, transmission lines with the lowest cost can be set up among substations to safely and efficiently control the entire power network.The rest of the paper is organized as follows. Section2 introduces the notation and terminology used in this paper. Problem formulation and preliminaries on graph theory are introduced in Section 3. The main results are given in Section 4. In Section 5, a network cost index is given to determine the minimum-cost edge-addition configuration. Finally, the summary of this paper and the prospect of future research are presented in Section 6.


## 2. Notations

In this paper,ℝ denotes the set of real numbers, ℝm is the space of real m-vectors, and ℝm×n is the space of m×n real matrices. For a set S, its cardinality is denoted by S.A directed graphG=V,E consists of a node set V=1,2,…,n and an edge set E=i,j. Here, i,j∈E implies that there exists a directed edge from node i to node j, and i and j are called the parent node and the child node, respectively. We can also say that the tail node i is pointing toward the head node j. For a digraph G, a directed path of length k+1 from node i to node j is defined as a sequence of distinct edges of the form i,i1,i1,i2,…,ik,j, in which all nodes i,i1,…,ik,j are distinct. Here, node i is called the beginning node and j the end node of the directed path. A node i2∈V is reachable from i1∈V if there exists a directed path in G from i1 to i2. A directed graph Gs=Vs,Es is a subgraph of G if Vs⊆V and Es⊆E. A directed graph is said to be strongly connected if there exists a directed path between any two nodes. A strongly connected component (SCC) is a maximal subgraph Gs that is strongly connected. Particularly, a source SCC has no incoming edges from another SCC.A digraphG contains a dilation if there is a subset of nodes S⊂V such that the common-neighbor set of S, denoted by TS, has fewer nodes than S itself, i.e., TS<S. Here, TS is the set of nodes j, in which there is a directed edge from node j to some other node in S. Notice that a digraph G contains no dilation if each node has its own independent parent node. It is intuitively plausible that a dilation is a subgraph containing a relatively large number of nodes that are “dominated” by a small number of other nodes.


## 3. Problem Statement and Preliminaries

Consider a linear time-invariant (LTI) networked dynamical system described by(1)x˙t=Axt+But,where xt=x1t,x2t,…,xntT∈ℝn is the state vector of all nodes; ut=u1t,u2t,…,umtT∈ℝm is the input vector; B=bij∈ℝn×m is the input matrix identifying the nodes that are directly controlled, and A=aij∈ℝn×n is the adjacency matrix of the underlying network. The overall networked system described by (1) can be denoted by the matrix pair A,B.Definition 1.
Linear network (1) is said to be state controllable if, for any initial state xt0∈ℝn and any final state xtf∈ℝn, there exist a finite time t1 and an input ut∈ℝm,t∈t0,t1, such that xt1;xt0,u=xtf.If networked system (1) is state controllable, we can say that the matrix pair A,B is state controllable.Definition 2.
(see [16, 31]). A linear control system A,B is a structured system if the elements in A and B are either fixed zeros or independent nonzero parameters. Both the two matrices A and B are called structured matrices.In this paper, it is assumed that we only know the structure of the matricesA and B. This means that we know which elements in the matrices are fixed to zero and consequently which elements are nonzero free parameters.Definition 3.
A linear control systemA,B is structurally controllable if we can set some values to the nonzero parameters in A and B such that the resulting system is state controllable in the sense of Kalman defined in Definition 1.A structured system can be represented by a directed graph whose nodes denote the (state and input) variables and edges indicate the connections between some variables [31]. In this paper, a structured system A,B is denoted by a directed graph GA,B=V,E, in which V=VA∪VB is the node set and E=EVA,VA∪EVB,VA is the edge set. In particular, VA=x1,x2,…,xn is the set of state nodes, corresponding to the n nodes in the original network; VB=u1,u2,…,um is the set of input nodes corresponding to the m inputs; EVA,VA=xi,xj|aji≠0 is the set of edges between state nodes; and EVB,VA=ui,xj|bji≠0 is the set of edges between input nodes and state nodes. In the whole paper, suppose that any input signal is applied to only one node, referred to as a driver node. A state node being reachable means that there is a directed path from some input node to this state node. Similarly, a node set is reachable if each node in the set is reachable. Notice that, in the remaining of the paper, unless otherwise specified, the reachability is only used for the state nodes.In a digraph, an edge subsetM˜ is a matching if no two edges in M˜ share a common parent node or a common child node. A matching of maximum size is called a maximum matching. The maximum matching of a digraph can be denoted by mapping the digraph to its bipartite representation. Consider a directed network GA,B, whose bipartite representation can be described by ℬA,B=ℬVA+∪VB,VA−,EVA+,VA−∪EVB,VA−, in which VA+=x1+,x2+,…,xn+ and VA−=x1−,x2−,…,xn−. That is, each state node xi of the original digraph is split into two nodes xi+ and xi−. Here, xi+,xj−∈EVA+,VA− if xi,xj∈EVA,VA and ui,xj−∈EVB,VA− if ui,xj∈EVB,VA. To describe the relationship between the digraph and its bipartite graph, we use a signal-notation mapping f:EVA,VA∪EVB,VA⟶EVA+,VA−∪EVB,VA− to map directed edges from the system digraph into undirected edges of the system bipartite graph as follows: fui,xj=ui,xj− and fxi,xj=xi+,xj−. Also, we have that f−1ui,xj−=ui,xj and f−1xi+,xj−=xi,xj.Definition 4.
The elementrij=1 in the matrix R∈ℝn×n if there is a directed path from node i to node ji≠j. Set rii=1, i=1,2,…,n. The matrix R is called reachable matrix.If only one external input is applied to node 1, then the first row of the matrixR can be used to determine which nodes are unreachable.Definition 5.
The elementpij=1 in the matrix P if edge i,j is one of the matching edges of a maximum matching about a bipartite graph. The matrix P is called maximum matching matrix.The maximum matching of a directed graph is not unique. Therefore, the corresponding maximum matching matrixP is not unique. It can be found from the matrix P that the number of nonzero elements in the matrix P is the number of matching edges in the maximum matching, and each row and each column have at most one nonzero element. The jth column is full of zero elements, indicating that node j in the network does not have its own independent parent node.Definition 6.
Consider a directed network, in which only one external input signal is applied to node 1. Ifn=∑j=1nr1j, r1j∈R, then such reachable matrix R is called 1−R matrix. For example,(2)1−R=1111101000111100001000011.Obviously, if the reachable matrixR of a network is a 1−R matrix, then all the state nodes in the network are reachable.Definition 7.
Consider a directed network, in which only one external input signal is applied to node 1. If the maximum matching matrixP has a unique nonzero element in each column except for the first column, then such maximum matching matrix P is called 1−P matrix. For example,(3)1−P=0100000100000100000100000.Obviously, if the maximum matching matrixP of a network is 1−P matrix, then there is no dilation in the network.A necessary and sufficient condition for the structural controllability of an LTI system is given as follows [31].Lemma 1.
(see [31]). The pairA,B is structurally controllable if and only if the following two conditions are satisfied simultaneously:(1)
Every state nodex∈VA in the digraph GA,B=VA∪VB,EVA,VA∪EVB,VA is reachable from some input node u∈VB(2)
The digraphGA,B contains no dilationsThen, we have the following controllability criterion.Theorem 1.
A directed networkGA,B with B=b1,0,…,0T is structurally controllable if and only if the following two conditions are satisfied simultaneously:(1)
The reachable matrix ofGA,B is a 1−R matrix(2)
The maximum matching matrix ofGA,B is a 1−P matrixIn this paper, given a structurally uncontrollable directed network, we study the problem of adding the least edges to improve the topology so as to obtain a structurally controllable system. After we get these optimal edge-addition configurations, we need to calculate the network cost of each optimization scheme and choose the one with the minimum cost. In summary, the problem is given as follows.Problem 1.
Given the pairA,B with B=b1,0,…,0T, find(4)A˜∗=argminA˜∈0,1n×nA˜0,s.t. the reachable matrix of digraph GA+A˜,B is a 1−R matrix and the maximum matching matrix is a 1−P matrix,whereA˜0 denotes the number of nonzero elements in a matrix A˜.IfA+A˜,B is structurally controllable, we refer to the matrix A˜ as an effective perturbed matrix and to A˜∗ in (4) as the modified matrix. The aim of this paper is to provide a characterization of all possible modified matrices by using graph-theoretical tools and design an algorithm to obtain such a solution.


## 4. Network Topology Optimization to Ensure Structural Controllability

Note that the system digraph is denoted byGA,B=VA∪VB,EVA,VA∪EVB,VA. Therefore, given an effective perturbed matrix A˜, we can relate a digraph to the perturbed structured system A+A˜,B, which we denote by GA+A˜,B=VA∪VB,EVA,VA∪EVB,VA∪E˜, where the edge set E˜⊆VA×VA is such that xi,xj∈E˜ if and only if a˜ji=1. Since the matrix A˜ is closely related to the E˜, we can rewrite Problem 1 in a different way.Problem 2.
Given the system digraphGA,B=VA∪VB,EVA,VA∪EVB,VA with B=b1,0,…,0T, find(5)E˜∗=argminE˜⊆VA×VAE˜,s.t. the reachable matrix of the digraph GA+A˜,B=VA∪VB,EVA,VA∪EVB,VA∪E˜ is a 1−R matrix and the maximum matching matrix is a 1−P matrix.Additionally, define a feasible edge-addition configuration as a set of directed edges that is a feasible solution of Problem2.The solutions to Problem2 are given in this section. First, a definition is introduced to describe the smallest set of edges needed to achieve reachability, i.e., satisfy condition (1) in Lemma 1. Let GA,B=VA∪VB,EVA,VA∪EVB,VA be the system digraph. The set of state nodes VA can be divided into two sets based on their reachability, namely, VA=R¯∪N¯, where R¯ is the set of reachable nodes and N¯ is the set of unreachable nodes. In addition, assume that there are r source SCCs that are unreachable, whose node sets are denoted by N1,N2,…,Nr⊆N¯. In order to make the nodes in these unreachable source SCCs reachable, we need to add a new edge between the reachable node and the node in the source SCC so that all the nodes in the source SCC are reachable. Moreover, since the source SCC has outgoing edges pointing to other nodes, the unreachable nodes that are connected to the source SCC will also become reachable.Definition 8.
A setSE is made up of connected edges, then the set SE is called the connected edge set. Here, the connected edge refers to the connecting edge between the reachable node and the unreachable node.Algorithm1 is illustrated in Figure 1. The connected edge set contains the minimum number of added edges required to ensure that all the state nodes are reachable. Obviously, the connected edge set can only satisfy condition (1) in Lemma 1 and cannot guarantee the structural controllability of the networked system. To ensure structural controllability of the system, these edge additions must satisfy two conditions: (i) a set of connected edges and (ii) the “tail” node of the new edge is not used as an independent parent node in the maximum matching. It is the “head” node of the edge that has no independent parent node.Algorithm 1:Set of connected edges.
Input: reachable nodes setsR¯ and unreachable nodes sets N¯(1)
Order the unreachable source SCCs:N1,N2,…,Nr(2)
Select any edgei,j in which i is in the set of reachable nodes and j is in the first source SCC(3)
Merge all reachable state nodes into a larger set (we can do it using either BFS/DFS or union-find)(4)
Call Steps 2-3 recursively until all unreachable source SCCs become reachableFigure 1
Illustration of Algorithm1. The black and blue nodes and all the black edges consist of the original directed network GA,B. The black nodes, except for the input node u, constitute the set of reachable state nodes R¯=x1,x2. Blue nodes constitute the set of unreachable state nodes N¯=x3,x4,x5,x6. There are two unreachable state source SCCs, N1 and N2. In (a), we give a possible edge-addition configuration for Algorithm 1. First, we add edge x1,x4 to SE. Then, the state node x4 from N1 becomes reachable, and thus the state node x3 becomes reachable. Next, we add edge x4,x5 to SE, and then the state nodes x5 and x6 from N2 become reachable, i.e., SE=x1,x4,x4,x5. In (b), we add edges x2,x4 and x4,x6 to SE′, i.e., SE′=x2,x4,x4,x6. Therefore, SE and SE′ are two possible sets of connected edges.
(a)(b)Theorem 2.
Consider a directed networkGA,B, whose bipartite representation is denoted by ℬA,B. Let M be a maximum matching, UoM=vio:i∈1,2,…,no be a node set in which each node is not used as independent parent node, and UrM=vir:i∈1,2,…,nr be a node set with no independent parent nodes. A set E˜ is a feasible edge-addition configuration if and only if it contains the union of the following two sets:(1)
SE is the set of connected edges(2)
SM=f−1vio,vir:vio∈UoM,vir∈UrM,i=1,2,…,nrTheorem2 provides some feasible edge-addition configurations, but we need to find the optimal one from these configurations. Therefore, the first task is to select the optimal solution from these feasible solutions. From the above discussion, it can be found that, after determining the maximum matching of a bipartite graph, if those unmatched nodes (nodes without independent parent nodes) happen to be distributed in different source SCCs, then the added edges just meet both conditions in Lemma 1, which is exactly what is needed. To explore this situation, we introduce the following concepts.Definition 9.
Consider a directed networkGA,B, whose bipartite representation is denoted by ℬA,B. Let M be a maximum matching associated with ℬA,B. Moreover, let UrM be the set of nodes in which each node has no independent parent nodes. If there is at least one node i, i∈UrM in an unreachable source SCC, then such an unreachable source SCC is called an ideal source SCC.Whether an unreachable source SCC is an ideal source SCC depends mainly on the specific maximum matching. Because there may be more than one maximum matching corresponding to a directed network, it is not possible to determine whether a node has an independent parent node in the maximum matching.Definition 10.
TheNs of the directed network GA,B is defined as the maximum number of ideal source SCCs in all the maximum matchings.We can determine a maximum matching attainingNs using Algorithm 2.Algorithm 2:Determine the ideal maximum matching to get Ns.
Input: A directed networkGA,B with B=b1,0,…,0T;(1)
Write the reachable matrixR of the directed network, and determine the unreachable node set N¯ in the network by the position (column ordinal) of the 0 element in the first row.(2)
Find the unreachable source SCCs.(3)
Select the nodes located in the source SCCs from the unreachable nodes setN¯ and mark their column ordinals.(4)
By using the marked column ordinals to identify an ideal maximum matchingM. Its corresponding maximum matching matrix is P∗. The column ordinals corresponding to all 0 columns in the matrix P∗ need to match the marked column ordinals as much as possible.(5)
According to Step 3, an ideal maximum matching matrixP∗ can be obtained. From the matrix P∗, the nodes corresponding to the matching column ordinals can be found.(6)
Based on the distribution of the nodes found in Step 5 in the source SCCs,Ns can be calculated.We take Figure2, for example, to illustrate Algorithm 2.Figure 2
Example illustrating Algorithm2.
(a)(b)(c)The reachable matrix corresponding to the digraph in Figure2(a) is expressed as follows:(6)R=110100010000111100000100000111000111.The unreachable node set can be determined asN¯=x3,x5,x6 by the position of the 0 element in the first row of R. Moreover, there are two unreachable source SCCs (red box), whose node sets are N1=x3 and N2=x5,x6, respectively. Then, we can label columns 3, 5, and 6 of R as follows:(7)R=∗∗∗110100010000111100000100000111000111.Figure2(b) shows the bipartite representation of the original directed network (Figure 2(a)). In order to make the column ordinals corresponding to all 0 columns in the maximum matching matrix P coincide with the marked column ordinals as much as possible, an ideal maximum matching M is determined in Figure 2(c), and its corresponding maximum matching matrix is expressed as follows:(8)P∗=∗∗110100010000111100000100000111000111.There are at most two 0 columns inP∗ that are consistent with the marked column ordinals, and the corresponding node x3 is located in N1, and node x5 is located in N2, so Ns=2.If all the state nodes that are not used as independent parent nodes are unreachable, then additional edges are needed to satisfy condition (1) in Lemma1. Therefore, in this case, calculating Ns according to Algorithm 2 does not necessarily lead to an optimal configuration of added edges. To illustrate this statement, we take Figure 3 for example.Figure 3
The maximum matching of a directed graph is not unique, and different maximum matchings will result in different feasible edge-addition configurations. In (a), the initial system digraphGA,B is given. The red edges in (b) and (d) form two different maximum matchings. The red edges in (c) and (e) are determined by the maximum matchings in (b) and (d), respectively. In (c), after determining the maximum matching, node x4 has no independent parent node and node x2 has not been used as the parent node. So, we need to add the edge x2,x4 to satisfy condition (2) of Lemma 1. Since node x2 is unreachable, we also need to add the edge x1,x2 to satisfy condition (1) of Lemma 1. Then, we have E˜1=x1,x2,x2,x4. In (e), after determining the maximum matching, node x4 has no independent parent node and node x1 has not been used as the parent node. So, we can add edge x1,x4 to satisfy both two conditions of Lemma 1, i.e., E˜2=x1,x4. Therefore, E˜2 is an optimal edge-addition configuration but E˜1 is not.
(a)(b)(c)(d)(e)Next, we will propose Algorithm3 to solve Problem 2. Algorithm 3 is mainly divided into the following four steps:Step 1. All the state nodes in the directed network are classified into a reachable node set and an unreachable node set, respectively, based on the node reachability.Step 2. Determine the ideal maximum matching to get Ns. If there exist some unreachable nodes that are not used as independent parent nodes in the ideal maximum matching, then we alter the matching by finding a directed path rooted at the input node.Step 3. Add some edges to satisfy Lemma 1. These edges start at reachable nodes that are not used as independent parent nodes and end at nodes that have no independent parent nodes in unreachable source SCCs.Step 4. If there are unreachable nodes that are not used as independent parent nodes, then we need to add a set of connected edges to ensure that both two conditions of Lemma 1 are satisfied.Algorithm 3:Minimal edge addition.
Input: A directed network GA,B;(1)
All the state nodes in the network are classified into a reachable node setR¯ and an unreachable node set N¯. Then, determine the unreachable source SCCs in the directed network GA,B.(2)
Using Algorithm2 to get M′ and Ns.(3)
ifUoM′∩R¯=∅, then(4)
Find an unreachable nodexj, and thus add the edge xi,xj,xi∈R¯;(5)
M←M′∪xi,xj;(6)
else(7)
SetM=M′;(8)
end if(9)
Obtain the unique set of disjoint directed pathsL=∪i=1qLi in M, where the beginning node of each Li is in some unreachable source SCCs and the end node is not used as a separate parent node;(10)
LetQ=q1,q2,…,qnandZ=z1,z2,…,zn, qi,zi are the beginning and end nodes of each path Li, respectively;(11)
LetE˜∗←∅,k←1;(12)
ifZ∩R¯=∅, then(13)
Find a reachable nodevo,vo∈UoM;(14)
fork≤q do(15)
E˜∗←E˜∪vk−1,qk;k←k+1;(16)
Z⊆R¯(17)
end for(18)
ifxi+∈UoM,UrM≠∅, then(19)
E˜∗←E˜∪xi,xj,xj−∈UrM;(20)
UoM←UoM\xi+;UrM⟵UrM\xj−;(21)
whenUrM=∅(22)
end ifGiven a structurally uncontrollable systemA,B that contains unreachable nodes and/or dilations. Therefore, we need to optimize the network topology to ensure structural controllability by adding edges. Algorithm 3 is given to obtain optimal edge-addition configuration to solve Problem 2.Next, an example in Figure4 is given to illustrate Algorithm 3.Figure 4
In (a), the directed networkGA,B contains a single input node u and eight state nodes x1,x2,…,x8. We will first decompose the directed graph according to the first step of Algorithm 3, R¯=x1,x2, N¯=x3,x4,x5,x6,x7,x8. There are three unreachable source SCCs in the digraph, N1=x4,N2=x6,N3=x7,x8. In (b), we provide ℬA,B the bipartite graph of the directed graph to attain a maximum matching M′(red edges) according to Step 2 of Algorithm 3, i.e., M′=u,x1,x1,x2,x4,x3,x8,x5,x7,x8. According to the maximum matching, nodes x4,x6,andx7 have no independent parent node, UrM′=x4,x6,x7. The nodes x2,x3,x5,andx6 are not used as the independent parent node, UoM′=x2,x3,x5,x6. According to Step 3 of Algorithm 3, reachable node x2 is not used as the parent node, x2∈R¯,x3,x5,x6∈N¯. Therefore, we need to pick nodes in UoM′ and UrM′, respectively, and they form edges that make nodes x3,x5,andx6 become reachable. The added edge x2,x4 can satisfy the above conditions (UoM⊆R¯). After the edge x2,x4 is added, a new maximum matching M=M′∪x2,x4 is formed. Then, the remaining set in which each node has not been used as an independent parent node is UoM=x5,x3,x6. The set with no independent parent node is UrM=x6,x7. According to Step 18 of Algorithm 3, UrM=x6,x7≠∅. So, we need to keep adding edges until the two conditions of Lemma 1 are satisfied. The other two edges added have four choices: x5,x6,x3,x7, x5,x7,x3,x6, x5,x6,x6,x7, and x3,x6,x6,x7. Finally, after adding three edges to the graph, both two conditions of Lemma 1 are satisfied, and thus a new directed graph GA+A˜,B is obtained. In summary, we can get four optimal edge-addition configurations as follows: E˜1∗=x2,x4,x5,x6,x3,x7, E˜2∗=x2,x4,x5,x7,x3,x6, E˜3∗=x2,x4,x5,x6,x6,x7, and E˜4∗=x2,x4,x6,x7,x3,x6 (a solution to Problem 2).
(a)(b)


## 5. Network Optimization Cost

We have solved the optimal edge-addition configuration problem; however, there are multiple potential edge-addition configurations to ensure structural controllability. From the application perspective, the lowest cost configuration is usually selected as the final optimization solution. Therefore, we present Problem3 based on Problem 2, taking the network cost into account. In order to solve Problem 3, we introduce an edge cost measurement index to calculate the edge cost and thus obtain the cost of the whole network. In addition, we need to adopt a simple and practical method to calculate the cost of the network and determine a minimum-cost configuration to ensure the controllability based on the optimal edge-addition configuration.Problem 3.
Consider a directed networkGA,B, find(9)E˜∗=argminE˜⊆VA×VAE˜,s.t. the new directed network GA+A˜,B contains neither unreachable nodes nor dilations. Also, the cost of the new directed network must be the lowest one.


### 5.1. Main Idea

Given a structurally uncontrollable directed networkGA,B. The optimal edge-addition configuration is obtained by using Algorithm 3. The first step of calculating the network optimization cost is to obtain the load of each node in the network. Note that the nature of node load is exactly consistent with the betweenness centrality of the node. Betweenness centrality of a node refers to the proportion of the number of paths passing through the node in the total number of shortest paths. Intuitively, the betweenness centrality reflects the importance of the node as a “bridge.” Therefore, the initial load on each node can be denoted by its betweenness centrality [27]. We can calculate the betweenness centrality of each node by “pajek” software after importing a directed network. There is a nonlinear relationship between the load of a node and its capacity [38, 39], so we can determine the node capacity by this nonlinear relation. The cost of a node can be measured by its node capacity in the network. We take the larger one of the two node capacities as the cost of the edge that connects these two nodes [40]. In this paper, we calculate the network costs of all optimal edge-addition configurations and then choose the one with the lowest network cost as the optimal edge-addition configuration.The specific calculation process of network cost is given as follows:Step 1. Node load can be measured by the betweenness centrality(10)CBv=∑s≠v≠t∈Vσstvσst,whereCBv denotes the betweenness centrality of node v, σstv denotes the number of the shortest directed paths s⟶t that passes through node v, and σst means the number of the shortest directed paths from node s to node t.Step 2. There is a nonlinear relationship between node load and node capacity described by(11)Capv=CBv+βCBvα,v=1,2,…,n,whereCapv is the capacity of node v, α>0,β>0. Since there is a positive correlation between node load and capacity, set α=β=1. Thus, the node capacity is determined by(12)Capv=2CBv.Step 3. Use the index of node capacity to measure the node cost(13)Costv=Capv=2CBv,whereCostv denotes the cost of node v.Step 4. Compare the capacities of two nodes of an edge, and take the larger one as the capacity of the edge (edge cost)(14)Costlij=maxCapvi,Capvj,whereCostlij is the cost of edge lij.Step 5. Calculate the network cost of each configuration according to Step 4(15)CostNet=∑Costlij,whereCostNet denotes the cost of the whole network.


### 5.2. Data Processing

In Figure4(a), the initial directed network GA,B is given. Get the optimal edge-addition configuration by Algorithm 3, E˜1∗=x2,x4,x5,x6,x3,x7 and E˜2∗=x2,x4,x5,x7,x3,x6 and E˜3∗=x2,x4,x5,x6,x6,x7 and E˜4∗=x2,x4,x6,x7,x3,x6.The new directed network resulting from the first configuration scheme is shown in Figure5. Figure 6 shows the curve of the state of each node over time.Figure 5
The new directed network resulting from the first configuration schemeE˜1∗=x2,x4,x5,x6,x3,x7.Figure 6
The different color curves in the figure represent the trend that the states of the 8 nodes in the new directed network change over time.We import this new directed networkGA+A˜,B into pajek software to calculate the betweenness centrality of each node. The original data of betweenness centrality of each node are shown in Table 1. In Table 2, we collate the data of node load, node capacity, edge cost, and network cost according to each step described in Section 5.1. Then, we get the network cost of the first configuration scheme.Table 1
The original data of betweenness centrality of each node in Figure5.
NodeValLabel10.47619051120.4761905230.3095238340.4761905450.3333333560.3333333670.1904762780.19047628We calculate the betweenness centrality value of eight nodes in Figure5 by pajek software.Table 2
The data of node load, node capacity, edge cost, and network cost for the first configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.48, 0.48)(0.96, 0.96)0.96(3, 1)(0.31, 0.48)(0.62, 0.96)0.96(2, 4)(0.48, 0.48)(0.96, 0.96)0.96(4, 3)(0.48, 0.31)(0.96, 0.62)0.96(4, 5)(0.48, 0.33)(0.96, 0.66)0.96(6, 1)(0.33, 0.48)(0.66,0 .96)0.96(5, 6)(0.33, 0.33)(0.66, 0.66)0.66(3, 7)(0.31, 0.19)(0.62, 0.38)0.62(7, 8)(0.19, 0.19)(0.38, 0.38)0.38(8, 7)(0.19, 0.19)(0.38, 0.38)0.38(8, 5)(0.19, 0.33)(0.38, 0.66)0.66Network cost8.46The new directed network resulting from the second configuration scheme is shown in Figure7. The original data of betweenness centrality of each node are shown in Table 3. Similarly, we can obtain the data of node load, node capacity, edge cost, and network cost, as shown in Table 4.Figure 7
The new directed network resulting from the second configuration schemeE˜2∗=x2,x4,x5,x7,x3,x6.Table 3
The original data of betweenness centrality of each node in Figure7.
NodeValLabel10.2857143120.3571429230.1428571340.4285714450.2380952560.0000000670.1428571780.02380958We calculate the betweenness centrality value of eight nodes in Figure7 by pajek softwareTable 4
The data of node load, node capacity, edge cost, and network cost for the second configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.29, 0.36)(0.58, 0.72)0.72(3, 1)(0.14, 0.29)(0.28, 0.58)0.58(2, 4)(0.36, 0.43)(0.72, 0.86)0.86(4, 3)(0.43, 0.14)(0.86, 0.28)0.86(4, 5)(0.43, 0.24)(0.86, 0.48)0.86(6, 1)(0.00, 0.29)(0.00, 0.58)0.58(5, 7)(0.24, 0.14)(0.48, 0.24)0.48(3, 6)(0.14, 0.00)(0.28, 0.00)0.28(7, 8)(0.14, 0.02)(0.28, 0.04)0.28(8, 7)(0.02, 0.14)(0.04, 0.28)0.28(8, 5)(0.02, 0.24)(0.04, 0.48)0.48Network cost6.26The new directed network resulting from the third configuration scheme is shown in Figure8. The original data of betweenness centrality of each node are shown in Table 5. Similarly, we can obtain the data of node load, node capacity, edge cost, and network cost, as shown in Table 6.Figure 8
The new directed network resulting from the third configuration schemeE˜3∗=x2,x4,x5,x6,x6,x7.Table 5
The original data of betweenness centrality of each node in Figure8.
NodeValLabel10.4523810120.4523810230.0714286340.4523810450.5238095560.5238095670.1666667780.16666678We calculate the betweenness centrality value of eight nodes in Figure8 by pajek software.Table 6
The data of node load, node capacity, edge cost, and network cost for the third configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.45, 0.45)(0.90, 0.90)0.90(3, 1)(0.07, 0.45)(0.14, 0.90)0.90(2, 4)(0.45, 0.45)(0.90, 0.90)0.90(4, 3)(0.45, 0.07)(0.90, 0.14)0.90(4, 5)(0.45, 0.52)(0.90, 1.04)1.04(6, 1)(0.52, 0.45)(1.04, 0.90)1.04(5, 6)(0.52, 0.52)(1.04, 1.04)1.04(6, 7)(0.52, 0.17)(1.04, 0.34)1.04(7, 8)(0.17, 0.17)(0.34, 0.34)0.34(8, 7)(0.17, 0.17)(0.34, 0.34)0.34(8, 5)(0.17, 0.52)(0.34, 1.04)1.04Network cost9.48The new directed network resulting from the fourth configuration scheme is shown in Figure9. The original data of betweenness centrality of each node are shown in Table 7. Furthermore, we can obtain the data of node load, node capacity, edge cost, and network cost, as shown in Table 8.Figure 9
The new directed network resulting from the fourth configuration schemeE˜4∗=x2,x4,x6,x7,x3,x6.Table 7
The original data of betweenness centrality of each node in Figure9.
NodeValLabel10.1547619120.2261905230.2857143340.2976190450.0000000560.2023810670.1547619780.05952388We calculate the betweenness centrality value of eight nodes in Figure9 by pajek software.Table 8
The data of node load, node capacity, edge cost, and network cost for the fourth configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.15, 0.23)(0.30, 0.46)0.46(3, 1)(0.29, 0.15)(0.58, 0.30)0.58(2, 4)(0.23, 0.30)(0.46, 0.60)0.60(4, 3)(0.30, 0.29)(0.60, 0.58)0.60(4, 5)(0.30, 0.00)(0.60, 0.00)0.60(6, 1)(0.20, 0.15)(0.40, 0.30)0.40(3, 6)(0.29, 0.20)(0.58, 0.40)0.58(6, 7)(0.20, 0.15)(0.40, 0.30)0.40(7, 8)(0.15, 0.06)(0.30, 0.12)0.30(8, 7)(0.06, 0.15)(0.12, 0.30)0.30(8, 5)(0.06, 0.00)(0.12, 0.00)0.12Network cost4.94Comparing the network costs of the above four configuration schemes, we choose the fourth scheme as the optimal edge-addition configuration so as to get the solution of Problem3.


### 5.3. Illustrative Example

In [23], a directed network as shown in Figure 10 is considered. The authors proposed 14 edge-addition configurations, i.e., E˜∗=x2,x10,x9,x5,xi,xj, i∈1,…,6,10,j∈7,8. However, they did not tell us which one is the optimal edge-addition configuration with the lowest cost. Using the results of our work, the cost of each optimization scheme can be calculated, and finally a scheme E˜8∗=x2,x10,x9,x5,x4,x8 with the lowest cost can be selected to ensure the structural controllability of the network.Figure 10
A directed network.


## 5.1. Main Idea

Given a structurally uncontrollable directed networkGA,B. The optimal edge-addition configuration is obtained by using Algorithm 3. The first step of calculating the network optimization cost is to obtain the load of each node in the network. Note that the nature of node load is exactly consistent with the betweenness centrality of the node. Betweenness centrality of a node refers to the proportion of the number of paths passing through the node in the total number of shortest paths. Intuitively, the betweenness centrality reflects the importance of the node as a “bridge.” Therefore, the initial load on each node can be denoted by its betweenness centrality [27]. We can calculate the betweenness centrality of each node by “pajek” software after importing a directed network. There is a nonlinear relationship between the load of a node and its capacity [38, 39], so we can determine the node capacity by this nonlinear relation. The cost of a node can be measured by its node capacity in the network. We take the larger one of the two node capacities as the cost of the edge that connects these two nodes [40]. In this paper, we calculate the network costs of all optimal edge-addition configurations and then choose the one with the lowest network cost as the optimal edge-addition configuration.The specific calculation process of network cost is given as follows:Step 1. Node load can be measured by the betweenness centrality(10)CBv=∑s≠v≠t∈Vσstvσst,whereCBv denotes the betweenness centrality of node v, σstv denotes the number of the shortest directed paths s⟶t that passes through node v, and σst means the number of the shortest directed paths from node s to node t.Step 2. There is a nonlinear relationship between node load and node capacity described by(11)Capv=CBv+βCBvα,v=1,2,…,n,whereCapv is the capacity of node v, α>0,β>0. Since there is a positive correlation between node load and capacity, set α=β=1. Thus, the node capacity is determined by(12)Capv=2CBv.Step 3. Use the index of node capacity to measure the node cost(13)Costv=Capv=2CBv,whereCostv denotes the cost of node v.Step 4. Compare the capacities of two nodes of an edge, and take the larger one as the capacity of the edge (edge cost)(14)Costlij=maxCapvi,Capvj,whereCostlij is the cost of edge lij.Step 5. Calculate the network cost of each configuration according to Step 4(15)CostNet=∑Costlij,whereCostNet denotes the cost of the whole network.


## 5.2. Data Processing

In Figure4(a), the initial directed network GA,B is given. Get the optimal edge-addition configuration by Algorithm 3, E˜1∗=x2,x4,x5,x6,x3,x7 and E˜2∗=x2,x4,x5,x7,x3,x6 and E˜3∗=x2,x4,x5,x6,x6,x7 and E˜4∗=x2,x4,x6,x7,x3,x6.The new directed network resulting from the first configuration scheme is shown in Figure5. Figure 6 shows the curve of the state of each node over time.Figure 5
The new directed network resulting from the first configuration schemeE˜1∗=x2,x4,x5,x6,x3,x7.Figure 6
The different color curves in the figure represent the trend that the states of the 8 nodes in the new directed network change over time.We import this new directed networkGA+A˜,B into pajek software to calculate the betweenness centrality of each node. The original data of betweenness centrality of each node are shown in Table 1. In Table 2, we collate the data of node load, node capacity, edge cost, and network cost according to each step described in Section 5.1. Then, we get the network cost of the first configuration scheme.Table 1
The original data of betweenness centrality of each node in Figure5.
NodeValLabel10.47619051120.4761905230.3095238340.4761905450.3333333560.3333333670.1904762780.19047628We calculate the betweenness centrality value of eight nodes in Figure5 by pajek software.Table 2
The data of node load, node capacity, edge cost, and network cost for the first configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.48, 0.48)(0.96, 0.96)0.96(3, 1)(0.31, 0.48)(0.62, 0.96)0.96(2, 4)(0.48, 0.48)(0.96, 0.96)0.96(4, 3)(0.48, 0.31)(0.96, 0.62)0.96(4, 5)(0.48, 0.33)(0.96, 0.66)0.96(6, 1)(0.33, 0.48)(0.66,0 .96)0.96(5, 6)(0.33, 0.33)(0.66, 0.66)0.66(3, 7)(0.31, 0.19)(0.62, 0.38)0.62(7, 8)(0.19, 0.19)(0.38, 0.38)0.38(8, 7)(0.19, 0.19)(0.38, 0.38)0.38(8, 5)(0.19, 0.33)(0.38, 0.66)0.66Network cost8.46The new directed network resulting from the second configuration scheme is shown in Figure7. The original data of betweenness centrality of each node are shown in Table 3. Similarly, we can obtain the data of node load, node capacity, edge cost, and network cost, as shown in Table 4.Figure 7
The new directed network resulting from the second configuration schemeE˜2∗=x2,x4,x5,x7,x3,x6.Table 3
The original data of betweenness centrality of each node in Figure7.
NodeValLabel10.2857143120.3571429230.1428571340.4285714450.2380952560.0000000670.1428571780.02380958We calculate the betweenness centrality value of eight nodes in Figure7 by pajek softwareTable 4
The data of node load, node capacity, edge cost, and network cost for the second configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.29, 0.36)(0.58, 0.72)0.72(3, 1)(0.14, 0.29)(0.28, 0.58)0.58(2, 4)(0.36, 0.43)(0.72, 0.86)0.86(4, 3)(0.43, 0.14)(0.86, 0.28)0.86(4, 5)(0.43, 0.24)(0.86, 0.48)0.86(6, 1)(0.00, 0.29)(0.00, 0.58)0.58(5, 7)(0.24, 0.14)(0.48, 0.24)0.48(3, 6)(0.14, 0.00)(0.28, 0.00)0.28(7, 8)(0.14, 0.02)(0.28, 0.04)0.28(8, 7)(0.02, 0.14)(0.04, 0.28)0.28(8, 5)(0.02, 0.24)(0.04, 0.48)0.48Network cost6.26The new directed network resulting from the third configuration scheme is shown in Figure8. The original data of betweenness centrality of each node are shown in Table 5. Similarly, we can obtain the data of node load, node capacity, edge cost, and network cost, as shown in Table 6.Figure 8
The new directed network resulting from the third configuration schemeE˜3∗=x2,x4,x5,x6,x6,x7.Table 5
The original data of betweenness centrality of each node in Figure8.
NodeValLabel10.4523810120.4523810230.0714286340.4523810450.5238095560.5238095670.1666667780.16666678We calculate the betweenness centrality value of eight nodes in Figure8 by pajek software.Table 6
The data of node load, node capacity, edge cost, and network cost for the third configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.45, 0.45)(0.90, 0.90)0.90(3, 1)(0.07, 0.45)(0.14, 0.90)0.90(2, 4)(0.45, 0.45)(0.90, 0.90)0.90(4, 3)(0.45, 0.07)(0.90, 0.14)0.90(4, 5)(0.45, 0.52)(0.90, 1.04)1.04(6, 1)(0.52, 0.45)(1.04, 0.90)1.04(5, 6)(0.52, 0.52)(1.04, 1.04)1.04(6, 7)(0.52, 0.17)(1.04, 0.34)1.04(7, 8)(0.17, 0.17)(0.34, 0.34)0.34(8, 7)(0.17, 0.17)(0.34, 0.34)0.34(8, 5)(0.17, 0.52)(0.34, 1.04)1.04Network cost9.48The new directed network resulting from the fourth configuration scheme is shown in Figure9. The original data of betweenness centrality of each node are shown in Table 7. Furthermore, we can obtain the data of node load, node capacity, edge cost, and network cost, as shown in Table 8.Figure 9
The new directed network resulting from the fourth configuration schemeE˜4∗=x2,x4,x6,x7,x3,x6.Table 7
The original data of betweenness centrality of each node in Figure9.
NodeValLabel10.1547619120.2261905230.2857143340.2976190450.0000000560.2023810670.1547619780.05952388We calculate the betweenness centrality value of eight nodes in Figure9 by pajek software.Table 8
The data of node load, node capacity, edge cost, and network cost for the fourth configuration scheme.
EdgeNode loadNode capacityEdge cost(1, 2)(0.15, 0.23)(0.30, 0.46)0.46(3, 1)(0.29, 0.15)(0.58, 0.30)0.58(2, 4)(0.23, 0.30)(0.46, 0.60)0.60(4, 3)(0.30, 0.29)(0.60, 0.58)0.60(4, 5)(0.30, 0.00)(0.60, 0.00)0.60(6, 1)(0.20, 0.15)(0.40, 0.30)0.40(3, 6)(0.29, 0.20)(0.58, 0.40)0.58(6, 7)(0.20, 0.15)(0.40, 0.30)0.40(7, 8)(0.15, 0.06)(0.30, 0.12)0.30(8, 7)(0.06, 0.15)(0.12, 0.30)0.30(8, 5)(0.06, 0.00)(0.12, 0.00)0.12Network cost4.94Comparing the network costs of the above four configuration schemes, we choose the fourth scheme as the optimal edge-addition configuration so as to get the solution of Problem3.


## 5.3. Illustrative Example

In [23], a directed network as shown in Figure 10 is considered. The authors proposed 14 edge-addition configurations, i.e., E˜∗=x2,x10,x9,x5,xi,xj, i∈1,…,6,10,j∈7,8. However, they did not tell us which one is the optimal edge-addition configuration with the lowest cost. Using the results of our work, the cost of each optimization scheme can be calculated, and finally a scheme E˜8∗=x2,x10,x9,x5,x4,x8 with the lowest cost can be selected to ensure the structural controllability of the network.Figure 10
A directed network.


## 6. Conclusions

In this paper, we have solved the problem of how to optimize the network topology to ensure structural controllability. Given a structurally uncontrollable directed network, Algorithm3 presents all possible edge-addition configurations. After determining the optimal edge-addition configuration, a network cost index is given to choose the lowest cost configuration.In future, we can combine these two strategies of adding edges and adding external input signals to ensure the network controllability and choose the scheme with the highest benefit by comparing the costs of several strategies. In addition, we can extend a single directed network to the topology design of a multiplex network [29, 41] so as to ensure the structural controllability of the multiplex network.



---

*Source: 6657307-2021-01-27.xml*