Geometric renormalization of weighted networks

加权网络的几何重整化

https://arxiv.org/pdf/2307.00879

复杂网络的几何重整化技术已成功揭示了实际网络拓扑结构的多尺度自相似性，并可应用于生成不同长度尺度下的网络副本。在这封信中，我们将几何重整化框架扩展至加权网络，其中相互作用的强度在其结构组织和功能中起着关键作用。我们的研究结果表明，在一个选择跨越越来越长长度尺度的最大权重连接的重整化协议下，真实网络中的权重表现出多尺度自相似性。我们提出了一种解释这种对称性的理论，并支持将最大权重的选择作为一种有意义的操作方法。基于我们的结果，可以轻松构建加权网络的缩小版副本，从而有助于在下游应用中研究各种与尺寸相关的现象。

实际网络的重整化 [2–4, 14] 可以在几何框架内进行 [14]，这得益于发现它们的结构下隐藏着一个双曲几何空间 [5, 6]。在这个空间中，节点之间的距离通过一条在所有尺度上运作并同时编码短程和远程连接的普遍规律决定了连接的可能性。这一几何原理能够解释许多真实网络的特征，包括小世界特性、无标度度分布以及高水平的聚集性，同时也解释了诸如增长网络中的优先连接等基本机制 [7]，以及社区结构的形成 [8, 9]。它还催生了可以从网络拓扑中生成几何表示的嵌入技术 [10–13]。

真实复杂网络中的权重 [15–19] 也可以用双曲网络几何范式建模。更具体地说，加权几何软配置模型（WSD）[15] 捕捉了网络拓扑与权重之间的非平凡耦合关系，能够准确再现真实网络的无权结构和加权结构。然而，几何重整化（GR）方法仅适用于无权网络。通过对无权网络图应用粗粒化和重缩放步骤，将其展开为一系列在逐渐增大长度尺度下的缩小版层次结构，GR揭示了多尺度自相似性是真实网络中普遍存在的一种对称性 [14]。这就引出了一个问题：GR是否可以推广到加权网络？在这种情况下，自相似性是否仍能保持？

除了GR之外，权重的几何重整化（GRW）应能将网络多尺度地展开为一层层加权的缩小层级，这些层级在流动过程中保留网络的加权结构。在此，我们提出了一个加权网络重整化的理论，支持选择最大值（或极值）作为在重整化层级中分配权重的有效近似方法。我们的理论基于WSD模型的可重整化性，这意味着GRW变换应是对被重整权重集合的一个重新缩放的p-范数。或者，最近一种将权重视为并联电路中的电流或电阻的经验方法已被用于扩展GR至加权网络——分别通过权重之和或其倒数之和的倒数进行重整化 [21]。这两种方法是我们理论的特定极限情况。

首先，我们提供证据表明，自相似性不仅广泛存在于真实网络拓扑结构的多尺度组织中，也存在于其权重的多尺度展开过程中。为此，我们实施了一种GRW变换，该变换需要预先对无权网络应用GR技术 [14]。

一旦生成了一个真实网络的几何地图，GR 将相似度圆划分为大小为 r 的连续节点块。然后这些块被粗粒化，形成新层级中的超节点。每个超节点的位置保留在对应块所定义的角度区域内，并保持节点顺序。一个超节点内的节点与另一个超节点中的节点之间的任何连接都被重整化为连接这两个超节点的一条边。这样，GR 消除了短程耦合，生成的新网络拓扑与原始网络自相似，只是平均度数在重整化流中增加了 [14]。

GRW技术涉及根据原始层级中的权重，按照特定规则为新层级中的连接分配强度。这一变换可以从第 l = 0 层的原始网络开始迭代进行，由于实际网络的有限尺寸，迭代次数大致受限于 lmax ∝ log(N) 步。结果生成了一系列自相似的网络层级 l——每个层级都比原网络小 r 倍——从而构成了原始网络的多尺度加权壳层。该过程在补充材料（SM）的图 S1 中有直观展示。GRW 的关键在于如何重整化权重，以确保其特性（如全局和局部权重分布、强度与度之间的关系）在整个重整化过程中得以保留。

