Research On Key Propagation Nodes Identification In Complex Networks Based On K-shell Algorithm

Networks are ubiquitous in life,such as social networks,transportation networks,power networks,etc.These networks can be abstracted into complex networks.It is of great significance to study complex networks,in which the identification of key nodes is an important part of complex network theory.Therefore,mining key nodes in networks is very important for studying the structure and information dissemination of complex networks.On the basis of the classical K-shell algorithm and multi index method,this thesis proposes two improved key node identification algorithms,namely,the improved hybrid K-shell algorithm and the multi index method to identify key nodes.Because the key nodes are important for the study of infectious diseases,two representative infectious disease models are selected,namely,SI model and SIR model.(1)The classical K-shell algorithm assigns importance to nodes according to their positions,which results in the same importance of a large number of nodes and low discrimination.This thesis proposes a new hybrid K-shell decomposition method,namely hybrid K-shell key node identification algorithm based on node degree.On the basis of the classical K-shell algorithm,it uses the degree value of nodes and network stratification to make improvements.In addition,a single index cannot describe the importance of a node,and the influence of second-order neighbor nodes on their own importance cannot be ignored.Therefore,the local attributes and location attributes of nodes are considered,This thesis uses the new Ks value and the second order neighbor degree of the node based on the degree improvement,and derives a standard network parameter to assign weight to these two indicators to calculate the importance of the node.The SI infectious disease model is used to conduct simulation experiments on four real networks,namely Karate,Celegans,USAir97 and Netscience.The infection status of incurable diseases such as AIDS is simulated.The results show that the method can effectively identify key nodes in the network.(2)Proximity centrality and eigenvector centrality assign importance to nodes according to their global attributes,so the global attributes of nodes contribute greatly to the importance.Based on this point of view,this thesis proposes a multi index method to identify key nodes,which comprehensively considers the degree centrality,Ks value,proximity centrality,feature vector centrality of nodes and the importance of neighbor nodes to nodes;At the same time,by combining the influence of subjective and objective factors on the weight,the comprehensive weight is assigned to each index;Finally,quantitatively measure the importance of nodes.Through the simulation experiment of SIR models in four real networks of Karate,Polbooks,Jazz and Hamsterster,the infection process of curable viruses such as COVID-19 is simulated.The results show that the accuracy of the method of identifying key nodes by multiple indicators is significantly better than the classical K-shell algorithm,the K-shell degree neighborhood algorithm based on potential edge weight and the improved K-shell key node identification method,Therefore,the method of combining local attributes,global attributes and location attributes of nodes can further improve the accuracy of identifying key nodes.Finally,the experimental results also prove that the proposed method reasonably determines the importance of the nodes,and can accurately identify the key nodes in the network.