集智俱乐部 10月14日 13:25

瓦解有害复杂网络：方法、挑战与未来方向

本文系统梳理了复杂网络瓦解的研究进展，重点介绍了五大类方法：基于数学规划、中心性指标、启发式算法、进化计算及机器学习。文章首先阐述了网络瓦解的数学模型，随后深入分析了各类方法的原理、优缺点及适用场景。此外，文章还展望了未来研究方向，包括从无向网络到有向、加权、空间、多层及动态网络，以及从结构瓦解到动力学干扰、从单目标到多目标、从简单约束到复杂约束、从静态决策到动态博弈等模型维度的拓展。最后，文章强调了开发高效、低复杂度算法的重要性。

🌐 **多维度网络演化与瓦解挑战**：研究正从传统的无向、无权、静态、单层网络，拓展至更贴近现实的有向、加权、空间、多层及时变网络。这些更复杂的网络结构和动态特性，对传统的瓦解方法提出了新的挑战，需要开发能够适应这些复杂性的新模型和算法。

⚙️ **瓦解模型与策略的深化**：未来的研究将超越单纯破坏网络结构，转向干扰网络动力学行为，例如通过信号干扰来瓦解敌方通信。同时，研究也将从单一目标瓦解转向多目标优化，并纳入时间、成本、信息等复杂约束条件，以制定更具现实意义的瓦解策略。

🤖 **算法创新与效率提升**：面对日益庞大的网络规模，算法的计算复杂性成为关键瓶颈。未来的研究重点在于开发高效、低复杂度的瓦解算法，包括分布式算法、并行算法以及人工智能方法，以应对现实世界中大规模网络系统的瓦解需求。

⚔️ **动态博弈与攻防策略**：网络瓦解研究正从单方面的静态决策转向考虑攻击者与防守者之间的动态博弈。理解并制定在攻防博弈框架下的均衡策略，将是未来研究的重要方向，因为防御策略会显著影响瓦解效果，使得关键节点的选择更加复杂。

原创吴俊等 2025-10-12 19:09 湖南

复杂网络瓦解的五大方法与三大前沿方向。

摘要

一般情况下, 我们面对的网络都是“有益的”, 但是有时候我们面对的网络也可能是“有害的”, 例如恐怖组织网络、疾病传播网络等。如何通过阻断、干扰、免疫、封锁、隔离等手段有效瓦解这些有害网络成为一个亟待解决的挑战性问题, 其核心是找到网络系统的“关键节点(边)”。吴俊团队发表综述首先给出了网络瓦解问题的数学描述, 在此基础上从基于数学规划、基于中心性指标、基于启发式算法、基于进化计算、基于机器学习等几个方面系统总结了运筹学、网络科学、计算机科学等领域关于复杂网络瓦解问题的研究进展, 最后分别从目标网络维度、瓦解模型维度、瓦解算法维度对复杂网络瓦解问题未来发展进行了展望。

集智俱乐部联合北京师范大学教授吴俊、国防科技大学副研究员谭索怡、北京化工大学副教授谷伟伟、中国科学技术大学博士后范天龙、国防科技大学在读博士卿枫共同发起「复杂网络瓦解读书会」，跨越网络结构、算法模型与应用场景的视角，探索复杂网络瓦解的前沿进展。重点探讨不同算法与优化框架如何帮助我们认识网络的脆弱性，并在现实约束下推动网络系统的智能演化与应用发展。扫描下方海报二维码即可加入！

关键词：复杂网络、瓦解、关键节点、免疫、反恐、体系对抗

吴俊等丨作者

张俊丽｜编译

1. 引言

2. 网络瓦解问题的数学描述

3. 基于数学规划的网络瓦解方法

4. 基于中心性指标的复杂网络瓦解方法

5. 基于启发式算法的复杂网络瓦解方法

6. 基于进化算法的复杂网络瓦解方法

7. 基于机器学习的复杂网络瓦解方法

8. 结论与展望

1. 引言

伴随着现代信息技术的不断发展, 人类社会已经进入网络化时代。万维网、社交网、物联网、电力网、贸易网……可以说, 我们生活在一个被网络包围的世界。这些网络规模庞大、结构多变, 既不是规则网络, 也不是随机网络，而且具有复杂的动力学行为, 因此被称之为“复杂网络”。自从现实世界中网络的小世界效应[1]和无标度特性[2]被揭示以来, 复杂网络研究在过去二十年里迅猛发展, 受到数学、物理、计算机、管理学、社会学、生物学等不同领域学者的共同关注，一门研究复杂网络共性规律和普适方法的交叉学科——网络科学迅速崛起，成为研究复杂系统的新范式[3-7]。

一般情况下, 我们面对的网络都是“有益的”。例如, 交通网络、电力网络、物流网络等。对于这些有益的网络, 我们希望通过规划设计、优化控制、防御保护等各种手段来保障它们持续、稳定、有效地维持功能。目前, 针对这些有益网络的设计、优化、控制与管理研究已经取得了丰富成果, 一直是管理科学、信息科学等多个学科领域共同关注的焦点[8-15]。但是, 很多时候我们面对的网络也可能是“有害的”。最典型的例子就是恐怖组织网络[16-18]。上个世纪60年代以来, 国际恐怖主义活动日益猖獗, 恐怖组织已经从传统的等级层次结构演化为网络化结构, 如何有效瓦解恐怖组织网络成为世界各国面临的共同难题。另外一个典型例子就是疾病传播网络[19, 20]。近年来, COVID-2019、SARS、埃博拉、疯牛病、禽流感等传染病接踵而至, 给人类社会造成巨大损失。如何有效阻断疾病在人群或动物之间扩散是全球公共卫生领域面临的艰巨任务。其中, 免疫是一种关键手段, 而免疫本质上就是通过注射疫苗从疾病传播网络中“移除”部分节点(人或动物)从而瓦解整个网络, 达到控制疾病扩散的目的。此外, 犯罪分子网络[21, 22]、毒品走私网络[23]、核材料走私网络[24]、癌细胞扩散网络[25]、谣言传播网络[26]、金融危机网络[27]以及军事对抗中的敌方网络[28]等都属于这类有害网络。如何通过阻断、干扰、免疫、封锁、隔离等手段有效瓦解这些有害网络成为一个亟待解决的问题。

伴随着网络科学的兴起,复杂网络瓦解问题也受到越来越多的关注,并取得了可喜进展。本文首先给出网络瓦解问题的数学描述, 在此基础上从基于数学规划、基于中心性指标、基于启发式算法、基于进化计算、基于机器学习等几个方面系统总结目前复杂网络瓦解问题的研究进展, 并对未来发展进行展望。

2. 网络瓦解问题的数学描述

所谓网络瓦解 (network disintegration[29], network interdiction[30], network inhibition[31], network dismantling[32], network destabilization[33]), 就是通过移除部分节点或边来破坏网络的结构、削弱网络的功能、干扰网络的行为。其问题的核心是如何在特定约束条件和各种瓦解目标下确定要移除的节点(边)集合, 也就是找到网络系统的“要害”, 其数学本质是一个组合优化问题。

令 G = (V, E) 表示目标网络, 其中 V={v1,v2,...,vN} 表示节点集合, 表示边的集合, N = |V|表示节点数量, W = |E|表示边数量。网络瓦解包括节点移除和边移除两种方式。令表示要移除的节点集合, 表示要移除的边集合, 表示瓦解之后的网络。通常, 我们假设节点移除后与之相关联的所有边都会随之移除。令 X={x1,x2,...,xN}表示节点瓦解策略, 其中若则xi = 1则, 否则xi = 0; 令Y = {y1, y2, …, yW}表示边瓦解策略, 其中若则yi = 1, 否则yi = 0。令I = (X, Y) ∈Ω表示一个网络瓦解方案, 其中Ω表示约束条件, 例如移除节点的数量不超过K, 即。令Φ(I)表示网络瓦解的目标函数, 则网络瓦解问题可以描述为如下的一般数学模型：

