通过多目标方法，在结构故障情况下平衡成本与影响力

《Swarm and Evolutionary Computation》：Balancing cost and influential ability under structural failures via a multi-objective approach

鲁棒影响最大化问题研究：提出多目标优化算法MOALO-CRIM，结合节点结构成本与抗级联故障能力，构建鲁棒性影响评估指标，并通过实验验证算法在复杂网络中的高效性与解集多样性。

　　

王帅|唐俊如|白秀丽

深圳中山大学智能系统工程学院，中国深圳518107

摘要

影响力最大化问题和网络鲁棒性提升作为与复杂系统相关的优化或信息挖掘任务，近年来受到了越来越多的关注。前者旨在识别一组能够最大化信息传播的种子节点，后者则旨在在网络发生故障或受到攻击时保持其功能。基于这些概念，引入了鲁棒影响力最大化（RIM）问题，以综合考虑影响力传播过程的鲁棒性。然而，现有研究主要采用单一目标方法，并且很大程度上忽略了节点选择所带来的成本。在本研究中，通过整合节点成本因素，对RIM问题进行了扩展性建模，从而将其视为一个多目标优化问题。我们的目标是在级联故障场景下同时最大化网络的鲁棒影响力并最小化成本，这是以往研究尚未涉及的。为了解决这个问题，我们提出了一种新的多目标算法MOALO-CRIM，该算法利用有效的随机游走和精英选择机制，在影响力和成本之间实现了有效的平衡。在真实世界和合成网络上进行的实验证明了所提出方法的有效性。该算法能够生成高质量的帕累托前沿，同时具备良好的收敛性和多样性。此外，我们还使用TOPSIS方法从帕累托集中选择代表性解决方案，以支持利益相关者的决策制定。

引言

复杂网络在现实世界系统中无处不在，构成了社交网络[1]、关键基础设施系统[2]和供应链网络[3]等众多领域的核心。复杂网络研究中的一个重要挑战是影响力最大化（IM）问题，该问题旨在识别一小部分具有高度影响力的节点，这些节点的激活能够在给定的传播模型下实现信息或影响力的最大传播。IM问题在病毒营销等领域得到了广泛应用，其中选择了一些个体（如客户）来启动信息传播，利用他们在网络中的位置来最大化覆盖范围和影响力[1]。多年来，已经提出了多种策略来解决IM问题。经典的贪心算法[4]在性能上提供了强有力的理论保证，但通常计算开销较高，不适合大规模网络。相比之下，基于节点中心性度量的启发式方法[5,6]计算效率更高，但通常缺乏最优性保证。最优性和计算效率之间的固有权衡突显了将IM方法应用于现实世界大规模网络时的持续挑战，这激发了寻找更有效和可扩展解决方案的需求。

网络系统的脆弱性和韧性引发了网络鲁棒性[7]的问题，即评估网络在遭受破坏时如何保持良好的功能特性。结合IM问题，这就引出了鲁棒影响力最大化问题（RIM）[8]，该问题专注于研究网络在经历波动、攻击甚至故障时的传播性能。在现实世界场景中，这些故障表现为用户暂时退出社交网络、关键基础设施设备故障或供应链中断导致的信息传播损失。过去的研究强调了输入数据的不确定性[8,9]、模型传播概率的不确定性[10]，以及针对攻击或其他类型故障的最大化影响力[11]。在本研究中，我们考虑了节点破坏可能引发的级联故障情况，对鲁棒影响力问题进行了研究。

与经典的IM问题类似，RIM的一个关键方面是与网络中节点的选择和激活相关的成本[12]。现有的鲁棒影响力最大化研究通常通过使用简单的结构度量（最常见的是节点度）来考虑节点选择成本。虽然这种成本建模部分反映了节点之间的差异，但它们往往忽略了更高层次的结构重要性，包括节点在全局连通性中的角色及其在网络中的战略位置[[13], [14]]。在本研究中，我们关注的是基于节点拓扑属性的结构感知成本，这些属性直接反映了节点传播影响力的能力，而这在之前的研究中尚未得到充分探讨。直观地说，位于网络中心或具有战略重要性的节点往往具有更强的传播能力，因此激活这些节点通常会带来更高的成本。这种内在关系引发了一个基本的权衡：虽然选择具有高影响力潜力的节点是有利的，但这样做通常会带来更高的成本。本研究在结构故障和成本限制的背景下扩展了RIM模型。为了明确捕捉和优化这一冲突，我们将成本感知的RIM（CRIM）问题构建为一个多目标优化问题，即识别一组能够同时最大化鲁棒影响力和最小化激活总成本的节点。

