多层网络重构：结构区分度如何决定可重构性？

导语

对单层网络的重构是一个被广泛关注的经典问题，但对于多层网络的重构问题，目前大多数工作通常沿用单层网络中的经典方法，而忽视了不同层之间的相关特征。浙江大学、仑斯勒理工大学、波斯顿大学的联合研究团队最新发表在 Communications Physics 的一项工作设计了一种利用多层网络聚合结构和局部观测等不完全信息的多层网络重构方法，并通过分析在不完全信息下多层网络结构的不确定性，提出了描述重构过程理论准确率的可重构性概念。同时，基于对该多层网络可重构性的分析，针对局部观测资源有限的实际场景，从理论上获得对于有限观测资源的最佳分配策略，从而实现对多层网络的最优重构。

研究领域：多层网络，网络重构，信息熵

贺诗波 | 作者

邓一雪 | 编辑

论文题目：

Discrimination reveals reconstructability of multiplex networks from partial observations

论文链接：

https://www.nature.com/articles/s42005-022-00928-w

1. 重构多层网络的必要性

随着对网络化系统的研究逐渐深入，研究发现生活中绝大多数不同网络之间会相互影响。于是，由若干层子网络构成的多层网络模型应运而生[1]。与单层网络相比，多层网络能更准确地描述不同类型节点之间的不同连接关系。

多层网络包含的信息非常丰富，不仅包括每一层的网络结构信息和不同层之间的结构信息，也包括每个节点的同、异构关系和每条边的同、异构关系等[2]。正因如此，在实际的大型网络化系统中，获得多层网络的完整信息非常困难，往往会因为各种原因出现信息遗漏、不完全，或者需要消耗大量的观测或实验成本等。所以，实际中获得的多层网络结构通常为不完全信息，例如其聚合网络结构、局部结构等信息。

2010 年 Buldyrev 等人在《自然》杂志发表的关于多层网络级联失效问题的研究工作，引起了人们关于多层网络完整结构重要性的巨大关注[3]。研究发现，在网络节点受到攻击时，相互依赖的多层网络会因级联失效现象，比其单层聚合网络更为脆弱，如图1所示。因此，多层网络的完整结构对于各类动力学性质的分析至关重要，通过不完全信息重构多层网络完整结构的重要性不言而喻。

图1. 多层网络与单层网络的脆弱性区别。a 在网络节点受到攻击时，相互依赖的两层网络会因为级联失效现象，导致大量节点（红色节点）脱离最大连通片。b 其单层聚合网络，在面对相同节点受到攻击时，只有少量节点（红色节点）脱离最大连通片。

2. 多层网络的重构方法

本文考虑的不完全信息包括多层网络的聚合网络结构、多层网络局部结构信息等。如图2a所示，多层网络结构由 M 表示， A⁰表示其单层聚合网络的邻接矩阵，而 Γ 表示多层网络中被观测到的局部结构集合。因此，多层网络重构方法的目标是推断多层网络中除 Γ 外任意一层中任意两个节点之间存在边的可能性。

具体地，多层网络重构方法的首先通过最大化概率 P(θ)=P(θ｜A⁰, Γ) ，以获得对参数 θ 的最大后验估计，其中 θ 是网络模型的参数，例如ER模型中的连接概率和配置模型中的度序列等。此外，由于同一张单层聚合网络可能由不同的多层网络所聚合而成，本文建立了多层结构 M 的概率分布，记为 Q(M) ，其中∑_MQ(M)=1。于是，对多层网络结构的重构即为对参数 θ 估计以后，并通过参数 θ 计算结构的后验分布 Q(M)=P(M｜A⁰, Γ, θ) 。

但是，多层网络的结构 M 是 P(θ) 的隐变量，理论上不能求得其显式解。于是，本文通过期望最大化算法以获得数值解，这一过程也即为网络参数空间与网络结构空间的坐标上升法，如图2b所示。以每层都为配置模型的两层网络为例，网络模型参数 θ 即为网络的度序列。如图2c所示，给定任意初始参数后，可以计算获得，其中每一条边的灰度代表了该方法所推断的连接存在概率。然后根据计算获得的，对参数进行更新以获得，因为此时假设了多层网络结构 M 是常数，已不再是隐变量。以此方式进行迭代更新，直至收敛，而期望最大化算法则保证了该迭代过程的收敛性。此外，可以证明该方法对网络模型参数的估计为渐进有效估计，即当网络规模趋向于无穷大时，对参数的估计方差趋向于克拉美罗下界 (CRLB, Cramer-Rao Lower Bound)。

图2. 基于不完全信息的多层网络重构方法。a 多层网络 M 与其单层聚合网络 A⁰ 和局部观测集 Γ 示例。b 期望最大化算法在参数空间和结构空间执行坐标上升法的迭代过程。c以配置模型为例的一张两层网络通过期望最大化算法的迭代过程示例。

3. 多层网络的可重构性

然后，本文提出多层网络的可重构性，以描述对多层网络重构的理论准确率，并进一步研究多层网络的可重构性和网络结构特征之间的关系。一般而言，影响多层网络重构准确率的直接因素为整张网络每条边的不确定性，不确定性越小，重构的准确率越高，反之亦然。