目标函数对于网络瓦解问题至关重要, 瓦解目标不同, 最优的网络瓦解方案就不一样[34, 35]。此外, 目标函数的选择还直接决定了网络瓦解问题的计算复杂性。网络被瓦解后通常会形成若干子图，若子图上任意两个节点间均存在一条链路, 则该子图可以称为连通片。令L表示网络瓦解后连通片的数量，nl (1 ≤ l ≤ L) 表示网络瓦解后每个连通片中包含节点的数量，dij表示节点vi和vj之间的最短路径长度。目前, 常用的网络瓦解目标函数Φ(I)主要包括：网络瓦解后连通片的数量[36-38]；网络瓦解后最大连通片的规模[39-43]，在加权网络中, 最大连通片也可以被定义为节点权重之和最大的连通片, 而不是包含节点数目最多的连通片[44]；网络瓦解后的赫芬达尔-赫希曼指数 (Herfindahl-hirschman index) [36]；网络瓦解后的信息熵[36, 45, 46]；网络瓦解后连通节点对的数量[36, 47-49]；网络瓦解后源节点和汇节点之间的最短路径长度[50-58]；网络瓦解后节点对之间的平均最短路径长度[40]；网络瓦解后节点对之间的效率[40]；网络瓦解后的源节点和汇节点之间的最大流[31, 59-67]；网络瓦解后的最大匹配[68, 69]；网络瓦解后的最小支撑树[70-72]；网络瓦解后的自然连通度[73]；网络瓦解后的最大介数[74]等。

无论节点瓦解方式还是边瓦解方式, 无论采用哪种瓦解目标函数, 除了少数特定网络, 网络瓦解问题都已经被证明是NP-complete问题[30, 31, 37, 38, 47, 50, 76, 77]。关于网络瓦解问题的计算复杂性, 可参见Lalou等撰写的综述[34]。

网络瓦解并不是一项简单的任务，由于其重要性和挑战性, 从上个世纪中期开始受到运筹学、网络科学、计算机科学等多个学科领域的广泛关注，取得了重要进展。早期的网络瓦解研究主要是从求解数学规划模型视角入手。从上个世纪末开始，伴随着复杂网络研究的兴起，基于中心性指标和启发式算法的网络瓦解方法开始兴起。近年来，进化算法以及机器学习的最新成果开始被应用到网络瓦解研究。下面，本文将分别从数学规划、中心性指标、启发式算法、进化计算、机器学习等几个方面总结复杂网络瓦解问题的研究进展。各个阶段的典型方法以及优缺点如表1所示。

表1 网络瓦解方法的分类及其典型方法

分类	典型方法	优缺点讨论
基于数学规划的网络瓦解方法	分支定界法；随机舍入法；混合迭代舍入法；单变量分解法；动态规划法	能得到最优的网络瓦解方案；对目标函数和约束条件有较高要求, 且不适用于大规模网络
基于中心性指标的网络瓦解方法	度中心性、K-核中心性、介数中心性、接近中心性	简单易实现；但单个指标下的重要节点集合不一定是最优的节点移除集合
基于启发式算法的网络瓦解方法	贪心算法、熟人免疫法、影响力扩散算法、置信传播分解算法、分支移除法、反向排序法、邻居信息概率算法、子图度中心算法、等量图分割法、最小和算法、谱分割算法	瓦解效果一般优于基于中心性指标的网络瓦解方法且具有较高的灵活性；但不一定能得到最优的网络瓦解方案
基于进化算法的网络瓦解方法	禁忌搜索算法、人工蜂群算法、遗传算法、模拟退火算法、种群增量学习算法、路径再链接的随机贪婪自适应搜索算法	能得到较好的网络瓦解方案, 具有高鲁棒性和广泛适用性；时间复杂度比较高
基于机器学习的网络瓦解方法	FINDER算法	与具体知识、规则无关, 适用于各类问题；不具有可解释性

3. 基于数学规划的网络瓦解方法

由于网络瓦解问题的本质是一个组合优化问题, 因此, 我们可以直接通过求解数学规划模型来寻找最优的网络瓦解方案。从上个世纪六十年代开始[59], 主要来自于运筹学领域的学者们提出了很多解决网络瓦解问题的数学规划模型和求解算法。下面, 我们简要介绍这个领域的研究成果。

3.1 目标函数为连通节点对数量

Arulselvan等[47]以连通节点对数量为目标函数, 提出了解决网络瓦解问题的线性整数规划 (integer linear programming, ILP) 模型。Di Summa等[78]在上述线性整数规划模型基础上, 通过改变约束条件和加入松弛变量, 使用分支定界方法使得模型可以在多项式时间内求解。值得指出的是, 上述整数规划模型中三角不等式约束的复杂度为O(n3), 从而限制了上述方法只能在小规模网络上使用(一般要求N<150)。为了克服这种限制, Veremyev等[79]提出了一种紧凑约束形式, 将复杂度从O(n3)降低到O(n2), 可以应用到中等规模网络中(N=1500)。Ventresca等[80]基于随机舍入 (randomized rounding) 方法给出了求解上述整数规划模型的近似算法, Shen等 [81]基于混合迭代舍入 (hybrid iterative rounding) 给出了求解上述整数规划模型的近似算法。

3.2 目标函数为连通片数量

Shen等[82]以连通片数量为目标函数, 提出了解决网络瓦解问题的混合整数规划 (mixed integer programming, MLP) 模型。Shen等[82]提出了当目标函数为最大化连通片数量、最小化最大连通片规模和最大化重构网络成本情况下的整数规划模型，并给出了针对前两个模型的动态规划求解算法。Veremyev等[75]提出了同时考虑移除节点和边的混合整数规划模型。Fan和Pardalos[83]考虑了网络中边上的权重不确定的情况, 提出了一种鲁棒优化模型 (robust optimization model)，并使用单变量分解法 (algorithm based on a decomposition on one variable)进行求解, 实验结果表明这一方法比直接使用分支定界的方法更有效。

4. 基于中心性指标的复杂网络瓦解方法

直接求解数学规划虽然能够给出最优的网络瓦解方案, 但是对目标函数和约束条件的数学形式有很高要求, 而且由于计算复杂性的原因无法应用于大规模网络。因此, 当面对大规模复杂网络时, 研究者开始尝试通过计算节点(边)的中心性指标, 也可以理解为重要性指标, 按照中心性指标的降序逐个进行节点(边)移除, 从而得到复杂网络瓦解策略。基于中心性指标的网络瓦解方法的本质是将网络瓦解问题简化为单个节点(边)的重要性排序问题[84, 85]。

4.1 基于度中心性的复杂网络瓦解方法

节点的度 (degree)，即和该节点直接相连的邻居节点数量, 是节点最基本也是最重要的属性之一。通常认为, 节点的度越大意味着该节点在网络中的重要性越高, 所以度中心性 (degree centrality) 是最直接也是最常用的中心性指标。Albert等[39]研究发现无标度 (scale-free) 网络对于“随机失效 (random failure) ”很健壮, 但是对于基于度中心性的“故意攻击 (intentional attack) ”非常脆弱, 移除少量度很大的核心节点后，无标度网络就会崩溃。Petter等[40]进一步研究了基于“重计算度中心性 (recalculated degree centrality) ”的网络瓦解方法, 即每次移除网络中度值最大的节点, 然后重新计算节点的度中心性。研究表明, 基于“重计算度中心性 (recalculated degree centrality) ”的网络瓦解效果要优于基于“初始度中心性 (initial degree centrality) ”的网络瓦解效果。

4.2 基于K-核中心性的复杂网络瓦解方法

度中心性作为一个局域信息的指标只度量了节点的邻居节点数目, 判定度数值相同则重要性也相同。但是, 相关研究结果表明在度量节点重要性的时候节点在网络中分布的位置也是关键因素。在网络中, 假如某个节点位于网络的关键位置, 尽管其度值较小, 通常也有较高的节点重要性; 而位于网络边缘的高度值节点其影响力通常有限。因此, Carmi[86]等人利用K-核分解算法 (k-shell decomposition) 来度量网络中节点的位置, 将网络边缘的节点逐层剥离, 位于网络内部层次的节点拥有更大的影响力。K-核分解可以看作是度中心性的一种扩展形式, Sebastian[87]等通过引入K-核分解研究了网络瓦解问题。

节点的K-核分解步骤如下：

Step1. 把度为1的节点及其所连接的边都去掉;

Step 2. 余下的网络中会重新产生一批度值为1的节点, 然后把上述度值为1的节点移除, 不断迭代, 直至当前网络中不存在度值为 1 的节点。此时, 所有被移除的节点就会形成一个层, 称作1-壳(记作Ks=1);