一种有效且简单的规则被称为 sup-GRW，它将两个超节点之间连接的权重定义为原始层级中它们所包含节点之间所有现有连接权重的最大值（即上确界）。我们将 sup-GRW 技术应用于来自生物学、交通、知识和社会系统等不同领域的12个不同的真实加权网络。这些网络使用大小为 r = 2 的块进行处理。更多细节见 SM。

其中两个网络在重整化流中权重的行为显示在图1(a)-(d)中，而图S2-S5则展示了其余网络的相应结果。强度-度的关系在图S5中展示。不同层级中的权重和强度的概率密度函数（pdf）一旦分别按相应层级的平均权重和平均强度重新缩放后，就会发生坍缩。此外，一旦度数按层级的平均度数重新缩放，强度与度之间的幂律关系也会重叠，如图S4和S5所示。为了量化权重的局部异质性，我们测量了节点周围权重的差异性，并将其表示为度的函数，详见SM的方法部分。结果显示，各层级之间再次表现出统计不变性。

需要注意的是，根据构造方式，在 sup-GRW 层级中，平均权重和平均强度随着 l 增大而增长。虽然这种行为对于描述网络加权结构的基本特征并不提供关键信息，但理解 ⟨w⟩ 和 ⟨s⟩ 如何依赖于观察尺度 l 仍可能具有意义，尤其是考虑到实际网络中的权重通常是以现实世界的单位表达的。相应的结果见图 S6 和 S7。此外，sup-GRW 变换在组合操作下展现出类似于无权网络 GR 中观察到的半群结构。这意味着，以一定粗粒化因子进行多次迭代等价于以更高粗粒化因子进行一次变换。图 S8 所示的结果支持了这一说法。

我们还测试了一种替代方案，称为 sum-GRW，其中新层级中的权重是通过对超节点内节点之间现有连接的权重求和来分配的，遵循文献 [21] 中描述的规则。虽然这一策略在许多真实网络中证明有效，但在某些情况下，重整化流中无法保持自相似性。当应用 sum-GRW 时，权重的全局分布、节点中权重的局部异质性以及强度与度之间的关系相比原始图变得更加异质。这一点在 Openflights 网络和科学合作网络中得到了体现，如图1(e)-(h) 以及图 S9 和 S10 所示。

上述结果得到了一个理论框架的支持，该框架阐明了在何种条件下，两种权重分配规则（选择超节点之间权重的上确界或总和）能够表现良好。我们的理论基于 WSD 模型 [15]，该模型使用 SD 模型来模拟真实网络的拓扑结构。在 WSD 模型中，权重被分配给任意两个相连节点 i 和 j 的连接，具体方式如下：

类似于 SD 模型中的 ̄ki ∝ κi，WSD 模型确保节点 i 的期望强度 ̄si 与隐藏强度 σi 成正比，即 ̄si ∝ σi。当 α = 0 时，权重独立于底层几何结构，主要受节点度数影响；而当 α = D 时，权重与底层度量空间最大程度耦合，度数不再直接起作用。最后，εij 是一个均值为1的随机变量，其方差调节网络中噪声的水平。在后续分析中，为了简化解析计算，我们假设模型无噪声，即 εij = 1 对所有 (i, j) 成立。

为了控制强度与度之间的相关性，并进而调整强度分布，我们假设隐藏变量 σ 和 κ 之间存在确定性的关系，形式为 σ = aκη，从而得到 s(k) ∼ akη，这与在真实复杂网络中观察到的情况一致。在此假设下，有效的 GRW 变换应保持强度与度之间的关系不变，特别是指数 η 不变，这意味着重整化后的隐藏度和强度应满足 σ′ = a′(κ′)η（为简化表示，我们用撇号表示重整化层中的量）。结合式(1)和拓扑模型的 GR 方程 [14]，这一要求导出了重整化权重的如下表达式：

