Prioritizing Nodes Based On The Network Robustness And Controllability Analysis

Many complex systems can be modeled as complex networks,and different nodes have different impacts on the system functions.Studies on prioritizing nodes helps to understand the underlying mechanism of system function implementation and provides guidance for further implementation of network control.In this thesis,by analyzing the influence of nodes on the controllability and the integrity of the topology of networks,node prioritizing methods based on network robustness and controllability theories are proposed respectively,and the proposed methods can effectively identify nodes that have important effects on network robustness and controllability,and the main research contents are as follows:A node prioritizing method Core LC is proposed.Firstly,a definition of node local centrality is proposed to prioritize the nodes in the 2-core and identify the decycling set;secondly,for the tree structure with the decycling set removed,the important nodes that can efficiently destroy the residual structure are identified by prioritizing the nodes.Finally,the robustness comparison experiments are conducted in the artificial network as well as four real networks,and it is found that removing nodes according to the important node sequence identified by Core LC method has a greater impact on the network robustness when compared to other node prioritizing methods.The study of robustness can help to understand the real system,and the level of understanding of the real system is ultimately reflected on the ability to control it.Controlling the entire large network is difficult and unnecessary,and in many cases only some specific nodes need to be controlled,i.e.,target control.Since each node doesn’t participate in target control with equal probability and there is still a lack of effective methods for quantitative analysis.In this thesis,a random sampling algorithm is proposed to simulate the probability of each node appearing in the minimum driver node sets,and the nodes are prioritized accordingly.Applying the algorithm to random networks(Erd(?)s-R(?)nyi,ER)and scale-free(SF)networks,it is found that the number of nodes with probability greater than 0 increases as the number of controlled nodes increases,implying that more nodes are required to participate in the control,and as the SF network becomes denser,the nodes with probability 0 show a bimodal distribution phenomenon,corresponding to two control modes: distributed,which requires most nodes to participate in control,and centralized,which requires a small number of nodes to participate in control.The association between the importance of nodes based on robustness and controllability is analyzed in ER and SF networks.The proposed Core LC is used to identify the important nodes based on robustness,and the node control importance is analyzed through the sampling algorithm proposed in the target control problem.The experiments reveal that the node importance sequences obtained based on robustness and controllability are negatively correlated.In addition,nodes with high degree have a lower probability of becoming driving nodes,and compared to attacking the nodes in descending order of control importance,ascending order attack has a more significant impact on the robustness of the system.