Enhancing Discrete Particle Swarm Optimization for Hypergraph-Modeled Influence Maximization
For researchers in complex network analysis, this work addresses the challenge of influence maximization in hypergraph models, but the improvements are incremental over existing methods.
The paper tackles influence maximization in hypergraphs, which capture higher-order interactions beyond standard graphs. The proposed discrete particle swarm optimization method with a two-layer local influence approximation outperforms baselines on synthetic and real-world hypergraphs.
Influence maximization (IM) is a fundamental problem in complex network analysis, with a wide range of real-world applications. To date, existing approaches to influential node identification in IM have predominantly relied on standard graphs, failing to capture higher-order intrinsic interactions embedded in many real-world systems. Hypergraphs can be employed to better capture higher-order interactions. However, using hypergraphs may lead to an excessively large search space and increased complexity in modeling cascading dynamics, making it challenging to accurately identify influential nodes. Therefore, in this study, we propose a new hypergraph-modeled IM method, based on the Discrete Particle Swarm Optimization algorithm and the threshold model. In the proposed method, a particle (i.e., a candidate solution) represents the selection information of seed nodes, and the fitness function is designed to accurately and efficiently evaluate the influence of seed nodes via a two-layer local influence approximation. We also propose a degree-based initialization strategy to improve the quality of initial solutions and develop rules for updating particles' velocity and position, incorporated with a local search to drive particles toward better solutions. Experimental results demonstrate that the proposed method outperforms baseline methods on both synthetic and real-world hypergraphs. In addition, ablation studies validate the effectiveness of both the local search and the initialization strategies.