# Research Progress in Enhancing the Controllability of Complex Networks

Authors: Yunyun Yang
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

At present, the controllability of complex networks is a hot issue in complex networks domain. From the perspective of graph theory, in the paper quite a few pioneering works on the controllability of complex networks were introduced, and the latest progress of the controllability of complex networks was emphatically summarized. In addition, the paper mainly discussed the basic ideas and effective methods to enhance the structural controllability of complex networks and analyzed the advantages and disadvantages of different methods. Finally, several problems and possible development directions of the controllability of complex networks were summarized.


---

## Body

## 1. Introduction

Along with the rapid development of the network in the late twentieth century, our human society entered into a new era of the network. Naturally, the network became a profound new topic studied by individuals [1, 2]. In particular, since a slice of discoveries of collective dynamics of small-world network, by Watts and Strogatz [3] published in Nature in 1998, and some discoveries of emergence of scaling in random networks, by Barabsi and Albert [4] published in Science in 1999, the academic circles have set off an upsurge of studying complex networks [5–8].Complex systems pervade in today, for example Internet [9, 10], communication networks [11], power networks [12, 13], transportation networks [14], and biological networks [15]. Complex systems have brought a great improvement for the production and life of human beings. Meanwhile, the failure of complex systems can cause a huge loss, such as the large-scale blackout of power grids, traffic paralysis, and the fast spread of rumours or infectious diseases. Hence complex systems should be controlled effectively. Then, the benefits can be utilized effectively, and the unnecessary disaster can be avoided. The phenomenon forced complex networks and systems engineering to flourish [16–19]. Meanwhile, networks and control gradually fused together in the development process of each other [20–22]. In gene regulatory networks [23–25], we select which genes as drug targets to make the whole biological systems to achieve a desired state. In social networks [26], we select which nodes as the information publishes nodes to achieve favorable promotional effects. Most of the complex practical systems can be regarded as complex networks, though they are different greatly in the real world. Therefore the control of complex systems can be transformed into the control of complex networks. These phenomena [27, 28] can be abstracted as how to effectively control complex networks to make the whole network into a desired state. Before conducting the control of the complex networks, whether the controlled plant can be controlled effectively should be investigated. And that is to say we should be clear in whether the controlled plant has the controllability. If the controlled plant does not have the controllability, it should be adjusted until it possesses the controllability; and the control action can be performed only after the condition that the controlled plant has the controllability is confirmed. So investigating the controllability is necessary for the control. In addition, due to the fact that the large control systems often contain a multitude of subnetworks, for example, wireless sensor networks and communication networks, and that numerous controllers are embedded in a variety of large-scale networks at the same time, the traditional control theory [29, 30] has no application in this case. Thus it can be seen that the development of complex networks has brought new opportunities and challenges for the traditional control theory.Based on the above, the research on the structural controllability of complex networks was published by Liu et al. [31] in Nature in 2011. From then on, the academic circles have set off an upsurge of studying structural controllability of complex networks [32–44]. The literature [31] regarded an entire network as a linear system and established the model of structural controllability of complex networks by skilfully introducing matching theory [45–47]. They converted the problem of complex networks’ controllability into directed networks, the maximum matching problem. The theory of structural controllability of complex networks, which literature [31] put forward, was aimed at directed networks. Then, the controllability of the undirected complex networks problem was researched and the theory of exact controllability of complex networks was given by Yuan et al. [48].In recent years, the controllability of complex networks was mainly developed based on the structural controllability of complex networks [31] and acquired some achievements. To date, the literature [31] had a high cited frequency in Google Scholar, as much as 1336. Consequently, it is necessary to summarize the current research progress from different perspectives and to discuss possible future directions of complex networks controllability. Despite the increasing study of the controllability of complex networks, exploiting its full potential is difficult due to its inherent problems such as structure complexity, enormous scale, and dynamic complexity. Enhancing the controllability of complex networks can address these problems by appropriate changing in the network topology. This paper mainly analyzed the optimization problem of structural controllability of complex networks and summarized some typical ways and measures of enhancing complex networks controllability by using topology optimization. Most of the complex practical systems can be regarded as complex networks, though they are different greatly in the real world. Therefore the control of complex systems can be transformed into the control of complex networks. Under system controllable circumstances, the purpose of controlling the system is achieved by artificially applying strategies. However, sometimes it is more expensive to directly control the system, or too many controllers are needed. In this case, without affecting the characteristics of the system, we can slightly change the structure of the system to achieve controllable purpose. This process is called strengthening the controllability of complex systems. Here, we provide an extensive survey of enhancing the controllability of complex networks research. We present a taxonomy based on the key issues in this area and discuss the different approaches taken to tackle these issues. We conclude the paper with a critical analysis of challenges that have not yet been fully met and highlight directions for future work. We aim at extracting more organized research train of thought by collating and summarizing the research status of this field. We try to hope for the research of network control to provide a reference and expect better able to guide future work.The rest of the paper is organized as follows. Section2 introduced the theory of structural controllability of complex networks. In Section 3, techniques to enhance the controllability of directed complex networks were shown in detail. Section 4 gave the conclusions and discussion.


