A Method For Enumerating All Minimum Driver Node Set And Research Of Control Importance Of Node For Complex Network

Many systems in the real world exist in the form of complex networks.In order to make these systems run normally,it is necessary to control the whole system,while the control capacity of complex network has been one of the basic problems of network science.Mapping the complex networks to a linear system,the thesis applies the maximum matching algorithm of bipartite graph to get the maximal matching and treat the unmatched nodes as the driver nodes,then the minimum driver node set of the network could be acquired.If we control the nodes of minimum node set,then we can control the whole network,in other words,a minimum set of driver node represents a kind of control scheme of the network.Then how to obtain all the control schemes of the network and explore the role which the node plays in the schemes has been a hot issue in the field of complex networks.First of all,according to the reversal theorem and enumerate theorem of the minimum driving node set,this thesis illustrates the feasibility of the enumeration of the minimum driver node set.And at the same time,this thesis improve the enumeration process with the method of deleting edges,parallel computing and the optimization of checking duplicate items.Finally,the thesis put forward a fast method to enumerate all the minimum drive node set.Based on the experiments for a large number of model networks and some real networks,this thesis analyzes the topological properties of the minimum drive node set.Secondly,this thesis treats every minimum driver node set as a node,constructs the relation network of all minimum driver node sets based on the relation of matching reversal between minimum driver node sets.On the basis of experiment of some model networks and real networks,this thesis illustrates how the topological properties of the relation network impact the controllability of original network.Finally,this thesis proposes the control importance of nodes and the reversal reachable set of node.The control importance of node is justified by the node's frequency of occurrence in all minimum driver node set.The reversal reachable set of node is defined via driver node set to which node can traverse via matching reversal.Though the experiments on model networks,the thesis point out that the reversal reachable set of node delimit the lower limit of the frequency of occurrence that nodes in the all the minimum driver nodes of network.