其中，求和运算遍历超节点i和j内部节点间的连边（推导见补充材料）。参数φ ≡ βD(η−1)+α 同时依赖于网络的加权与非加权结构，而C = ν′/ν (a′/a)² r^(α/D)。实际应用中，我们通过每层的平均权重对权重进行重新标度，使得常数C可忽略。

根据加权模型，对于具有特定φ值的网络，权重的φ-GRW变换（式(2)）能保持表征强度-度关系的指数η。同时，由于假设隐度分布在GR变换下保持不变，隐强度分布与权重分布亦得以保留——该结论在β > (γ−1)/2时成立。否则，隐度的幂律分布在非加权重整化流中会丧失自相似性，从而破坏权重的自相似性。值得注意的是，φ-GRW变换对复合操作具有半群结构，且与φ取值无关。

我们在真实网络（图S11-S12）和合成网络（图S14-S17）中验证了φ-GRW变换的自相似性及其半群性质。所有案例均显示，权重分布与强度分布在重整化流中的自相似行为，以及强度-度关系的幂律特征在不同尺度上均保持良好，这验证了我们的解析计算。

需指出，式(2)的变换是φ-范数（欧几里得范数的推广）。随着φ增大，φ-范数逐渐由式(2)中wₘₙ项的上确界主导。事实上，当φ→∞时，φ-GRW退化为sup-GRW。此外，求和重整化对应φ=1，而逆权重和重整化则对应φ=−1。

为阐明用sup-GRW近似φ-GRW的效能，我们研究了φ-范数随可粗粒化权重集合元素数E和权重异质性水平的渐近行为（详见补充材料第六节）。图2展示了在本文分析的两个真实网络中，应用上确界与求和方案相比φ-GRW权重重整化的效果（其余网络见图S20-S21）。在合成网络中，我们通过分布p(ωₘₙ)∼ωₘₙ^(−δ)模拟权重（δ用于调节异质性水平），并分别用式(2)（C=1，不同φ值）及求和/上确界方案进行重整化（结果见图S18-S19）。

在权重分布具有显著无标度特性的异质网络中，除极低φ值和小权重情况外，上确界近似偏差极小。随着E增加及度分布趋于均匀，偏差逐渐增大。虽然较高φ值能减小φ-范数与上确界估计的差异，但在涵盖现实网络参数值的广泛范围内，二者通常吻合良好，现存偏差均较轻微。需注意，尽管某些实证权重分布（如JCN网络，图S20-S21）中sup-GRW与sum-GRW产生相同重整化权重，但一般而言sum-GRW无法保持隐强度与隐度的关系（详见补充材料方法部分）。

强度-度关系σ = aκ^η的保持性，使我们能从平均度的流动解析推导平均强度的流动。在GR变换中，层间平均度变化近似满足⟨k⟩^(l+1) = r^ξ ⟨k⟩^(l)（缩放因子ξ取决于原始网络的连接结构[14]）。结合式(2)并假设权重缩放常数C在流动中不变，我们得到：

由于观测强度与隐藏强度之间的比例关系，这意味着平均观测强度的变化流也遵循相同的缩放规律。因此，在 D = 1 的情况下，强度的增长遵循一个依赖于指数 η、拓扑与几何之间的耦合参数 α，以及平均度变化流的缩放因子 ξ 的缩放规律（详见补充材料中的方法部分）。这为我们提供了关于平均强度随平均度变化的增长行为的一个解析近似：

这与合成网络中的测量结果一致，在这些网络中，平均权重在流动过程中可能增加、保持不变或减少，如图3所示。

