人工蜂群技术与变邻域搜索算法的结合：为社会网络中影响力最大化问题提供全新视角

《Swarm and Evolutionary Computation》：Artificial bee colony meets variable neighborhood search: Fresh insights into influence maximization in social networks

　　唐建新|董方杰|吴晨|陈文环|魏慧怡
兰州理工大学计算机科学与人工智能学院，中华人民共和国

**摘要**
在复杂网络研究中，影响力最大化问题是核心议题之一，其目标是寻找能够最大化影响传播的关键节点。然而，传统的元启发式算法由于邻域生成策略僵化以及缺乏方向性指导，难以找到最优的种子节点集合。为此，本文提出了基于可变邻域搜索策略的人工蜂群算法来应对这些挑战。具体来说，该算法采用了一种精英-全局协同邻域构建机制，通过引入方向性线索来避免无目的的探索；同时引入了一种可变邻域搜索策略，能在细粒度的邻域结构之间动态切换，从而在探索与利用之间实现良好的平衡。当种群过早收敛到局部最优解时，细粒度的个体中心停滞控制机制与具有停滞感知的种群管理机制相结合，能够在个体和种群层面维持搜索活力。通过对九个实际网络的实验验证，该算法在影响传播方面相较于所有基线方法平均提升了6.3%，展现了其在不同类型网络中的强大适用性。这些成果表明了该算法在谣言控制和级联故障等实际应用中的潜力。

**引言**
如何通过单一帖子改变公众认知，而大规模的宣传活动却未能产生效果？这种明显的不对称性促使我们思考如何准确定位信息传播的源头。复杂网络建模可以将复杂的社交结构映射到图中，从而回答这一问题。然而，在实践中，检测这些源头节点如同穿越迷宫一般困难。关键在于找到能够引发广泛影响的关键节点，这需要先进的策略和对网络结构的深刻理解[1]。这种复杂性不仅带来计算挑战，还为多个实际领域带来了重大价值：能够识别有影响力的节点有助于引导理性对话、阻止电网故障的扩散、影响选举结果，并推动社会运动的发展[2]。在更微妙的层面，这种技术还帮助医院通过社交媒体传递重要健康信息，保护社区并促进福祉[3]。

为将这一问题数学化，复杂网络领域的学者将其定义为影响力最大化（IM）问题。目标是在网络中选择初始用户（通常称为种子节点），以在特定传播模型下最大化影响传播[4]。然而，确定最优种子节点集合远非易事。每个节点的影响传播能力独特，这决定了其对邻近节点的影响程度。难点不仅在于识别有影响力的节点，还在于如何结合它们的潜力以实现整体传播的最大化。Kempe等人[5]证明IM问题属于NP难问题，这意味着在多项式时间内找到最优解是不可能的。早期研究侧重于具有近似保证的贪心算法，但这些算法需要大量蒙特卡洛模拟来逐一选择有影响力的节点。为了提高计算效率，研究人员开发了基于网络拓扑特征的启发式方法[6]以规避高昂的模拟成本。然而，直接依赖顶级节点选择的方法会忽略种子节点之间的影响重叠，从而降低性能。为解决这一问题，基于深度学习的方法[7]通过集成图拓扑结构来减轻影响重叠，但精度提升的代价是训练成本过高。

与这些方法不同，独立于问题特性的元启发式算法长期以来被用于解决NP难问题[8]。这些算法模仿自然界的巧妙机制，在探索与利用之间实现动态平衡。许多元启发式算法已成功应用于IM问题，包括遗传算法[9]、群体智能行为（如Harris鹰优化算法[10]）以及物理过程（如引力搜索算法[11]）。尽管这些方法广泛应用，但由于三个主要缺陷，它们生成的种子节点集准确性较低：首先，缺乏方向性指导导致盲目利用；其次，单一邻域搜索策略降低了种群多样性；最后，后期迭代中探索减少会增加过早收敛的风险。为应对这些挑战，本文提出了基于可变邻域搜索策略的人工蜂群算法（ABCVNS）。由于ABC的扰动逻辑与IM中的节点替换操作相匹配，因此被选为基础优化器[12]。然而，ABC的随机性可能导致搜索方向性失准。为此，引入了精英-全局协同邻域构建（EGCNC）机制，通过动态应用精英知识来优化搜索方向[13]。为了实现探索与利用之间的平衡，引入了可变邻域搜索（VNS）策略[13]。VNS策略允许在多种邻域结构之间动态切换，而现有元启发式算法仅限于单一固定模式。这种邻域结构的灵活性增强了ABCVNS避免局部最优解的能力。

