DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks

Influence maximization (IM) is the problem of finding a small subset of nodes in a social network so that the number of nodes influenced by this subset can be maximized. Influence maximization problem plays an important role in viral marketing and information diffusions. The existing solutions to influence maximization perform badly in either efficiency or accuracy. In this study, we analyze the causes for the low efficiency of the greedy approaches and propose a more efficient algorithm called degree-descending search evolution (DDSE). Firstly, we propose a degree-descending search strategy (DDS). DDS is capable of generating a node set whose influence spread is comparable to the degree centrality. Based on DDS, we develop an evolutionary algorithm that is capable of improving the efficiency significantly by eliminating the time-consuming simulations of the greedy algorithms. Experimental results on real-world social networks demonstrate that DDSE is about five orders of magnitude faster than the state-of-art greedy method while keeping competitive accuracy, which can verify the high effectiveness and efficiency of our proposed algorithm for influence maximization.