Studies On Controllability Of Complex Networks

The problem of controllability of complex networks is central in network theory. In the last ten years, the study of controllability of complex network has blossomed and has yield many promising and significant results. However, much less effort has been devoted to study the minimum controlled vertex set through which control over the network with arbitrary structure can be achieved. This thesis focuses on the research of the minimum controlled node set and the optimal input configuration in structural controllability of complex networks、the minimum driver node set and controlled node set in exact controllability of complex networks、the recovering of structural controllability of complex networks. The main research contents are as follows:According to the problem that the minimum driver nodes which are driven by different inputs can not ensure the complex network full control in many real complex networks, the thesis studies the problem of identifying the minimum controlled node set and the optimal input configuration. In this thesis, we have proved that the minimum driver nodes driven by different inputs are not sufficient to ensure the full control of network when the associated graph contains the inaccessible strongly connected component which has perfect matching. Secondly, on the basis of input accessible condition and perfect matching condition of structural controllability of complex networks, this thesis shows that the key to identify the minimum controlled node set and optimal input configuration is to find the minimum unmatched node set and the minimum inaccessible node set which have the biggest intersection. Considering the large scale characteristic of complex networks, this thesis presents a combinatorial optimization algorithm with constraints and a polynomial algorithm based on maximum weight perfect matching to identify the minimum unmatched node set and minimum inaccessible node set which have the biggest intersection.And the simulation results show that the controllability of network is correlated to the number of inaccessible strongly connected components which have perfect matching and this result promotes us to better understand the relationship between the network’s structural characteristic and its control. Moreover, using strong graph tool, we map the minimal controlled node set and optimal input configuration problem to the maximum weight matching problem and propose a polynomial algorithm to identify the minimum controlled node set.According to the framework of structural controllability can not been used to study the undirected network or the network with exact link weight, based on the framework of exact controllability introduced by Yuan, in this thesis we focus on the minimum driver node set and controlled node set of exact controllability. At first we show that different minimum driver node set has different control capacity and introduce the concept of node’s control capacity to measure the role of node in network control. Then base on node’s control capacity, we propose an algorithm to identify the minimum driver node set. The simulation results in some model and real networks show that the minimum driver node set which is computed by our algorithm can ensure the exact controllability of many model and real networks.Finally, motivated by the fact that there exist many networks which can not ensured the controllability by minimum driver nodes and the identifying the minimum controlled node set is NP hard, we introduce heuristic algorithms to identify the controlled node set. The simulation results show that the size of minimum driver node set which is computed by our algorithm approximates to the size of minimum driver node set.According to a full control network, potentially malicious attacks, random node’s failures or edge’s failures will lead to the damage of the controllability, this thesis introduces the concept of the degree of controllability defect of network to quantify the degree of controllability of network. And for the networks whose degree of controllability defect is more than zero we give the recovery algorithm around the minimum inputs and minimum state nodes required to control. The simulation results on many model and real networks show that there is a close relationship between the cost of the complex network recovery and the topology of the network.