一种基于社区感知的创新随机行走方法，用于识别复杂网络中的关键节点

《RELIABILITY ENGINEERING & SYSTEM SAFETY》：A novel community-aware random walk for identifying critical nodes in complex networks

　　钱莉 | 刘家鑫 | 费荣 | 黑新红
西安工业大学计算机科学与工程学院，中国陕西省西安市金华南路5号，710048

**摘要**
识别关键节点对于流行病防控、基础设施保护和生物医学至关重要，这是网络科学领域的核心问题。然而，几乎所有识别方法都基于成对拓扑结构，忽略了没有直接连接的节点之间的信息交互或功能耦合——这可能会降低关键节点识别的准确性。为了解决这个问题，本文提出了一种社区感知随机游走（CARW）方法。通过抽象虚拟节点来构建一个社区感知的两层网络，目的是提供一个能够捕捉社区交互特征和信息传输机制的网络表示框架。在此基础上，设计了一种社区感知随机游走策略：通过定义外出游走和进入游走，并将网络的社区影响力与节点之间的成对交互相结合，从而捕捉节点之间的更广泛信息交换，并生成一个社区感知的转移矩阵。最后，通过整合反映全局游走信息的PageRank来确定节点的重要性排名。在12个多样化的标准数据集上与十种先进的节点识别方法进行比较表明，所提出的方法具有显著优势。它在包括一致性验证、信息传播最大化、网络拆解问题和网络鲁棒性在内的多种网络任务中都取得了改进。

**引言**
在复杂网络中识别关键节点对于理解网络的拓扑结构、传播动态、鲁棒性和控制机制至关重要[1]，是复杂网络分析中的关键问题。关键节点通常是信息传播的核心，识别它们可以应用于精准营销、舆论引导等场景。在谣言或病毒传播的背景下，识别和控制关键节点有助于迅速打破传播链[2]、[3]。在关键基础设施方面，识别关键节点可以提高电力网[4]、燃料传输网络和交通系统[5]等系统的监控和维护能力，从而实现最佳资源分配和调度。在生物医学领域，识别关键节点有助于检测和控制基因调控网络和大脑网络[6]，以及制定有效的干预策略。此外，在生态系统种群互动网络和社会学中的人际关系网络中，识别关键节点对于揭示核心机制也至关重要。因此，关键节点识别是复杂网络研究的一个重点。

近年来，越来越多的研究人员关注复杂网络中节点的重要性。使用了诸如关键节点、重要节点、影响力节点等不同术语，从而开发了一系列评估节点重要性的方法。这些方法大致可以分为四类：
1. **基于拓扑的中心性方法**：度中心性[7]、[8]、介数中心性[9]、[10]、K-核中心性[10]、[12]、特征向量中心性[10]、[13]、[14]、PageRank[15]、[16]等。这些方法仅依赖于网络的静态拓扑关系，没有考虑其动态演化过程；它们的特点是计算简单且易于解释，是最基本的关键节点识别方法[7]、[10]、[14]。
2. **基于传播和网络动态的方法**：包括网络传播模拟[2]、[17]、扩散模型[18]、[19]和动态敏感性分析[11]、[14]。这类方法计算成本较高，需要多次模拟动态过程，其结果取决于传播参数（例如，感染率和恢复率）的设置。
3. **基于学习的方法**：主要涵盖图神经网络（GNNs）[20]、[21]、图卷积网络（GCNs）[22]、[23]、图嵌入[21]、[24]、对比学习[22]、[24]和强化学习[20]、[23]。这些方法可以模拟复杂的特征关系，但需要大量高质量的标记数据，并且解释性相对较弱。
4. **基于优化和控制的方法**：包括影响力最大化模型[25]、[26]、[27]、人工蜂群算法[25]、[28]、遗传算法[26]、[29]和进化算法[26]、[29]等相关方法。这些方法将问题建模为求解最小关键节点集，不关注每个节点的个体差异。

然而，这些关键节点识别方法都是基于具有成对拓扑结构的系统。实际上，一个节点往往受到与多个其他节点的非线性交互的影响，这样的交互不能简化为简单的成对关系，涉及更大的节点集[30]。例如：在社交网络中，产品推荐可能来自社区内的多个个体（包括直接的朋友或属于同一社区但没有友谊关系的个体）；相互不认识的个体可以通过共享的在线论坛或微信 Moments 传递信息；在大脑网络中，多个神经元必须协调以执行特定功能；在工业集群中，多个企业之间存在相互交织的供应关系。这类问题的本质特征在于存在没有直接连接的节点之间的信息交互或功能耦合。换句话说，可能需要分析更大群体内节点之间的间接交互。Battiston等人[31]认为，许多现象的发生和传播不仅取决于直接的邻接关系，还可能受到网络中更宏观或更复杂结构模式的影响。成对结构不足以准确捕捉这些群体内的相互影响，从而对传统的关键节点识别和中心性测量方法构成了重大挑战。

社区群体是复杂系统的重要组成部分，在塑造网络动态和探索隐式交互信息方面起着关键作用[32]、[33]。将社区视为更大的节点集可以更好地揭示节点之间的相互影响和功能关系[34]、[35]、[36]。以社区为背景，摆脱对成对节点的传统关注，采用更广泛的视角来探索节点交互的隐式信息——这使得能够捕捉节点之间的间接交互或功能耦合，从而为信息传播、流行病传播和网络鲁棒性分析提供新的见解。

