通过消息传递算法将网络划分为同步节点的集群：一种可扩展的方法

《Physica A: Statistical Mechanics and its Applications》：Partitioning networks into clusters of synchronized nodes via the message-passing algorithm: A scalable approach

　　摘要：将大型网络划分为由同步节点构成的稳定簇是一项具有挑战性的任务。基于谱分析的最新方法能够为特定动态提供精确结果，但难以应用于规模极大的网络。此外，在随机框架下，尚不清楚应选择何种动态来研究同步现象。本文提出了一种可扩展的消息传递框架，该框架利用类似伊辛模型的有效替代动态的集体行为，以识别大型网络中的同步相关分区。通过利用类似伊辛模型临界点处出现的集体行为，我们识别出具有动态一致性的同步节点簇，并在一些大型现实世界网络中展示了该方法。我们发现，与连续时间动态不同，即使在简单图中，也无需引入高阶相互作用即可出现突然的失步现象。然而，当存在噪声时，同步过渡会变得更加平滑，并通过形成平台期来实现，但代价是需要更大的耦合强度。

引言：网络理论[1]、[2]、[3]为研究包括物理、生物、生态和社会系统在内的各种领域的复杂系统提供了通用框架，涵盖了从结构到功能的多个组织层次。在过去的三十年间，受数字技术、互联网以及近期人工智能革命的推动，复杂网络理论在理论发展与应用层面都取得了快速进展。这一发展的动力来自于大量现实世界数据集的出现，这些数据集的规模和多样性本身也构成了重大挑战，即所谓的“大数据”[4]、[5]、[6]。在许多科学领域，现有数据的数量和多样性已经超出了传统数值方法的处理能力。这一问题在生物和生态系统尤为严重[7]、[8]、[9]、[10]，因为这些系统中的数据来自不同的空间和时间尺度，且由多种不同的实验和观测技术产生。基因组学就是一个典型例子，人类基因组的大小从10^4个碱基对到数十亿个不等。在这样的背景下，直接或简单应用网络理论很快就会变得不切实际。采用基于网络的描述方法的最初动机之一在于，它能够将系统的完整N×N连接信息简化为有限的几项全局指标的紧凑统计描述，如度分布、聚类系数和平均路径长度。这些量能够捕捉系统的关键特征，在分析网络上的动态过程（如渗透效应和疾病传播）中起着核心作用[11]。除了全局描述符之外，局部结构属性也同样重要。在这方面，较早提出的社区概念[12]、[13]、[14]——大致定义为具有相似行为的元素子集——长期以来一直发挥着重要作用。实际上，通过使用更现代的标记网络对称性概念，可以更精确地定义节点群之间的相似性，这一概念有多种密切相关的定义[15]、[16]、[17]、[18]、[19]、[20]、[21]、[22]。根据参考文献[22]的定义，当一组顶点的外部邻域相同且度数相等时，就存在对称性。具有这种对称性的子集构成了拓扑等价节点群，而在相同的初始条件下，这些节点的动态行为会呈现出一致性。根据动态性质的差异，这种一致性——如果稳定的话——可能表现为收敛到共同的稳态（共识状态），或者表现为持续的相干振荡（同步）。在这两种情况下，其背后的机制是相同的。因此，将网络划分为对称群可以为理解网络功能提供有价值的见解。相反，观察到的集体动态也可以用来推断底层网络的结构特性。本文正是朝着这个方向展开研究的。近年来，同步的一般理论取得了显著进展，并在复杂的现实世界网络中得到了重要应用。这些发展的一个重要成果是形成了双重认识：首先，如前所述，网络对称性在实现簇同步[16]、[17]、[18]、[19]、[20]、[23]和保护性同步[22]方面起着核心作用；其次，实证研究表明，与传统的网络理论模型（如随机图模型、配置模型或巴巴拉西-阿尔伯特模型）不同，现实世界网络通常具有大量的此类对称性[15]、[21]。尽管取得了这些进展，但正如参考文献[21]所指出的，其在实际网络分析中的应用似乎仅被部分探索，而且很少被利用。造成这一差距的原因可能有两个。一方面，现有的研究局部同步的方法严重依赖于谱分析技术，而这种技术对于大规模网络来说计算成本过高。另一方面，在生物和生态系统所典型的随机环境中，相关的底层动态往往未知或定义不明确，这使得基于动态模型的分析难以实施。在本研究中，我们通过引入基于消息传递算法的同步检测框架来克服这些限制[24]、[25]、[26]、[27]。消息传递算法提供了一种离散时间的可扩展替代动态，能够在不假设任何特定微观动态模型的情况下识别出同步节点簇。更确切地说，这种替代动态并非源自某种特定的微观模型，即基于物理或生物规律的模型；而是源于一种统计动力学方法，该方法的主要假设是，无论相互作用的具体性质如何，都是通过给定网络中的链接进行消息交换来实现的，这里假定给定的网络就是唯一的实际输入数据。具体而言，在本研究中，我们考虑了消息传递算法最简单的实现方式：每个节点都有一个二进制（类似伊辛模型的）状态变量，网络中所有相连的节点都以相同的协作方式相互作用（均匀的正耦合）。该方法的可扩展性体现在其计算成本随网络规模N的增长而近乎线性上升。虽然消息传递算法在物理学和计算机科学中已被广泛使用，但其用于研究同步现象似乎尚未被探索。通过改变类似伊辛模型的耦合参数，我们探究了临界点处的集体行为，并利用它来区分同步节点簇。我们发现，拓扑等价节点充当同步的核化中心，在具有大量对称性诱导结构的网络中产生了丰富的同步场景。特别是，我们发现，即使在简单图中，也不需要引入高阶相互作用就能出现突然的失步转变[28]。然而，当引入随机噪声时，同步转变会变得更加平滑，并通过明确的平台期实现，但代价是需要更大的耦合强度。本文的结构如下：第2节阐述为何将消息传递算法作为无偏的替代动态；第3节定义用于表征同步的可观测量并明确主要目标；第4节正式定义拓扑等价的概念；第5节回顾消息传递算法；第6节应用消息传递算法，根据三种不同情况分析同步现象：均匀初始条件、随机初始条件以及带有噪声的随机初始条件；第7节在两个大型现实世界网络中展示该方法的应用；第8节给出结论与展望，随后是附录。

