基于微观马尔可夫链方法识别高阶网络中的关键传播节点

《Physica A: Statistical Mechanics and its Applications》：Identifying influential spreaders in higher-order network based on microscopic Markovian chain approach

　　摘要：识别网络中最具影响力的传播者是充分利用现有资源、最大化或抑制传播过程影响范围的关键步骤。现有研究大多基于具有成对相互作用的复杂网络，而在许多现实世界系统中，节点还会以群体形式相互作用，这类系统可通过单纯复形或超图等高阶网络来表示。本文采用微观马尔可夫链方法，研究如何识别单纯复形中的重要传播者。我们提出了一种名为“高阶传播影响力”的新指标，用于评估高阶网络中节点在传播过程中的影响力。该指标性能优异，因为它考虑了高阶网络中沿1-单形（边）的感染与被感染的对称性，以及沿2-单形（三角形）的不对称性。在合成单纯复形以及基于现实数据构建的六个单纯复形上的仿真结果表明，与现有的高阶网络中心度指标以及低阶复杂网络中最先进的中心度指标相比，该指标能更准确地预测高阶网络中的重要传播者。

引言：许多自然和社会现象都可以视为复杂网络中的动态过程。例如，人类接触网络中的疫情传播、电网中的级联故障、计算机邮件系统中的病毒扩散，以及金融系统中的危机蔓延。由于网络具有异质的局部和全局结构，节点的传播影响力存在显著差异，有些节点的影响力远高于其他节点，这些节点被视为重要传播者或超级传播者。研究表明，超级传播是基于网络的传播过程中的常见现象[1][2]。例如，在推特和微博等社交网络中，某些人能够更快地传播信息，覆盖更广泛的用户群体[3]；在疫情期间，超级传播者会感染人群中不成比例的大量个体[4]；在生态系统中，某些物种对于维持生态网络的稳定性和完整性起着关键作用[5]。节点中心度是最简单的结构属性，用于衡量节点在网络中的结构重要性，如度中心度、特征向量中心度、介数中心度、k核指数、紧密度中心度等。中心度较高的节点被认为在网络中具有更大的传播影响力。基于这些基本中心度，人们提出了许多指标来识别复杂网络中的重要传播者[6][7][8][9][10]，这些方法在不同应用场景下的识别精度都有所提升。此外，最短路径、分形维数、结构循环与结构洞、节点间的有效距离等其他拓扑特征也被认为能够预测节点的影响力[11][12][13][14][15]。除了拓扑特征外，消息传递法、马尔可夫链、引力模型以及机器学习模型也被用于评估节点的传播影响力并识别重要传播者[16][17][18][19]。例如，图卷积网络被用来识别重要传播者，该模型利用节点的局部特征、中心度以及邻接矩阵来学习它们与标签之间的关系[20][21]。由于网络结构各异，且重要传播者因问题不同而有所差异，因此不存在适用于所有问题的通用指标或算法。尽管已有诸多进展，但现有研究仍局限于具有二元相互作用的网络。然而，大量数据表明，实际系统中的节点之间存在更高阶的依赖关系，即节点之间存在群体互动、多类型互动以及时间依赖性互动，这些都可以用高阶网络来建模[22]。例如，由不同数量科学家组成的研究团队、参与生化反应的两种以上物种、社会经济系统中的多个主体（买家、卖家、经纪人）等都属于此类情况。若将数据中的复杂互动简化为成对互动，将会大大降低对真实数据背后机制的理解精度[24]。高阶网络能够更准确地捕捉具有多元相互作用的网络特性。单纯复形和超图是两类能够体现群体互动或任意规模节点集合间相互作用的高阶网络模型[25]。研究表明，在这类高阶网络中，高阶结构会导致不连续的相变、加速动态过程、降低疫情爆发阈值，以及网络中多种竞争性疫情的共存[26][27][28][29][30][31]。高阶网络中的中心度指标被提出用于量化节点及高阶群体的重要性，这类指标通常是复杂网络中心度的扩展，如高阶度中心度、高阶特征向量中心度、高阶PageRank以及向量中心度[32][33][34]。例如，有一类基于特征向量中心度的指标可用于识别超图中的重要节点和超边，其核心思想是：节点的重要性取决于其所属于的超边的重要性，而超边的重要性则取决于其所包含节点的重要性[35]。针对超图，还提出了一种超核分解方法，该方法根据节点的超度以及超边的基数将超图分解为不同的层次，这是k核分解的推广形式[36]。研究表明，具有较高超核性的节点具有更强的传播能力，疫情传播会集中在核心超核区域。此外，还提出了一种基于多阶图的随机游走模型，该模型结合了高阶二分图和成对图，可用于识别信息传播和网络拆解过程中的关键节点[37]。在高阶网络中，还有更多网络特征被用来识别重要节点，如网络的方向性[38]、社区结构[39]以及最短路径[40]。现有方法主要关注中心节点的拓扑特征，但研究表明，节点的传播影响力既受网络拓扑结构的影响，也受传播过程特性的影响。与仅基于网络拓扑的方法相比，综合考虑传播过程特征的方法能够更准确地识别网络传播中的重要传播者[41][42]。本文研究的是在通过不同阶数群体互动实现传染的单纯复形中识别重要传播者。为简化问题，我们研究的是D=2阶的单纯复形，即仅包含最多二阶单形的单纯复形。在关于高阶网络中疫情传播的研究中，无论是建模工作还是实际疫情分析，大多都针对二阶单纯复形展开[26][28][31][43]。基于微观马尔可夫链方法，我们提出了单纯复形中节点的高阶传播影响力（HSI）指标。该指标整合了高阶网络结构与疫情传播过程的信息，同时还能体现节点沿边感染与被感染的对称性，以及沿2-单形的不对称性。在两个合成单纯复形以及六个基于现实数据的单纯复形上的实验结果表明，HSI指标比高阶网络的中心度指标以及复杂网络中最先进的中心度指标能更准确地预测节点的传播影响力。