Step 3. 针对某个特定节点而言, 剥离一层后在余下的网络中节点的度值就称作该节点的剩余度值。根据Step 2的方法, 移除网络中所有剩余度值为2的节点，不断迭代直至移除网络中的所有节点。通过实验可以发现[40]，基于K-核分解的网络瓦解效果要明显低于度中心性与介数中心性策略及其衍生策略所对应的网络瓦解效果。

4.3 基于介数中心性的复杂网络瓦解方法

节点的介数中心性[88] (betweenness centrality, BC) 是度量节点重要性的全局静态特征指标, 可以刻画某个节点在整个网络中的流量负载和重要性。一般提到的介数中心性指的是最短路径介数中心性 (Shortest Path BC), 该指标的核心是计算网络中所有节点对的最短路径, 如果众多节点对的最短路径都经过某一节点, 那么这个节点就越重要。介数中心性度量的是节点对网络中按照最短路径扩散的信息流量的控制能力。节点vi的介数定义为

其中，gst为从节点vs到vt的所有最短路径的数目，为从节点vs到vt的gst条最短路径中经过vi的最短路径的数目。基于介数中心性的复杂网络瓦解算法其最大的弊端在于计算整个网络节点对之间的最短路径开销较大, 当网络的规模不断扩大, 计算节点的介数所需要的时间开销就会增加，通常会因为其算法复杂度太高而无法适用于处理大规模网络数据。因此, Sebastian等[87]在网络瓦解问题中引入近似的介数求解算法[89], 在确定节点移除顺序时只需计算近似介数即可。

4.4 基于接近中心性的复杂网络瓦解方法

接近中心性 (closeness centrality) [90]根据求解节点与网络中余下全部节点的距离的平均值来降低特殊值的干扰。如果某个节点与网络中余下节点的平均距离值越小, 则对应节点的接近中心性值就越大。接近中心性一般可以看作根据信息在网络中的平均传播时间来判断节点的重要性。通常来讲, 接近中心性值较大的节点对于网络中信息的传播拥有较好的观测视角。针对拥有n个节点的连通网络, 能够求解任意一个节点vi到网络中其他节点的平均最短距离:

di越小意味着节点vi更接近网络中的其他节点, 于是把di的倒数定义为节点vi的接近中心性, 即：

Qin等[91]在研究恐怖分子网络瓦解问题时, 提出利用接近中心性指标来进行恐怖分子网络瓦解。和基于度中心性和介数中心性的瓦解策略类似, 基于接近度的瓦解策略可以分为原始网络瓦解和重复计算瓦解。接近度中心性刻画的是节点在网络中所处的位置, 它是一个全局特征指标, 该瓦解策略的瓦解效果比基于局部信息的瓦解策略稍好。

5. 基于启发式算法的复杂网络瓦解方法

虽然基于中心性指标的复杂网络瓦解方法简单易实现, 但是很多情况下瓦解效果并不理想, 这是因为由单个重要节点(边)组成的集合未必就是最重要的节点(边)集, 这就好比最厉害的两个单打球员组合在一起未必就是最厉害的双打组合一样。为了提升网络瓦解效果, 研究人员提出了大量基于启发式算法的复杂网络瓦解方法，成为研究复杂网络瓦解问题的重要途径。

5.1 贪心算法

贪婪算法也叫做贪心算法, 该算法的核心思想是每一步均朝着在当前看来最好的选择方向迭代。Arulselvan等[47]提出了基于最大独立集 (Maximal independent set, MIS) 的贪心算法，并证明了上述贪心算法的计算复杂性为O(N2M), 因此仅适用于小规模网络。此外， Aringhieri等[92]改进了局域搜索的交换操作流程, 提出了可变邻域搜索法 (Variable neighborhood search, VNS), 将局域搜索的复杂性降为O(N2)。Wayne等[93]在贪婪算法中加入了多启动机制。此外，在影响力最大化的相关研究中[94-96], 也引入了多种改进的贪婪算法进行求解, 这些算法对于网络瓦解研究也有着较大的借鉴意义。

5.2 熟人免疫法

Cohen等[41]以阻断病毒传播为背景提出了熟人免疫 (Acquaintance immunization) 算法。熟人免疫是从网络中随机选出若干节点, 再从这些选出的节点随机选择一个它们的邻居节点进行免疫 (移除)。这种策略巧妙地解决了基于度中心性的目标瓦解策略 (Targeted immunization) 需要知道全局信息的问题。 Holme等[97]对熟人免疫法进行了改进，对于随机选出的节点, 不是随机在这些节点的邻居中寻找瓦解目标, 而是选取邻居中度最大的节点。Gallos等[43]也提出了类似的改进方法, 对于随机选出的节点, 在它们的邻居中选取度大于随机选取节点的度或者超过某个阈值的节点。

5.3 影响力扩散算法

影响力扩散算法 (collective influence, CI) [98]是用于度量节点的影响力, 通过划定一定的影响力范围, 利用该范围中每个节点的直接邻居和间接邻居来定量刻画节点的影响力数值, 进而基于节点影响力数值的降序进行节点移除。Mugisha等[99]提出采用CI算法进行网络瓦解, 通过选出网络中拥有最大传播影响力的节点逐一进行移除, 其对应的瓦解效果优于中心性算法。

5.4 置信传播分解算法

Zhou等[100]提出了一种称为BPD (Belief propagation-guided decimation) 的概率模型来度量当前网络中每个节点的移除概率, 并按照移除概率进行节点移除。 Mugisha[99]针对CI算法和BPD算法进行了瓦解效果的比较, 并发现在同等条件下, BPD算法所对应的瓦解效果要优于CI算法。Qin[101]等引入BPD算法作为移除节点顺序时的基本瓦解策略, 并采用节点爆炸性渗流算法 (Node explosive percolation, NEP) 对BPD算法选出的节点进行排序, 即NEP-BPD (NBA) 算法, 并在多种模型网络和实证网络中验证了该算法的有效性。

5.5 分支移除法

分支移除法的核心思想是令网络中节点的分支权重为Wi, 若节点度为1则其对应的Wi=1, 反之则为0。在得到第一层分支的基础上, 令所有节点的分支权重等于其邻居节点中所有度为1的分支权重之和, 并且在求和的基础上自加1 (若最终得到的分支权重值超过了该连通分量中所有节点数的一半则放弃自加1) , 最后移除当前网络中度为1的分支节点, 迭代直至无法继续移除节点。Marek等[102]提出通过评估每个节点的分支权重来进行逐个节点移除。在多种模型网络实验中, 分支移除法的瓦解效果显著优于ID、IB、RD和RB等中心性算法。

5.6 反向排序法

反向排序法首先通过一定的瓦解策略对网络进行瓦解并记录当前网络所移除的节点集Vhat, 然后从被瓦解后的网络出发, 将被移除节点逐个添加至被瓦解后的网络, 选取能够对应最小连通分量规模的被移除节点, 并将该节点放入增加节点集Vadd, 迭代直至将所有被移除节点添加到被瓦解后的网络, 最后将增加节点集中的所有节点序号反转即可得到对应最低R指标值的瓦解策略。Marek等[102]提出从被瓦解后的网络 (网络中仅包含孤立节点或度为1的节点) 出发, 通过向网络中尽可能少地增加节点和边来重建网络, 最后将所增加的节点序列反转则可以得到正向的瓦解序列。其算法复杂度为O(n2), 在模型网络的瓦解实验中, 反向排序法的瓦解效果优于分支移除法。

5.7 邻居信息概率算法

邻居信息概率算法是以邻居节点信息的概率模型为核心。Li等[103]通过设定保留机制和更新机制来进行更优解的搜索, 即在每一次的搜索中, 保留一定比例的节点使其状态不变, 进而在余下的节点中随机选出两个相异状态节点并交换其当前状态。通过实验发现, 邻居信息概率算法的瓦解效果显著优于度中心性策略和介数中心性策略。

5.8 子图度中心算法