## 2. Structural Controllability of Complex Networks

In this section, we first reviewed the definition of linear time-invariant system controllability and classical judgment controllability theorem and then introduced the judgment theorems of complex networks controllability.Here we consider a linear time-invariant (LTI) dynamics equation (1) on a directed network:(1)x˙t=Axt+Qut,where A is the transpose of the adjacency matrix of the network, xt is a time-dependent vector of the state variables of the nodes, ut is the vector of input signals, and Q is the so-called input matrix, which defines how the input signals are connected to the nodes of the network.Based on the linear system control theory [30], a complex network is controllable if and only if it satisfies Kalman’s controllability rank condition [49]. It can be controlled from any initial state to any desired state infinite time, if and only if the N×NM controllability matrix C has full rank. It can be formalized as follows:(2)rankC=rankQ,AQ,A2Q,…,An−1Q=N,where x=x1,x2,…,xN is called the state vector, A=aijN×N is the state matrix, and aij denotes the weight of a directed edge from node j to i. Q is the input matrix, and u=u1,u2,…,uM is the input or control vector.But for large-scale systems or high dimensional complex networks [50], the rank critical condition is impossible to test, because it is needed to calculate a large amount of matrix combinations. Accordingly, for large systems or high dimensional complex networks, it is not feasible to judge their controllability by using the traditional method. For this reason, a newly general method, which is suitable for controllability of directed complex networks was introduced in the literature [31].Recently, Liu et al. [31] developed the minimum input theory to efficiently characterize the structural controllability of directed networks. According to the literature [31], the structural controllability of directed networks can be mapped into the problem of the maximum matching, where external control is necessary for every unmatched node. The maximum matching is defined and the method for finding a maximum matching is, respectively, as follows.Generally, a maximum matching of a directed network problem is transformed into a maximum matching of a bipartite network problem. A maximum matching of a digraphG=V,E can be found in its bipartite representation, denoted as FV (see Figure 1). The bipartite graph is defined as FV=V+∪V−,Γ. Here, V+=x1+,x2+,…,xN+ and V−=x1−,x2−,…,xN− are the sets of nodes corresponding to the N columns and rows of the state matrix A, respectively. Γ=i+,j−|aij≠0 is the edge set, i.e., if there is an edge from node i to node j, then link node i+ and node j−. According to the algorithm of a bipartite graph maximum matching, we can obtain a maximum matching of the directed graph.Figure 1
A simple network, its bipartite representation, and its maximum matching. (a) A simple network with five nodes and five edges. (b) The bipartite representation of the network and its maximum matching. Matched (unmatched) nodes are shown in green (red) and matching edges are shown in green, respectively.
(a)
(b)