综上所述，我们的研究结果表明，sup-GRW 对于真实网络来说是一个良好的近似，并且相较于 φ-GRW 具有某些优势。其一在于它避免了估计网络加权结构与底层几何之间耦合参数的需求，而这些参数在实际应用中往往难以准确获取。sup-GRW 相当于设定 φ = ∞，并且由于变换本身的性质，在相对较低的 φ 值时即可有效逼近该极限。此外，使用求和方式进行重整化相当于设定 φ = 1，通常无法保持 σ 与 κ 之间关系的指数 η 不变，详见补充材料中的方法部分的解析推导。

除了理论意义之外，GRW 的实际应用还扩展到生成加权网络的缩小版副本。这些副本可以作为宝贵的测试平台，用于评估计算密集型协议的可扩展性，或研究网络规模起作用的过程。生成一个缩小版副本包括：首先获得拓扑结构的简化版本（如文献 [14] 所述），然后将重整化层级中的权重重新缩放以匹配原始网络的水平。详细步骤见补充材料，真实加权网络缩小副本的结果展示在图 S25–S28 中。

总之，将几何重整化框架扩展至加权网络表明，只要采用适当的重整化方案，多尺度自相似性不仅存在于网络拓扑结构中，也存在于其加权结构中。此外，这些网络中的权重源于决定相互作用强度的过程，我们的研究结果表明，这些过程在不同长度尺度上遵循相同的底层原理。值得注意的是，理论所隐含的变换可通过选择最大权重的规则来很好地近似，这是一种高度有效的策略，即使在权重受到显著噪声影响的情况下也能直接应用于真实网络。这一观察结果使我们确信，噪声不会从根本上改变本研究所报告的定性结果。

本研究为建立一个全面的网络结构重整化框架迈出了重要的一步，并为对真实网络上的动力学过程进行重整化打开了可能性。未来的研究需要不仅考虑连接的拓扑结构及其权重，还需考虑方向性，因为方向性在许多现实世界的过程中至关重要。

加权网络几何重整化的补充材料

B：方法

  1. 实证数据集描述

  • 货轮网络（Cargo ships） ：全球货轮运输网络由2007年世界主要商业港口之间的航运次数构成 [1]。

  • 大肠杆菌代谢网络（E. coli） ：大肠杆菌 K-12 MG1655 的代谢网络中的权重代表两种代谢物共同参与的不同代谢反应的数量 [2, 3]。

  • 美国通勤网络（US commute） ：该通勤网络反映了2000年美国各县之间通勤者的日常流动情况 [4]。

  • Facebook类社交网络（Facebook） ：该社交网络来源于2004年4月至10月期间加州大学欧文分校学生使用的在线社区 [5, 6]。在网络中，节点代表学生，当学生之间交换在线消息时建立联系。有向边的权重定义为一个学生发送给另一个学生的消息数量。我们忽略所有边的方向，并将权重 ωij 定义为双向消息数量之和，即 ωij = ωi→j + ωj→i。请注意，本文仅考虑无向加权网络的最大连通分支。

  • 科研合作网络（Collaboration） ：这是基于1995年至1999年间发表在arXiv凝聚态物理板块上的预印本构建的合作网络 [7]。作者被表示为节点，如果两位科学家至少合著过一篇文章，则他们之间存在一条边。权重是他们共同发表的文章总数。请注意，本文仅考虑无向加权网络的最大连通分支。

  • 全球航班网络（Openflights） ：2010年全球商业机场之间的航班网络，数据源自 Openflights.org 数据库 [8]。节点代表机场，权重代表两个机场之间的航线数量。我们忽略方向性，并将权重 ωij 定义为双向航线数量之和，即 ωij = ωi→j + ωj→i。请注意，本文仅考虑无向加权网络的最大连通分支。

  • 期刊引用网络（JCN） ：从汤森路透引文索引中提取的1900年至2013年科学论文引用数据重建出的引用网络 [9]。每个节点代表一个在特定时间段内发表论文的期刊。如果期刊 i 中的文章引用了期刊 j 中的文章，则期刊 i 到 j 之间存在一条有向边，边的权重为这样的引用次数。在本研究中，我们使用了三个不同时间窗口（2008–2013、1985–1990 和 1965–1975）生成的无向加权网络。数据来自文献 [10]。

  • 新西兰科研合作网络（NZCN） ：这是一个新西兰各机构间的科研合作网络。节点代表机构（如大学、组织等），边表示它们之间的合作。具体来说，若Scopus数据库列出机构 i 和 j 在2010–2015年间至少有一篇联合发表的文章，则两节点相连。边的权重记录此类合作的数量。数据来自文献 [11]。请注意，本文仅考虑无向加权网络的最大连通分支。

  • 罂粟与毛地黄下胚轴细胞互作网络（Poppy and foxglove hypocotyl cellular interaction networks）：这些网络捕捉了罂粟和毛地黄下胚轴（胚胎茎）内的全局细胞连接性。节点代表细胞，边表示它们在三维空间中的物理关联。边的权重由相邻细胞界面的大小决定，节点还标注了细胞类型。数据来自文献 [12]。

