A Landscape-Aware Discrete Particle Swarm Optimization for the Influence Maximization Problem in Social Networks

Influence maximization (IM) is a pivotal challenge in social network analysis, which aims to identify a subset of key nodes that can maximize the information spread across networks. Traditional methods often sacrifice solution accuracy for spreading efficiency, while meta-heuristic approaches face limitations in escaping local optima and balancing exploration and exploitation. To address such challenges, this paper introduces a landscape-aware discrete particle swarm optimization (LA-DPSO) to solve the IM problem. The proposed algorithm employs a population partitioning strategy based on a fitness distance correlation index to enhance population diversity. For the two partitioned subpopulations, a global evolutionary mechanism and a variable neighborhood search mechanism are designed to make a symmetrical balance between the exploration and exploitation. The fitness landscape entropy is introduced to detect the local optima and prevent the population from premature convergence during the evolution. Experiments conducted on six real-world social networks demonstrate that the proposed LA-DPSO achieves an average performance improvement of 16% compared to state-of-the-art methods while exhibiting excellent scalability across diverse network types.