## 3. Enhancing the Structural Controllability of Complex Networks

For large-scale complex networks, there may be more unmatched nodes and we need to pay a high price to keep their structural controllability. A larger valueND indicates a worse structural controllability. It means that we need to provide more input signals to control the network. In fact, a multitude of actual networks have large values ND. Therefore, in order to improve structural controllability of the network, it is a critical problem on how to properly change the network topology structure to reduce the amount of the driver nodes [51–53].There are different ways of improving the structural controllability of complex networks. Now some existing methods are mainly from the following three aspects to take into account: adding edges [51, 54, 55], swapping edges [56–58], and changing directions of edges [59, 60]. This section focused on the typical methods.


### 3.1. Based on Adding Edges, Enhancing the Structural Controllability of Complex Networks

Based on adding edges, there are two ways to enhance the structural controllability of complex networks. One is simply to add some new edges into the network, and another is to add some new edges and remove the same number edges (original edges) at the same time. The former makes the number of edges in the network increase. In the latter case, the number of edges remains unchanged in the network.Adding edges can be implemented in two ways: randomly adding edges and intentionally adding edges according to a certain formula. Randomly adding edges means randomly selecting two nodes and adding an edge between them if there is no edge between them. Intentionally adding edges means according to a certain formula selecting two nodes and adding an edge between them if there is no edge between them, for example, based on node degree ratiokr [55], where kr=kout+1/kin+1. After adding an edge, if the number of driver nodes decreases, then keep the new edge. If the number of driver nodes does not change, then delete the new edge and choose again. Here, we introduced two kinds of intentionally adding edges to enhance the structural controllability of complex networks.Maximum matching of a graph is not unique and the corresponding set of matched nodes is not the same. Hence, choosing different maximum matchings would result in different sets of unmatched nodes, that is, different sets of driver nodes. According to the frequency of nodes occurrences within all the minimum sets of driver nodes, all nodes can be divided into three categories: critical nodes, ordinary nodes, and redundant nodes [36]. Critical nodes represent that they appear in every minimum set of driver nodes. Redundant nodes represent that they do not appear in any minimum set of driver nodes. Ordinary nodes represent that they appear in part of the minimum sets of driver nodes. Analogously, all edges can be divided into three categories: critical edges, ordinary edges, and redundant edges [31]. Critical edges mean if they are removed from the network, then the number of the minimum sets of driver nodes will increase for the case where the network states are structural controllability. Redundant edges mean they are removed from the network without altering the number of the minimum sets of driver nodes. And yet, ordinary edges mean they are removed affecting some of the minimum sets of driver nodes.Thus it can be seen that adding a new edge may enhance the structural controllability of complex networks, but definitely would not make it weaken. Enhancing structural controllability of complex networks is to make as multitude critical edges and as fewer redundant edges. Therefore, the literature [55] proposed a method of enhancing structural controllability of complex networks by using adding some critical edges while removing the same number of redundant edges. The method [55] was based on the node degree ratio and was presented in detail as follows.Step 1: In the entire network select a node with the smallestkr, denoted as Vminkr, and select another node with the largest kr, denoted as Vmaxkr. If there is more than one such node with the smallest kr, then randomly select one of those. For node Vmaxkr, it is similar to the node with the smallest kr.Step 2: Add a new directed edge withVminkr as a starting node and Vmaxkr as an ending node. If there is already an edge between the two selected nodes, then reselect until there does not exist an edge between the two selected nodes.Step 3: After adding a directed edge, recount the degree ratio of nodes and repeat the above steps.Compared with the method of random adding edges, this method is more effective. The validity of the method is to reduce the heterogeneity degree of a network, which should contribute to enhancing the controllability of the network.Moreover, Wang et al. [51] studied, for a directed network with N state nodes, if we use only one input node to control the network, how many we need to add edges into the network, and which positions we need to add edges in the network. On the basis of the literature [31], an optimization algorithm of adding edges was proposed. Firstly, the maximum matching set of the network is divided into three categories: directed paths, circles, and isolated nodes. Circles do not need an additional input signal to control. Therefore they do not need to be considered. Then, all directed paths and isolated nodes are connected with one another in turn head-to-tail and form a new directed path.