子图度中心 (CoreHD) 算法的核心是得到网络的2-核, 2-核是初始网络的一个子图, 可以通过移除初始网络中所有的叶子节点来得到, 也就是移除网络中所有只包含一条连边的节点。在得到2-核的基础上, 按照度中心性策略对2-核进行节点移除。不难发现, CoreHD算法是基于K-核分解机制将网络中的一阶节点全部剥离, 然后将剩余网络中的节点按照节点度序列降序移除。Lenka等[104]提出了CoreHD算法来进行网络瓦解, 并将CoreHD算法与CI算法、BPD算法相比较, 发现CoreHD算法的瓦解效果虽稍逊于BPD算法, 但是优于CI算法的瓦解效果, 且计算时间远低于CI算法和BPD算法。

5.9 等量图分割法

在目标免疫过程中, 由于部分关键的中心节点 (hub) 通常隐藏导致难以被捕捉到, 或是疫苗无法提供百分百的完全保护, 造成目标免疫效果不佳。因此, 等量图分割算法通过改进传统的Nested Dissection (ND) 算法, 将原始网络划分成若干个拥有同等节点规模的子网络。比如, 当需要将网络划分为三块等量子网络时, 首先按照节点规模将网络划分为2:1的两块子网络, 然后再按照ND算法将较大子网络分为第一节点团、第二节点图和分割节点团, 通过不断优化分割节点团中的节点数目来将较大子网络划分为两份等量子块, 从而完成原始网络的等量图分割算法。显然, 相对于目标免疫算法, 等量图分割算法在本质上属于一种基于全局信息的高效免疫算法。Chen等[105]以疾病免疫为背景, 提出了一个基于图分割的网络瓦解方法, 在达到相同瓦解效果的情况下, 该方法所需要使用的疫苗数量相较于经典的中心性瓦解策略更少，但等量图分割法的瓦解效果要弱于影响力扩散算法。

5.10 最小和算法

最小和算法 (Min-sum algorithm) 的核心是将网络瓦解问题转换为消圈问题, 在移除节点集中增加一定数量的节点来消除被瓦解网络中可能存在的圈。在完成网络消圈后, 部分树型连通分量的规模可能还大于阈值C, 因此再对最小和算法得到的消圈网络引入贪婪树分解机制来完成最终的网络瓦解。Braunstein[32]等提出了最小和算法并应用到多种模型网络和实证网络中, 结果表明最小和算法的瓦解效果要显著优于CI等经典瓦解算法。

5.11 谱分割算法

谱分割算法的核心是利用Courant-Fischer定理对目标网络进行不断分割, 即将网络的分割问题最终转化成寻找网络的Laplacian矩阵的第二小特征值和特征向量问题。由Courant-Fischer定理可将网络的分割问题最终转化成寻找网络的Laplacian矩阵的第二小特征值, Ren[106]等提出一种谱分割近似算法, 主要分为以下三步：(1)在单位空间中构建随机向量v, 令随机向量v与Lw的最小特征向量垂直, 引入线性算子使得随机向量v不断迭代, 在大规模网络中近似收敛到Lw的次小特征值所对应的特征向量, 从而将目标网络分割为M和两部分; (2)构建子网络G*=(V*, E*), 其中边集E*表示连接M和的所有边, 点集V*表示E*关联的所有节点, 通过求解边集E*中对应最小移除成本的顶点覆盖集来确定当前的瓦解节点集; (3)判断当前最大连通片规模是否小于阈值, 满足则算法终止, 否则继续迭代步骤(1)-步骤(2)进行网络分割和求解顶点覆盖集。实验结果表明, 谱分割算法在大多数情况下优于BPD算法、等量图分割算法和min-sum算法, 但当评价指标为临界移除比时表现较差。

6. 基于进化算法的复杂网络瓦解方法

虽然基于启发式算法的网络瓦解方法比基于中心性指标的网络瓦解方法更加有效, 但是大多数情况下都不是最优的。因此, 近年来很多研究人员将进化算法 (元启发算法) 引入网络瓦解问题, 试图通过各种进化手段来帮助决策者从庞大的解空间中寻找接近最优的复杂网络瓦解策略。

6.1 基于禁忌搜索的复杂网络瓦解方法

禁忌搜索算法是解决组合优化问题的常用方法, 该算法的基本思想是先生成一个初始解，再从初始解的邻域内搜索一个更好的解，然后将其设置为当前最优解, 重复这一步骤直到算法满足终止条件为止。设置禁忌列表的目的是为了避免搜索过程陷入循环。邓烨等[107]基于禁忌搜索研究了面向无向网络的复杂网络最优瓦解策略; 禹扬等[108]研究了基于禁忌搜索的有向网络最优瓦解策略; 祁明泽等[109]利用禁忌搜索研究了多层网络的最优瓦解策略; 邓烨等[110]将禁忌搜索算法运用在空间网络瓦解领域, 禁忌搜索算法也因其高效的搜索效率和灵活的初始解构建方法，已经在多种瓦解场景和瓦解对象中得到了广泛应用。

6.2 基于人工蜂群算法的复杂网络瓦解方法

人工蜂群算法由三个要素组成：食物来源、雇佣蜂和非雇佣蜂。在搜索最优解的过程中, 使用随机生成的蜂群开始进行迭代搜索。在算法的迭代过程中, 不同种类的蜜蜂主要有两种常见的行为模式：雇佣蜜蜂寻找食物源以及抛弃某个食物源。Lozano等[111]在文献中将复杂网络最优瓦解策略问题转化为求解使余下网络中最大介数最小化的节点移除组合优化问题, 并将其称为Min-Max BC问题。通过实验发现，人工蜂群算法在部分参数组合下的模型网络中，其瓦解效果优于介数瓦解策略、稳态遗传算法和模拟退火算法等多种基于智能优化算法的复杂网络瓦解策略。

6.3 基于遗传算法的复杂网络瓦解方法

遗传算法 (Genetic algorithm, GA) 是基于自然界个体繁殖、变异和自然选择的进化过程, 由孟德尔的遗传学和达尔文的进化论演化而来的一种搜索算法。在遗传算法的实际运用过程中, 研究者通常会根据问题的特征对多个编码字符串进行编码, 并将这些编码字符串为生物界中的个体。经过基因复制、杂交、突变等遗传操作, 按照适者生存的自然选择规律, 通过不断迭代, 可以获得比父代更优越的个体, 使搜索朝着不断“进化”的方向发展。最后, 根据终止准则得到近似全局最优解。多年来, 由于其优秀的算法特性, 在计算机科学、应用数学、决策科学和应用经济学等领域中得到了广泛应用。

邓烨等[112]在文献中介绍了基于成本约束模型求解最优瓦解策略的遗传算法, 并分析了最优瓦解策略的节点选择趋势, 最后发现在成本约束条件下, 小度节点会在遗传算法求解出的最优瓦解策略中发挥更大作用。此外, Zhou等[113]采用模因算法 (Memetic algorithm, MA) 求解网络瓦解问题, MA算法是以模因 (Meme) 为文化交流的基本单元, 结合遗传算法和局部搜索策略的一种新型智能算法。该算法继承了遗传算法本身的优点, 具有较强的全局优化能力和较快的计算速度, 并通过局部调整和进化产生新个体，从而极大提高了算法的局部搜索能力。

6.4 模拟退火算法

模拟退火算法是对热力学中退火过程的模拟。在优化算法中引入Metropolis准则, 可以在多项式时间内给出近似最优解。其本质是一种基于蒙特卡洛方法的一种启发式随机搜索算法。Ventresca等[48]在网络瓦解研究领域引入了模拟退火算法, 为了探讨该算法的有效性, 进一步在ER随机网络、BA无标度网络和WS小世界网络中讨论了该算法的有效性, 取得比较好的实验结果。

6.5 种群增量学习算法

基于群体的增量学习算法 (population based incremental learning, PBIL) 将原优化问题的解空间S映射到基因解空间Sl。可行解sl ∈ Sl由l个基因位组成, 其中第i位的值可以是集合中的任意一个或多个。集合称为第i位的等位基因。如果第i位只能取中的一个值, 则称第i位为单等位基因位。对于有l个基因位、每个基因位都可以从中取值的优化问题, 其解可以用矩阵表示, 如果矩阵元素sij=1, 就表示第i个基因位的取值等于该基因位的第j个等位基因值。

在向量中, Pl=(P1, P2, …, Pl)表示解空间Sl中的l个基因位取对应于该基因位的等位基因值的概率, 其中表示第i个基因位取与该基因位对应的ni个等位基因值的概率。pij为第i个基因位取等位基因集合中第j个值的概率, 且j = 1, 2, …, ni 且。

