IM-SSO: Maximizing influence in social networks using social spider optimization

Abstract

Online social networks play a pivotal role in the propagation of information and influence as in the form of word-of-mouth spreading. The influence maximization (IM) problem is a fundamental problem to identify a small set of individuals, which have a maximal influence spread in the social network. Unfortunately, the IM problem is NP-hard. It has been depicted that a hill-climbing greedy approach gives a good approximation guarantee. However, it is inefficient to run on large-scale social networks. In this paper, a global influence evaluation function is presented for the IM optimization problem. The global influence evaluation function provides a reliable expected diffusion value of influence spread under the traditional diffusion models. To optimize global influence evaluation function, an influence maximization algorithm based on social spider optimization (IM-SSO) is presented. IM-SSO redefines the representation and update rule of spider's vibration and performs random walk towards target vibration. The algorithm uses a jump away process to overcome the weakness of premature convergence. The experimental results on six real-world social networks show that the proposed algorithm is more effective than the state-of-the-art heuristics and more time-efficient than CELF++, static greedy, and PSO with an approximate influence spread. © 2019 John Wiley & Sons, Ltd.