### 3.2. Based on Reversing Edge Directions, Enhancing the Structural Controllability of Complex Networks

Although the controllability of a network could be enhanced by adding some edges, the topology of the network would be changed. In addition, from the point of view of cost, adding some edges into a network, for example, a power network, requires a high price. Hence, for some actual networks, it is not feasible by adding some edges to improve their controllability. The edge direction plays a vital role in the controllability of a network. Based on this, it was proposed reversing some edge directions to enhance the structural controllability of complex networks [56–58]. This way keeps the total number of edges unchanged and also does not change the network topology.As earlier work has already pointed out, the maximum matching consists of isolated nodes, matching paths, and matching cycles. Isolated nodes are invariably unmatched. Each matching path contains only an unmatched node. Since matching cycles do not contain unmatched nodes, matching cycles are not needed to be taken into consideration. Accordingly,ND is equal to the total number of isolated nodes and matching paths. If we connect an isolated node or matching path to another isolated node or matching path, ND decreases by one.Based on the maximum matching, nodes can be categorized into four types: start nodes, middle nodes, end nodes, and isolated nodes [56]. Start nodes have an outgoing edge and no incoming edge. If a node has only an outgoing edge without incoming edges, then the node is a start node. Instead, if a node has only an incoming edge without any outgoing edges, then the node is an end node. If a node has both outgoing and incoming edges, then the node is a middle node. And yet, if a node has no edges belonging to the maximum matching, then the node is an isolated node.Based on the type of a node, five types of edges need to change directions. Those edges were called candidate edges. The five types of edges were referred to as SI, IE, SE, SS, and EE (see Figure2). (a) SI: edges leading from a start node pointing to an isolated node; (b) IE: edges leading from an isolated node pointing to an end node; (c) SE: edges leading from a start node pointing to an end node; (d) SS: edges leading from a start node pointing to a start node; (e) EE: edges leading from an end node pointing to an end node.The algorithm [56] is the following:Step 1: According to the Hopcroft–Karp algorithm [30], obtain a maximum matching of a network.Step 2: All the nodes are categorized into four types: start nodes, middle nodes, end nodes, and isolated nodes.Step 3: Identify the candidate edges: SI, IE, SE, SS, and EE.Step 4: Run through a sequence of operations on the candidate edges with the type SI. In the first place, change the directions of the candidate edges with the type SI. There is one more point, based on the new matching path, the types of the corresponding nodes and edges are refreshed. Apply the same operations to the candidate edges with the types IE and SE.Step 5: Run through a sequence of operations on the candidate edges with the type SS. The first and foremost is to compare the length of two matching paths. Secondly, change the directions of the edges in the shorter path. Then, based on the new matching path, the types of the corresponding nodes and edges are refreshed. Apply the same operations to the candidate edges with the type EE.Step 6: The controllability of the network has improved to some extent after changing the edge direction. Then, gain a new maximum matching of the improved network (see Figure3). When the controllability of the network has reached the desired state or its controllability of the network remains constant in the long run, the algorithm stops, or return to Step 2.On the basis of the matching path, the basic thought of the method is to seek candidate edges. This method is based on only part structure and offers a strategy to improve the controllability. Since the global topology of numerous real networks is unknown and, in general, we just get part structure information, this strategy may be more practical than those that need whole topology information.


### 3.3. Based on Maximum-Weighted Independent Set, Enhancing the Structural Controllability of Complex Networks

