201. Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization.
- Author
-
Tang, Jianxin, Zhang, Ruisheng, Yao, Yabing, Yang, Fan, Zhao, Zhili, Hu, Rongjing, and Yuan, Yongna
- Subjects
- *
SOCIAL network analysis , *PARTICLE swarm optimization , *COMPUTER algorithms , *DISCRETE choice models , *RADIO wave propagation - Abstract
Abstract Influence maximization aims to select a subset of top- k influential nodes to maximize the influence propagation, and it remains an open research topic of viral marketing and social network analysis. Submodularity-based methods including greedy algorithm can provide solutions with performance guarantee, but the time complexity is unbearable especially in large-scale networks. Meanwhile, conventional centrality-based measures cannot provide steady performance for multiple influential nodes identification. In this paper, we propose an improved discrete particle swarm optimization with an enhanced network topology-based strategy for influence maximization. According to the strategy, the k influential nodes in a temporary optimal seed set are recombined firstly in ascending order by degree metric to let the nodes with lower degree centrality exploit more influential neighbors preferentially. Secondly, a local greedy strategy is applied to replace the current node with the most influential node from the direct neighbor set of each node from the temporary seed set. The experimental results conducted in six social networks under independent cascade model show that the proposed algorithm outperforms typical centrality-based heuristics, and achieves comparable results to greedy algorithm but with less time complexity. Highlights • We make further exploration on discrete PSO for influence maximization problem. • We design a network topology-based local search to enhance the exploitation of DPSO. • Our algorithm achieves comparable results to greedy algorithm and the CELF algorithm. • The proposed algorithm provides steady performance on identifying influential nodes. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF