基于鲁棒性识别超网络中的重要节点和超边

《Expert Systems with Applications》：Identification of important nodes and hyperedges on hypernetworks based on robustness

本文基于谱图论与扰动理论，分析超网络代数连通性变化，提出节点与超边重要性度量方法（EMN、EIMN、EME、LME、LIME），并验证其在新旧网络中的优越性。

　　

Jin-Xuan Yang|Haiyan Wang|Ji Cai Zhang|Ying Tan|Zhijuan Cao

云南财经大学统计与数学学院，中国昆明市龙泉路237号，650221

摘要

超网络或超图已成为描述复杂网络中高阶交互作用的重要手段。超网络的鲁棒性体现在其在部分节点和超边丢失后仍能保持连通性的能力。超图的鲁棒性被广泛用于评估复杂系统抵抗攻击和损害的能力。在超图网络中，找到关键节点和超边并保护它们免受攻击可以更好地维持系统的稳定性。同时，识别网络中的关键节点还可以用于控制谣言、疾病和传播。标准网络与超网络在描述鲁棒性和节点重要性方面存在显著差异，因为超图的超边具有非零权重。在本文中，我们基于谱图理论和扰动理论，对超图的代数连通性（超图的拉普拉斯矩阵的第二小特征值）的变化进行了详细理论分析，并提出了一些方法来更有效地找到均匀超图上的关键节点或超边。这些节点和超边在决定系统鲁棒性方面起着重要作用。通过在实际和合成网络上使用经典评估方法，我们证明了我们方法的优越性。

引言

