A Search Space Reduction-Based Progressive Evolutionary Algorithm for Influence Maximization in Social Networks
Lei Zhang, Kaicong Ma, Haipeng Yang, Cheng Zhang, Haiping Ma, Qi Liu
Abstract
Influence maximization (IM) problem, which selects a subset of nodes from a social network to maximize the influence spread, appeals to numerous scholars. Since the IM problem is NP-hard, it is still an arduous task to achieve good results in terms of influence spread and running time at the same time. This article proposes a novel search space reduction strategy-based progressive evolutionary algorithm (SSR-PEA) for solving IM problems effectively and efficiently. In SSR-PEA, a novel search space reduction strategy (SSR) in the light of the power-law distribution of the social network is designed to reduce the computational overheads, which eliminates a great deal of less influential nodes in a sensible way. After that, we propose a progressive evolutionary framework based on SSR, where the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -element individual is optimized on the basis of the ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -1)-element individual to speed up the optimal solution search process. Experimental results on ten real-world networks demonstrate that the proposed algorithm SSR-PEA can achieve 98% of the influence spread achieved by cost-effective lazy forward (CELF) on average, and its running time is two or even three orders of magnitude shorter. Thus, SSR-PEA strikes a better balance between effectiveness and efficiency.