Identifying influential nodes for influence maximization problem in social networks using an improved discrete particle swarm optimization

Influence maximization problem is to select a set of influential nodes and maximize the influence spread of the seed set in the social networks. Greedy strategies are high time consumption, especially in large-scale networks, and therefore cannot be efficiently applied to practical scenarios. Meta-heuristic algorithms have been demonstrated by simulations as efficient ways to solve the intractable problem, but some of them suffer from premature easily. To solve the problem effectively, an improved discrete particle swarm optimization called IDPSO is proposed in this study. According to the framework, in the local search operation, nodes in the candidate seed set are randomly selected to be improved, giving each node an even opportunity to be selected as a candidate. Then, particles tend to be trapped into local optimum are labeled for further exploitation. Finally, local search operation is performed on the labeled particles and the current global optimal particle. Results on practical social networks show that IDPSO outperforms as a more promising and robust method.