Algorithm Research And Design Of Vital Nodes Identification In Complex Networks

Complex systems usually consist of a large number of interconnected components.These complex systems can often be described through a network structure.From the perspective of mathematics and computer science,a complex network is a system graph data structure that describes a large and complex real world.In different systems,each component plays different roles in different tasks and scenarios,and has different importance to the system.Finding important nodes in complex systems has attracted the attention of more and more computer scientists and physical sociologists.The goal of finding important nodes is generally divided into two categories,KPP-POS?key players for the purpose of optimally diffusing something?and KPP-NEG?key players for the purpose of disrupting or fragmenting the network?.KPP-POS refers to the search for one or more seed nodes for propagation activities,so that the final propagation range is the largest;KPP-NEG refers to finding one or more nodes and removing them from the network to maximize the extent of network damage.This article focuses on the KPP-POS problem to find the most influential spreader in the network.For this problem,it is generally divided into important nodes rank problem and influence maximization problem.This article focuses on how to find a group of nodes with the largest impact.The research on this problem gradually evolved from the greedy strategy of simple single node combination with high importance and its improved algorithm to the more complicated heuristic strategy algorithm.Based on the existing algorithms,this article proposes two novel algorithms for mining important node groups from different perspectives.The main research and innovations in this article are as follows:?1?This article proposes a heuristic node mining algorithm EnRenew based on node information entropy.This algorithm uses the node information entropy as a basic index to measure the importance of a single node,and then uses the selection strategy which similar to VoteRank and improve it.EnRenew algorithm has very low time complexity and can be applied to large-scale networks.In addition,through simulation experiments of SIR and SI propagation models,the algorithm shows a larger propagation scale in real network data.Compared with the optimal comparison algorithm,the EnRenew algorithm in the Hamster network has a 31%increase in infection scale and 17%in the CEnew network.?2?The PPS_proproposed in this article is a new and effective evaluation index for the importance of node groups.In this article,the original probability propagation model is improved to make it more close to the propagation process of SIR single contact propagation model.The improved probability propagation model is applied to the propagation process of multiple infection sources.The probability estimation value PPS_proof the infection scale that the node group can reach is calculated by the probability propagation model.The larger the value is,the larger the influence of the node group is.?3?Based on the probability propagation model and the obtained PPS_provalue,in this article uses PPS_proas an adaptive function,and uses the improved genetic algorithm to mine important node groups,and then proposes the SPGA algorithm.Through experimental analysis,in the SIR and SI propagation models,the effect of the SPGA algorithm has been greatly improved compared to the comparison algorithm in most networks.Especially in the small-scale network CEnew,Email and Hamster,the final infection scale of SPGA algorithm is 20%higher than that of the optimal comparison algorithm.Compared with the VoteRank algorithm,the EnRenew algorithm strengthens the weakening of the importance of the neighbors of the selected nodes,thereby making the selected neighbors more dispersed and improving the algorithm effect.However,the weakening of the influence of the selected nodes'neighbors is mostly a heuristic artificial setting.There is no theoretical study of its optimal value,which will be one of the research points for heuristic algorithms in the future.In addition,although the SPGA algorithm has improved significantly,and the computational complexity of the PPS_provalue obtained through the probability propagation model is low,a large number of searches by the genetic algorithm cause the SPGA algorithm to be inefficient.How to optimize this process is also the future research direction.