谱邻域攻击:一种具有邻居移除策略的谱网络瓦解框架

《Physica A: Statistical Mechanics and its Applications》:Spectral Neighborhood Attack: A spectral framework for network dismantling with neighbor removal strategy

【字体: 大 中 小 】 时间:2026年08月29日 来源:Physica A: Statistical Mechanics and its Applications 3.1

编辑推荐:

   摘要 网络瓦解是网络科学中一个研究充分的问题,在网络安全、谣言防控和基础设施保护等领域有着广泛的应用。传统的瓦解策略侧重于移除单个节点,但在某些现实场景中,可能需要同时移除目标节点及其直接邻居以破坏网络连接性。本文提出了一种基于谱论的框架——谱邻域攻击(Spectral Ne

  

摘要 网络瓦解是网络科学中一个研究充分的问题,在网络安全、谣言防控和基础设施保护等领域有着广泛的应用。传统的瓦解策略侧重于移除单个节点,但在某些现实场景中,可能需要同时移除目标节点及其直接邻居以破坏网络连接性。本文提出了一种基于谱论的框架——谱邻域攻击(Spectral Neighborhood Attack,SNA),该框架利用邻接矩阵的主特征向量对闭邻域进行排序,以确定优先移除的对象。通过一阶谱摄动分析推导出邻域层面的评分规则,并在每次移除操作后对残存的巨型连通分量重新计算评分。通过对十四个真实网络的广泛实验,并与涵盖中心性启发式方法、谱方法和基于机器学习方法的九种基线方法进行对比,结果表明SNA在报告的那些基准上能够提高瓦解效率,通常能够以较低的移除成本实现更快的网络碎片化。

引言 复杂网络[1]、[2]、[3]作为自然界和人类社会中无处不在的交互系统的抽象表示,已成为理解和控制复杂系统行为的核心范式。从微观世界的细胞代谢和蛋白质相互作用[4],到金融关系[5]、社会群体[6]、互联网[7]和电网[8]等宏观系统,这些系统的组成部分相互紧密连接形成庞大的网络,产生了远比各部分简单相加更为复杂的集体行为。在这些网络上分析的现象因研究而异,包括动态系统[9]、社区检测[10]、链路预测[11]、影响力最大化[12]和网络瓦解[13]。

网络瓦解[14]是减轻负面影响的一个重要问题。其目标是识别出最小的节点集合,移除这些节点后能将网络分割为许多不连通的子网络。网络的拓扑结构不仅决定了其功能,还影响其对扰动和内部故障的响应[15]。一个小的局部扰动,如单个节点或边的故障,可能被网络吸收而不产生严重后果;然而,在某些条件下,同样的扰动可以通过网络连接性被放大,引发连锁反应,可能导致大规模的体系崩溃。移除这些节点在控制各种网络动态过程中发挥着重要作用,例如消除谣言传播[16]、[17],防止恐怖活动[18],识别关键电网节点[8],分析关键金融网络节点以防止系统性金融危机[19],以及评估生态网络中物种灭绝的后果[20]、[21]。

自Albert、Jeong和Barabási的开创性工作[15]揭示了拓扑结构在网络脆弱性中的关键作用以来,网络瓦解[22]、[23]研究沿两条主要路线不断深入和拓展:首先,丰富网络模型以更准确地捕捉现实系统的复杂性;其次,开发更高效、更智能的算法来应对这些复杂模型带来的组合优化挑战。早期研究主要关注最简单的经典无权网络,但随着该领域的成熟,研究者逐渐意识到许多现实系统具有内在的异质性、空间约束和高阶交互模式,这些特征可以显著影响网络的瓦解过程和机制。忽略这些特征可能会限制理论研究的实际应用性,并导致误导性的结论。因此,将网络瓦解理论扩展到加权网络、空间网络[24]、[25]、[26]、多层网络[27]和超网络[28]、[29]已成为该领域发展的重要方向。这种扩展并不总是现有方法的简单推广,而可能需要在新情境下重新定义关键成分和解绑目标,通常伴随着计算难度的显著增加以及定制算法框架的需求。

算法的进展从朴素中心性启发式方法发展到复杂的消息传递和基于学习的方法,每种方法在理论最优性、可扩展性和对领域特定约束的适应性之间提供了不同的权衡。关于网络瓦解问题的算法,可以分为近似算法[30]、[31]、启发式算法[32]、[33]、[34]和机器学习算法[35]、[36]。近似算法提供理论性能保证,但计算成本可能较高。启发式算法通常更快、更具可扩展性,但缺乏形式化的保证。机器学习方法可以实现高性能,但需要大量训练数据,且可能缺乏可解释性。基于网络的拓扑结构,这些方法可分为:节点中心性、社区结构[37]、[38]、[39]和网络分解[31]、[40]。节点中心性方法包括度中心性[15]、紧密度中心性[41]、特征向量中心性[42]、Katz中心性[43]、介数中心性[44]以及集体影响力[45]、[46]。近期的中心性相关研究还纳入了高阶结构信息,如基于高阶网络的增强随机游走[47],以及基于谱熵或纠缠的度量来识别关键参与者[48]。

特别是,谱方法在利用网络最大特征值(λ_max)与其结构和动态鲁棒性之间的联系方面很有用[49]。这些方法通常通过评估单个节点移除对λ_max的影响来衡量节点的重要性。据我们所知,现有的谱方法并未明确纳入邻域删除的概念。虽然集体影响力等方法使用邻域数据进行评分,但它们仍然通过移除单个节点来操作。

现实中的瓦解可能需要禁用目标节点及其邻居,因为局部冗余和替代路径可能在单个节点故障后仍能维持连接性。这一邻域层面的攻击概念在之前的网络不稳定化[50]和空间瓦解圈[24]研究中已被隐性地探索过。开发考虑邻居的网络瓦解方法的动机源于对现有方法局限性的几个观察:(1) 现实攻击场景:在实际的网络安全和基础设施保护场景中,攻击者可能入侵整个网络段,包括目标节点及其支撑基础设施(即邻居)。这促使我们除个体节点移除外,还应考虑邻域层面的攻击策略。(2) 网络韧性与冗余:现代网络通常设计有冗余和替代路径,使得在某种情境下单个节点的移除不足以造成破坏。一个关键节点可能通过其邻居拥有多条备份连接,因此协调移除局部结构对于实现有意义的网络碎片化可能是相关的。(3) 局部结构中的协同效应:局部网络邻域可能具有不能通过孤立分析单个节点来捕捉的特性。一个节点及其邻居的集体移除有时会产生与顺序个体移除不同的结构变化。(4) 计算效率限制:现有的谱方法在迭代应用时,需要对大矩阵进行重复的特征分解[49]、[50]、[51],导致大规模网络的高计算成本。需要一种能在保持合理计算复杂度的同时获得有效瓦解结果的方法。

一个典型的应用是疫情控制。在接触追踪和隔离中,感染者可能与其密切接触者一起被隔离,因此干预措施自然对应于移除闭邻域而非单个节点。受此场景启发,我们在第3.3节中进一步纳入了易感-感染-康复(SIR)控制模拟,以检验不同的邻域移除策略是否会导致残存网络出现不同的爆发规模。

本文研究了邻域移除协议下的网络瓦解问题,其中选择目标节点时会同时移除该节点及其所有邻居。我们提出了谱邻域攻击(SNA),一个为此场景设计的谱启发式框架。通过对十四个真实网络的广泛实验,并与九种基线方法进行对比,结果表明SNA在报告的那些基准上表现优异,在邻域移除模型下通常能以较低的移除成本实现更快的网络碎片化。SNA的关键组成部分如下:1. 基于谱摄动的邻域评分:我们使用概率松弛作为分析工具,推导出闭邻域移除的一阶谱增益,从而得到基于主特征向量的简单评分。2. 邻域策略:SNA不是移除单个节点,而是同时移除整个邻域(一个节点及其所有邻居),使该方法能够建模单个节点移除无法捕捉的局部干预效应。3. 残存图重新优化:每次邻域移除后,SNA在残存图上重新计算巨型连通分量(GCC)、主特征向量和所有候选邻域评分,避免对已移除节点的冗余考虑。

图1展示了SNA与高介数方法之间的一个关键流程差异。在图1的两个面板中,邻域都被迭代地选择和移除;每次移除后,图被更新并重新计算巨型连通分量(GCC)的大小。两种流程都收敛到相同的最终GCC值0.04,但所需的总移除成本不同:HB = 32,SNA = 14。该例子说明SNA通过结合谱评分、成本归一化和动态重计算,在此例中以较低的成本实现了相当的碎片化效果,而HB方法侧重于高介数的桥接节点。

本文的结构如下:详细方法在第2节中描述。实验结果和讨论在第3节中呈现。第4节对全文进行总结。

问题建模 设G=(V,E)为一个具有n=|V|个节点的无向无权图。对每个节点v,定义其开邻域N(v)={u∈V | (v,u)∈E}及其闭邻域N[v]={v}∪N(v)。邻域攻击选择目标节点集S?V,并移除?_{v∈S} N[v]中的所有节点。优化问题为:在满足约束max_{C∈components(G??_{v∈S} N[v])} |C| ≤ c的条件下,最小化|?_{v∈S} N[v]|。该建模采用单位移除成本模型:干预的成本是被禁用的不同节点数,包括所选目标节点及其邻居。

数据集 我们在十四个真实网络上评估SNA算法的性能,涵盖广泛的领域:所有数据集均按照第2.1节中的无向无权表述进行一致处理:有向或加权边列表被转换为无向简单图,自环被移除,当网络不连通时,实验在其巨型连通分量上进行。这些数据集主要用作结构基准而非作为…

结论 本文研究了邻域移除协议下的网络瓦解问题,并提出了谱邻域攻击(SNA),一个为此场景设计的谱启发式框架。SNA利用谱摄动理论推导出邻域层面的评分规则,并在每次移除操作后对残存的巨型连通分量重新计算评分。在十四个真实网络上的实验结果表明,SNA与比较的基线方法相比表现良好。

CRediT作者贡献声明 Xuan Li:撰写—原稿、可视化、验证、软件、方法论。Xingqin Qi:撰写—审阅与编辑、指导、资金获取、概念化。Zhulou Cao:撰写—审阅与编辑、指导、资源、项目管理、调查研究、数据整理。

生成式AI和AI辅助技术在稿件准备过程中的声明 在本作品的准备过程中,作者使用了ChatGPT(OpenAI)来辅助语言编辑、可读性改进和稿件格式化。核心研究思想、算法设计、实验、数据分析、解释和结论均由作者完成。在使用该工具后,作者根据需要审阅和编辑了内容,并对出版物的内容承担全部责任。

利益冲突声明 作者声明不存在已知的竞争财务利益或个人关系,这些关系可能影响本文所报告的工作。

致谢 本工作得到了国家自然科学基金(CN,编号:12471330)和山东省自然科学基金(编号:ZR2025MS71)的资助。

Xuan Li | Xingqin Qi | Zhulou Cao 山东大学,数学与统计学院,威海,264209,中国
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号