本文的主要贡献如下：
• 提出了一种HSI指标，用于识别单纯复形中的重要传播者。
• 通过考虑SIR传播过程中感染的不对称性，HSI指标能够同时反映节点沿1-单形和2-单形的传播影响力。
• 大量仿真结果表明，与现有基准方法相比，HSI指标在识别合成及现实世界高阶网络中的重要传播者方面表现更为出色。

章节节选：
单纯复形中的SIR传播模型：单纯复形K是由不同阶数的单形构成的集合[25]。一个k阶单形σ=[v0,v1,…,vk]由k+1个节点组成，代表了这k+1个节点之间的群体互动。在单纯复形K中的每一个k阶单形，其所有的子面也都属于该单纯复形K。例如，如果2阶单形s={v0,v1,v2}?K，那么{v0}、{v1}、{v2}、{v0,v1}、{v0,v2}和{v1,v2}也都属于K。为简化问题，本文研究的单纯复形仅包含最多二阶的单形。

d=2阶单纯复形中的高阶传播影响力：在本节中，我们提出了高阶传播影响力（HSI）指标，用于评估单纯复形中节点的传播影响力。该指标是基于微观马尔可夫链方程计算得出的，这些方程描述了高阶网络中SIR传播过程中节点处于不同状态的概率随时间的变化规律。设piX(t)表示时间t时节点i处于状态X的概率，其中X∈{S,I,R,IΓ,IΔ,RΓ,RΔ}。这里IΓ和IΔ分别代表节点被感染的状态。

研究方法：我们进行了大量数值仿真，以验证HSI指标在预测高阶网络中节点传播影响力方面的性能，并将其与五种最先进的中心度指标进行比较。首先，我们介绍了两种类型的合成高阶网络的构建方法[44]，即均匀网络和异质网络，同时还介绍了用于仿真的六个现实世界高阶网络。随后，我们列出了用于比较的基准中心度指标。

研究结果：我们在合成及现实世界的高阶网络上进行了大量实验，评估了高阶传播影响力（HSI）指标在排序节点影响力方面的性能。为了获得作为感染源的单个节点的实际传播影响力，我们采用了蒙特卡洛仿真方法。初始时，节点i被设定为处于I状态，而所有其他节点均处于S状态。随后启动SIR传播过程，直到不再有新的感染发生为止。计算感染比例……

结论与讨论：识别最具影响力的传播者是控制网络中传播过程的关键步骤。本文研究了高阶网络中重要传播者的识别方法。通过采用微观马尔可夫链方法，我们能够分别计算节点通过边以及高阶互动被感染的概率。通过考虑沿边的感染与被感染的对称性，以及沿2-单形的不对称性，我们……

CRediT作者贡献声明：
江莉：初稿撰写、可视化、验证、软件开发、方法设计、研究实施、正式分析、审稿与编辑。
刘颖：审稿与编辑、初稿撰写、指导监督、资金获取、正式分析、概念构思、方法设计。
王伟：正式分析、资金获取、方法设计、指导监督。
高福娟：正式分析、方法设计、初稿撰写。
周涛：正式分析、方法设计、指导监督、写作。

未引用参考文献：[51]、[52]

利益冲突声明：作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。

致谢：本研究得到了四川省科技计划项目（编号2020YJ0125）以及四川省特殊教育语言智能哲学社会科学重点实验室开放课题（编号YYZN-2025-13）的支持。

江莉 | 刘颖 | 王伟 | 高福娟 | 周涛
中国四川成都610500，西南石油大学计算机与软件学院