为了量化多层网络 M 的不确定性，本文将以两层网络为例，计算在已知单层聚合网络 A⁰ 的情况下，多层网络的信息熵 H(M｜A⁰) 。经过平均场近似，发现了该信息熵与局部观测比例 c ，两层网络平均度之比 r ，两层边重合度 v 高度相关。图3a展示了信息熵 H 与 c, r, v 三者之间的关系。于是，H 的大小描述了多层网络关于微观结构的区分度，因为较高的区分度（例如 r 接近0）会导致较小的信息熵。

通过大量数据实验发现，重构准确率可以由指标 ρ·H 线性确定，且

Accurary≈1-ρ·H，

如图3b所示。其中 ρ 是 c, r, v 的函数，而 s 是关于局部观测量减少不确定性的尺度因子。如图3c所示，研究进一步发现 s 与多层网络的度序列的余弦相似性成正比，描述了多层网络的中观结构特征。图 3d展示了不同的度序列余弦相似性在多层网络中的示例。因此，多层网络的可重构性被与微观和中观结构有关的区分度指标 (1-ρ·H) 所确定。以上结论表明，可以通过该区分度指标预测重构准确率，从而在 ρ 或 H 较小的情况下获得较高的重构准确率。

图3. 多层网络可重构性的与网络结构的理论研究。a：信息熵 H 与 c, r, v 的关系。b：重构准确率与指标 ρ·H 的线性关系。c：尺度因子 s 与度序列余弦相似性之间的正比关系。d：不同的度序列余弦相似性在多层网络中的示例。

4. 多层网络的最优重构

在实际中，获取多层网络局部结构的观测资源通常是有限的。因此，在一定的观测总量下，研究不同层中的资源分配比例，以提高重构准确率具有重要意义。同样，以两层网络为例，记c₁为第一层的局部观测量，而c₂为第二层的局部观测量。当观测总量一定时，以每一层的局部观测量之比c₁/c₂作为变量，建立对应的观测策略空间，如图4c所示，并根据不同策略计算相对应的信息熵函数，以表征整张网络的不确定性。

进一步通过理论分析得到，发现该信息熵函数存在一个0到1之间的阈值，使得平均观测量小于该阈值时，信息熵函数单调，重构准确率会随着c₁/c₂的增加而增加，并随着c₁/c₂趋于无穷而达到最大值。但是，如果平均观测量大于该阈值时，信息熵函数不单调，此时对每一个驻点、每一个边界点对应的函数值进行比较后发现重构准确率会在c₁/c₂趋于0时达到局部最大值，并在趋向于无穷时达到全局最大值。

上述结论表明当观测到单层聚合网络和两层中的任意一层时，可以更有效地对多层网络进行重构。图4a和图4b分别展示了对两个真实多层网络的实验结果，均验证了上述理论分析，其中不同的彩色记号代表不同平均观测量对应的实验结果，不同深度的粉色实线表示不同平均观测量对应的理论值。这些结果可以为制定观测资源分配提供有效策略，从而获得对多层网络的最优重构。

图4. 不同分配策略在真实多层网络上的重构结果。a 对伦敦多层交通网络的重构结果。b 对秀丽隐杆线虫神经网络的重构结果。c 多层网络中局部观测量取不同比值 c₁/c₂ 时的示例。

5. 结语

本文设计了基于期望最大化算法的多层网络重构方法，并分析了多层网络结构特征对重构准确率的影响。然后，基于对不完全信息下多层网络结构信息熵的理论分析，获得了一个综合了多层网络微观和中观结构的区分度指标，一般性地决定了重构的准确率。对于该可重构性的分析，可以在给定的观测资源总量下，制定最佳的分配策略，以获得对多层网络的最优重构。本文的结果为多层网络的结构与可重构性之间的关系提供了新的见解，揭示了多层网络可重构性与其结构特征之间的本质关系。本文提出的方法可以在从生物学、社会学等许多不同的领域中产生更广泛的影响，包括链路预测、丢失连接恢复、异常连接定位等。

参考文献

[1] Boccaletti S, Bianconi G, Criado R, et al. The structure and dynamics of multilayer networks[J]. Physics reports, 2014, 544(1): 1-122.

[2] Moreno Y, Perc M. Focus on multilayer networks[J]. New Journal of Physics, 2019, 22(1): 010201.

[3] Buldyrev S V, Parshani R, Paul G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028.

高阶网络读书会启动

随着对现实世界的探索不断深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元交互关系，也广泛存在多个体同时（或以特定顺序）进行交互，即高阶交互现象。为此，研究人员分别发展出了基于超图、单纯复形、依赖关系等的网络高阶表示模型，为复杂网络分析和研究提供了新的思路。为了促进此领域的交流与合作，我们发起了【高阶网络读书会】。

集智俱乐部读书会是面向广大科研工作者的系列论文研读活动，其目的是共同深入学习探讨某个科学议题，激发科研灵感，促进科研合作。【高阶网络读书会】由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，每周分享时间为每周四 19:30-21:30 进行，预计持续 10-12 周。这其间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本次读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。