一种针对网络结构破坏下鲁棒影响力最大化问题的Memetic算法

• 作者: 王帅 刘静
• 来源期刊: 计算机学报
• 关键词: 复杂网络 影响力最大化问题 鲁棒性 优化 Memetic算法
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 人工智能与社会计算
• 页码范围: 1153-1167
• 页数: 15页
• 分类号: TP18
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2021.01153

摘要

复杂网络问题的建模与应用是目前研究的热点之一.如何从网络中选择具有信息传播能力的成员,即影响力最大化问题,引发了广泛的关注.目前的研究主要集中在如何将网络上的信息传播过程建模,以及如何选择可靠的传播种子节点.这些工作一定程度上帮助我们了解了网络上的信息传播过程,但是已有研究并未考虑外界因素对于网络系统的影响,比如结构损毁对于网络连通性以及网络上信息传播过程造成的干扰.这使得目前的影响力最大化问题解决方案无法鲁棒地应对现实中的多种应用场景.针对这一不足,本文从结构受损的角度定义了鲁棒影响力最大化问题,在已有工作的基础上设计了对应的性能衡量指标.在该指标的指导下,设计了尝试解决鲁棒影响力最大化(Robust Influence Maximization,RIM)问题的Memetic算法(Memetic Algorithm,MA),记为MA-RIM,其目的 是寻找具有鲁棒信息传播能力的种子节点.多种网络上的实验结果验证了MA-RIM算法在解决鲁棒影响力最大化问题上的有效性.