Scalable influence maximization based on influential seed successors

摘要

Influence maximization is a fundamental problem, which is aimed to specify a small subset of individuals as the seed set to influence the individuals as much as possible under a certain influence cascade model. Most existing works on influence maximization assume that all of the seeds would like to spread the designated information. However, in reality, a small number of the seeds may be unwilling to spread this information, which may waste unnecessary resources. Thus, it is important for us to find a series of successors to replace these useless seeds. To deal with this challenge, we put forward a new method, which utilizes the degree discount algorithm to find the original seed set firstly. Moreover, we design a candidate selection strategy to select a large number of candidate seeds combining the largest degree nodes and the neighbors of removed nodes. At last, by optimizing the combination of original seeds and candidate seeds, our algorithm can select the combination of the most influential seeds by simulated annealing method. Furthermore, exhaustive experiments demonstrate that our proposal performs better than the other conventional algorithms in the aspects of influence spread and running time.