高阶交互打破了仅考虑二元交互的局限性。研究高阶复杂网络有助于更好地理解高阶复杂系统的结构和功能，特别是单个组件故障对系统整体性能的影响。利用高阶网络的拓扑结构和几何结构来研究高阶交互动态引起了研究人员的极大兴趣（Benson, Gleich, & Leskovec (2016); Bianconi & Dorogovtsev (2024); Boccaletti et al. (2023); Liu, Chu, & Meng (2023); Lu & Peng (2015); Majhi, Perc, & Ghosh (2022); Mulas, Kuehn, B?hle, & Jost (2022); Pan, Zhou, Zhou, Boccaletti, & Bonamassa (2024); Torresy, Blevinsz, Bassettz, & Eliassi-Rady (2021)）。超图可能更有效地描述复杂系统的高阶拓扑结构（Banerjee (2021); Bretto (2013）。在超图中，一个节点表示一个结构单元，而一个超边代表多个结构单元之间的协作关系。

图或超图的鲁棒性表征了复杂系统在节点和边丢失（无论是由于有针对性的移除还是级联故障）时抵抗攻击和损害的能力（Albert, Jeong, & Barab’asi (2000); Callaway, Newman, Strogatz, & Watts (2000); Chen, Surana, Bloch, & Rajapakse (2021); Chen (2016); Peng et al. (2022a); Schneidera, Moreirab, Andrade, Havlinc, & Herrmann (2011)）。近年来，为了找到普通图中的关键节点或边，提出了多种中心性度量方法，如接近中心性（Freeman (1979)、度中心性（Bonacich (1972)、介数中心性（Brandes (2001)）、特征向量中心性（Bonacich (2007) 和行走中心性（Lee, Park, Kahng, & Lee (2013); Mieghem, Wang, Ge, Tang, & Kuipers (2010); Restrepo, Ott, & Hunt (2007) 等）。最近，Guo 等人设计了一种改进的局部和全局中心性算法来识别关键节点（Guo, Ye, & Liu (2026）；Zhang 等人提出了一种基于线图变换和深度强化学习的关键节点检测方法（Zhang, Feng, Ge, Wang, & Yang (2026）；Guo 等人提出了通过线图变换和深度强化学习在复杂网络中找到关键边的方法（Guo et al. (2025)）。

同时，许多中心性度量方法也被扩展到超图和多层网络。Dubey 等人基于射线簇超图理论讨论了社交网络中节点影响的新度量方法（Dubey & Samanta (2025）；Lv 等人基于多 PageRank 中心性定义了多层网络中关键节点的改进引力中心性（Lv et al. (2024）；Peng 等人提出了在节点受到高或低超度攻击的背景下分析随机超图网络鲁棒性的理论框架（Peng et al. (2022a）；Wang 等人提出了基于超边基数大小探索超图网络对抗有针对性攻击鲁棒性的数学框架（Peng et al. (2022b）；Liu 等人使用渗透方法分析了超图的鲁棒性（Duan, Huang, Deng, & Ni (2024); Liu et al. (2023）；Pan 等人开发了用于研究相互依赖超图鲁棒性的二分网络框架（Pan et al. (2024）；Zhang 等人引入了一种协作效率度量来衡量混合超图的鲁棒性（Zhang, Wang, Xiang, & Wang (2024））。然而，基于鲁棒性的超图中心性度量研究尚未得到充分解决。

代数连通性（图的拉普拉斯矩阵的第二小特征值）（Fiedler (1973）在确定图的连通性、多智能体系统的共识以及随机游走的收敛速度方面起着重要作用（Alon (1986); Boyd, Diaconis, & Xiao (2004); Olfati-Saber (2005）。超图网络拓扑结构的变化会导致代数连通性的变化，这成为衡量网络鲁棒性的重要手段。也就是说，当许多关键节点被移除或许多超边被删除时，代数连通性的变化可以成为衡量节点和超边重要性的重要指标。在超图网络中，找到关键节点和超边并保护它们免受攻击可以更好地维持复杂系统的稳定性。值得强调的是，基于代数连通性找到超图网络中关键节点和超边的方法在以往的研究中很少被提及。大多数中心性指标缺乏足够的理论分析，导致超图的性能不尽如人意。标准网络与超网络在找到关键节点/超边方面存在显著差异，因为超图的超边具有非零权重。

在本文中，我们使用谱图理论和扰动理论对超图的代数连通性变化进行了详细理论分析。基于 Fiedler 向量，我们从鲁棒性的角度将几种用于普通网络的关键节点或超边度量方法扩展到均匀超图。我们的主要贡献如下：

•

基于代数连通性的特征向量变化，提出了两种新的度量方法（EMN 和 EIMN）来找到超图的关键节点。

•

分别使用原始超图和其线图的代数连通性特征向量，提出了三种度量方法（EME、LME 和 LIME）来找到超图的关键超边。

通过在实际和合成网络上使用经典的鲁棒性评估方法，并与传统的度中心性、邻居中心性和行走中心性度量方法进行比较，我们证明了我们方法的优越性。

本文的其余部分安排如下。第 2 节是预备知识。第 3 节基于对代数连通性降低的详细理论分析，我们提出了一些度量方法来确定均匀超图上节点/超边的重要性。第 4 节描述了许多先前的中心性度量方法，并通过实验评估了这些方法在实际和合成网络上的性能。最后，我们得出了结论。

小节片段

预备知识

在本节中，我们介绍了许多关于 r-均匀超图的理论概念。超图（Banerjee (2021); Bretto (2013）

$H=(V,E)$ 是一组节点$V=\{v_1,v_2,..,v_n\}$ 和超边$E=\{e_1,e_2,..,e_m\}$。每个超边 e 属于 E。每个超边 e 表示 V 的一个子集。 和 分别表示节点和超边的数量。一个 r-均匀超图是指每个超边恰好包含 r 个节点的超图，即。当 $r=2$ 时，超图就变成了一个普通图。

寻找关键节点和超边的度量方法

在本节中，我们从网络鲁棒性的角度出发，提出了几种基于谱图理论和扰动理论在 r-均匀超图上寻找关键节点/超边的方法。实验结果表明，我们的方法在均匀超图上能够更有效地找到关键节点和超边，尤其是在小世界网络中。

实验

在本节中，我们比较了不同方法在 r-均匀超图上寻找关键节点和超边的性能。超图中每个节点的交互是等可能的，即每个超边被视为一个完整的子图以便于比较。不同的超边可以通过超边的交集建立连接。首先，描述了许多先前的度量方法进行比较。然后介绍了评估标准（Comparison criteria）。

讨论与结论

超图可以更好地描述高阶复杂系统的交互行为。在超图网络中，找到关键节点和超边并保护它们免受攻击可以更好地维持复杂系统的稳定性。在本文中，我们使用超图的谱理论来研究高阶复杂系统的鲁棒性。由于均匀超图的拉普拉斯矩阵是一个大型加权矩阵，特别是在多交互情况下，传统的度量方法在寻找关键节点和超边时并不适用。

作者贡献

所有作者对本工作做出了同等贡献。所有作者都阅读并批准了最终稿件。

利益冲突

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

CRediT 作者贡献声明

Jin-Xuan Yang: 方法论、撰写——初稿。Haiyan Wang: 概念化、形式分析、调查。Ji Cai Zhang: 撰写——审阅与编辑。Ying Tan: 资源、监督。Zhijuan Cao: 数据管理。

利益冲突声明

作者声明他们没有已知的利益冲突或个人关系可能影响本文报告的工作。