An adaptive differential evolution algorithm driven by multiple probabilistic mutation strategies for influence maximization in social networks

Influence maximization is a critical research topic of social network analysis, particularly with the increasing involvement of individuals in the global networked society. The purpose of the problem is to identify k influential nodes from the social network and activate them initially to maximize the expected number of influenced nodes at the end of the spreading process. Although some meta-heuristics based on swarm intelligence or biological evolution have been proposed to tackle this intractable problem, further investigation is required to refine the exploration and exploitation operations based on the iterative information from the evolutionary process. In this paper, an adaptive differential evolution algorithm driven by multiple probabilistic mutation strategies is proposed for the influence maximization problem. In order to enhance the evolutionary capability of the later stages of the discrete differential evolution, the mutation in the framework, consisting of three policies, namely comprehensive learning particle swarm mutation strategy, differential mutation strategy, and perturbation strategy, is implied based on different probabilistic models. An adaptive local search strategy is presented to improve the local optimum results based on a potential alternative library consisting of structural hole nodes, which guides the differential evolution to find a more optimal solution. Experimental results on six real-world social networks demonstrate the competitive performance of the proposed algorithm in terms of both efficacy and efficiency compared to state-of-the-art algorithms.