导语

由于在建模相互依赖的系统方面具有很高的实用性，多层网络在许多研究领域中受到广泛。但是，多层网络的聚类，尤其是使用高阶交互信息的聚类，仍处于起步阶段。反过来，高阶连接通常是多层网络应用程序的关键。最近一篇发表于 PNAS 的论文中，研究人员将拓扑数据分析的概念引入到复杂的多层网络的研究中，提出了一种网络聚类的拓扑方法，他们将这种方法称为基于持续性图的聚类（clustering of multilayer networks，CPD）。CPD系统地考虑了网络层内和网络层之间节点交互的不同的高阶特性，并集成了来自近邻节点的信息。研究人员通过将CPD应用于一个具有社会重要性的新问题来说明CPD的效用：在房屋保险理赔的背景下，对房屋进行分区，以表示天气和气候引起的风险。

论文题目：

Topological clustering of multilayer networks

论文地址：

https://www.pnas.org/content/118/21/e2019994118

一、背景

1. 一些网络具有复杂和高度结构

现代社会中的许多系统都具有复杂且高度相互依赖的结构[1-7]，多层网络可以用来对这些结构进行建模。因此，研究人员对使用复杂多层网络进行跨学科分析产生了浓厚的兴趣。多层网络考虑了多层连接（即网络）之间的关系，其中每一层网络代表一个系统或子系统。由于关键基础设施对抵御自然灾害、恐怖活动和网络威胁的安全性和抵抗力方面的需求[8-14]，当今多层网络研究的主要目标之一是更好地了解多层网络中哪些部分更为重要，更易受特定危害的影响，并制定积极的策略以实现最佳分区，从而隔离不健康的系统组件并降低进一步故障传播的风险[15-17]。

与单层网络的情况类似，多层网络聚类的目的是揭示有意义的节点分组模式，并通过考虑节点之间可能涉及的不同交互方式将节点划分为社区。不过，与单层网络相反，多层网络的聚类仍然是一个相对欠发达的领域[18-24]。多层网络聚类提出了新的挑战。首先，多层网络的划分需要考虑到同一层中节点之间的关系以及不同层中节点之间的相互作用。其次，多层网络中不同层可能表现出不同的局部和全局结构特性。最后，高阶网络通常显示出更强的社区存在信息。

2. 多层网络的拓扑聚类的提出

为了应对这些挑战，研究人员将拓扑数据分析（topological data analysis，TDA）的概念引入到复杂的多层网络的研究中，并提出了一种网络聚类的拓扑方法。TDA是代数拓扑和数据科学[31-34]的一种新兴方法，它提供了一种数学上严格的机制来分析数据形状。尤其是，TDA允许人们分析观察数据的拓扑和几何特性，从而更深入地了解数据生成过程背后的隐藏机制。[35-38]

拓扑网络聚类背后的关键思想是根据近邻节点形状相似程度对其进行分组。特别是，该算法使用拓扑方法基于持续性图对每个节点周围的局部拓扑和几何进行比较，因此被称为“使用持续性图的聚类”（CPD）。CPD方法既可以系统地计算网络层内部和网络层之间的异构高阶特性，又可以集成来自近邻节点及其相互作用的重要信息。[39-41]

研究人员说明了他们的CPD算法的应用以及拓扑概念在复杂网络聚类中的实用性。他们以多层网络在房屋保险中为例进行说明。研究人员通过引入基于气候条件和房屋保险变量的多层复杂网络，基于拓扑CPD方法对房屋进行分区。与基于简单地理邻近度的传统工具相比，基于环境和社会人口统计学特征相似度的风险图可以更准确地模拟气候风险。

二、多层网络拓扑聚类的算法实现

1. 多层网络

研究人员使用图建模单层网络，得到一个对称的邻接矩阵A。之后，他们使用多层图建模多层网络，多层图是带有权重的单层图邻接矩阵的一个集合，包含层内关系和层间相互作用。最终，多层网络为具有矩阵块结构的超邻接矩阵的形式。[49-53]

2. 基于相似度的网络

