Maximizing the spread of influence via the collective intelligence of discrete bat algorithm

• DOI: 10.1016/j.knosys.2018.06.013
• Publication Date: 2018-08-06T21:04:59Z
• Authors: Jianxin Tang; Ruisheng Zhang; Yabing Yao; Zhili Zhao; Ping Wang; Huan Li; Jinliang Yuan
• Keywords: Maximization

Abstract Influence maximization aims to select a small set of k influential nodes to maximize the spread of influence. It is still an open research topic to develop effective and efficient algorithms for the optimization problem. Greedy-based algorithms utilize the property of “submodularity” to provide performance guarantee, but the computational cost is unbearable especially in large-scale networks. Meanwhile, conventional topology-based centrality methods always fail to provide satisfying identification of influential nodes. To identify the k influential nodes effectively, we propose a metaheuristic discrete bat algorithm (DBA) based on the collective intelligence of bat population in this paper. According to the evolutionary rules of the original bat algorithm (BA), a probabilistic greedy-based local search strategy based on network topology is presented and a CandidatesPool is generated according to the contribution of each node to the network topology to enhance the exploitation operation of DBA. The experimental results and statistic tests on five real-world social networks and a synthetic network under independent cascade model demonstrate that DBA outperforms other two metaheuristics and the Stop-and-Stair algorithm, and achieves competitive influence spread to CELF (Cost-Effective Lazy Forward) but has less time computation than CELF.