Research On The Fundamental Theory Of Controllability Of Complex Networks

The controllability of complex networks is one of the hottest topics in network science and also the ultimate goal of complex network research,which focuses on how to select suitable input nodes to driver a networked system from any initial state to any desired final state.In 2011,Liu Yang-Yu,the world's leading cybernetics expert,and Barabasi,the world's famous network science expert,jointly published a paper entitled "Controllability of Complex Networks" in Nature,which combined control theory and complex network theory for the first time and successfully solved the structural controllability of directed networks,drawing great attention from both cybernetic community and complex network community.Soon afterwards,the exact controllability theory was proposed to address the controllability of arbitrary networks including but not limited to directed,undirected,weighted,unweighted networks,and so on.Based on these two theories,the research on controllability of networks has sprung up and achieved many fruitful results.In this doctoral dissertation,we are committed to addressing the following three basic theoretical issues about network controllability:controllability of the deterministic model networks and power grids,optimization of the controllability of complex networks consisting of both state nodes and control nodes,and the control robustness of complex networks under node and edge attacks.The main contributions of the dissertation are summarized as follows.(1)We studied the controllability of deterministic model networks for the first time.We numerically analyzed the controllability of six classical deterministic model networks and found that the number of driver nodes ND grows linearly with the network size N;when the network size is large enough,the controllability of the network nD approaches a constant that is much less than 0.3905,the average controllability value of 37 real-world networks,indicating that the deterministic model networks are relatively easy to control.We also studied the nodal degree and clustering coefficient of driver nodes and found that the driver nodes tend to avoid high degree nodes but to have high clustering coefficients.(2)We studied the controllability of power grids for the first time.By employing the exact controllability theory,we investigated the controllability of six IEEE power grids,Middle China Power Grid and Northeast China Power Grid.It is found that the degree distribution of power grids basically follows the power law and shows scale-free property.The controllability values of IEEE118,IEEE145 and Northeast China Power Grid are much larger than the corresponding ER random networks,indicating that these power grids are relatively hard to control;whereas the other IEEE power grids together with Middle China Power Grid are easier to control.We also studied the nodal degree,nodal betweenness,nodal closeness of the driver nodes of these power grids,and found that the driver nodes of power grids tend to be low-degree nodes but avoid Hub nodes;tend to be low-betweenness nodes but avoid bottleneck nodes;and have little to do with nodal closeness.One interesting finding is that although the driver nodes themselves avoid Hub nodes,their neighbor nodes are mostly Hub nodes.Finally,we found that the controllability of power grids is mainly determined by the degree distribution and heterogeneity,sparse and heterogenous power grids are usually the most difficult to control.(3)We proposed a genetic algorithm based optimization framework to optimize the controllability of arbitrary networks consisting of both state nodes and control nodes.The proposed algorithm has the following remarkable advantages,a)The proposed algorithm can be applied to arbitrary networks without any limitations,while the previous state-of-the-art algorithm can only treat directed networks.b)The proposed algorithm saves about 40%time than the previous state-of-the-art algorithm under the same conditions.c)The proposed algorithm converges to fewer control nodes than the previous state-of-the-art algorithm.d)Despite of heuristics,the proposed algorithm can actually find global optimums in most cases.e)The parameters of the proposed algorithm such as crossover probability and mutation probability can be adjusted adaptively according to the evolutionary information of population without manual intervention.A large number of numerical experiments have proved the effectiveness of the proposed algorithm and the evolution of optimal topology has been captured.Finally,the effects of average degree and heterogeneity on network controllability have been investigated and it is found that for networks consisting of both state nodes and control nodes,sparse and heterogenous networks are the most difficult to control.(4)We systematically studied the control robustness of the canonical model networks and the real-world networks against random and deliberate attacks on the basis of node and edge.The deliberate attacks are chosen based on degree and betweenness centralities evaluated with initial network information as well as recalculated network information:ID,RD,IB and RB;random attack(RA)is as a comparison.It is found that the node based attacks are usually more harmful to the network controllability than the edge based attacks,so are the recalculated attacks than their counterparts.The ER random network is more control vulnerable to the degree-based attacks(RD and ID);while the small-world networks(WS and NW)are more control vulnerable to the betweenness-based attacks(RB).The BA scale-free network turns out to be the most control vulnerable model network due to the existence of Hub nodes.However,it is surprising that meanwhile the BA network is strongly robust to the deliberate edge attacks(RB,IB,RD and ID).The control robustness of real-world networks is much different from model networks.Most real-world networks exhibit good control robustness to random node failures but poor robustness to random edge failures,which have not been observed in model networks.The regulatory networks and organizational networks turn out to be the most control robust real-world networks subject to node attacks;the organizational networks also show very strong robustness to random edge attacks.The recalculated betweenness based attack proves to be the most harmful strategy to damage the controllability of real-world networks,while the edge degree based attacks(ID and RD)can hardly damage the controllability of any network.