影响最大化(IM)是复杂网络分析中的基础性问题,具有广泛的实际应用场景。迄今为止,现有IM方法在识别关键节点时主要依赖于标准图模型,难以刻画许多现实系统中固有的高阶交互关系。超图可更有效地建模此类高阶交互。然而,采用超图可能导致搜索空间过大及级联动力学建模复杂度升高,从而难以准确识别关键节点。为此,本研究提出一种基于离散粒子群优化(Discrete Particle Swarm Optimization)算法与阈值模型(threshold model)的新型超图建模IM方法。在该方法中,一个粒子(即候选解)表示种子节点的选择信息;适应度函数通过双层局部影响近似机制,对种子节点的影响范围进行准确且高效的评估。我们还提出一种基于度数的初始化策略以提升初始解质量,并设计了融合局部搜索的粒子速度与位置更新规则,以引导粒子向更优解收敛。实验结果表明,所提方法在合成超图与真实超图上均优于基线方法。消融实验进一步验证了局部搜索策略与初始化策略的有效性。
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.