A Research Of Identifying Vital Nodes Algorithm Based On Graph Partition

In this thesis,network robustness minimization is taken as the goal of graph partition,and key nodes are mined to find the nodes which are important to maintain the network structure.This issue is important in practical applications.Identifying the important nodes in the network can help us better control the spread of diseases in the infectious disease network and maintain infrastructure more efficiently in the power grid.Because of the important value of key node mining in practice,it has become a hot issue in complex network research.In this thesis,the properties of network robustness are thoroughly analyzed,and the planning inverse targeting algorithm is proposed.Then the definition of robustness is improved,and a new key node mining algorithm is proposed based on the new definition.The main contents and innovations of this thesis are as follows:(1)The definition and properties of network robustness are deeply analyzed in this thesis.The range of network robustness is proved,and its optimal sequence characteristics and combination law are proved.The characteristics of the optimal sequence indicate that the nodes selected by the optimal sequence each time must be in the current maximum connected component of the network.The combination law shows that under the condition of meeting the optimal sequence characteristics,the results of each part of the network can be used to directly calculate the results of the synthetic network.(2)Based on the analysis of network robustness,the planning inverse targeting algorithm is proposed.The community discovery method is introduced into the planning inverse targeting algorithm.First,the structure of the network is detected,and the nodes in the network are divided into the internal nodes and the edge nodes of the community.According to the different types of nodes,key nodes are mined.Finally,the removal node sequence optimization method is used to optimize the obtained results,and the final results are obtained.Compared with other common methods,this method achieves better results.(3)This thesis points out the shortcomings of the traditional robustness definition,puts forward the definition of the new network robustness,and proves the various properties of the new robustness definition.The network robustness standard mainly focuses on the maximum connected branches of the network,and does not take into account the differences between nodes,so it can not be well applied to the network with node weights.Node weights are taken into account in the robustness of the new network.In this thesis,the characteristics of the new network robustness,such as the range of values,the optimal sequence characteristics and the combination law,are analyzed in depth,and the similarities and differences between the new network robustness and the original network robustness are compared.The compatibility of the two definitions is proved.(4)Based on the new network robustness index,this thesis proposes a new reverse target algorithm,which can better mine the key nodes in the network.The new inverse objective algorithm takes minimizing the importance of critical connected branches as a greedy goal.In many practical networks and model networks,the new reverse target algorithm achieves good results.In this thesis,the reasons for the difference of experimental results are analyzed.From the point of view of probability theory,it is proved that the robustness of the new network converges to the robustness of the original network when the network tends to infinity,under arbitrary network structure,under arbitrary node weight random distribution,and for arbitrary node removal sequence.