鉴于成本感知的RIM问题也属于NP难问题，穷尽所有最优种子集在计算上是不可行的。为了解决这一挑战，提出并应用了一种多目标优化算法——多目标蚁狮优化器（MOALO）[15]来解决这个离散的多目标问题。MOALO算法以其快速收敛能力和通过随机游走机制的有效探索能力而著称，特别适合处理这一任务的固有复杂性。

本文的主要贡献有三个方面：首先，通过纳入种子节点的结构重要性，建立了一个鲁棒的成本模型。该模型为评估与用户激活相关的成本提供了一个现实的框架，并可以扩展到虚拟市场中的定价策略。据我们所知，这是首次尝试将RIM问题与成本限制相结合。其次，通过提出的一种两跳近似方法，将鲁棒影响力的概念扩展到了加权网络和非加权网络。第三，MOALO算法成功应用于多目标RIM问题，并且与其他求解器相比表现出了更优越的性能。此外，还提出了一种鲁棒的种子节点集选择策略，优先考虑低成本和高鲁棒影响力。

本文的其余部分结构如下：第2节全面回顾了与IM问题、RIM问题以及当前种子节点选择成本模型相关的现有文献。第3节介绍了所使用的评估指标，详细介绍了鲁棒影响力（RI_cf）指标和提出的成本函数；该节进一步探讨了定义的成本与RI_cf之间的复杂关系。第4节详细描述了MOALO-CRIM算法。第5节展示了在合成网络和真实世界网络上进行的广泛实验结果，包括加权网络和非加权网络。最后，第6节总结了我们的主要发现并提出了结论性意见。

节选内容

背景知识

复杂网络正式表示为一个图G = (V, E)，其中V = {1, 2, …, N}是N个节点的集合，E = {e_ij | i, j ∈ V}表示连接节点对的M条边的集合。该图可以用邻接矩阵或边列表的形式表示。具体来说，如果相应的权重w_ij = 1，则存在边e_ij，表示节点i和节点j之间的连接。权重w_ij量化了这种连接的强度或属性，例如节点之间的激活概率

级联故障场景下的鲁棒性感知影响力评估指标

传统的IM方法通常依赖于大量的蒙特卡洛模拟，这对于大规模网络来说计算成本过高。为了降低大规模网络的计算复杂性，提出了基于独立级联（IC）模型的高效两跳近似方法来估计种子集S的影响力传播σ(S)[26]。最近的研究进一步将RIM扩展到了级联效应中的节点影响力研究

MOALO-CRIM

本节详细介绍了为这个多目标和离散优化问题定制的ALO算法的关键组件和调整。多目标蚁狮优化器用于成本感知的鲁棒影响力最大化（MOALO-CRIM）是一种新颖的元启发式算法，旨在识别网络中受保护的节点集，同时最大化RI_cf并最小化相关的种子成本，同时提高了解决方案的收敛性和覆盖率。

实证分析

首先在本节验证了RI_cf指标的有效性。随后进行了广泛的模拟实验来测试MOALO-CRIM的性能，并将其与几种最先进的多目标优化方法进行了基准测试。然后进行了消融研究，以展示算法中各个组件的贡献。最后，进行了真实世界实验，全面评估了算法的鲁棒性和泛化能力。

结论

总之，我们的研究建立了一个成本模型，该模型考虑了在级联故障期间加权网络和非加权网络中的传播特性和节点选择成本。我们引入了RI_cf指标来量化网络的鲁棒影响力，该指标反映了网络在结构故障下保持连通性的能力，同时保留了其影响力范围。种子集的成本使用结构成本指标来定义，代表了

CRediT作者贡献声明

王帅：撰写——原始草稿，验证，调查，数据整理。唐俊如：可视化，验证，数据整理。白秀丽：资源获取，数据整理。