此外，还采用了双层机制来降低过早收敛的风险：在个体层面，通过ABC的独特放弃策略实现了细粒度的个体中心停滞控制机制，实时重置失败节点而不影响整体种群；在种群层面，具有停滞感知的种群管理机制应对多样性衰减。最后，建立了一个稳健、可解释且通用的解决框架，不仅解决了IM问题，也为其他组合优化问题开辟了通用途径。

**主要贡献**
1. 提出了基于VNS的ABC算法，作为一种新颖的优化方法，用于应对复杂的IM问题。通过动态切换不同的邻域结构，有效克服了局部最优解的陷阱，并实现了探索与利用之间的平衡。
2. 通过精英-全局协同邻域构建（EGCNC）机制解决了标准ABC的方向性失准问题，将搜索从无目的游走转变为以精英节点为导向的精细调整。
3. 利用ABC的放弃策略实现了细粒度的个体中心停滞控制机制，实时解决个体停滞问题。

**论文结构**
第2节回顾相关文献；第3节详细介绍了ABCVNS算法；第4节报告实验结果与分析；第5节讨论优势、不足及潜在应用；第6节总结。

**参考文献**
Kempe等人[5]提出了一个具有(1?1/e??)近似保证的爬山贪心算法；Leskovec等人[14]解决了时间复杂性问题。

**预备知识**
社交网络可用图G=(V,E)表示，其中V表示个体，E表示它们之间的相互关系。IM问题旨在从给定网络中选择一组节点（S），在特定传播模型下触发最大的影响传播，公式为：S=argmaxS?V,|S|≤kσ(S)，其中σ(S)表示种子集S的影响传播。

**实验结果与分析**
第4节系统评估了ABCVNS算法，包括实验设置、模块化消融研究以及与最新算法的对比分析。所有程序均用Python编写，并在配备Intel(R) Core(TM) i9-14900HX处理器（2.2 GHz）和32 GB RAM的Windows 11服务器上执行。

**讨论**
与现有方法相比，传统贪心算法受限于耗时的蒙特卡洛模拟，尽管提供了近似保证，但效率较低；而启发式算法由于忽略种子节点间的影响重叠，通常产生较差的结果。ABCVNS通过适应性函数避免了昂贵的模拟成本。

**结论**
本文通过将ABC算法与VNS策略结合，创新出一种名为ABCVNS的智能优化算法。该算法利用VNS策略实现动态邻域切换，增强了局部搜索能力；同时设计了一种精英-全局协同邻域构建机制，根据历史信息调整搜索方向。

**作者贡献声明**
唐建新：撰写、审阅与编辑、数据分析；董方杰：撰写、原始草稿、软件开发与方法论；吴晨：撰写、审阅与编辑、可视化；陈文环：监督、资源协调；魏慧怡：形式化分析、概念化。

**材料与代码可用性**
代码可按需提供。

**声明**
在撰写过程中使用了AI辅助工具进行错误校正以提高可读性和语言表达。作者在使用后对内容进行了审查和编辑，并对出版物的内容负全责。

**利益冲突声明**
作者声明没有已知的可能影响本文工作的财务利益或个人关系。

**致谢**
本研究得到了国家自然科学基金（项目编号62562044和62162040）、甘肃省大学教师创新基金（项目编号2024A-024）、甘肃省杰出青年科学基金（项目编号23JRRA766）以及甘肃省技术创新引导计划（项目编号24CXGA046）的支持。