Research On The Methods Of Vital Nodes Identification In Complex Network

Most spreading phenomena in the real world are usually modeled as spreading processes on complex networks,such as the spreading of human diseases,the propagation of Internet rumors,and the diffusion of viruses,etc.These harmful spreading have incurred huge losses to human society.It is of great theoretical and practical significance that controlling the spreading process on networks for curbing harmful spreading in the real world.As one of the important methods to control the network spreading process,the vital nodes identification in complex networks has received great extensive attention.In recent years,vital nodes identification methods based on different ideas are proposed,but the accuracy of existing methods for weighted networks is still an opening challenge.This paper mainly focuses on the following two aspects,1)identifying vital nodes in networks based on network topology structure;2)identifying vital nodes in networks by combining with the graph embedding method.The specific contents are summarized as follows:(1)Research on identification of vital nodes based on both their global and local topology structure.On the one hand,we propose normalized degree centrality to measure the local influence of each node.On the other hand,the K-Shell decomposition is improved,and a fine-grained K-Shell is proposed to measure the global influence of each node.Furthermore,a novel vital nodes identification method is proposed by combining the normalized degree centrality and fine-grained K-Shell(NDF-FKS),its time complexity is O(|E||V|).In the experiments,the Susceptible-Infected-Recovery(SIR)model is used to simulate the network spreading process.The NDC-FKS is compared with other six methods on small-world networks,scale-free networks and real networks,respectively.The experimental results show that the accuracy of NDC-FKS outperforms existing six methods and has a competitive performance on distinguishing influential nodes.(2)Research on identification of vital nodes based on graph embedding method.On the one hand,we use Deep Walk to embed the nodes into low-dimensional representation vectors.By the node representation vectors to measure the topological similarity between nodes,and obtain the top-k most similar node sets of each node.The frequency of node appearing in all top-k most similar node sets as an index to measure the spreading influence of nodes.On the other hand,the weight information of the node neighborhood is adopted to describe the interaction between nodes.Finally,by combining the above two aspects,an extended node structure similarity centrality is proposed to determine the importance of nodes,its time complexity is O(|E|+|V|(k)).In the experiment,the SIR propagation model is used to simulate the network spreading process.The proposed method is compared with eight existing vital nodes identification methods in accuracy and resolution on ten synthetic networks and four real networks.Experimental results show that the extended node structure similarity outperforms the other eight methods in both accuracy and resolution.