网络统计信息见表 S1。

2. 网络嵌入以生成几何网络图

我们使用文献 [13] 中提出的名为 Mercator 的算法，将每个所研究的网络嵌入到双曲空间中。Mercator 以网络的邻接矩阵 Aij 作为输入（若节点 i 和 j 之间存在连接，则 Aij = Aji = 1，否则为 0），然后返回推断出的隐藏度数、节点的角度位置以及全局模型参数。更具体地说，双曲空间中的映射是通过寻找每个节点的隐藏度数和角度位置 {κi} 和 {θi} 来实现的，这些参数使得网络结构由 S1 模型生成的可能性最大化，其中：

4. 重整化权重的理论推导

在几何重整化（GR）下，结果层级中超节点的隐藏变量 κ′ 和 θ′ 是根据构成该超节点的原始节点的隐藏变量计算得出的，具体表示为：

在最后一步中，我们假设对于每一对节点 (m, n)，都可以从对应的权重 ωmn 中得到乘积 κmκn，这在一般情况下并不成立，因为有些节点之间可能并不存在连接。然而，这一近似是合理的，因为它仅遗漏了隐藏度数乘积中最小的部分。现在，上述变换若没有嵌入中的精确距离信息是无法进行的，因为它依赖于 dmn。但考虑到 dmn = R∆θmn，其中 ∆θmn 表示节点之间的角度间隔，并且事实上所有这些角度间隔近似等于它们所属超节点之间的角度间隔，我们可以看出，只要设定 α′ = α，就可以消除所有对距离的依赖性。

2 sup-GRW 变换中的半群结构

几何重整化变换在组合操作下具有阿贝尔半群结构，这意味着一定次数的给定分辨率迭代等价于一次更高分辨率的变换。我们在 sup-GRW 变换中使用合成网络和实证网络验证了这一半群结构。给定一个原始网络，我们分别进行了 r = 2 和 r = 4 的 sup-GRW 变换。当几何重整化变换到相同的网络尺寸时，我们比较了它们的网络属性。图 S8 展示了一个代表性合成网络的结果。

G：随机-GRW 结果

如果从可粗粒化的权重集合中随机选择两个超节点之间的权重，并且该选择集合中还补充了同一超节点内节点之间的连接，则这种方法在权重分布上始终会呈现出自相似性。然而，在重整化过程中，这些内部连接会被粗粒化处理，而超节点内部连接权重与不同超节点之间连接权重的平衡决定了随机选择方法在哪些情况下有效。

在合成网络中的实验结果（见图 S22 和 S23）表明，权重分布的异质性有利于实现更好的自相似缩放效果。当在 WSD 模型中降低权重与拓扑及几何结构之间的耦合时，权重分布变得更加均匀，从而导致流动过程中的自相似性丧失。有关大肠杆菌代谢网络的相关结果，请参见补充信息图 S24。

原文链接：https://arxiv.org/pdf/2307.00879