Research On The Enumeration Algorithm And The Optimal Selecting Algorithm Of The Minimum Driver Node Set For Complex Network Controllability

In the real world, many systems exist in the form of directed complex networks. In order to make them run formally, we must control the whole system. Mapping the complex networks on linear system, we apply the maximum matching algorithm of bipartite graph and treat unmatched nodes as driver nodes to achieive a minimum driver node set. The driver nodes in this set are in turn put into external signals, thus realizing the effective control of the complex network. Yet the maximum matching of a network is not unique, and this leads to more than one minimum driver node set accordingly. In this regard, how to get all the minimum driver rode set of network is of vital importance for analyzing network controllability.Major findings of the current study are recapped as follows:First, this thesis proposes an algorithm to enumerate all the minimum driver node sets encompassing the complex networks. Until now, numerous studies in this field employ the maximum matching of network to get the minimum driver node set, and this method is inevitably ineffective. In order to overcome the weaknesses of the previous studies, this study proposes an enumeration algorithm to work out all the minimum driver node sets encompassing the complex networks and conducts experiments in real world network to test its effectiveness. The results show that the algorithm proposed in this study is much more effective than the previous ones. A network encompassing all the minimum driver rode sets is constructed, and the topology structure of this newly generated network and its influence on network control are analyzed. The minimum driver nodes are in turn classified as covering driver nodes, covering matched nodes, and mix nodes. This classification is based on the different roles these nodes play in the minimum driver node sets, and the typology feature of the three types of nodes is discussed.Second, an algorithm of selecting an optimal minimum driver node set is also proposed. This study assigns the cost of controlling nodes as the weight of nodes, defines the weight of edges as the weight of their target nodes, and applies the maximum weight matching algorithm of network to work out the maximum weight matching set. As the total weight of network is fixed, the minimum driver node set with the least cost of cccccolling the eetwork, namely, the optimal driver node set, is generated. The characteristics of this set are also elaborated.