要点摘录：
动机：作为可扩展无偏动态的消息传递算法
大多数现实世界的复杂系统都受其元素间相互作用的随机动态控制，这些元素的拓扑结构可以用图G=(V,E)来表示，此处我们假设该图是静态的，同时这些系统还与外部环境存在相互作用。即便将系统视为自主系统——即忽略外部影响或将它们视为噪声——这些相互作用的本质以及由此产生的动态通常仍然是未知的。除了纯粹的……

主要目标：将网络划分为同步节点簇
给定一个具有N=|V|个标记节点的简单无向图G=(V,E)，这些节点的标签属于自然数集{1,…,N}，该图的邻接矩阵为对称矩阵A，再给定一个阈值?>0，我们的目标是为任意的耦合强度J找到一种将V划分为Q个不相交的非空集合（或簇）H(1),…,H(Q)?V的分法，使得在消息传递算法的动态作用下，每个簇中的所有节点最终都能同步到阈值?以内。换句话说，我们希望找到Q组节点索引H(1),…,H(Q)……

拓扑等价节点
与同步节点簇的概念相对应的是之前提到的拓扑等价节点群的概念[22]。考虑一组度数相同的N′个节点，对于每个节点，查看不属于该节点群的第一个邻居集合。如果所有这些集合都相同，那么我们就说这N′个节点构成一个拓扑等价群。用公式表示，对于?i1,…,i|H|∈H，我们需要满足：∑j∈VAi1,j=?=∑j∈VAi|H|,j,Ai1,k=?=Ai|H|,k,?k∈V?H。也就是说，该群中的每个节点看到的第一个邻居都是相同的……

消息传递算法
在本节中，我们将回顾消息传递算法（或称信念传播算法）[24]、[25]、[26]、[27]，它可以被视为一种用于控制消息在物理或抽象网络中传播的有效算法。更准确地说，正如第2节所提到的，消息传递算法能够根据给定图G=(V,E)的相关条件概率，还原出联合分布Pt(x1.…,xN)的所有特征。消息传递算法在物理学等诸多不同领域都有应用……

应用消息传递算法进行聚类
在这里，我们介绍了应用消息传递算法将给定图G划分为同步簇的一般步骤，这些步骤是根据第3节给出的定义来执行的，同时我们也说明了如何根据第4节给出的定义，建立同步簇与拓扑等价群之间的关系。如前所述，为简化问题，我们设定Ji,j=J>0?(i,j)∈E。关于具有不同耦合强度的应用场景，我们将在其他地方讨论。此外，此处我们还假设β=1。

在现实世界网络中的应用
我们将所提出的算法应用于两个现实世界网络：美国电网和WordNet词汇网络。这两个网络的规模分别为N=4941和N=145994，目前还不属于大数据范畴；不过，它们的规模已经足够大——尤其是后者——足以对这种方法的可扩展性和效率进行有效的测试。在两种情况下，我们都成功地将网络划分成了同步群，并将得到的数据存储起来……

结论与展望
在本研究中，我们解决了在底层微观动态未知或为随机情况时，如何在大型复杂网络中识别出稳定的同步节点簇的问题。通过采用概率论视角，并引入基于消息传递算法的替代动态，我们提出了一种可扩展的框架，避免了对手动假设系统动态的依赖。虽然这种方法的理论结构仍然非常通用（见第2至4节），但我们的数值……

利益冲突声明
作者声明，他们没有已知的可能影响本文研究的财务利益或个人关系。

致谢
本研究得到了巴西国家科学技术发展委员会（CNPq）的资助，项目编号为409180/2023-8。同时，我们也感谢CNPq-FAPESB生产力资助项目（编号302787/2025-9）的支持。

马西莫·奥斯蒂利
巴西巴伊亚联邦大学物理研究所，萨尔瓦多，BA 40170-115，巴西