最近的研究越来越多地将社区信息整合到节点重要性评估中。例如，高阶随机游走可以捕捉局部的高阶结构[37]，基于社区的 centrality 指标[38]可以衡量社区内部和社区之间的连通性，将社区概念纳入多层网络抽象方法可以模拟复杂重叠的场景[39]、[40]。然而，这些现有方法在表征现实世界大规模网络的动态方面仍存在明显局限性。具体来说，依赖于单纯形或模式的更高阶随机游走可能会忽略更大群体之间的复杂交互；在大规模网络中，这类三角形结构或高阶团体的数量庞大，导致计算成本过高。基于静态社区的社区中心性指标通常仅依赖于第一阶邻域统计信息，无法捕捉节点的全局多跳可达性。虽然多层网络模型具有全面的表示能力，但它们存在严重的计算可扩展性问题，并且高度依赖于主观预定义的层间耦合参数[41]。此外，当前的随机游走方法仅允许在成对节点或相邻高阶团体内的节点之间进行转换，从根本上阻碍了它们的可扩展性。因此，迫切需要开发能够有效整合社区信息的新随机游走模型。

为了解决上述局限性，提出了一种整合社区信息的新随机游走框架，该框架解决了传统方法在量化节点间的间接交互和功能耦合方面面临的困难。我们首先构建了一个社区感知的两层网络，以表示社区结构与传统节点之间的交互。然后，通过定义外出和进入游走，利用社区结构信息获得两步游走转移矩阵。结合改进的经典转移矩阵，调整了社区交互和成对节点交互，最终得到一个社区感知的转移矩阵。接下来，通过将社区感知随机游走与 PageRank 随机游走相结合，确定节点重要性排名。通过与常用网络基准数据集上的十种先进关键节点识别方法进行比较，我们的方法显示出显著的优势，在包括一致性验证和信息传播最大化在内的多种网络任务中都有不同程度的改进。广泛的实验证明了所提出方法的优异性能。该框架提供了一种更稳健和可扩展的关键节点识别新方法。我们的主要贡献总结如下：
I. 该方法将社区抽象为虚拟节点层，并构建了一个由原始网络层和虚拟节点层组成的社区感知的两层网络。这种架构创新地将宏观社区拓扑与微观节点连通性耦合起来，为多尺度空间中的网络动态提供了新的物理模型。
II. 通过定义原始节点和虚拟节点之间的双向外出和进入游走机制，该方法将抽象的社区成员资格转化为动态的概率转移过程。这种设计克服了传统随机游走仅依赖于邻接关系的限制，使游走具有社区感知能力，从而更准确地捕捉复杂网络中的长距离相关性。
III. 该方法不仅改进了传统的随机游走，还通过多维特征融合行走方案重建了节点影响力，该方案将改进的游走与 PageRank 的全局权重相结合。这种融合机制同时考虑了节点在本地社区内的活动和在全局网络中的结构重要性，从而显著提高了节点排名的鲁棒性。
IV. 该方法的关键创新在于提供了一个通用的信息增强框架。通过虚拟节点的桥梁效应，静态社区结构信息无缝地融入动态随机游走过程，实现了对复杂网络中信息扩散和链接预测等问题的新理论视角。

本文的其余部分安排如下：第2节讨论相关工作；第3节介绍本文提出的相关方法；第4节介绍实验数据集、参数描述和结果展示；第5节进行了一些讨论；最后，第6节提供了本文的总结和主要亮点。

**复杂网络描述**
复杂网络可以被视为一个广泛的关系图，展示了不同实体（如个人、基因和基础设施）之间的复杂交互。这促进了复杂网络研究作为一个热门跨学科领域的出现，为理解和调节各种复杂系统提供了新的理论工具和技术方法。

**方法论**
在复杂网络分析中，传统方法通常仅关注节点之间的成对交互，难以有效捕捉网络的社区结构和其所体现的群体交互特征。作为网络中紧密连接的子集，社区结构反映了功能模块和组织模式，对于理解信息传播、影响扩散和网络稳定性具有重要意义。

**实验平台和数据集**
本文提出的 CARW 方法以及其他比较方法都是在 PyCharm 2024 环境中使用 Python 3.12 编程语言实现的。所有实验都在配备 Intel? Core? i5-11400 处理器（2.60 GHz）和 16 GB 内存的计算机上进行的。

**关于社区检测算法的讨论**
由于 CARW 依赖于社区结构信息，因此选择社区检测算法可能会影响其排名结果。因此，本小节讨论了三个相关问题：为什么在本文中采用 Louvain 算法，Louvain 的随机性是否会影响 CARW 的稳定性，以及是否可以使用其他社区检测方法作为替代方案。

**结论**
在复杂网络中识别关键节点对于理解和控制网络结构和动态至关重要。传统方法主要考虑成对连接，而忽略了群体交互。为了解决这个问题，本文提出了一种社区感知随机游走（CARW）方法，该方法通过双层结构模拟节点-社区交互，并结合外出和进入游走来捕捉节点和社区之间的信息交换。新生黑：写作、审稿与编辑工作；监督。
利益冲突声明：
作者声明他们不存在任何可能影响本文研究的已知财务利益冲突或个人关系。