近日，北京师范大学系统科学学院张江教授团队联合帕多瓦大学物理学院Manlio De Domenico团队共同提出了一种基于统计物理和机器学习的复杂网络粗粒化方案，该方案既能在压缩网络尺寸的同时保留网络的信息动力学特性，又能够显著降低网络压缩算法的时间复杂度，并揭示网络的多尺度规律。研究团队人员来自北京师范大学，集智科学研究中心和帕多瓦大学。相关研究成果以“Coarse-graining network flow through statistical physics and machine learning”为题发表于《自然通讯》（Nature Communications）。相关算法也已在github开源。

研究背景

复杂网络的拓扑结构与其上的信息动力学共同作用，支撑着复杂网络的功能。而在现实世界中，许多复杂网络都以其巨大的结构体量为算力提出了挑战。因此，网络科学中的一个重大问题在于，我们是否以及如何能够在保留网络宏观信息动力学的情况下对其进行粗粒化处理。传统的重整化方法，例如几何重正化群（GRG）和拉普拉斯重正化群（LRG），主要关注某种结构不变性的度量。其中一种方法利用潜在的几何特性，而另一种方法则是滤除快速扩散模式，仅保留最慢的扩散模式。然而，如果我们希望在所有尺度上保留完整的信息流动力学，而不施加结构性约束，又该如何实现？本文通过结合统计物理与机器学习（ML）的方法，推动这一问题的解决迈出了一大步。

统计物理描述网络的信息动力学行为

对网络的信息动力学行为已经有了非常多的经典研究，近年来，通过将统计物理引入复杂网络，人们找到了更好的理解网络动力学行为的工具。平衡态统计物理是一个重要的研究领域，其主要研究系统在平衡态下的宏观行为与微观状态之间的关系，尤其关注系统在不同温度下的能量分布以及温度如何影响系统的自发过程。

考虑到复杂网络作为一种重要的物理和数学模型，在其中的信息传播、扩散等现象也具有极强的动态性和全局性，因此人们可以借助扩散动力学过程，将平衡态统计物理范式迁移到复杂网络上，从而帮助我们理解网络的动力学行为。与经典的统计物理范式不同的是，在经典统计物理中，我们的研究对象是处于特定温度下的热力学系统，其中系统的不同能量状态具有特定的存在概率，这些状态的分布与温度的变化密切相关。而在复杂网络上，人们的关注对象从系统的不同能量状态和其对应的概率转化为信息传播的模式和其对应强度。具体来说，网络中的节点和边构成了扩散过程中的“微观状态”，而信息通过这些节点和边的传播模式决定了系统的宏观行为。

尽管观察对象有所变化，但与经典的统计物理相似，人们仍然可以定义配分函数、熵、自由能等物理量。在诸多物理量中，配分函数占据特殊地位，不仅因为它在热力学系统的描述中起到核心作用，而且由于配分函数包含了系统的全部信息，因此所有其他物理量都可以由配分函数导出。配分函数可以看作是描述系统的状态空间的总和，它将系统的所有微观状态的贡献加权汇总，从而为我们提供了计算系统宏观性质的基础。

当人们将平衡态统计物理扩展至复杂网络上的时候，人们同样可以定义网络的配分函数，假设存在一个无向图，已知其上的扩散动力学微分方程为

其中L代表网络的拉普拉斯矩阵，那么该过程的解为

据此，可以定义网络的配分函数为

其中

是L的第i个特征值，配分函数有明确的物理含义，其表示保留在所有原始节点上的信息量。

图1：空手道俱乐部网络的配分函数

图1展示了一个经典的复杂网络空手道俱乐部网络及其配分函数，可以看到，配分函数是一个单调递减的函数，横坐标是扩散时间，纵坐标的归一化配分函数值代表留在原始节点的信息量。在扩散开始时，所有信息都留在原始节点，配分函数取到其全局最大值，随着扩散的进行，最终信息均匀地分布在所有节点上，配分函数降至全局最低点。其特性类平衡态统计物理系统中，系统状态随着温度降低而变化。而这一曲线体现了信息传播的动态，例如当网络更加稠密时，配分函数会以更快的速度下降，当网络存在明显的社团结构时，局部信息传播速度很快而全局信息传播受到桥节点数量的限制而很慢，在配分函数上将会体现为前段速降而后段缓降的情况。因此，配分函数是一个对信息传播动力学在不同时间尺度的详细而综合的描述。