In directed networks, there are often such types of dilations and inaccessibility. The edges in dilations and inaccessibility are huge obstacles for structural controllability of the network. Because they can lead the network to discount ability to state structural controllability. Usually, we call these edges as “inappropriate edges.” Firstly, we must recognize these “inappropriate edges Then, change the directions of the edges. The literature [59] summarized several types of “inappropriate edges,” as shown in Figure 2. The literature [57] mainly discussed how to remove these “inappropriate edges” and added the same number of new edges in the meantime, neglecting the impacts of edge direction on the enhancement network controllability.Figure 2
The type of candidate edges. (a) SI: edges from a start node to an isolated node; (b) IE: edges from an isolated node to an end node; (c) SE: edges from a start node to an end node; (d) SS: edges from a start node to a start node; (e) EE: edges from an end node to an end node. Candidate edges are marked by dashed edges; isolated nodes are marked by black diamonds; start nodes are marked by green circles; middle nodes are marked by violet pentagons; end nodes are marked by red triangles.
(a)
(b)
(c)
(d)
(e)Firstly, add the edges with the opposite direction into the initial directed network G (see Figure4(a)) and get a symmetric directed network, recorded as G' (see Figure 4(b)). Here assume that the weight of each initial edge is 1 and the weight of each new edge is 0. Secondly, translate the symmetric directed network into an undirected switching network, recorded as H (see Figure 4(c)). The translation rules are provided in the next paragraph. Each node aij in H corresponds to a directed edge vi,vj in G, and the weight of each node is 1 or 0.Figure 3
The improved network. The edges assigned by contrary direction are marked by bold edges. Start nodes are marked by green circles; middle nodes are marked by violet pentagons; end nodes are marked by red triangles.
(a)
(b)
(c)
(d)
(e)Figure 4
An example network based on the switching network. (a) An initially directed network G; (b) the symmetric directed network G'; (c) the switching network H; (d) maximum-weighted independent set.
(a)
(b)
(c)
(d)The connection rule between the nodes in H is Rule I: if two nodes in H correspond to the symmetric directed edges in G, then it needs to connect the two nodes, shown as the black edges in Figure4(c); Rule II: if two nodes in H correspond to the symmetric directed edges having the same tail or head node in G, then it needs to connect the two nodes, shown as the red and green edges in Figure 4(c). According to such rules, we can get the switching network H.Then, seek the maximum-weighted independent set of H. In the maximum-weighted independent set (see Figure4(d)), the node with weight 0 means the corresponding to an edge of G needs to change the direction.Therefore, by using this method we can find those edges which need to change directions. Of course, there may be several different maximum-weighted independent sets, but each set contains the same number of nodes. Different maximum-weighted independent sets mean different control configurations.Indeed, it is a typical NP-hard problem to seek a maximum-weighted independent set for arbitrary graphs according to computational complexity theory.In general, these methods have their advantages and disadvantages. In the future, we will need to combine the advantages of both and present a hybrid approach to enhance the structural controllability of complex networks.


## 3.1. Based on Adding Edges, Enhancing the Structural Controllability of Complex Networks

