Research Of Alternative Components And The Method To Alter The Control Mode For Complex Network Controllability

Controlling a complex system is one of the common questions of many fields. Complex network can describe many complex systems in the real world, such as computer networks, electric power and transportation networks, biological networks, economic and financial networks, social networks, etc. In order to make sure these systems run formally, we must control the whole system. Mapping the complex networks to linear systems, we apply the maximum matching algorithm of bipartite graph and then treat these unmatched nodes as driver nodes. To realize the effective control of complex networks, we must put external signals into these driver nodes.Based on the maximum matching, we define alternative neighbor and alternative connected component so as to make a further research on the controllability of complex networks. We divide our study into three parts.Firstly, we propose an algorithm to enumerate all possible drivers. In general, a network has more than one minimum driver node sets. It is a #P problem to enumerating all the minimum driver node sets. However, we find a method to get the union of all the minimum driver node sets, which is also called all possible drivers. The complexity of the algorithm is O(N1/2L). Compared with the exist algorithm, our algorithm is more time-saving.Secondly, we put forward the definition and construct method of alternative connected component. There exist three different alternative connected components, including driver alternative component, unsaturated matched alternative component and saturated matched alternative component. We analyze the distribution of alternative component, and find that there exists a giant alternative component in the network with high average degree. We conclude that the bimodality in networks is raised by the different giant alternative components. Furthermore, we study the frequency of giant alternative components. It is discovered that as the increase of average degree, there will appear a giant saturated matched alternative component. Accordingly, for networks with identical in- and out- distribution, the centralized control mode is more than the distributed control mode. For networks with different in- and out- distribution, there also exist two control modes.Lastly, we bring forward a new method to identify control mode and a method to alter control mode. Aimed at the limit of the existing method to identify control mode, we propose an identifying method based on alternative component and validate its effectiveness. Because of the lack of an efficient method to alter the control mode of a network, we propose an add edge strategy based on alternative component. After the experiment on model networks and real networks, we find that adding only a few edges will change a large amount of nodes in the network.