Studies On The Controllability Inspired Optimization Of Complex Networks

With the rapid development of 3C (Computer, Communication and Control) tech-nology, many complex interconnected dynamical systems in natural, social, physical and man-made-engineered fields, such as Internet, world wide web, power grids and natural gas networks, etc., can be represented or modeled by a complex network. The analysis, modeling and control of a complex network have become a multidisciplinary challeng-ing subject in computer, control, communication and engineering societies. Conceptually, system controllability is one of the most important system structure properties to measure whether a system is under control or controllable. However, due to the high dimension-ality and complexity of a complex network, the studies on the controllability of complex networks are still under early stage, but have been a critical subject particularly in control and network societies. Some progresses have been made in the areas like controllability in-dex computing and optimization, impact analysis of network structure on its controllability and control-related index optimization under the constraint of network controllability. The major challenges to research and development could be controllability optimization for directed and weighted networks, recovery of network controllability and controllability optimization for network integration, etc.Based on the published results on controllability of complex networks, the major research activities being presented in this dissertation focus on the analysis, design and optimization of controllability for directed complex networks with novel optimization so-lutions. From the perspective of graph theory, control theory and operation research, the major innovative aspects covered in this dissertation are:(1) determining the minimum control nodes for the directed and weighted networks subject to the network complete con-trollability; (2) the optimization of network controllability with fixed number of control nodes; (3) recovering the controllability from a damaged network; (4) providing a node in-dex for quantifying its importance for maintaining the network’s controllability. Moreover, as an example, the unit commitment problem under the constraint of grid controllability in power grids is studied.The detailed contributions made in this dissertation could be summarized as follows:1. Propose a general optimization framework on the control over network; study the minimum control nodes for the directed and weighted networks while maintaining its complete controllability; develop a novel optimization tool with extremal dynamics. The experimental results show the effectiveness and efficiency of this optimization methodology and reveal some interesting relationship between minimum number of control nodes and the underlying structure of a given directed and weighted network.2. Introduce the concept of network controllability index to measure the maximum di-mension of controllable sub-network; develop an optimal design paradigm of control configuration, under which the network controllability index reaches its maximum; prove the optimality of this design paradigm. The simulation results show the pro-posed design paradigm has the superior performance compared to other common-used methods, such as degree-based design strategy. Moreover, the relationship be-tween the network underlying structural characteristics and its controllability index is also revealed.3. Introduce the concept of degree of controllability to quantify the control level of the directed network; propose two novel optimal recovering strategies, OAN (short for optimal adding-node) strategy and OAE (short for optimal adding-edge) strategy, to repair controllability-damaged networks; prove the optimality of these two strategies. The results of experiments conducted on the various real and model networks demon-strate the effectiveness of these two strategies and the better performance compared to their randomized counterparts, RAN (short for randomized adding-node) strategy and RAE (short for randomized adding-edge) strategy. Moreover, the relationship between a network’s underlying structural characteristics and the cost to recover its controllability is also revealed.4. Introduce the concept of minimum control scheme for a given directed network; pro-pose a new node centrality measure to quantify a node’s significance on maintaining the structural controllability of the network; develop a random sampling algorithm to compute this measure. The results of experiments conducted on the various real and model networks show the distribution of this measure is mainly determined by the network’s underlying degree distribution, and this measure is positively correlated to its local topological characteristics.5. Study the unit commitment problem for power grids under the constraint of its con-trollability; develop a solution framework inspired by extremal dynamics. Simulation results on multiple IEEE test cases demonstrate competitive performance with EO method compared with other existing methods for UC problem, such as GA (genetic algorithm), SA (simulated annealing) and PSO (particle swarm optimization).The concluding remarks and the future research directions are given at the end of the dissertation.