Ventresca等[48]将种群增量学习算法和模拟退火算法运用于多种网络中, 并比较了两种算法应用于网络瓦解研究中的有效性, 实验结果表明种群增量学习算法优于模拟退火算法。

6.6 基于路径再链接的随机贪婪自适应搜索算法

贪婪随机自适应搜索算法 (greedy randomized adaptive search procedure, GRASP) 是一个具有多个起始点的迭代算法, 具体来说, 该算法的每次循环包括两个阶段：生成可行解和搜索局部最优解。在生成可行解的阶段, 首先初始化可行解x和候选解集C, 然后迭代构造可行解, 每次迭代生成可行解的一个元素。在每次迭代中, 根据贪婪函数对候选集合C中的每个元素进行评估, 作为进入限制候选列表的基础, 然后从列表中随机选取一个元素加到可行解中, 并更新候选解集合。在生成可行解阶段, GRASP算法可以通过连续迭代的方式在初始可行解的邻域内寻找最优解来进行替换操作, 从而解决初始可行解质量不高的问题, 在具体操作时, 如果局部最优解优x于已搜索到的最优解x*, 则用x更新x*。

为了进一步提高算法的有效性, 可以在第二个阶段, 即搜索局部最优解结束前考虑加入路径重新链接步骤, 设置大小确定的精英集合, 设x为当前的局部最优解, 设y为在这个集合中随机选择的一个解, 如果x比y的质量更高, 则增加一条从x到y的路径, 否则增加一条从y到x的路径。

Purevsuren等[114]将基于路径再链接的随机贪婪自适应搜索算法引入网络瓦解研究领域, 并在多种网络上进行了实验, 结果表明该算法的瓦解效果优于模拟退火算法和增量式学习算法等基于进化算法的网络瓦解方法。

7. 基于机器学习的复杂网络瓦解方法

在各类求解复杂网络瓦解问题的算法中, 无论是基于数学规划模型的精确求解算法还是各种启发式算法, 都存在非常明确的求解过程, 可以遵循一定的数学模型或启发式规则求解目标策略。而随着机器学习领域的快速发展, 为网络瓦解问题提供了一种全新的求解范式, 尤其是那些与具体知识、规则无关, 但是由于节点异质性而变得难以求解的网络类型, 该问题转换为如何通过强化学习训练智能体在已知答案的模拟网络上寻找最优瓦解策略。

强化学习是机器学习领域的三大范式之一, 它是一个不断与环境交互、获得反馈、更新策略、反复迭代直到学习出最优策略的过程。基于马尔可夫决策过程 (Markov decision process, MDP) 理论来描述这种环境交互作用如下: 该过程包含状态空间S、动作空间A、回报函数R、状态转移概率V和折扣因子γ的五元组构成。Q学习是强化学习的主要算法之一。它采用动作-价值函数Q(s,a)来评估策略的优劣, 表示在初始状态s0=s, 执行动作后a0=a, 获得累计奖励的期望值。

深度强化学习 (deep reinforcement learning, DRL) 指的是利用深度神经网络作为值函数逼近器的强化学习算法, 如前所述, DRL不是通过独立估计每个状态-动作对的Q值, 而是通过深度神经网络将状态向量直接映射到Q值。此外, 深度神经网络可以在不需要先验知识的情况下自动从高维原始数据中提取特征, 对于大规模的状态空间问题是有效的。

Fan等[115]创新地利用深度强化学习算法解决网络瓦解问题, 并在此基础上提出了FINDER算法, 具体来说, FINDER算法首先在小规模的BA网络中进行离线学习, 然后在可以利用暴力穷举法找到最优解的网络中进行离线学习, 之后在真实场景下的网络中使用之前训练好的智能体, 以根据当前网络持续决定要移除的节点, 最终给出节点的移除顺序, 并将该算法与其他算法进行了比较。

该过程具体分为两步：首先是编码操作, 具体来说, 基于图嵌入算法GraphSAGE提取网络中每个节点的特征, 而每个节点的特征向量会把该节点的特征传递到周围节点。然后是解码操作, 强化学习中的Q学习用于依据移除节点后的连通性变化与最优连通性变化间的差异调整生成策略 (下一步移除哪个节点) 的神经网络的参数。该神经网络是两层全连通结构, 并选择Relu函数作为该神经网络的激活函数, 在端对端的训练过程中, 待优化的损失函数为步后网络重构误差与Q学习的奖励函数之和。为了证明算法的有效性, 该算法在训练过程中采取了两种连通性评价指标 (连接边/最大连通片的大小), 并分别在加权节点和未加权节点的情况下对不同的网络进行训练和评测, 结果表明在上述四种组合下, FINDER 算法的性能都表现优异。

8. 结论与展望

复杂网络瓦解因为其广泛的应用背景正在成为多个学科领域共同关注的前沿热点, 其数学本质是一个组合优化问题。本文首先探讨了网络瓦解问题的内涵与应用背景, 建立了网络瓦解问题的一般数学模型, 在此基础上从基于解析求解、基于中心性指标、基于启发式算法、基于进化计算等几个方面系统总结了目前复杂网络瓦解问题的研究进展。从前文可以看出, 复杂网络瓦解问题研究方兴未艾, 虽然取得了大量研究成果, 但仍有很多需要进一步研究解决的问题。作为本文的结束语, 下面我们从目标网络维度、瓦解模型维度、瓦解算法维度对复杂网络瓦解问题研究的未来发展方向进行展望。

8.1 目标网络维度

8.1.1 从无向网络到有向网络

当前网络瓦解研究主要集中于无向网络, 很少考虑有向边对瓦解效果的影响。实际上, 现实世界中的目标网络很多都是有向网络。例如, 恐怖组织网络中的单向联络, 交通网络中的单行道等。当前已有学者[108]初步构建了有向网络的瓦解模型, 但是如何针对网络中有向边的分布情况快速有效找出有向网络中的关键节点(边)仍是一个值得关注的问题。

8.1.2 从无权网络到加权网络

当前网络瓦解研究主要集中于无权网络, 即假设网络中的节点或边都是同质的。实际上, 现实世界中的目标网络很多都是加权网络。例如, 恐怖组织网络中的不同节点危害程度不一样, 谣言传播网络节点之间可能有多重边等等。如何扩展现有网络瓦解方法使之适用于加权网络的瓦解是一个值得关注的问题。

8.1.3 从拓扑网络到空间网络

当前网络瓦解研究主要集中于拓扑网络, 很少考虑节点(边)的地理空间位置。实际上, 现实世界中的目标网络很多都是地理空间网络。我们在寻找网络瓦解方案时不再是简单寻找关键节点或关键边, 而是变成寻找关键区域。当前, 相关文献[110, 116]已初步尝试将优化算法和启发式规则运用于求解空间网络瓦解问题。但是, 如何综合考虑网络的拓扑结构和节点(边)的位置分布, 依然是未来空间网络瓦解问题的一个难点问题。

8.1.4 从单层网络到多重网络

当前网络瓦解研究主要集中于单层网络, 很少考虑多重网络之间耦合、依赖、级联等复杂关系。多重网络是当前复杂网络研究的一个前沿热点, 祁明泽等[109, 117]引入多种瓦解规则初步研究了多重网络的瓦解问题。但由于多重网络各层的结构关联性复杂, 使得多重网络的瓦解问题未来仍将是一个值得关注的挑战性问题。

8.1.5 从静态网络到时变网络

当前网络瓦解研究主要集中于静态网络, 即假设目标网络是静态的、确定的。实际上, 现实世界中的目标网络很多都是动态网络、时变网络。例如, 无人机集群的网络结构会随着无人机的相对位置变化而演化, 疾病传播网络中的感染只能发生在特定时间段等等。相关文献[118-120]基于层间相似性和排名聚合等手段探讨了时变网络的节点重要性, 并以此计算了移除重要节点对时变网络连通性的影响力, 而如何针对时变网络层间关系与各层网络结构特点来构建合理的网络瓦解模型将是未来复杂网络瓦解问题的一个难点。

8.2 瓦解模型维度

8.2.1 从结构到动力学

