Towards data-driven identification and control of complex networks
Xiaofan Wang · National Science Review · 2014
Control theory has been well recognized as a ‘mature’ discipline, but research interest has repeatedly been renewed due to the emergence of new viewpoints and introduction of new methodologies [1]. Recent interests on identification and control of complex networks provide excellent examples of such evidence (Fig. 1). Uncovering complex networked systems from data is a fundamental problem for understanding and controlling a variety of dynamical processes taking place on complex networks. Recently, Wang's group developed a novel framework based on compressive sensing to reconstruct structure of a complex network from time series [2]. Compressive sensing is an optimization approach for sparse signal reconstruction with broad applications in signal and image processing [3]. Requiring extremely small amount of data is the most striking characteristic of compressive sensing. The natural sparsity of most real-world networks enables the conversion from the network reconstruction problem to the sparse signal reconstruction problem. However, implementing the conversion is highly non-trivial, especially when binary time series are used. Wang's group presented an interesting method based on Hamming distance to identify a set of base strings and their associated subordinate strings in binary time series. Combining each base string and its subordinate strings gives rise to a set of equations, the solution of which pertains to the network structure and can be optimized by exploiting some standard compressive-sensing algorithms. High accuracy, high efficiency and wide applicability in a significant stochastic environment with measurement noise and missing information are the remarkable characteristics of the reconstruction approach. The reconstruction framework opens new avenues towards controlling complex networked systems that are ubiquitous in the real world using observable data, especially when we are confronting the explosive growth of large amount of data in the information era. There exist well-established theoretical frameworks of controllability for linear systems in control theory. However, challenges arise when applying the traditional controllability criteria to complex networked systems. Directly controlling every node in a network with a huge number of nodes is usually impossible and often unnecessary. Thus, a key challenge is to identify a minimum set of controlling nodes (or driver nodes) to guarantee the complete controllability. The standard way in control theory to find the controllability matrix does not work well due to the fact that the number of configurations to be tested increases exponentially with the network size, prohibiting matrix rank checking for large-scale networks. Liu, Slotine and Barabási [4] proposed a framework of structural controllability for complex networks based on Lin's theory [5] that is rooted in the Kalman controllability condition. Recently, Wang's group developed a new framework for measuring the exact controllability of general complex networks [6]. In contrast to the structural controllability, the alternative approach stems from the classical PBH controllability criterion in control theory. In particular, they proved that for arbitrary complex networks with any weight distributions, the minimum number of driver nodes, on which external control signals are injected, is determined by the maximum geometric multiplicity of the eigenvalues of the network matrix. For undirected networks, the controllability defined by the ratio of the minimum number of driver nodes to the network size is determined by the maximum algebraic multiplicity, namely the maximum number of identical eigenvalues. For sparse networks, to which most real networks belong, the controllability measure is further simplified to be determined by the matrix rank. Based on the exact controllability condition, the minimum set of driver nodes can be identified by incorporating a column canonical transformation performed on a modified network matrix. The exact controllability theory offers exactly the same results as that of the structural controllability theory where it is applicable. We hope that the recent studies on identification and control of complex networks could stimulate more interests and efforts devoted to the interaction of network science and control theory, thus establishing further links between the two research fields. Data-driven identification and control of complex networks. The compressive-sensing-based network reconstruction allows us to identify the structure of a complex network, while the exact controllability framework yields a minimum set of driver nodes, by controlling which we can achieve full control of the whole networked system.