可以使用各种联系和度量来定义多层网络中边之间的权重。在不存在应用驱动的边的概念的情况下，通常基于节点之间的相似度ω来构建边，从而形成所谓的基于相似度的网络。一种最广泛使用的相似性度量是相关系数，基于相关网络的应用范围从金融[54-56]到脑科学[57-59]到气候学[60-62]。研究人员使用类似的方式进行气候保险多层网络的具体案例研究，并基于观测变量的非线性非参数转换获得的最大相关性。

3. 节点嵌入

从复杂的网络中提取有意义的信息需要大量的计算量和内存空间。节点嵌入在保留结构信息的同时将复杂网络转换为低维空间，从而为解决这两个问题提供了方案。节点嵌入的方法可以分为两类：矩阵分解方法（matrix factorization methods）和随机游走方法（random walk methods）[64-65]。研究人员使用多层网络嵌入（multilayered network embedding），这是多层网络矩阵分解的扩展形式。

4. 基于持续性图的聚类（CPD）

研究人员提出了一种多层网络聚类方法，如图1所示。研究人员的目标是从以多种分辨率记录的数据形状相似性的角度，在无监督的环境中对多层网络进行聚类。为了在不断变化的相似度尺度上系统地量化多层网络的形状动力学，研究人员将拓扑数据分析的多透镜工具引入聚类方法中。[69-70]

图1. 三层网络CPD算法的流程图

三、多层网络的拓扑聚类的应用

研究人员重点介绍了将多层网络分析和拓扑聚类应用于真实房屋保险数据的结果。他们研究有关在10年内（2002年至2011年）加拿大安大略省504个正向分拣区因降雨破坏而造成的房屋保险索赔的信息，并通过对数据进行处理的方式消除了社会人口增长和通货膨胀的影响。

索赔数量和损失的分布在空间上是相同的（图2）。在所有考虑的变量中，信用评分的空间格局最不明显，而降水的空间格局最强，表现出在东南方向（朝向安大略湖和伊利湖地区；图2）的增加。

图2. 变量的空间分布

图3展示了由不同聚类算法提供的加拿大安大略省的聚类数量及其空间位置。四种方法都倾向于在安大略省的西北部形成一个大型簇。为了从不同的方法中分析聚类，研究人员研究了聚类中各种属性均值的差异。

图3. 加拿大安大略省南部的邮政区域的聚类标签：（A）K-PaWM、（B）CPD、（C）Hierarchical和（D）K-medoids

CPD形成了两个大型类（集群1和集群2），占据超过70％的区域（表3）。这两个集群的降水量、信用评分、平均索赔数和平均每项索赔损失相似，但是第二个类位于安大略省的城市地区，房屋年龄高于平均年龄。第三类的平均降水量最高，因此平均索赔数最高，每个地区的平均损失也最高。值得注意的是，与其他三种聚类方法相比，CPD的属性在聚类内的变异性要小。

四、结论

在本文中，研究人员将拓扑数据分析工具的新兴机制引入到复杂多层网络的分析中，开发了一种拓扑聚类算法，即CPD。它基于拓扑数据分析持续性图概念，基于多层网络中固有数据形状的多透镜比较。他们验证了CPD方法相对于基于欧几里得距离的传统算法的实用性。此外，他们基于拓扑相似性度量（即Wasserstein距离）提出了一种聚类算法的修改版本K-PaWM。他们发现，当数据表现出复杂的时空相关结构时，两种拓扑方法（即CPD和K-PaWM）都是传统聚类工具的竞争替代品。

将来，他们计划将提出的拓扑方法扩展到动态多层网络的聚类中，并证明拓扑聚类的稳定性保证。另一个有趣的方向是通过对总体中具有较少或更多共同形状特征的点进行分组，将基于相似性的聚类（similarity-based agglomerative clustering）[71-73]与CPD相结合。研究人员认为这种聚类在生物医学成像（例如肿瘤检测）中可能特别有用。他们认为拓扑和几何方法为复杂的多层网络的建模、分析和推理开辟了许多新的发展空间。

潘佳栋 | 作者

邓一雪 | 编辑

商务合作及投稿转载｜swarma@swarma.org◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧!