多层网络由于其在相互依赖系统建模中的高度实用性，在许多研究领域引起了广泛的关注。然而，多层网络的聚类，特别是使用高阶交互信息的聚类，仍处于初级阶段。相反，高阶连接性通常是多层网络应用的关键。在最近发表在PNAS上的一篇论文中，研究人员将拓扑数据分析的概念引入到复杂多层网络的研究中，并提出了一种网络聚类的拓扑方法。他们称这种方法为多层网络聚类（CPD）。CPD系统地考虑了网络层中和网络层之间节点交互的不同高阶特征，并集成了来自相邻节点的信息。研究人员通过将CPD应用于一个具有社会重要性的新问题来说明CPD的效用：在住房保险索赔的背景下对房屋进行分区，以表示天气和气候造成的风险。
论文题目：
多层网络的拓扑聚类
论文地址：
https//www.pnas。comorg/content/118/21/e2019994118
1.有些网络是复杂的、高度结构化的
现代社会中的许多系统具有复杂且高度相互依赖的结构[1-7]，多层网络可用于对这些结构进行建模。因此，研究人员对使用复杂的多层网络进行跨学科分析有着浓厚的兴趣。多层网络考虑多层连接（即网络）网络的每一层之间的关系表示一个系统或子系统。由于关键基础设施的安全性和抵御自然灾害、恐怖活动和网络威胁的能力[8-14]，当今多层网络研究的主要目标之一是更好地了解多层网络的哪些部分更重要，更容易受到特定危害，并制定积极的策略以实现最佳分区，从而隔离不健康的系统组件并降低进一步故障传播的风险[15-17]。
与单层网络的情况类似，多层网络聚类的目的是揭示有意义的节点分组模式，并通过考虑节点之间可能涉及的不同交互模式将节点划分为社区。然而，与单层网络相比，多层网络的集群仍然是一个相对不发达的领域[18-24]。多层网络集群带来了新的挑战。首先，多层网络的划分需要考虑同一层中节点之间的关系以及不同层之间的节点间的相互作用。其次，多层网络中的不同层可能表现出不同的局部和全局结构特征。最后，高阶网络通常显示更强的社区存在信息。
2.提出了多层网络的拓扑聚类方法
为了应对这些挑战，研究人员将分析拓扑数据（拓扑数据分析，TDA）将网络聚类的概念引入到复杂多层网络的研究中，提出了一种网络聚类的拓扑方法。TDA是代数拓扑和数据科学中的一种新方法[31-34]。它提供了一种数学上严格的机制来分析数据形状。特别是，TDA允许人们分析和观察数据的拓扑和几何特征，从而更深入地了解数据生成过程背后的隐藏机制。[35-38]
拓扑网络聚类的核心思想是根据最近邻节点的形状相似性对其进行分组。特别地，该算法基于持久图，采用拓扑方法比较每个节点的局部拓扑和周围的几何结构，因此被称为“使用持久图”群集”（持续专业发展）。CPD方法不仅可以系统地计算网络层内和层间的异构高阶特征，而且可以集成来自相邻节点及其交互的重要信息。[39-41]
研究人员解释了他们的cpd算法的应用以及拓扑概念在复杂网络聚类中的实用性。他们以住房保险中的多层网络为例。通过引入基于气候条件和住房保险变量的多层复杂网络，研究人员基于拓扑cpd方法划分住房。与基于简单地理邻近性的传统工具相比，基于环境和社会人口特征相似性的风险地图能够更准确地模拟气候风险。
1.多层网络
研究人员利用图对单层网络进行建模，得到对称邻接矩阵a，然后利用多层图对多层网络进行建模。多层图是一组加权的单层图邻接矩阵，包括层内关系和层间交互。最后，多层网络采用矩阵块结构的超邻接矩阵形式。[49-53]
2.基于相似度的网络
可以使用各种连接和度量来定义多层网络中边之间的权重。当没有应用驱动的边缘概念时，通常是基于节点间的相似性ω来构造边缘，从而形成所谓的基于相似性的网络。最广泛使用的相似性度量之一是相关系数，基于相关网络的应用范围从金融[54-56]到脑科学[57-59]气候学[60-62]。研究人员使用类似的方法对气候保险多层网络进行了具体的案例研究，并基于观测变量的非线性非参数变换获得了最大相关性。
3.节点嵌入
从复杂网络中提取有意义的信息需要大量的计算和存储空间。节点嵌入将复杂网络转化为低维空间，同时保留结构信息，为这两个问题提供了解决方案。节点嵌入的方法可以分为两类：矩阵分解法（矩阵分解法）随机游走法（随机游走法）[64-65]。研究人员使用多层网络嵌入（多层网络嵌入），这是多层网络矩阵分解的一种扩展形式。
4.基于持久性图的聚类（CPD）
研究人员提出了一种多层网络聚类方法，如图1所示。研究人员的目标是从多分辨率记录数据的形状相似性的角度，在无监督的环境中对多层网络进行聚类。为了在不断变化的相似尺度上系统地量化多层网络的形状动力学，研究人员将拓扑数据分析的多镜头工具引入到聚类方法中。[69-70]
图1三层网络cpd算法流程图
研究人员重点关注将多层网络分析和拓扑聚类应用于实际住房保险数据的结果。他们在10年内学习了大约10年(2002-2011)加拿大安大略省504前向分类区提供因降雨损害而导致的住房保险索赔信息，并消除社会人口增长和通货膨胀影响。
索赔数量和损失分布在空间上是相同的（图2）。在所有考虑的变量中，信用评分的空间格局最不明显，而降水的空间格局最强，表现在东南部（方向）安大略伊利湖地区；图2）增加。
图2变量的空间分布
图3显示了不同聚类算法提供的加拿大安大略省的聚类数量及其空间位置。这四种方法都倾向于安大略一个大的集群形成于西北部。为了从不同的方法分析聚类，研究人员研究了聚类中各种属性均值的差异。
图3加拿大安大略省南部邮政区的集群标签：（a）k-pawm，（b）CPD，（c）AndyLau和（d）k-medoids
CPD形成两大类（第1组和第2组），占地面积超过70%（表3）。两个集群的降水量、信用评分、平均索赔数量和每次索赔的平均损失是相似的，但第二类位于安大略省的城市地区，房屋年龄高于平均年龄。第三类的平均降雨量最高，因此索赔的平均数量最高，每个地区的平均损失最高。值得注意的是，与其他三种聚类方法相比，聚类中CPD属性的可变性较小。
在本文中，研究人员将拓扑数据分析工具的新兴机制引入到复杂多层网络的分析中，并开发了一种拓扑聚类算法cpd。它基于拓扑数据分析持久图的概念和多层网络中固有数据形状的多镜头比较。他们验证了CPD方法相对于欧几里德距离传统算法的实用性。此外，它们基于拓扑相似性度量（即瓦瑟斯坦距离）提出了一种改进的聚类算法k-pawm。他们发现，当数据显示复杂的时空相关结构时，两种拓扑方法（即cpd和k-pawm）是传统集群工具的竞争替代品。
未来，他们计划将提出的拓扑方法扩展到动态多层网络的聚类，并证明拓扑聚类的稳定性保证。另一个有趣的方向是基于相似性的聚类，通过对群体中具有较少或更多共同形状特征的点进行分组（基于相似性的凝聚聚类）[71-73]与持续专业发展相结合。研究人员相信这种聚类在生物医学成像中是有用的（例如肿瘤检测）可能在某些情况下特别有用。他们认为拓扑和几何方法为复杂多层网络的建模、分析和推理开辟了许多新的发展空间。
作家潘佳栋
邓一雪，编辑
业务合作及稿件转载（swarma@swarma.org
◆◆◆
搜索公众号：奇奇俱乐部
加入“无墙学院”
赠送苹果用力点！
