Effects of Edge Directions on the Structural Controllability of Complex Networks.

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.

Edge orientation for optimizing controllability of complex networks.

Recently, as the controllability of complex networks attracts much attention, how to design and optimize the controllability of networks has become a common and urgent problem in the field of controlling complex networks. Previous work focused on the structural perturbation and neglected the role of edge direction to optimize the network controllability. In a recent work [Phys. Rev. Lett. 103, 228702 (2009)], the authors proposed a simple method to enhance the synchronizability of networks by assignment of link direction while keeping network topology unchanged. However, the controllability is fundamentally different from synchronization. In this work, we systematically propose the definition of assigning direction to optimize controllability, which is called the edge orientation for optimal controllability problem (EOOC). To solve the EOOC problem, we construct a switching network and transfer the EOOC problem to find the maximum independent set of the switching network. We prove that the principle of our optimization method meets the sense of unambiguity and optimum simultaneously. Furthermore, the relationship between the degree-degree correlations and EOOC are investigated by experiments. The results show that the disassortativity pattern could weaken the orientation for optimal controllability, while the assortativity pattern has no correlation with EOOC. All the experimental results of this work verify that the network structure determines the network controllability and the optimization effects.