当前网络瓦解研究主要集中于破坏网络结构, 以降低结构连通性为目标。实际上, 除了破坏网络结构, 通过干扰节点(边)的动力学行为也可以达到瓦解网络的目的, 例如通过诱导信号干扰破坏敌方无人机集群的同步。这需要我们结合瓦解背景建立相关网络动力学模型来寻找最优的网络瓦解方案, 是一个值得关注的前沿方向。

8.2.2 从单目标到多目标

当前网络瓦解研究主要集中于单目标瓦解, 即目标函数只有一个。如何同时权衡考虑多个目标函数寻找有效的网络瓦解策略是一个挑战性问题。多目标进化算法将是求解这类问题的有效途径。

8.2.3 从简单约束到复杂约束

当前网络瓦解研究考虑的约束较少, 大多数研究中只考虑移除节点或边的总数量等简单约束条件。实际上, 我们在制定网络瓦解方案时要考虑时间、成本、信息或者其他特定的约束条件。如何在复杂约束条件下找到合理、有效的瓦解策略是一个亟待解决的问题。

8.2.4 从静态决策到动态博弈

当前网络瓦解研究主要还是考虑单方面的静态决策问题, 很少考虑攻击者和防守者之间的博弈。实际上, 因为网络瓦解的效果不仅和瓦解策略有关, 还和防御策略有关, 因此制定网络瓦解方案不仅要考虑目标网络还要考虑保护者的防御策略。在攻防博弈框架[121-123]下, 原来看起来非常重要的关键节点(边)因为考虑防御策略很可能不再被移除。在不同的网络结构中什么是攻击者和防御者的均衡策略？这是一个十分有趣而又非常复杂的问题。

8.3 瓦解算法维度

现实世界中网络系统的节点规模越发庞大, 节点数量少则几百, 多则上百万, 算法的计算复杂性将成为制约网络瓦解问题研究的一个瓶颈。研究提出高效率、低复杂度的瓦解算法是目前复杂网络瓦解问题研究的当务之急, 其中分布式算法、并行算法以及人工智能方法将是可能解决途径。

作者

编译

参考文献

[1]Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks [J]. Nature, 1998, 393(6684): 440-442.

[2]Barabási A L, Albert R. Emergence of scaling in random networks [J]. Science, 1999, 286(5439): 509-512.

[3]方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(上) [J]. 物理学进展, 2007, 27(3): 239-343.

Fang J Q, Wang X F, Zheng Z G, et al. New interdisciplinary science: Network science(I)[J]. Prog Phys, 2007, 27(3): 239-343.

[4]方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(下) [J]. 物理学进展, 2007, 27(4): 361-448.

Fang J Q, Wang X F, Zheng Z G, et al. New interdisciplinary science: Network science(II) [J]. Prog Phys, 2007, 27(4): 361-448.

[5]汪小帆, 李翔, 陈关荣. 网络科学导论 [M]. 北京: 高等教育出版社, 2012.

Wang X F, Li X, Chen G R. Network science: An introduction [M]. Beijing: Higher Education Press, 2012

[6]刘作仪. 复杂网络理论及相关管理复杂性研究的资助进展 [J]. 中国科学基金, 2008, 22(1): 13-17.

Liu Z Y. Research progress on complexity network and it's application in the area of management science[J]. Science Foundation in China, 2008, 22(1): 13-17.

[7]Barabási A-L. Network science [M]. Cambridge: Cambridge University Press, 2016.

[8]Shargel B, Sayama H, Epstein I R, et al. Optimization of robustness and connectivity in complex networks [J]. Phys Rev Lett, 2003, 90(6): 068701.

[9]谭跃进, 吕欣, 吴俊, 等. 复杂网络抗毁性研究若干问题的思考 [J]. 系统工程理论与实践, 2008, 28(S0): 116-120.

Tan Y J, Lv X, Wu J, et al. On the invulnerable research of complex networks [J]. System Eng Theor Prac, 2008, 28(S0): 116-120.

[10]吴俊, 段东立, 赵娟, 等. 网络系统可靠性研究现状与展望 [J]. 复杂系统与复杂性科学, 2011, 8(2): 77-86.

Wu J, Duan D L, Zhao J, et al. Status and prospects on network reliability [J]. Complex Syst Complexity Sci, 2011, 8(2): 77-86.

[11]Schneider C M, Moreira A A, Andrade J S, et al. Mitigation of malicious attacks on networks [J]. Proc Natl Acad Sci USA, 2011, 108(10): 3838-3841.

[12]Gouveia L, Leitner M. Design of survivable networks with vulnerability constraints [J]. Eur J Oper Res, 2016, 258(1): 89-103.

[13]Ouyang M. A mathematical framework to optimize resilience of interdependent critical infrastructure systems under spatially localized attacks [J]. Eur J Oper Res, 2017, 262(3): 1072-1084.

[14]Peng G-S, Wu J. Optimal network topology for structural robustness based on natural connectivity [J]. Physica A, 2016, 443(2): 212-220.

[15]Wu J, Tan S-Y, Liu Z, et al. Enhancing structural robustness of scale-free networks by information disturbance [J]. Sci Rep, 2017, 7(1): 1-13.

[16]付举磊, 孙多勇, 肖进, 等. 基于社会网络分析理论的恐怖组织网络研究综述 [J]. 系统工程理论与实践, 2013, 33(9): 2177-2186.

Fu J L, Sun D Y, Xiao J, et al. Review of the research on the terrorist networks based on social network analysis [J]. System Eng Theor Prac, 2013, 33(9): 2177-2186.

[17]Carley K M, Reminga J, Kamneva N. Destabilizing terrorist networks[C]. In: Proceedings of the 8th International Command and Control Research and Technology Symposium, National Defense War College, Washington DC, 2003.

[18]Chaurasia N, Tiwari A. Efficient algorithm for destabilization of terrorist networks [J]. Int J Inf Technol Comput Sci, 2013, 12: 21-30.

[19]曹进德, 王毅. 复杂网络疾病传播动力学研究进展 [J]. 大学数学, 2016, 32(4): 1-11.

Cao J D, Wang Y. Research developments of disease spread dynamics in complex networks [J]. College Math, 2016, 32(4): 1-11.

[20]孙皓宸, 徐铭达, 许小可. 基于真实人际接触数据的新冠肺炎校园传播与防控 [J]. 电子科技大学学报, 2020, 49(3): 399-407.

Sun H C, Xu M D, Xu X K. Infection and prevention of COVID-19 in schools based on real-life interpersonal contact data [J]. J Univ Electron Sci Technol Chin, 2020, 49(3): 399-407.

[21]Anggraini D, Madenda S, Wibowo E P, et al. Network disintegration in criminal network[C]. In: Proceeding of the 11th International Conference on Signal-Image Technology & Internet-Based Systems, IEEE, 2015: 192-199.

[22]Bright D, Greenhill C, Britz T, et al. Criminal network vulnerabilities and adaptations [J]. Global Crime, 2017, 18(4): 424-441.

[23]Malaviya A, Rainwater C, Sharkey T. Multi-period network interdiction problems with applications to city-level drug enforcement [J]. IIE Trans, 2012, 44(5): 368-380.

[24]Michalopoulos D P, Barnes J W, Morton D P. Prioritized interdiction of nuclear smuggling via tabu search [J]. Optim Lett, 2015, 9(8): 1477-1494.

[25]Quayle A P, Siddiqui A S, Jones S J M. Preferential network perturbation [J]. Physica A, 2006, 371: 823-840.

[26]Tripathy R M, Bagchi A, Mehta S. A study of rumor control strategies on social networks[C]. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010: 1817-1820.

[27]Kobayashi T, Hasui K. Efficient immunization strategies to prevent financial contagion [J]. Sci Rep, 2014, 4(1): 1-7.

[28]金伟新. 体系对抗复杂网络建模与仿真 [M]. 北京: 电子工业出版社, 2010.

Jin W X. SoS-Ops M&S based on the complex network [M]. Beijing: Publishing House of Electronics Industry, 2010.

[29]Tan S-Y, Wu J, Lu L, et al. Efficient network disintegration under incomplete information: the comic effect of link prediction [J]. Sci Rep, 2016, 6: 1-9.

[30]Wood R K. Deterministic network interdiction [J]. Math Comput Model, 1993, 17(2): 1-18.

[31]Phillips C A. The network inhibition problem[C]. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing. 1993: 776–785.

