DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks
- ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
- Publication Type:
- Journal Article
- Journal of Network and Computer Applications, 2018, 103, pp. 119-130
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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.
Please use this identifier to cite or link to this item: