Towards An Influential Node Set Identification Algorithm Based On Dynamic Selection Of Candidates

In recent years,with the vigorous development of social platforms,a variety of social platforms have appeared in people's daily lives.People's ability to exchange information has reached an unprecedented speed,and a huge amount of data has been left for merchants and enterprises to mine and use.As one of the key issues in the field of social network analysis,the Influence Maximization Problem(IMP)has been widely concerned by researchers.It selects a group of users(called the seed set)from social networks to maximize the expected number of affected users(called influence diffusion).The impact maximization problem has a wide range of application scenarios,such as word-of-mouth marketing,detection of essential proteins,wireless sensor deployment,etc.,so it has important research value and practical significance.The existing influence maximization algorithms are mainly divided into three categories.Although the influence maximization algorithm based on the greedy framework and the intelligent optimization algorithm have better results,but with the explosive growth of network scale,the above two types of algorithms cannot be applied to large scale networks due to high time complexity and large memory requirements.The heuristic algorithm based on network characteristics has attracted wide attention due to its advantages of low time complexity and fast calculation efficiency.The seed set selected by the existing algorithm based on network characteristics is susceptible to interference from the "rich club" phenomenon in the network when information is diffused,resulting in a large amount of overlap in the spread of the seed set,which is not conducive to the wide range of information in the network spread.In order to solve the above two problems,this paper proposes an influence maximization algorithm(IMax)based on dynamic selection of candidates.In order to ensure that the seed nodes have better propagation capabilities,the IMax algorithm takes into account the degree centrality.In order to make the propagation range between the seed sets generated by the IMax algorithm overlap as little as possible,this paper uses breadth-first traversal to calculate the distance between nodes to select the nodes that are as far away as possible from the seed node set to join the seed set.In order to more accurately characterize the potential information dissemination capability of a node,we reduce the possibility of seed node neighbors joining the seed set by attenuating the degree of the node,and use the candidate node set to accomplish this goal.For the decay of node degree,this paper proposes two strategies.One is to decay the degree of seed node neighbors to 0,named Zero-IMax;the other is to decay the degree of seed node neighbors to 1/2 of the existing degree,named Half-IMax.In order to verify the effectiveness of the algorithm proposed in this paper,the algorithm proposed in this paper is compared and analyzed on the SIR model with 5currently popular impact maximization algorithms on 14 real public data sets.Experimental results show that the method in this paper has good performance and stability,and is significantly better than the Degree algorithm,H-index algorithm,and K-shell algorithm.In most cases,it is equivalent to the Vote Rank algorithm and the LIR algorithm,and sometimes even better than the Vote Rank algorithm and LIR.algorithm.