用于量化图不相似性的网络层次熵

为什么网络中的细微差异很重要

从社交媒体的好友关系到航线网络再到蛋白质结构，许多我们周围的系统都可以表示为节点与连边组成的网络。但是要判断两个这样的网络何时在实质上不同却出人意料地困难，尤其当它们乍看相似时。本文提出了一种新的度量方法，能够衡量两个网络的真实差异——它不仅关注单个点（节点），还关注连接（边）以及它们如何共同作用。该方法称为网络层次熵，能够发现其他工具漏检的细微结构变化，甚至有助于区分酶蛋白与非酶蛋白。

逐层审视网络

为了理解一个网络，作者首先考虑从某一节点到其他每个节点沿连边所需的步数。围绕任意选定的节点，其他节点可以被分组为若干层：直接邻居、邻居的邻居，依此类推。节点周围的这种“层次”描述了影响力或感染如何向外扩散。值得注意的是，两张结构截然不同的网络可能具有相同的节点级别层次，因此仅靠这一视角可能无法将它们区分开来。论文给出了经典例子，例如德萨格图（Desargues）和十二面体图（Dodecahedral），它们尽管内部连线不同，却共享相同的节点层次。

让边“发声”：收缩节点对

为捕捉节点视角遗漏的信息，作者将注意力转向边——节点之间的连结——以及它们如何重塑网络中的距离。他们引入了一个简单但强有力的思想：“节点对收缩”。在此操作中，两个相连的节点被暂时合并为一个新的单一节点，同时保留它们合并后的邻居关系。这样可以揭示相比于各端点单独出发，网络中其它节点与该节点对的接近程度有何不同。从这些分层距离模式中，他们为节点和边分别定义了“层次中心性”，并发现该量与在真实网络上模拟流行病传播时节点或边作为传播者的效果高度相关。

用熵衡量信息损失

基于这些中心性指标，作者定义了两类层次熵。边层次熵的问题是：如果我们试图仅通过平均其两端节点的重要性来近似一条边的重要性，会丢失多少信息？节点层次熵则反过来考虑节点与其周围边之间的信息损失。两种量都进行了归一化处理，使其不依赖于网络的总体规模。它们共同构成了任意网络的两数指纹。两个网络之间的距离便是其指纹之间的几何距离。该新度量满足距离的一般公理，并与直觉一致，例如当某种改变导致网络破裂时会给出更大的惩罚。

观察更细的结构与随时间的变化

作者在人工和真实网络上测试了他们的度量。在模拟社会或技术系统的合成基准测试中，该新度量能跟踪网络随着模型参数变化的演化，并能清晰地区分具有强社区结构的网络与社区较弱的网络，即使竞争方法在这些情况下也表现吃力。在经过精心重新排列以保留许多常见统计特性（如度序列甚至距离分布）的对照实验中，层次熵距离仍然能检测出其他流行度量视为微不足道的差异。它还擅长将同一网络的随机化版本分组到正确的类别中，表明它对超越简单连边和路径计数的更高阶结构具有敏锐的敏感性。

现实应用：出行与蛋白质

为展示其实用价值，作者将该距离度量应用于COVID-19最初几个月期间数百个中国城市之间的每日移动网络。以一月上旬为基线，层次熵揭示了贯穿春节出行高峰、严格隔离开始以及逐步恢复期间出行模式的变化，这与已知的政策变动和出行社区格局高度一致。在另一个应用中，他们将蛋白质结构视为当氨基酸在空间上接近时连接起来的网络。在没有任何学习或人工设计特征的情况下，基于该新距离对蛋白质进行聚类，在区分酶与非酶方面达到了约75%的准确率——与现代监督神经网络方法具有竞争力。

通俗来说这意味着什么

归根结底，这项工作表明，关注节点与连边如何共同塑造网络中的距离，比仅看节点能够提供更清晰的“指纹”。通过量化当我们试图用端点替代边，或用周围的边替代节点时会丢失多少信息，所提出的层次熵距离突出了那些会强烈影响传播、出行和生物功能的细微结构差异。对于处理任何类型网络数据的科学家和分析师，这提供了一个实用且通用的比较复杂系统的工具——它既有数学依据，又与实际网络上过程的展开方式密切相关。

引用: Mou, J., Wang, L., Zhang, C. et al. Network hierarchy entropy for quantifying graph dissimilarity. Commun Phys 9, 83 (2026). https://doi.org/10.1038/s42005-026-02523-9

关键词: 网络相似性, 复杂网络, 熵度量, 流行病传播, 蛋白质结构网络