由于以上性质，研究者们选择将归一化配分函数的一致性作为网络粗粒化的目标，据此进行网络粗粒化算法的设计。

基于图神经网络的复杂网络粗粒化方案

图神经网络（Graph Neural Network, GNN）是近年来兴起的一类专门用于处理图结构数据的深度学习模型。图结构数据可以用来表示诸如社交网络、推荐系统、分子结构、知识图谱等复杂关系。GNN的核心思想是通过节点之间的连接（边）来传播信息，进而学习到图中每个节点或整个图的表示。由于许多实际问题本质上可以通过图结构来建模，因此图神经网络在多个领域都有广泛的应用，如社交网络中的社群检测，生物信息学中的药物发现，自然语言处理领域的文本分类等等。

研究者们采用图神经网络解决网络压缩问题的方法如图2所示。在此方法中，他们利用图神经网络来聚合节点特征，并输出节点的分组分布。同一组内的节点会被压缩为一个超节点，而它们之间连接的总和则成为该超节点的加权自环。当然，不同组之间的连接则成为了各超节点间的加权链接。粗粒化的效果则通过比较归一化配分函数Z的平均绝对误差（MAE）来进行评估。在优化过程中，模型通过梯度下降方法不断调整从节点局部结构特征到节点分组的映射关系。这种调整确保了最终生成的宏观网络具有与原始网络相似的归一化配分函数。

图2：模型架构说明

由于宏观网络中的节点数量可以灵活配置为一个可调的超参数，因此我们可以将原始网络数据压缩为任意节点数量的宏观网络，从而适应不同任务的需求。此外，这一模型的时间复杂度为 O(N+E)，其中 N和 E 分别表示原始网络中的节点数和边数。这一复杂度相较于其他模型具有显著优势。因此，该方法能够高效压缩非常大规模（如十万个节点）的网络。

模型表现

首先，研究人员发现模型很好的实现了其的预定目标，即在粗粒化网络的同时保留配分函数，此外通过实验，研究人员还发现了很多模型的有趣性质：

误差与规模之间的无尺度性质

尽管模型已经能够很以很高的精度保留原始配分函数，但由于网络数据被压缩到了低维空间，配分函数信息将会自然的有所损失，且信息损失将会随着网络尺寸的减少而增加。但有趣的是，研究人员发现配分函数的误差与网络尺寸呈现无标度关系，这意味着并不存在某个最适用于模型和数据的“最优粗粒化尺寸”。

图3：人造网络实验：压缩精度与宏观网络尺寸的关系

具有相似局部结构的节点将被粗粒化为相同超节点

研究人员不仅关注模型的精确度，还十分关注模型学到了何种具体的粗粒化策略，在对网络的粗粒化过程中，研究人员发现具有相似局部结构的节点将会被模型粗粒化为相同的超级节点。在下图中，他们以美国机场网络的粗粒化实验为例来说明这一效应：

图4：美国机场网络粗粒化

美国机场网络（不包括阿拉斯加区域）是一个具有超过五百个节点的网络，研究人员依据经过机场的航线数量（即机场节点的度数）对机场进行排序，并展示将其中的前15个机场被纳入了哪些宏观节点。可以发现，当将原始网络粗粒化为50个节点的宏观网络时（左列），这些大机场都被纳入了3个宏观节点上，而当进一步压缩网络尺寸为20个宏观节点时（右列），可以发现宏观节点也被进一步合并为两个。这说明这些大度节点都被纳入了少量宏观节点中。

模型可解释性探究

研究者们进一步分析了模型的可解释性，尤其探索了将相似局部节点粗粒化为相同超级节点的这一策略。首先，需要意识到这本身是图神经网络的自然选择，因为图神经网络以节点的局部特征作为输入，并输出节点分组。但这一天然策略本身也十分契合压缩网络尺寸并保留信息动力学行为的目标，如图5所示：

图5：将局部结构相似的节点压缩为相同超级节点的合理性

图5展示了三类具有不同局部特征的节点，以及为什么将他们粗粒化为相同的超级节点有助于保留信息动力学行为。

具有高聚类系数的节点通常其邻近节点之间存在较多互连，在网络中的信息扩散过程中，这些互连会起到将信息局限在局部的作用。当高聚类系数的节点被归为一组时，它们之间的众多互连会转化为超节点上的高权重自环，从而继续发挥局限信息于局部的作用，如子图a所示。

中心节点在网络中充当全局信息扩散的桥梁。通过将中心节点聚类在一起，中心节点与其他节点之间的边会转化为粗粒化网络中超节点之间的连接，从而仍然保证全局信息的顺畅传递。然而，如果把一个中心节点及其邻近节点归为一组，那么它们之间的互连关系会转变为该超节点的自环，这会导致信息被局限在局部，进而对全局信息传播形成阻碍，如子图b所示。

具有明显社区结构的网络由于社区间连接较少，全局信息扩散速度较慢。将同一社区内的节点聚合在一起时，大量的社区内连接会转化为超节点上的自环，从而导致信息局限在局部范围内。与此同时，少量的社区间连接则转化为超节点之间的低权重边，同样起到减缓全局信息扩散速度的作用，如子图c所示。通过这三个典型例子，可以发现这种粗粒化方案减少了冗余结构，而相应的功能却得以保留。因此，这种方法在压缩网络时能够自然地有助于保留信息动力学行为。

基于这一原则，模型将进一步优化连续的分组策略，从而微调出适用于特定网络的粗粒化策略。

网络密度影响模型性能

为了进一步验证模型在更广泛的数据上的可用性，尤其探究模型更适用于哪些领域，研究人员在由不同领域的真实网络组成的数据集上进行了实验，如图5所示：

图6：真实世界网络实验

首先，可以发现模型的表现并不会随着数据所属领域而呈现出不同，但的确存在着网络的结构属性将会对模型的粗粒化后保留配分函数的精确度造成显著影响，那就是原始网络的密度，如图5右图所示：原始网络密度和压缩后的配分函数误差近似呈现幂律关系。这或许是因为更高的密度意味着更高的信息传递方式的多样性，从而使粗粒化难度增大。

总结

在网络粗粒化领域中，目前仍缺乏一种能够粗粒化不同网络结构并确保留信息流行为的方法，而本工作填补了这一空白。传统的经典方法往往依赖一组规则来识别网络中的节点组，并通过粗粒化构建压缩表示。相比之下，本工作采用数据驱动的方法，借助机器学习提取最优的粗粒化规则，并通过训练调整模型参数。与大多数试图最大化宏观网络与原始网络结构相似性的网络压缩方法不同，该模型倾向于保留网络中的信息流行为，因此对网络的结构和动力学特性同时具有天然的敏感性。此外，该方法极低的复杂度（相比于其他方法低1-2个数量级）让网络规模不再是人们分析大网络的阻碍，具备在众多学科中广泛的应用潜力，这些学科涉及从城市交通到连接组学等所有需要研究互联系统内部信息流动的领域，同时也揭示了网络组件之间信息交换的多尺度特性，助力人们进一步理解复杂系统的结构，信息交互和涌现之谜。

欢迎大家到原始论文（https://www.nature.com/articles/s41467-025-56034-2）中查看更多信息与结论，如压缩过程中的结构属性变化，大规模（十万个节点）网络的粗粒化效果，方便使用的预训练模型，不同目标函数的性质以及和其他方法的对比等等。也欢迎大家直接使用该论文的开源代码（https://github.com/3riccc/nfc_model）助力自身领域的复杂网络科研实践。

供稿：张 章

编辑：郝林青

审核：李 辉