Based on adding edges, there are two ways to enhance the structural controllability of complex networks. One is simply to add some new edges into the network, and another is to add some new edges and remove the same number edges (original edges) at the same time. The former makes the number of edges in the network increase. In the latter case, the number of edges remains unchanged in the network.Adding edges can be implemented in two ways: randomly adding edges and intentionally adding edges according to a certain formula. Randomly adding edges means randomly selecting two nodes and adding an edge between them if there is no edge between them. Intentionally adding edges means according to a certain formula selecting two nodes and adding an edge between them if there is no edge between them, for example, based on node degree ratiokr [55], where kr=kout+1/kin+1. After adding an edge, if the number of driver nodes decreases, then keep the new edge. If the number of driver nodes does not change, then delete the new edge and choose again. Here, we introduced two kinds of intentionally adding edges to enhance the structural controllability of complex networks.Maximum matching of a graph is not unique and the corresponding set of matched nodes is not the same. Hence, choosing different maximum matchings would result in different sets of unmatched nodes, that is, different sets of driver nodes. According to the frequency of nodes occurrences within all the minimum sets of driver nodes, all nodes can be divided into three categories: critical nodes, ordinary nodes, and redundant nodes [36]. Critical nodes represent that they appear in every minimum set of driver nodes. Redundant nodes represent that they do not appear in any minimum set of driver nodes. Ordinary nodes represent that they appear in part of the minimum sets of driver nodes. Analogously, all edges can be divided into three categories: critical edges, ordinary edges, and redundant edges [31]. Critical edges mean if they are removed from the network, then the number of the minimum sets of driver nodes will increase for the case where the network states are structural controllability. Redundant edges mean they are removed from the network without altering the number of the minimum sets of driver nodes. And yet, ordinary edges mean they are removed affecting some of the minimum sets of driver nodes.Thus it can be seen that adding a new edge may enhance the structural controllability of complex networks, but definitely would not make it weaken. Enhancing structural controllability of complex networks is to make as multitude critical edges and as fewer redundant edges. Therefore, the literature [55] proposed a method of enhancing structural controllability of complex networks by using adding some critical edges while removing the same number of redundant edges. The method [55] was based on the node degree ratio and was presented in detail as follows.Step 1: In the entire network select a node with the smallestkr, denoted as Vminkr, and select another node with the largest kr, denoted as Vmaxkr. If there is more than one such node with the smallest kr, then randomly select one of those. For node Vmaxkr, it is similar to the node with the smallest kr.Step 2: Add a new directed edge withVminkr as a starting node and Vmaxkr as an ending node. If there is already an edge between the two selected nodes, then reselect until there does not exist an edge between the two selected nodes.Step 3: After adding a directed edge, recount the degree ratio of nodes and repeat the above steps.Compared with the method of random adding edges, this method is more effective. The validity of the method is to reduce the heterogeneity degree of a network, which should contribute to enhancing the controllability of the network.Moreover, Wang et al. [51] studied, for a directed network with N state nodes, if we use only one input node to control the network, how many we need to add edges into the network, and which positions we need to add edges in the network. On the basis of the literature [31], an optimization algorithm of adding edges was proposed. Firstly, the maximum matching set of the network is divided into three categories: directed paths, circles, and isolated nodes. Circles do not need an additional input signal to control. Therefore they do not need to be considered. Then, all directed paths and isolated nodes are connected with one another in turn head-to-tail and form a new directed path.


## 3.2. Based on Reversing Edge Directions, Enhancing the Structural Controllability of Complex Networks