[32]Braunstein A, Dall'asta L, Semerjian G, et al. Network dismantling [J]. Proc Natl Acad Sci USA, 2016, 113(44): 12368-12373.

[33]Carley K M, Lee J-S, Krackhardt D. Destabilizing networks [J]. Connections, 2002, 24(3): 79-92.

[34]Lalou M, Tahraoui M A, Kheddouci H. The critical node detection problem in networks: A survey [J]. Comput Sci Rev, 2018, 28: 92-117.

[35]Faramondi L, Oliva G, Setola R, et al. Performance analysis of single and multi-objective approaches for the critical node detection problem[C]. In: Proceedings of the International Conference on Optimization and Decision Science. Springer, Cham, 2017: 315-324.

[36]Borgatti S P. Identifying sets of key players in a social network [J]. Comput Math Org Theor, 2006, 12(1): 21-34.

[37]Zwaan R V D, Berger A, Grigoriev A. How to cut a graph into many pieces[C]. In: Proceedings of the International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2011, 184-194.

[38]Shen S, Smith J C. Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs [J]. Networks, 2012, 60(2): 103-119.

[39]Albert R, Jeong H, Barabási A L. Error and attack tolerance of complex networks [J]. Nature, 2000, 406(6794): 378-382.

[40]Holme P, Kim B J, Yoon C N, et al. Attack vulnerability of complex networks [J]. Phys Rev E, 2002, 65(2): 056109.

[41]Cohen R, Havlin S, Ben-Avraham D. Efficient immunization strategies for computer networks and populations [J]. Phys Rev Lett, 2003, 91: 247901.

[42]Holme P. Efficient local strategies for vaccination and network attack [J]. Europhys Lett, 2004, 68(6): 908-914.

[43]Gallos L K, Liljeros F, Argyrakis P, et al. Improving immunization strategies [J]. Phys Rev E, 2007, 75(4).

[44]Pajouh F M, Boginski V, Pasiliao E L. Minimum vertex blocker clique problem [J]. Networks, 2014, 64(1): 48-64.

[45]Hewett R. Toward identification of key breakers in social cyber-physical networks[C]. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. IEEE, 2011: 2731-2736.

[46]Ortiz-Arroyo D, Hussain D M. An information theory approach to identify sets of key players[C]. In: Proceedings of the European Conference on Intelligence and Security Informatics. Springer, Berlin, Heidelberg, 2008: 15-26.

[47]Arulselvan A, Commander C W, Elefteriadou L, et al. Detecting critical nodes in sparse graphs [J]. Comput Oper Res, 2009, 36(7): 2193-2200.

[48]Ventresca M. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem [J]. Comput Oper Res, 2012, 39(11): 2763-2775.

[49]Ventresca M, Aleman D. A derandomized approximation algorithm for the critical node detection problem [J]. Comput Oper Res, 2014, 43(4): 261-270.

[50]Ball M O, Golden B L, V.Vohra R. Finding the most vital arcs in a network [J]. Oper Res Lett, 1989, 8(2): 73-76.

[51]Israeli E, Wood R K. Shortest-path network interdiction [J]. Networks, 2002, 40(2): 97-111.

[52]Nardelli E, Proietti G, Widmayer P. Finding the most vital node of a shortest path [J]. Theor Comput Sci, 2003, 296(1): 167-177.

[53]Bayrak H, Bailey M D. Shortest path network interdiction with asymmetric information [J]. Networks, 2008, 52(3): 133-140.

[54]Sefair J A, Smith J C. Dynamic shortest-path interdiction [J]. Networks, 2016, 68(4): 315-330.

[55]Song Y, Shen S. Risk-averse shortest path interdiction [J]. Informs J Comput, 2016, 28(3): 527-539.

[56]Sadeghi S, Seifi A, Azizi E. Trilevel shortest path network interdiction with partial fortification [J]. Comput Ind Eng, 2017, 106: 400-411.

[57]Holzmann T, Smith J C. Shortest path interdiction problem with arc improvement recourse: A multiobjective approach [J]. Nav Res Logist, 2019, 66(3): 230-252.

[58]Pay B S, Merrick J R W, Song Y. Stochastic network interdiction with incomplete preference [J]. Networks, 2019, 73(1): 3-22.

[59]Wollmer R. Removing arcs from a network [J]. Oper Res, 1964, 12(6): 934-940.

[60]Corley H W, Chang H. Finding the n most vital nodes in a flow network [J]. Manage Sci, 1974, 21(3): 362-364.

[61]Ratliff H D, Sicilia G T, Lubore S H. Finding the n most vital links in flow networks [J]. Manage Sci, 1975, 21(5): 531-539.

[62]Rocco S C M, Ramirez-Marquez J E. Deterministic network interdiction optimization via an evolutionary approach [J]. Reliab Eng Syst Saf, 2009, 94(2): 568-576.

[63]Altner D S, Ergun O, Uhan N A. The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability [J]. Oper Res Lett, 2010, 38(1): 33-38.

[64]Akgun I, Tansel B C, Wood R K. The multi-terminal maximum-flow network-interdiction problem [J]. Eur J Oper Res, 2011, 211(2): 241-251.

[65]Sullivan K M, Smith J C. Exact algorithms for solving a Euclidean maximum flow network interdiction problem [J]. Networks, 2014, 64(2): 109-124.

[66]Rad M A, Kakhki H T. Two extended formulations for cardinality maximum flow network interdiction problem [J]. Networks, 2017, 69(4): 367-377.

[67]Lei X, Shen S, Song Y. Stochastic maximum flow interdiction problems under heterogeneous risk preferences [J]. Comput Oper Res, 2018, 90: 97-109.

[68]Zenklusen R. Matching interdiction [J]. Discret Appl Math, 2010, 158(15): 1676-1690.

[69]Feng P, Schild A. Interdiction problems on planar graphs [J]. Discret Appl Math, 2013, 198: 215–231.

[70]Lin K C, Chern M S. The most vital edges in the minimum spanning tree problem [J]. Inf Process Lett, 1993, 45(1): 25-31.

[71]Bazgan C, Toubaline S, Vanderpooten D. Efficient determination of the k most vital edges for the minimum spanning tree problem [J]. Comput Oper Res, 2012, 39(11): 2888-2898.

[72]Bazgan C, Toubaline S, Vanderpooten D. Critical edges/nodes for the minimum spanning tree problem: complexity and approximation [J]. J Comb Optim, 2013, 26(1): 178-189.

[73]Deng Y, Wu J, Xiao Y, et al. Efficient disintegration strategies with cost constraint in complex networks: The crucial role of nodes near average degree [J]. Chaos, 2018, 28(6): 061101.

[74]Lozano M, Garcia-Martinez C, Rodriguez F J, et al. Optimizing network attacks by artificial bee colony [J]. Inf Sci, 2017, 377: 30-50.

[75]Veremyev A, Prokopyev O A, Pasiliao E L. An integer programming framework for critical elements detection in graphs [J]. J Comb Optim, 2014, 28(1): 233-273.

[76]Lewis J M, M M Y. The node-deletion problem for hereditary properties is NP-complete [J]. J Comput Syst Sci, 1980, 20(2): 219-230.

[77]Yannakakis M. Node-deletion problems on bipartite graphs [J]. SIAM J Comput, 1981, 10(2): 310-327.

[78]Di Summa M, Grosso A, Locatelli M. Branch and cut algorithms for detecting critical nodes in undirected graphs [J]. Comput Optim Appl, 2012, 53(3): 649-680.

[79]Veremyev A, Boginski V, Pasiliao E L. Exact identification of critical nodes in sparse networks via new compact formulations [J]. Optim Lett, 2014, 8(4): 1245-1259.

[80]Ventresca M, Aleman D. A derandomized approximation algorithm for the critical node detection problem [J]. Comput Oper Res, 2014, 43: 261-270.

[81]Shen Y, Nguyen N P, Xuan Y, et al. On the discovery of critical links and nodes for assessing network vulnerability [J]. IEEE/ACM Trans Netw, 2013, 21(3): 963-973.

[82]Shen S, Smith J C, Goli R. Exact interdiction models and algorithms for disconnecting networks via node deletions [J]. Discret Optim, 2012, 9(3): 172-188.

