Analysis Of Controllability Of Complex Network Structures Based On Graph Theor

Controllability has been a hot topic in complex network research,among which,the analysis of structural controllability is an important branch,which has been widely concerned by scholars at home and abroad.In this thesis,with the help of graph theory,algebraic graph theory and other theoretical knowledge,the structural controllability of complex networks is studied.The main contents are as follows:Firstly,the concept of leader and follower is introduced into the study of structural controllability of complex networks,and the network is simplified by analyzing the influence of edge connection between nodes of different roles on the structural controllability of networks.On this basis,from two perspectives of dilation and leader’s unreachable node point,this thesis explores in detail what characteristics the topology meets so that the network can achieve structural controllability after the leader is determined,and an algorithm to judge the structural controllability of the network is designed according to these characteristics.Secondly,this thesis investigates the structural controllability of some special leader-follower networks based on directed path and unidirectional cycle,and the scheme of connecting edges from the leader network to the follower network with corresponding special topology is given under structural controllability.Also,this thesis gives the leader selection mechanism and the number lower bound of directed tree graph under the strong structural controllability with the help of zero-forcing set.Thirdly,when exploring the minimum controllable node set of complex network under structural controllability,a partition method of strongly connected components is proposed.Through this method,the minimum node set controlled by external input when the network meets input’s reachability,can be quickly determined,that is,the key input reachable node set.At the same time,combined with tools such as matching and DM(Dulmage-Mendelsohn)decomposition,the minimum node set controlled by external input when the network does not exist dilation can be determined,that is,the key no dilation node set.Furthermore,this thesis gives the result that the minimum controllable node set is equivalent to the union of the key input reachable node set and the key no dilation node set.Finally,considering the different situations that the state nodes accept external control inputs,this thesis explores the minimum input and the minimum driver node set of network system when the set of minimum controllable nodes is equivalent to the union of the key input reachable node set and the key no dilation node set in detail.At the same time,when the set of minimum controllable nodes is not equivalent to the key input reachable node set and the key no dilation node set,the external input control mode and the mode of state node receiving input are clarified,and the node composition and the minimum input in corresponding cases are given.