Although the controllability of a network could be enhanced by adding some edges, the topology of the network would be changed. In addition, from the point of view of cost, adding some edges into a network, for example, a power network, requires a high price. Hence, for some actual networks, it is not feasible by adding some edges to improve their controllability. The edge direction plays a vital role in the controllability of a network. Based on this, it was proposed reversing some edge directions to enhance the structural controllability of complex networks [56–58]. This way keeps the total number of edges unchanged and also does not change the network topology.As earlier work has already pointed out, the maximum matching consists of isolated nodes, matching paths, and matching cycles. Isolated nodes are invariably unmatched. Each matching path contains only an unmatched node. Since matching cycles do not contain unmatched nodes, matching cycles are not needed to be taken into consideration. Accordingly,ND is equal to the total number of isolated nodes and matching paths. If we connect an isolated node or matching path to another isolated node or matching path, ND decreases by one.Based on the maximum matching, nodes can be categorized into four types: start nodes, middle nodes, end nodes, and isolated nodes [56]. Start nodes have an outgoing edge and no incoming edge. If a node has only an outgoing edge without incoming edges, then the node is a start node. Instead, if a node has only an incoming edge without any outgoing edges, then the node is an end node. If a node has both outgoing and incoming edges, then the node is a middle node. And yet, if a node has no edges belonging to the maximum matching, then the node is an isolated node.Based on the type of a node, five types of edges need to change directions. Those edges were called candidate edges. The five types of edges were referred to as SI, IE, SE, SS, and EE (see Figure2). (a) SI: edges leading from a start node pointing to an isolated node; (b) IE: edges leading from an isolated node pointing to an end node; (c) SE: edges leading from a start node pointing to an end node; (d) SS: edges leading from a start node pointing to a start node; (e) EE: edges leading from an end node pointing to an end node.The algorithm [56] is the following:Step 1: According to the Hopcroft–Karp algorithm [30], obtain a maximum matching of a network.Step 2: All the nodes are categorized into four types: start nodes, middle nodes, end nodes, and isolated nodes.Step 3: Identify the candidate edges: SI, IE, SE, SS, and EE.Step 4: Run through a sequence of operations on the candidate edges with the type SI. In the first place, change the directions of the candidate edges with the type SI. There is one more point, based on the new matching path, the types of the corresponding nodes and edges are refreshed. Apply the same operations to the candidate edges with the types IE and SE.Step 5: Run through a sequence of operations on the candidate edges with the type SS. The first and foremost is to compare the length of two matching paths. Secondly, change the directions of the edges in the shorter path. Then, based on the new matching path, the types of the corresponding nodes and edges are refreshed. Apply the same operations to the candidate edges with the type EE.Step 6: The controllability of the network has improved to some extent after changing the edge direction. Then, gain a new maximum matching of the improved network (see Figure3). When the controllability of the network has reached the desired state or its controllability of the network remains constant in the long run, the algorithm stops, or return to Step 2.On the basis of the matching path, the basic thought of the method is to seek candidate edges. This method is based on only part structure and offers a strategy to improve the controllability. Since the global topology of numerous real networks is unknown and, in general, we just get part structure information, this strategy may be more practical than those that need whole topology information.


## 3.3. Based on Maximum-Weighted Independent Set, Enhancing the Structural Controllability of Complex Networks

In directed networks, there are often such types of dilations and inaccessibility. The edges in dilations and inaccessibility are huge obstacles for structural controllability of the network. Because they can lead the network to discount ability to state structural controllability. Usually, we call these edges as “inappropriate edges.” Firstly, we must recognize these “inappropriate edges Then, change the directions of the edges. The literature [59] summarized several types of “inappropriate edges,” as shown in Figure 2. The literature [57] mainly discussed how to remove these “inappropriate edges” and added the same number of new edges in the meantime, neglecting the impacts of edge direction on the enhancement network controllability.Figure 2
The type of candidate edges. (a) SI: edges from a start node to an isolated node; (b) IE: edges from an isolated node to an end node; (c) SE: edges from a start node to an end node; (d) SS: edges from a start node to a start node; (e) EE: edges from an end node to an end node. Candidate edges are marked by dashed edges; isolated nodes are marked by black diamonds; start nodes are marked by green circles; middle nodes are marked by violet pentagons; end nodes are marked by red triangles.
(a)
(b)
(c)
(d)
(e)Firstly, add the edges with the opposite direction into the initial directed network G (see Figure4(a)) and get a symmetric directed network, recorded as G' (see Figure 4(b)). Here assume that the weight of each initial edge is 1 and the weight of each new edge is 0. Secondly, translate the symmetric directed network into an undirected switching network, recorded as H (see Figure 4(c)). The translation rules are provided in the next paragraph. Each node aij in H corresponds to a directed edge vi,vj in G, and the weight of each node is 1 or 0.Figure 3
The improved network. The edges assigned by contrary direction are marked by bold edges. Start nodes are marked by green circles; middle nodes are marked by violet pentagons; end nodes are marked by red triangles.
(a)
(b)
(c)
(d)
(e)Figure 4
An example network based on the switching network. (a) An initially directed network G; (b) the symmetric directed network G'; (c) the switching network H; (d) maximum-weighted independent set.
(a)
(b)
(c)
(d)The connection rule between the nodes in H is Rule I: if two nodes in H correspond to the symmetric directed edges in G, then it needs to connect the two nodes, shown as the black edges in Figure4(c); Rule II: if two nodes in H correspond to the symmetric directed edges having the same tail or head node in G, then it needs to connect the two nodes, shown as the red and green edges in Figure 4(c). According to such rules, we can get the switching network H.Then, seek the maximum-weighted independent set of H. In the maximum-weighted independent set (see Figure4(d)), the node with weight 0 means the corresponding to an edge of G needs to change the direction.Therefore, by using this method we can find those edges which need to change directions. Of course, there may be several different maximum-weighted independent sets, but each set contains the same number of nodes. Different maximum-weighted independent sets mean different control configurations.Indeed, it is a typical NP-hard problem to seek a maximum-weighted independent set for arbitrary graphs according to computational complexity theory.In general, these methods have their advantages and disadvantages. In the future, we will need to combine the advantages of both and present a hybrid approach to enhance the structural controllability of complex networks.