[83]Fan N, Pardalos P M. Robust optimization of graph partitioning and critical node detection in analyzing networks[C]. In: Proceedings of the International Conference on Combinatorial Optimization and Applications. Springer, Berlin, Heidelberg, 2010: 170-183.

[84]刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展 [J]. 物理学报, 2013, 62(17): 9-18.

Liu J G, Ren Z M, Guo Q, et al. Node importance ranking of complex networks [J]. Acta Phys Sin, 2013, 62(17): 9-18.

[85]任晓龙, 吕琳媛. 网络重要节点排序方法综述 [J]. 科学通报, 2014, 59(13): 1175-1197.

Ren X L, Lv L Y. Review of ranking nodes in complex networks [J]. Chin Sci Bull, 2014, 59(13): 1175-1197

[86]Carmi S, Havlin S, Kirkpatrick S, et al. A model of Internet topology using k-shell decomposition [J]. Proc Natl Acad Sci USA, 2007, 104(27): 11150-11154.

[87]Wandelt S, Sun X, Feng D, et al. A comparative analysis of approaches to network-dismantling [J]. Sci Rep, 2018, 8(1): 1-15.

[88]Freeman L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977: 35-41.

[89]Geisberger R, Sanders P, Schultes D. Better approximation of betweenness centrality[C]. In: Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics, 2008: 90-100.

[90]Freeman L C. Centrality in social networks conceptual clarification [J]. Soc Networks, 1978, 1(3): 215-239.

[91]Qin J L, Xu J, Hu D, et al. Analyzing terrorist networks: A case study of the global salafi jihad network[C]. In: Proceedings of the International Conference on Intelligence and Security Informatics. Springer, Berlin, Heidelberg, 2005: 287-304.

[92]Aringhieri R, Grosso A, Hosteins P, et al. VNS solutions for the critical node problem [J]. Electron Notes Discret Math, 2015, 47: 37-44.

[93]Pullan W. Heuristic identification of critical nodes in sparse real-world graphs [J]. J Heuristics, 2015, 21(5): 577-598.

[94]Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009: 199-208.

[95]Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]. Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010: 1029-1038.

[96]胡庆成, 尹龑燊, 马鹏斐, 等. 一种新的网络传播中最有影响力的节点发现方法[J]. 物理学报, 2013, 62(14): 9-19.

Hu Q C, Yin Y S, Ma P F, et al. A new approach to identify influential spreaders in complex networks [J]. Acta Phys Sin, 2013, 62(14): 9-19.

[97] Holme P. Efficient local strategies for vaccination and network attack [J]. Europhys Lett, 2004, 68(6): 908-914.

[98]Morone F, Makse H A. Influence maximization in complex networks through optimal percolation [J]. Nature, 2015, 524(7563): 65-68.

[99]Mugisha S, Zhou H. Identifying optimal targets of network attack by belief propagation [J]. Phys Rev E, 2016, 94(1): 012305.

[100]Zhou H. Spin glass approach to the feedback vertex set problem [J]. Eur Phys J B, 2013, 86(11): 1-9.

[101]Qin S-M, Ren X-L, Lü L-Y. Efficient network dismantling via node explosive percolation [J]. Commu Theor Phys, 2019, 71(6): 764.

[102]Simon M, Luptakova I D, Huraj L, et al. Combined heuristic attack strategy on complex networks [J]. Math Probl Eng, 2017, 2017: 1-9.

[103]Li Q, Liu S, Yang X. Neighborhood information-based probabilistic algorithm for network disintegration [J]. Expert Syst Appl, 2020, 139: 112853.

[104]Zdeborova L, Zhang P, Zhou H. Fast and simple decycling and dismantling of networks [J]. Sci Rep, 2016, 6(1): 1-6.

[105]Chen Y, Paul G, Havlin S, et al. Finding a better immunization strategy [J]. Phys Rev Lett, 2008, 101(5): 058701.

[106]Ren X, Gleinig N, Helbing D, et al. Generalized network dismantling [J]. Proc Natl Acad Sci USA, 2019, 116(14): 6554-6559.

[107]Deng Y, Wu J, Tan Y-J. Optimal attack strategy of complex networks based on tabu search [J]. Physica A, 2016, 442(1): 74-81.

[108]Yu Y, Deng Y, Tan S-Y, et al. Efficient disintegration strategy in directed networks based on tabu search [J]. Physica A, 2018, 507(10): 435-442.

[109]Qi M, Deng Y, Deng H, et al. Optimal disintegration strategy in multiplex networks [J]. Chaos, 2018, 28(12): 121104.

[110]Deng Y, Wu J, Qi M, et al. Optimal disintegration strategy in spatial networks with disintegration circle model [J]. Chaos, 2019, 29(6): 061102.

[111]Lozano M, Garciamartinez C, Rodriguez F J, et al. Optimizing network attacks by artificial bee colony [J]. Inf Sci, 2017, 377: 30-50.

[112]Deng Y, Wu J, Xiao Y, et al. Optimal disintegration strategy with heterogeneous costs in complex networks [J]. IEEE Trans Syst Man Cybern Syst, 2020, 50(8): 2905-2913.

[113]Zhou Y, Hao J, Glover F. Memetic search for identifying critical nodes in sparse graphs [J]. IEEE Trans Cybern, 2019, 49(10): 3699-3712.

[114]Purevsuren D, Cui G, Win N N H, et al. Heuristic algorithm for identifying critical nodes in graphs [J]. Adv Comput Sci Int J, 2016, 5(3): 1-4.

[115]Fan C, Zeng L, Sun Y, et al. Finding key players in complex networks through deep reinforcement learning [J]. Nature Mach Intell, 2020, 2: 317–324.

[116]Wang Z G, Deng Y, Wang Z, et al. Disintegrating spatial networks based on region centrality [J]. Chaos, 2021, 31(6): 061101.

[117]Qi M Z, Bai Y, Li X H, et al. Optimal disintegration strategy in multiplex networks under layer node-based attack [J]. Appl Sci-Basel, 2019, 9(19): 3968.

[118]郭强, 殷冉冉, 刘建国. 基于TOPSIS的时序网络节点重要性研究 [J]. 电子科技大学学报, 2019, 48(2): 296-300.

Gou Q, Yin R R, Liu J G. Node importance identification for temporal networks via the TOPSIS method [J]. J Univ Electron Sci Technol Chin, 2019, 48(2): 296-300.

[119]梁耀洲, 郭强, 殷冉冉, 等. 基于排名聚合的时序网络节点重要性研究 [J]. 电子科技大学学报, 2020, 49(4): 519-523.

Liang Y Z, Guo Q, Yin R R, et al. Node importance identification for temporal network based on ranking aggregation [J]. J Univ Electron Sci Technol Chin, 2020, 49(4): 519-523.

[120]杨剑楠, 刘建国, 郭强. 基于层间相似性的时序网络节点重要性研究 [J]. 物理学报, 2018, 67(4): 279-286.

Yang J N, Liu J G, Guo Q. Node importance idenfication for temporal network based on inter-layer similarity [J]. Acta Phys Sin, 2018, 67(4): 279-286.

[121]Peng R, Wu D, Sun M, et al. An attack-defense game on interdependent networks [J]. J Oper Res Soc, 2020: 1-11.

[122]Li Y-P, Tan S-Y, Deng Y, et al. Attacker-defender game from a network science perspective [J]. Chaos, 2018, 28(5): 051102.

[123]Li Y, Deng Y, Xiao Y, et al. Attack and defense strategies in complex networks based on game theory [J]. J Syst Sci Complex, 2019, 32(6): 1630-1640.

参考文献可上下滑动查看

复杂网络瓦解读书会

从复杂网络的构建到智能优化的演化，理解网络的鲁棒性与瓦解机制始终是一个深刻的挑战。更值得深思的是，网络的结构和算法设计如何决定了网络在遭遇局部攻击时的脆弱性，及其整体瓦解的速度与范围。动态演化过程中的节点和边的变化，也会影响系统如何在瓦解中保持部分功能，或如何适应新的结构。因此，网络瓦解研究聚焦于一个核心问题：在不同类型的网络结构（如高阶网络、空间网络、时序网络）中，局部的破坏如何引发整体功能的丧失？在面对网络的异质性和约束条件下，不同的优化算法如何有效识别并摧毁关键节点与连接，从而最大化网络的瓦解效应，进而影响系统的整体稳定性与韧性？