Effects of Edge Directions on the Structural Controllability of Complex Networks

Yandong Xiao; Songyang Lao; Lvlin Hou; Michael Small; Liang Bai

doi:10.1371/journal.pone.0135282

Abstract

Recent advances indicate that assigning or reversing edge direction can significantly improve the structural controllability of complex networks. For directed networks, approaching the optimal structural controllability can be achieved by detecting and reversing certain “inappropriate” edge directions. However, the existence of multiple sets of “inappropriate” edge directions suggests that different edges have different effects on optimal controllability—that is, different combinations of edges can be reversed to achieve the same structural controllability. Therefore, we classify edges into three categories based on their direction: critical, redundant and intermittent. We then investigate the effects of changing these edge directions on network controllability, and demonstrate that the existence of more critical edge directions implies not only a lower cost of modifying inappropriate edges but also better controllability. Motivated by this finding, we present a simple edge orientation method aimed at producing more critical edge directions—utilizing only local information—which achieves near optimal controllability. Furthermore, we explore the effects of edge direction on the controllability of several real networks.

Citation: Xiao Y, Lao S, Hou L, Small M, Bai L (2015) Effects of Edge Directions on the Structural Controllability of Complex Networks. PLoS ONE 10(8): e0135282. https://doi.org/10.1371/journal.pone.0135282

Editor: Satoru Hayasaka, Wake Forest School of Medicine, UNITED STATES

Received: May 25, 2015; Accepted: July 20, 2015; Published: August 17, 2015

Copyright: © 2015 Xiao et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited

Data Availability: The data of real networks are available from the network controllability database (http://boseinst.ernet.in/soumen/Network_Controllability_Datasets.html). Other data are within the paper and its Supporting Information files.

Funding: This work was supported by Fundamental Funds for Open Cooperation Research under grant number 2014021 and the Graduate Innovation Fund under grant number B150501. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

Competing interests: The authors have declared that no competing interests exist.

Introduction

One of the most fundamental challenges in network science is to understand the impact of structural properties on network functionality. In part, this is because understanding the network structure is prerequisite to answering the challenging questions related to the system’s dynamics [1–3]. Structure and dynamics are always coupled and ultimately led to many remarkable advances in the past decade in such areas as epidemic spreading [4, 5], random walks [6, 7], cascade failure [8, 9], and synchronization [10, 11]. Questions concerning the management and control of complex networks are important in engineering [12], finance [13], biology [14] and other fields because the ultimate proof of our understanding of such complex systems and their basic principles is reflected in our ability to control [15–19] and ultimately observe them [20]. The framework for computing the controllability of complex networks proposed by Liu and Barabási [19] offers a general, rigorous, and well-understood means of investigating how we can control complex networks with the fewest input signals. Recent advances in the application of control theory to complex networks have shed new light on this problem [21–30]. The main finding has been that the application of external signals to some subset of nodes can cause a system to approach a desired state within finite time.

Obviously, controllability in general can be achieved through the control of only the subset of nodes termed driver nodes. The minimum driver node set can be efficiently identified using the Minimum Inputs Theorem of Ref. [19]. Based on this approach to the minimization of the driver node set, several advances in the optimization of network controllability have already been made, the most representative methods of which rely on adding edges [25, 31], rewiring edges [32] and assigning edge directions [33, 34]. Compared with the first two methods (which stem from the modification of the network structure), assigning edge directions to optimize network controllability appears to be the most effective from the perspective of designing a network with improved or even optimal controllability because it neither changes the original structure of the network nor incurs the external cost of adding links. By edge orientation, we refer to the process of assigning edge directions to undirected edges in an undirected network or (equivalently) reversing the directions of directed edges in a directed network. This method aims to approach optimal controllability without requiring any modification of the network structure, by which we mean that the presence or absence of a link between each pair of nodes remains unchanged. To this end, Xiao et al. [34] have systematically proposed the definition and solution for the edge orientation of optimal controllability (EOOC). Solving the EOOC problem requires constructing a corresponding network and transforming the problem into one of finding a maximum independent set (MIS) of this corresponding network.

For directed networks, there are certain “inappropriate” edge directions that may weaken the controllability of a network, i.e., so-called dilations and inaccessibility. First, we must identify all these “inappropriate” edge directions in a network and then reverse them. However, there are several different “inappropriate” direction sets for a given network, and the existence of multiple “inappropriate” direction sets suggests that different edges play different roles in optimal controllability. Previous work has focused on how to detect these “inappropriate” edge directions while ignoring the effects of edge direction on the optimal network controllability. In this work, we briefly review the definition of the EOOC and the framework in which to solve this problem. The remainder of this paper is organized as follows. We first classify all edge directions into three categories: critical edge directions, which always appear in the optimal direction set during the optimization process and are also called the skeleton of optimal controllability; redundant edge directions, which have no effect on optimization; and intermittent edge directions, which participate in some optimal direction sets but not others. In Ref. [29], Jia et al. also propose the similar definition of node classification to explore the role of individual nodes in acting as a driver node in all, some or none of the control configurations. However, though the definitions of node classification and edge classification are similar ideas, the research points do not have directed relations. It is because that we study the roles of edge direction when we assign them to approach the optimal controllability for a given network skeleton. Next, we study the correlation between critical edge directions and driver nodes and demonstrate that the existence of more critical edge directions in a network implies not only a lower cost of modifying inappropriate edges but also better controllability. Motivated by this finding, we analyze the structural properties of the three categories of edge directions and develop a simple edge orientation method based on the generation of more critical edge directions. The results of numerical experiments suggest that this method achieves a near-optimal optimization effect while requiring only local structural information. Finally, we apply the developed tool to a series of real networks and successfully explain why the structures of electronic circuit networks take advantage of controllability.

Edge Orientation for Optimal Controllability

Ref. [34] provides a general solution to the problem of finding an edge direction set for optimal controllability, summarized as follows. First, construct a corresponding network and transform the EOOC problem into a problem of finding a maximum independent set of vertices in the corresponding network. A directed network G (Fig 1(a)) and its corresponding symmetric directed network G′ (Fig 1(b)) are a pair (V, E) and (V, E′) that consisted of a set of nodes V and edges E, E′. If each directed edge (v_i, v_j) in G′ corresponds to a node a_ij, then we can construct a corresponding network H = (A, B) that consisted of a set of nodes A and edges B. The construction of links in H follows three simple principles.

Rule I: two nodes in H that correspond to a pair of symmetric directed edges of G′ must be connected (green edges in Fig 1(c)).
Rule II: two or more nodes in H that correspond to the edges pointing to a tail node must be connected (purple edges in Fig 1(c)).
Rule III: two or more nodes in H that correspond to the edges pointing from a head node must be connected (orange edges in Fig 1(c)).

Download:

Fig 1. Illustration of Edge Orientation for Optimal Controllability.

(a) A directed network G = (V, E) with 5 nodes and 5 directed edges. For directed networks, some edges with “inappropriate” direction affect the controllability of networks, such as e_ed. If we change its direction, we can improve the controllability. (b) G′ is the symmetric directed network. Here we assume that the weight of real edge is 1 otherwise it is 0. Thus it results in the nodes of H with different weight. (c) The corresponding network H. The maximum-weighted independent set means not only the optimal edge orientation but also the least number of edges required to have their direction changed, because the node with weight 0 (the white nodes) in the maximum-weighted independent set implies the “inappropriate” edge of G. (d) The different maximum-weighted independent sets result in the different control configurations. The light blue nodes represent the real edges of G.

https://doi.org/10.1371/journal.pone.0135282.g001

The next step is to calculate the maximum independent vertex set of H. Ref. [34] has shown that through the assignment of edge directions based on the MIS of H, the optimal controllability can be approached for a given undirected network. The detailed proof of this assertion can be found in Ref. [34]. In fact, the EOOC effectively mitigates the negative effects of inaccessibility and dilations, which are the two main factors that weaken network controllability.

In directed networks, the EOOC can allow for the detection of several “inappropriate” edges and the reversal of their directions to approach optimal controllability. For example, in Fig 1(a), the edge e_ed weakens the controllability because this directed edge results in the inaccessibility of node e. If we reverse the original direction of e_ed, the number of required driver nodes decreases from 2 to 1. The extent of the directed network for the EOOC only considers the edge weights of the original network. We assume a directed graph G = (V, E, W) and its symmetric directed graph G′ = (V, E′, W′), both of which are edge-weighted (W, W′ represent the edge weight set). The weight of any real edge is 1 if it exists in G′; otherwise, it is 0 (Fig 1(b)). Thus, every node of H = (A, B, W′) corresponds to weight 0 or 1. The maximum-weighted independent set (MWIS) of vertices in H corresponds to the orientation set for optimal controllability of the directed network G. The basic theory follows from the analysis of the EOOC for an undirected network. The principle of maximum weight guarantees that the independent set contains the most nodes of weight 1 and the fewest nodes of weight 0, meaning that the number of edges that need to be modified is minimal. For example, Fig 1(d) shows the MWIS of H. The white nodes represent the reversal of “inappropriate” edge directions in Fig 1(a). It has been proven that the calculation of the MWIS is a typical NP-hard problem in computational complexity theory [35–37]; thus, a polynomial-time algorithm to find MWIS solutions for arbitrary graphs is not feasible. In the following, we will proceed using an integer linear programming (ILP) formulation for MWIS computation, in which the optimal solution was calculated using the IBM ILOG CPLEX v.12.6. From H = (A, B, W′), the ILP instance is constructed as following: (1) The set {v∣x_v = 1} then clearly corresponds to a maximum-weighted independent set.

Categories of Edge Directions for Optimal Structural Controllability

A directed network possesses several sets of “inappropriate” edges because there are multiple MWIS configurations by which the network can approach optimal controllability. This phenomenon suggests that different edge directions have different effects on the optimal structural controllability. Therefore, the existence of these multiple configurations leads to the classification of edge directions into three categories: critical edge directions, corresponding to edges that are always present in the MWIS configurations; redundant edge directions, describing those edges that are never a part of an MWIS; and intermittent edge directions, corresponding to edges that participate in some MWISs but not in others. According to these definitions, edges that belong to the critical direction set play a significant role in the optimal controllability because they must appear in any optimal orientation set. Thus, the critical direction set can be regarded as the skeleton of optimal controllability. Conversely, the redundant direction set has no effect on the optimal controllability. The role of intermittent edge directions lies somewhere between these two extremes, as some cases require the directions of these edges to be reversed to approach optimal controllability. Fig 2 shows all optimal control configurations identified using the MWIS approach for Fig 1(a). The red edges in Fig 2(a), 2(b) and 2(c) and the red nodes in Fig 2(d) indicate the critical edge directions of the initial directed network G. The blue nodes in Fig 2(d) correspond to the intermittent edge directions. The blue dashed edge in Fig 2(a), 2(b) and 2(c) becomes an “appropriate” edge after the reversal of the original directions.

Download:

Fig 2. Illustration of classification of edge direction for EOOC in a directed network.

(a, b, c) The networks are modified by maximum-weighted independent sets showing optimal controllability. (d) The different maximum-weighted independent sets show the different control configurations. The red nodes, e_ab and e_bc, always appear on the MWIS, called the critical edge direction. The blue nodes, defined as intermittent edge directions, participate in some MWISs but not every MWIS.

https://doi.org/10.1371/journal.pone.0135282.g002

The detailed procedures CriticalMWIS (Algorithm 1 in S1 File) and RedundantMWIS (Algorithm 2 in S1 File) for the classification of edge directions are included in S1 File. Fig 3 shows the fractions of critical, redundant and intermittent edge directions in two basic network models of different average degree 〈k〉, the Erdös-Rényi (ER) model [38], and scale-free (SF) model [39]. SF networks are generated from the static model in Ref. [40]. Note that in the case of γ → ∞, this model is equivalent to the classical ER random network model. The green columns represent edges with weight 0, i.e., the non-real edges in the original directed networks. According to the definition of critical edge directions, the directions of edges with weight 0 (green columns) in the critical set must be modified during the optimization process. However, as 〈k〉 increases, the proportion of the critical set consisting of edges with weight 0 decreases and may even vanish. In the redundant edge direction set, non-real edges constitute the larger proportion, and as 〈k〉 increases, the redundant set tends to consist entirely of non-real edges. Compared with the redundant set, the intermittent edge direction set exhibits the opposite tendency of variation, as real edges constitute the larger proportion of this set. In particular, for an ER network with high 〈k〉, the intermittent set tends to consist entirely of real edges.

Download:

Fig 3. Characteristics of the fraction of three different edge direction sets in the directed networks.

(a-c) ER network under different average degree 〈k〉. (d-f) SF network with γ = 2.5 under different average degree 〈k〉. The grey columns represent the real edges in the original directed networks G or nodes with weight 1 in the corresponding network H, while the green columns imply the non-real edges in G or nodes with weight 0 in H. The number of nodes is 10³.

https://doi.org/10.1371/journal.pone.0135282.g003

In fact, the critical edge direction set can be regarded as the skeleton of optimal controllability because these directions can never be modified. In other words, these directions are always appropriate for a given network. If a network contains a larger number of critical edge directions, it implies not only a lower cost for modifying “inappropriate” edge directions but also better controllability. Therefore, we analyze the relationship between driver nodes and critical edge directions. Here, the fraction of driver nodes is a measure of the network controllability because the existence of fewer driver nodes implies better controllability. For a network with a fixed average degree, as shown in Fig 4, we consider various fractions of critical edge directions and their corresponding driver nodes in the ER and SF models. Here, a different fraction of critical edge directions in a given network is produced by edge swapping while keeping the degree of each node unchanged. Hence, in the original network, we swap the connections of two randomly chosen edges; that is, the edges e_ij and e_kl become edges e_il and e_kj, respectively. At each step, we calculate and compare the fractions of critical edge directions before and after the edge swap. If the fraction of critical edge directions decreases, we consider the swap to be successful. If it is unsuccessful, the swap is reversed, and another swapping step is tested. As seen in Fig 4, for both ER and SF model, the number of driver nodes decreases with an increasing fraction of critical edge directions. The numerical results confirm the above analysis.

Download:

Fig 4. Scatterplot of the faction of critical edge directions the corresponding driver nodes.

The number of nodes is 10³. We repeat this procedure until the total number of swapping reaches 10⁶. The results are 10 independent realizations.

https://doi.org/10.1371/journal.pone.0135282.g004

Structural Analysis of Critical Edge Directions

To more deeply understand the properties of the three different edge direction sets, we analyze the corresponding degrees of edges with critical, redundant and intermittent edge directions. Here, the corresponding degree of an edge means its number of neighboring nodes in the corresponding network H, as every directed edge corresponds to a node in H. Fig 5(a) and 5(b) reproduce portions of Fig 1(c) and 1(b), respectively, to illustrate the meaning of the corresponding degree of an edge. The four nodes in Fig 5(a) correspond to the four edges in Fig 5(b), according to the rules of EOOC. In fact, these four edges in Fig 5(b) represent three “inappropriate” control conditions: two edges pointing toward the common tail (red and purple edges), two edges pointing from the head node (red and orange edges) and two edges constituting a 2-cycle (red and green edges). The first two “inappropriate” control conditions, called inaccessibility and dilation, respectively, can weaken controllability and should appear in a network as rarely as possible. The last condition, edges constituting a 2-cycle, is meaningless with regard to edge orientation because EOOC only assigns a single direction for an undirected link. According to the rules of link construction in H, the node in Fig 5(a) is connected with other nodes which produces the above three “inappropriate” conditions. Therefore, the corresponding degree of an edge reflects its associated number of “inappropriate” control conditions. Ref. [34] has deduced the node degree of the corresponding network H, i.e., (2) Here, a_{(i, j)} and a_{(j, i)} are the symmetric directed edges and correspond to two nodes in H, and k_{a(i, j)} is the corresponding degree of a directed edge.

Download:

Fig 5. Illustration of three “inappropriate” control conditions.

The red and green edges of (b) constitute a 2-cycle—which is meaningless for EOOC. The red and orange edges of (b) point from the common head node which produces dilation in the network. The red and purple edges of (b) point to the common tail node which increases an inaccessible node in the network. Actually, the corresponding degree of directed edge v_ba means the number of “inappropriate” control conditions.

https://doi.org/10.1371/journal.pone.0135282.g005

Fig 6 shows the average corresponding degrees of the critical, redundant and intermittent edge direction sets under various values of 〈k〉 for the ER and SF networks. The average corresponding degrees of the three direction categories represent the average numbers of associated “inappropriate” control conditions. In Fig 6(a) and 6(b), as 〈k〉 increases, the average corresponding degrees of all three categories also increase. However, compared with the other two direction sets, the critical direction set has the smallest average corresponding degree. Meanwhile, the redundant edge set has the largest average corresponding degree. The corresponding degree of the intermittent edge set is between those of the critical and redundant direction sets. Fig 6(c) and 6(d) display the corresponding degrees of edges with a weight of 1 (real edges) or 0 (non-real edges). For all three direction categories, the average corresponding degrees of real edges are larger than those of non-real edges. Moreover, the corresponding degree of critical edge directions associated with non-real edges initially increases and then decreases with increasing 〈k〉. It is because that, with the increase of 〈k〉, the fraction of critical edge directions corresponding to non-real edges become smaller and even disappeared, which could be approved by Fig 3(a) and 3(d). So these non-monotonic results are caused by the decrease in the number of critical edge directions associated with non-real edges. Therefore, an edge direction associated with fewer “inappropriate” control conditions is more likely to be a critical edge direction.

Download:

Fig 6. Characteristics of the corresponding degree of critical, redundant and intermittent edge direction set under different 〈k〉 for ER and SF networks.

The corresponding degree of edge direction means the number of “inappropriate” control conditions. The subplots (c, d) display the degree of edge with weight 1 (real edges) and 0 (non-real edges) respectively. The number of nodes is 10³.

https://doi.org/10.1371/journal.pone.0135282.g006

In Fig 7, we classify the real edges into three categories and rank the nodes in ascending order of corresponding degree. In accordance with the symmetric property of the corresponding network, we also display the category of each non-real edge. Thus, the x axis of Fig 7 refers to pairs of symmetric directed edges (real and non-real edges). Notably, the degrees of the symmetric non-real edges are also ranked in ascending order, and the two symmetric non-real edges have same degree. As seen from Fig 7, all symmetric non-real edges corresponding to edges in the critical edge direction set appear in the redundant edge direction set. This is because the critical edge directions appear in every MWIS and, therefore, their symmetric edges can never appear in any MWIS. With regard to the real edges associated with intermittent edge directions, their symmetric non-real edges of low degree also tend to belong to the category of intermittent edge directions, whereas most of their symmetric non-real edges of high degree are likely to appear in the redundant edge direction set. With regard to the real edges associated with redundant edge directions, their symmetric non-real edges of low degree tend to appear in the intermittent edge direction set or even the critical edge direction set, but their symmetric non-real edges of high corresponding degree are still likely to have redundant edge directions. These results indicate that nodes of low degree may have either significant (due to their critical edge directions) or partial (due to their intermittent edge directions) effects on optimal controllability.

Download:

Fig 7. Characteristics of the category of symmetric real and non-real edges for ER and SF models.

The x-axis displays every two symmetric directed edges. The real edges are divided into three categories and are ranked in ascending order of node degree. Due to the symmetric real and non-real edges having the same degree, the non-real edges are also ranked in the ascending order of degree. The number of nodes is 10³.

https://doi.org/10.1371/journal.pone.0135282.g007

Edge Orientation by Critical Directions

In this section, we present a method for generating more critical edge directions, which we call edge orientation by critical directions (EOCD). The different categories of edge directions play different roles in the optimal controllability of a network. Based on the above analysis, we can draw two conclusions: (i) more critical edge directions are beneficial for enhancing controllability and decreasing the cost of improvements because there are fewer driver nodes and fewer “inappropriate” directions to be reversed, and (ii) an edge direction associated with fewer “inappropriate” control conditions is more likely to be a critical edge direction, that is, low-degree nodes have positive effects on optimal controllability. Moreover, previous studies of network controllability have indicated that the number of driver nodes is correlated with the control path [33] and the density of low in- and out-degree nodes [31]. In fact, the EOOC [34] approach attempts to produce the longest disjoint control path after the orientation of edge directions. Thus, we propose an edge orientation algorithm to produce the longest possible disjoint control path and as many critical edge directions as possible, starting from a node of the lowest degree. Consider an undirected network G(V, E). The EOCD method can be described as follows. The residual degree k′ of a node represents the number of undirected links of that node; k′ is initially equal to k, where k is the degree of the node. Note that if there are multiple such nodes matching the conditions, we randomly select one of them.

Compute k′(i) + k′(j) for two nodes i and j connected by a link e_ij. Select the two nodes with the smallest sum of their residual degree. The selected node with the smaller degree is denoted as V₁, and the selected node with big degree is labelled as V₂. Note that we do not consider the isolated nodes.
Assign the edge direction to be from V₁ to V₂. Consequently, the residual degree of the selected nodes is reduced, i.e., k′(V₁) = k′(V₁) − 1, k′(V₂) = k′(V₂) − 1.
Select the node with the smallest degree among the neighbors of V₂, and confirm that the newly selected node is not yet labelled. The newly selected node is denoted by V₂, and the node formerly labeled V₂ is now re-labelled as V₁. Note that V₁ and V₂ are different.
Repeat step (ii) until all neighbors of V₂ are labeled.
If k′ is equal to 0 for all nodes, proceed to step (vi). Otherwise, clear the labels all nodes, delete the assigned edges, and repeat step (i).
Orient all edge directions assigned at step (ii).

For comparative experiments, we consider the method of random direction assignment (RAD), a method based on the node residual degree (NRD) [33] and the method of edge orientation for optimal controllability (EOOC) [34]. Assigning directions based on the node residual degree (NRD) is an effective method of enhancing network controllability that is superior to random direction assignment (RAD). However, the NRD method cannot consider the effects of critical edge directions. The EOCD method is similar to the NRD method except for the manner in which the starting node is selected for each orientation step. Fig 8 (a), 8(b) and 8(c) present the optimization results of EOCD, which are close to the optimal EOOC solutions and superior to the NRD results. Fig 8 (d), 8(e) and 8(f) indicate that EOCD can generate more critical edge directions than the NRD method but, naturally, fewer than the EOOC. Moreover, the EOCD method is advantageous in terms of time complexity because it neither constructs a corresponding graph nor calculates the maximum independent set. In other words, EOCD requires only local structural information but achieves a near-optimal result.

Download:

Fig 8. Characteristics of fraction of driver nodes (n_D) and critical edge directions as a function of 〈k〉 for the method of random direction assignment (RAD), the method based on node residual degree (NRD), the method of edge orientation for optimal controllability (EOOC) and the method of edge orientation by critical directions (EOCD) on (a, d) ER networks, (b, e) SF networks with γ = 2.5, (c, f) SF networks with γ = 3.

The number of nodes is 10³.

https://doi.org/10.1371/journal.pone.0135282.g008

Analysis of Real Networks

We now use the tools developed above to explore the controllability of several real networks, presented in Table 1. Previous work [19] has shown that there is no correlation between the N_D of an original network and the N_D of its randomized counterpart because a system’s controllability is, to a great extent, encoded by the underlying network’s degree distribution. To identify the topological features that affect the optimization of network controllability, we randomize each real network using a full randomization procedure (rand-ER) that transforms the network into a directed random ER network with N and L unchanged. We also apply a degree-preserving randomization procedure (rand-Degree), which leaves the in-degree and out-degree of each node unchanged but randomly selects which nodes are linked to each other. From the results presented in Fig 9(b), we find that the optimization is also affected by the network structure because is similar to . In fact, it can be said that the EOOC optimizes the controllability without changing the network skeleton. Moreover, we find that the networks of electronic circuits possess features distinct from those of other real networks. Generally, , because random networks are more easily controlled. However, the of an electronic circuit network is smaller than , and its is also smaller than . These results imply that the structure of an electronic circuit network is highly controllable. Meanwhile, compared with the other networks shown in Fig 9(c), the three electronic circuit networks possess a high number of critical edge directions, which can be regarded that the main skeleton of optimal controllability in these network is higher than other real networks. We also present the degree distributions of the electronic circuit networks in Table 2. Nodes of low degree (k_in or k_out = 1 or 2) account for a large proportion of the degree distribution. The number of driver nodes is determined be the density of low in- and out-degree [31]. Obviously, according to this conclusion, the electronic circuit networks should exhibit poor controllability. However, the true situation is precisely the opposite. The results indicate that the structures of the three electronic circuit networks is beneficial for structural controllability, and in the case of same average degree they require the fewer number of driver nodes.

Download:

Fig 9. Plot of drive nodes of real, rand-Degree and rand-ER network (a) before (

,

) and (b) after optimization by EOOC (

,

), and (c) the faction of critical, redundant and intermittent edge direction of 14 real networks.

https://doi.org/10.1371/journal.pone.0135282.g009

Download:

Table 1. The characteristics of the real networks analyzed in the paper.

For each network, we show its type, name; number of nodes (N) and links (L); driver nodes of real network ; driver nodes of real network after optimization ; driver nodes of rand-Degree network ; driver nodes of rand-Degree network after optimization ; driver nodes of rand-ER network ; driver nodes of rand-ER network after optimization respectively. All the data used are publicly available in the network databases from Ref. [42].

https://doi.org/10.1371/journal.pone.0135282.t001

Download:

Table 2. The degree distribution of Electronic Circuits networks.

https://doi.org/10.1371/journal.pone.0135282.t002

However, of the real networks considered in this paper, the Prison and Protein-1 networks also have high fractions of critical edge directions; why are these two networks unable to demonstrate such excellent controllability? This can be explained in terms of P(k_in = 0). Nodes with k_in = 0 are called source nodes [41] because they must be controlled by input signals, that is, these nodes are driver nodes. In Table 3, it is seen that the P_{rand − ER}(k_in = 0) values of S838, S420 and S208 are much larger than P_real(k_in = 0), whereas the P_{rand − ER}(k_in = 0) values of the Prison and Protein-1 networks are nearly equal to P_real(k_in = 0). Here, P_{rand − ER}(k_in = 0) is calculated using with z₀ = z/2 = 〈k_out〉 = 〈k_in〉. In the three real electronic circuit networks, the low P_real(k_in = 0) values contribute to the fewer driver nodes. By contrast, in rand-ER networks with fixed average degree, the high P_{rand − ER}(k_in = 0) values give rise to more driver nodes. Therefore, from the perspective of P(k_in = 0) and critical edge directions, we can fully explain why the structures of electronic circuit networks are more advantageous with regard to controllability than those of any other real networks.

Download:

Table 3. The P(k_in = 0) of five real networks.

https://doi.org/10.1371/journal.pone.0135282.t003

Discussion

In a directed network, the edge directions are the most significant properties that represent the ubiquitous dynamics of real networks. The edge directions and their correlations influence the driver nodes and are therefore especially relevant to the controllability of complex networks. Previous work has focused on developing edge orientation solutions to achieve the optimal controllability without changing the network structure, and this approach is more economical and practical than other optimization methods, such as adding or rewiring edges. However, it still lacks the ability to reveal the effects of different edge directions on optimal controllability, which could aid in understanding how the network structure affects controllability. For example, the structures of electronic circuit networks are advantageous for controllability despite the vast majority of nodes in these real networks having k_in and k_out values of 1 or 2. Based on the conclusion of previous work, controllability is determined by the density of low in- and out-degree nodes [31]. It is obvious that the electronic circuit networks should exhibit poor controllability. However, the true situation is precisely the opposite. Moreover, through degree-preserving randomization, the controllability of electronic circuit networks decreases noticeably. These behaviors can be explained by observing that these networks contain high concentrations of critical edge directions for optimal controllability. In summary, this work reveals the effects of the different classes of edge directions on optimal controllability and presents a simple edge orientation method based on the properties of the different direction sets. This simple method requires only local information but achieves a near-optimal optimization effect. All results demonstrate that the effects of edge directions can be recognized as a complement to previous measures in understanding network control.

Supporting Information

S1 File. The detailed procedures to computations of CriticalMWIS (Algorithm 1) and RedundantMWIS (Algorithm 2).

https://doi.org/10.1371/journal.pone.0135282.s001

(PDF)

Author Contributions

Conceived and designed the experiments: YDX SYL. Performed the experiments: YDX LLH. Analyzed the data: YDX LLH. Wrote the paper: YDX MS LB.

References

1. Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286: 509–512. pmid:10521342
- View Article
- PubMed/NCBI
- Google Scholar
2. Newman M (2003) The structure and function of complex networks. SIAM Review 45: 167–256.
- View Article
- Google Scholar
3. Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang DU (2006) Complex networks: Structure and dynamics. Physics Reports 424: 175–308.
- View Article
- Google Scholar
4. Moreno Y, Nekovee M, Pacheco AF (2004) Dynamics of rumor spreading in complex networks. Phys Rev E 69: 066130.
- View Article
- Google Scholar
5. Brockmann D, Helbing D (2013) The hidden geometry of complex, network-driven contagion phenomena. Science 342: 1337–1342. pmid:24337289
- View Article
- PubMed/NCBI
- Google Scholar
6. Noh JD, Rieger H (2004) Random walks on complex networks. Phys Rev Lett 92: 118701. pmid:15089179
- View Article
- PubMed/NCBI
- Google Scholar
7. Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci USA 105: 1118–1123. pmid:18216267
- View Article
- PubMed/NCBI
- Google Scholar
8. Motter AE (2004) Cascade control and defense in complex networks. Phys Rev Lett 93: 098701. pmid:15447153
- View Article
- PubMed/NCBI
- Google Scholar
9. Buldyrev S V, Parshani R, Paul G, Stanley HE, Havlin S (2010) Catastrophic cascade of failures in interdependent networks. Nature 464: 1025–1028. pmid:20393559
- View Article
- PubMed/NCBI
- Google Scholar
10. Donetti L, Hurtado PI, Munoz MA (2005) Entangled networks, synchronization, and optimal network topology. Phys Rev Lett 95: 188701. pmid:16383953
- View Article
- PubMed/NCBI
- Google Scholar
11. Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C (2008) Synchronization in complex networks. Physics Reports 469: 93–153.
- View Article
- Google Scholar
12. Sorrentino F, Bernardo M, Garofalo F, Chen G (2007) Controllability of complex networks via pinning. Phys Rev E 75: 046103.
- View Article
- Google Scholar
13. Delpini D. et al (2013) Evolution of controllability in interbank networks. Scientific Reports 3: 1626. pmid:23568033
- View Article
- PubMed/NCBI
- Google Scholar
14. Wuchty S (2014) Controllability in protein interaction networks. Proc Natl Acad Sci USA 111: 7156–7160. pmid:24778220
- View Article
- PubMed/NCBI
- Google Scholar
15. Kalman RE (1963) Mathematical description of linear dynamical systems. Journal of the Society for Industrial & Applied Mathematics, Series A: Control 1: 152–192.
- View Article
- Google Scholar
16. Lin CT (1974) Structural controllability. IEEE Transactions on Automatic Control 19: 201–208.
- View Article
- Google Scholar
17. Rugh WJ (1996) Linear System Theory (Prentice-Hall, Englewood Cliffs, NJ) 2nd ed.
18. Lombardi A, Hörnquist M (2007) Controllability analysis of networks. Physical Review E 75: 056110.
- View Article
- Google Scholar
19. Liu YY, Slotine JJ, Barabási AL (2011) Controllability of complex networks. Nature 473: 167–173. pmid:21562557
- View Article
- PubMed/NCBI
- Google Scholar
20. Liu YY, Slotine JJ, Barabási AL (2013) Observability of complex systems. Proc Natl Acad Sci USA 110: 2460–2465. pmid:23359701
- View Article
- PubMed/NCBI
- Google Scholar
21. Gao J, Liu YY, D’Souza RM, Barabási AL (2014) Target control of complex networks. Nature Communication 5: 5415.
- View Article
- Google Scholar
22. Yuan ZZ, Zhao C, Di ZR, Wang WX, Lai YC (2013) Exact controllability of complex networks. Nature Communication 4: 2447.
- View Article
- Google Scholar
23. Nepusz T, Vicsek T (2012) Controlling edge dynamics in complex networks. Nature Physics 8: 568–573.
- View Article
- Google Scholar
24. Liu YY, Slotine JJ, Barabási AL (2012) Control centrality and hierarchical structure in complex networks. PLoS ONE 7: e44459. pmid:23028542
- View Article
- PubMed/NCBI
- Google Scholar
25. Wang WX, Ni X, Lai YC, Grebogi C (2012) Optimizing controllability of complex networks by minimum structural perturbations. Phys Rev E 85: 026115.
- View Article
- Google Scholar
26. Hou LL, Small M, Lao SY (2014) Maximum entropy networks are more controllable than preferential attachment networks. Phys Lett A 378: 3426–3430.
- View Article
- Google Scholar
27. Pósfai M, Liu YY, Slotine JJ, Barabási AL (2013) Effect of correlations on network controllability. Scientific Reports 3: 1067. pmid:23323210
- View Article
- PubMed/NCBI
- Google Scholar
28. Hou LL, Lao SY, Small M, Xiao YD (2015) Enhancing complex network controllability by minimum link direction reversal. Physics Letters A 379: 1321–1325.
- View Article
- Google Scholar
29. Jia T. et al (2013) Emergence of bimodality in controlling complex networks. Nature Communication 4: 2002.
- View Article
- Google Scholar
30. Jia T, Barabási AL (2013) Control capacity and a random sampling method in exploring controllability of complex networks. Scientific Reports 3: 2354. pmid:23912679
- View Article
- PubMed/NCBI
- Google Scholar
31. Menichetti G, Dall’Asta L, Bianconi G (2014) Network controllability is determined by the density of low in-degree and out-degree nodes. Phys Rev Lett 113: 078701. pmid:25170736
- View Article
- PubMed/NCBI
- Google Scholar
32. Hou LL, Lao SY, Bu J, Bai L (2013) Enhancing Complex Network Controllability by Rewiring Links. IEEE Inter. Conf. on Intelligent System Design and Engineering Applications 709–711.
- View Article
- Google Scholar
33. Hou LL, Lao SY, Liu G, Bai L (2012) Controllability and Directionality in Complex Networks. Chin Phys Lett 29: 108901.
- View Article
- Google Scholar
34. Xiao YD, Lao SY, Hou LL, Bai L (2014) Edge orientation for optimizing controllability of complex networks. Phys Rev E 90: 042804.
- View Article
- Google Scholar
35. Gazmuri PG. Independent sets in random sparse graphs. Networks 14: 367–377.
- View Article
- Google Scholar
36. Balaji S, Swaminathan V, Kannan K (2010) A simple algorithm to optimize maximum independent set. Adv Model Optim 12: 107–118.
- View Article
- Google Scholar
37. Robson J M (1986) Algorithms for maximum independent sets. J Algorithms 7: 425–440.
- View Article
- Google Scholar
38. Erdős P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hungar Acad Sci 5 17–61.
- View Article
- Google Scholar
39. Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286: 509–512. pmid:10521342
- View Article
- PubMed/NCBI
- Google Scholar
40. Goh KI, Kahng B, Kim D (2001) Universal behavior of load distribution in scale-free networks. Phys Rev Lett 87: 278701. pmid:11800921
- View Article
- PubMed/NCBI
- Google Scholar
41. Ruths J, Ruths D (2014) Control profiles of complex networks. Science 343: 1373–1376. pmid:24653036
- View Article
- PubMed/NCBI
- Google Scholar
42. Network controllability datasets. http://boseinst.ernet.in/soumen/Network_Controllability_Datasets.html.

[ref1] 1. Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286: 509–512. pmid:10521342
View Article
PubMed/NCBI
Google Scholar

[2] View Article

[3] PubMed/NCBI

[4] Google Scholar

[ref2] 2. Newman M (2003) The structure and function of complex networks. SIAM Review 45: 167–256.
View Article
Google Scholar

[6] View Article

[7] Google Scholar

[ref3] 3. Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang DU (2006) Complex networks: Structure and dynamics. Physics Reports 424: 175–308.
View Article
Google Scholar

[9] View Article

[10] Google Scholar

[ref4] 4. Moreno Y, Nekovee M, Pacheco AF (2004) Dynamics of rumor spreading in complex networks. Phys Rev E 69: 066130.
View Article
Google Scholar

[12] View Article

[13] Google Scholar

[ref5] 5. Brockmann D, Helbing D (2013) The hidden geometry of complex, network-driven contagion phenomena. Science 342: 1337–1342. pmid:24337289
View Article
PubMed/NCBI
Google Scholar

[15] View Article

[16] PubMed/NCBI

[17] Google Scholar

[ref6] 6. Noh JD, Rieger H (2004) Random walks on complex networks. Phys Rev Lett 92: 118701. pmid:15089179
View Article
PubMed/NCBI
Google Scholar

[19] View Article

[20] PubMed/NCBI

[21] Google Scholar

[ref7] 7. Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci USA 105: 1118–1123. pmid:18216267
View Article
PubMed/NCBI
Google Scholar

[23] View Article

[24] PubMed/NCBI

[25] Google Scholar

[ref8] 8. Motter AE (2004) Cascade control and defense in complex networks. Phys Rev Lett 93: 098701. pmid:15447153
View Article
PubMed/NCBI
Google Scholar

[27] View Article

[28] PubMed/NCBI

[29] Google Scholar

[ref9] 9. Buldyrev S V, Parshani R, Paul G, Stanley HE, Havlin S (2010) Catastrophic cascade of failures in interdependent networks. Nature 464: 1025–1028. pmid:20393559
View Article
PubMed/NCBI
Google Scholar

[31] View Article

[32] PubMed/NCBI

[33] Google Scholar

[ref10] 10. Donetti L, Hurtado PI, Munoz MA (2005) Entangled networks, synchronization, and optimal network topology. Phys Rev Lett 95: 188701. pmid:16383953
View Article
PubMed/NCBI
Google Scholar

[35] View Article

[36] PubMed/NCBI

[37] Google Scholar

[ref11] 11. Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C (2008) Synchronization in complex networks. Physics Reports 469: 93–153.
View Article
Google Scholar

[39] View Article

[40] Google Scholar

[ref12] 12. Sorrentino F, Bernardo M, Garofalo F, Chen G (2007) Controllability of complex networks via pinning. Phys Rev E 75: 046103.
View Article
Google Scholar

[42] View Article

[43] Google Scholar

[ref13] 13. Delpini D. et al (2013) Evolution of controllability in interbank networks. Scientific Reports 3: 1626. pmid:23568033
View Article
PubMed/NCBI
Google Scholar

[45] View Article

[46] PubMed/NCBI

[47] Google Scholar

[ref14] 14. Wuchty S (2014) Controllability in protein interaction networks. Proc Natl Acad Sci USA 111: 7156–7160. pmid:24778220
View Article
PubMed/NCBI
Google Scholar

[49] View Article

[50] PubMed/NCBI

[51] Google Scholar

[ref15] 15. Kalman RE (1963) Mathematical description of linear dynamical systems. Journal of the Society for Industrial & Applied Mathematics, Series A: Control 1: 152–192.
View Article
Google Scholar

[53] View Article

[54] Google Scholar

[ref16] 16. Lin CT (1974) Structural controllability. IEEE Transactions on Automatic Control 19: 201–208.
View Article
Google Scholar

[56] View Article

[57] Google Scholar

[ref17] 17. Rugh WJ (1996) Linear System Theory (Prentice-Hall, Englewood Cliffs, NJ) 2nd ed.

[ref18] 18. Lombardi A, Hörnquist M (2007) Controllability analysis of networks. Physical Review E 75: 056110.
View Article
Google Scholar

[60] View Article

[61] Google Scholar

[ref19] 19. Liu YY, Slotine JJ, Barabási AL (2011) Controllability of complex networks. Nature 473: 167–173. pmid:21562557
View Article
PubMed/NCBI
Google Scholar

[63] View Article

[64] PubMed/NCBI

[65] Google Scholar

[ref20] 20. Liu YY, Slotine JJ, Barabási AL (2013) Observability of complex systems. Proc Natl Acad Sci USA 110: 2460–2465. pmid:23359701
View Article
PubMed/NCBI
Google Scholar

[67] View Article

[68] PubMed/NCBI

[69] Google Scholar

[ref21] 21. Gao J, Liu YY, D’Souza RM, Barabási AL (2014) Target control of complex networks. Nature Communication 5: 5415.
View Article
Google Scholar

[71] View Article

[72] Google Scholar

[ref22] 22. Yuan ZZ, Zhao C, Di ZR, Wang WX, Lai YC (2013) Exact controllability of complex networks. Nature Communication 4: 2447.
View Article
Google Scholar

[74] View Article

[75] Google Scholar

[ref23] 23. Nepusz T, Vicsek T (2012) Controlling edge dynamics in complex networks. Nature Physics 8: 568–573.
View Article
Google Scholar

[77] View Article

[78] Google Scholar

[ref24] 24. Liu YY, Slotine JJ, Barabási AL (2012) Control centrality and hierarchical structure in complex networks. PLoS ONE 7: e44459. pmid:23028542
View Article
PubMed/NCBI
Google Scholar

[80] View Article

[81] PubMed/NCBI

[82] Google Scholar

[ref25] 25. Wang WX, Ni X, Lai YC, Grebogi C (2012) Optimizing controllability of complex networks by minimum structural perturbations. Phys Rev E 85: 026115.
View Article
Google Scholar

[84] View Article

[85] Google Scholar

[ref26] 26. Hou LL, Small M, Lao SY (2014) Maximum entropy networks are more controllable than preferential attachment networks. Phys Lett A 378: 3426–3430.
View Article
Google Scholar

[87] View Article

[88] Google Scholar

[ref27] 27. Pósfai M, Liu YY, Slotine JJ, Barabási AL (2013) Effect of correlations on network controllability. Scientific Reports 3: 1067. pmid:23323210
View Article
PubMed/NCBI
Google Scholar

[90] View Article

[91] PubMed/NCBI

[92] Google Scholar

[ref28] 28. Hou LL, Lao SY, Small M, Xiao YD (2015) Enhancing complex network controllability by minimum link direction reversal. Physics Letters A 379: 1321–1325.
View Article
Google Scholar

[94] View Article

[95] Google Scholar

[ref29] 29. Jia T. et al (2013) Emergence of bimodality in controlling complex networks. Nature Communication 4: 2002.
View Article
Google Scholar

[97] View Article

[98] Google Scholar

[ref30] 30. Jia T, Barabási AL (2013) Control capacity and a random sampling method in exploring controllability of complex networks. Scientific Reports 3: 2354. pmid:23912679
View Article
PubMed/NCBI
Google Scholar

[100] View Article

[101] PubMed/NCBI

[102] Google Scholar

[ref31] 31. Menichetti G, Dall’Asta L, Bianconi G (2014) Network controllability is determined by the density of low in-degree and out-degree nodes. Phys Rev Lett 113: 078701. pmid:25170736
View Article
PubMed/NCBI
Google Scholar

[104] View Article

[105] PubMed/NCBI

[106] Google Scholar

[ref32] 32. Hou LL, Lao SY, Bu J, Bai L (2013) Enhancing Complex Network Controllability by Rewiring Links. IEEE Inter. Conf. on Intelligent System Design and Engineering Applications 709–711.
View Article
Google Scholar

[108] View Article

[109] Google Scholar

[ref33] 33. Hou LL, Lao SY, Liu G, Bai L (2012) Controllability and Directionality in Complex Networks. Chin Phys Lett 29: 108901.
View Article
Google Scholar

[111] View Article

[112] Google Scholar

[ref34] 34. Xiao YD, Lao SY, Hou LL, Bai L (2014) Edge orientation for optimizing controllability of complex networks. Phys Rev E 90: 042804.
View Article
Google Scholar

[114] View Article

[115] Google Scholar

[ref35] 35. Gazmuri PG. Independent sets in random sparse graphs. Networks 14: 367–377.
View Article
Google Scholar

[117] View Article

[118] Google Scholar

[ref36] 36. Balaji S, Swaminathan V, Kannan K (2010) A simple algorithm to optimize maximum independent set. Adv Model Optim 12: 107–118.
View Article
Google Scholar

[120] View Article

[121] Google Scholar

[ref37] 37. Robson J M (1986) Algorithms for maximum independent sets. J Algorithms 7: 425–440.
View Article
Google Scholar

[123] View Article

[124] Google Scholar

[ref38] 38. Erdős P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hungar Acad Sci 5 17–61.
View Article
Google Scholar

[126] View Article

[127] Google Scholar

[ref39] 39. Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286: 509–512. pmid:10521342
View Article
PubMed/NCBI
Google Scholar

[129] View Article

[130] PubMed/NCBI

[131] Google Scholar

[ref40] 40. Goh KI, Kahng B, Kim D (2001) Universal behavior of load distribution in scale-free networks. Phys Rev Lett 87: 278701. pmid:11800921
View Article
PubMed/NCBI
Google Scholar

[133] View Article

[134] PubMed/NCBI

[135] Google Scholar

[ref41] 41. Ruths J, Ruths D (2014) Control profiles of complex networks. Science 343: 1373–1376. pmid:24653036
View Article
PubMed/NCBI
Google Scholar

[137] View Article

[138] PubMed/NCBI

[139] Google Scholar

[ref42] 42. Network controllability datasets. http://boseinst.ernet.in/soumen/Network_Controllability_Datasets.html.

Figures

Abstract

Introduction

Edge Orientation for Optimal Controllability

Categories of Edge Directions for Optimal Structural Controllability

Structural Analysis of Critical Edge Directions

Edge Orientation by Critical Directions

Analysis of Real Networks

Discussion

Supporting Information

S1 File. The detailed procedures to computations of CriticalMWIS (Algorithm 1) and RedundantMWIS (Algorithm 2).

Author Contributions

References