## 4. Summary and Outlooks

At the end of the the 20th century, network science started to emerge, and in the past several years it has made significant overall progress. Particularly in the past two years, the research results have jumped from simple network science to network engineering and made the momentous meaning of the network control and measures have been highly developed [29, 40, 42, 61–68]. By now, network science and engineering had grown into one independent and new subject of research. Among them, network control, which is the ultimate goal of network science, is at the forefront of network science. Interestingly, the judgment method of the controllability of complex networks is derived from classical control theory but with its differences. We have given an extensive survey of the current controllability of complex networks research in this paper. Highlighting the motivation for enhancing the controllability of complex networks, we have also presented different approaches of enhancing networks controllability in the literature. We have presented a taxonomy of issues found in this area and the approaches in which these issues have been tackled. Maybe later more effective methods can improve networks controllability to guarantee the stability of extremely pivotal infrastructure systems. Finally, based on the related literature, at the end of the article we carried on the summary and also raised some problems which need further research from our personal point of view. These are the gaps in the reviewed work that would prove to be directions for future work.(i)
In the paper, the methods mentioned, of course, only apply to linear coupling dynamical systems of complex networks. In reality, however, there are all kinds of dynamical systems of complex networks, such as switched network dynamical systems, bilinear network dynamical systems, nonlinear network dynamical systems, and so on. The systems have more diverse and complex dynamic behaviors. Consequently, it is more arduous to control these systems and we need further technical development and perfect the control theories and methods of complex networks systems.(ii)
At present, there are corresponding strategies to enhance the structural controllability of complex networks. And yet, the researches on enhancing exact controllability of complex networks have not been systematically studied. Therefore, how to find more effective control strategies to solve the optimization problem of exact controllability of complex networks?(iii)
Since the control range of the combination of multiple nodes has no related conclusions, further study is still needed.(iv)
There are two issues to fulfilling control of large-scale complex networks: one is structural controllability and the other is optimal control. Structural controllability implies that in finite time it is able to guide a dynamical system from any initial state to any desired final state, with a suitable choice of inputs. Optimal control is a central topic of control theory and refers to minimize the cost of driving the network to a predefined state with a given number of control inputs [69]. For large-scale complex networks without global information of network topology, combining graph theory and control theory, the literature [70] solved the two issues simultaneously using only local network topology information. However, it is often difficult to accurately distinguish the size of the network. How large is a large-scale network? And for different dimensions networks, how to compare their controlabilities? In the future, we need to develop a more universal theory to solve two problems.(v)
How to put the theory mentioned into the reality networks, e.g., smart grid, and to make the actual networks toward the expected direction? How to use the theories and methods of controllability of complex networks to study the dynamics of social collective behavior patterns?



---

*Source: 5759264-2020-03-27.xml*