导语

多层网络因其在相互依赖系统建模中的高实用性，被广泛应用于许多研究领域。然而，多层网络聚类，尤其是使用高阶交互信息的聚类，仍处于起步阶段。相反，高阶连接通常是多层网络应用的关键。在PNAS最近发表的一篇论文中，研究人员将拓扑数据分析的概念引入到复杂多层网络的研究中，并提出了一种网络聚类的拓扑方法，他们称之为多层网络聚类(CPD)。CPD系统地考虑了网络层内部和网络层之间节点交互的不同高阶特性，并整合了来自相邻节点的信息。研究人员通过将CPD应用于一个具有社会重要性的新问题来说明CPD的效用：在家庭保险理赔的背景下，房屋被划分为多个区域，以显示天气和气候造成的风险。

论文题目：

多层网络的拓扑聚类

论文地址：

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

一、背景

1.一些网络具有复杂且高度结构化的结构。

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

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

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

为了应对这些挑战，研究者将拓扑数据分析(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◆ ◆ ◆

搜索公众号：集智俱乐部

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

让苹果砸得更猛烈些吧!