An Efficient Memetic Algorithm for Influence Maximization in Social Networks

摘要

Influence maximization is to extract a small set of nodes from a social network which influences the propagation maximally under a cascade model. In this paper, we propose a memetic algorithm for community-based influence maximization in social networks. The proposed memetic algorithm optimizes the 2-hop influence spread to find the most influential nodes. Problem-specific population initialization and similarity-based local search are designed to accelerate the convergence of the algorithm. Experiments on three realworld datasets demonstrate that our algorithm has competitive performances to the comparing algorithms in terms of effectiveness and efficiency. For example, on a real-world network of 15233 nodes and 58891 edges, the influence spread of the proposed algorithm is 12.5%, 13.2% and 173.5% higher than the three comparing algorithms Degree, PageRank and Random, respectively.