复杂网络研究新方向：全齐性子网络

原创范天龙集智俱乐部

导语

近日，知名学者史定华（第一作者）、吕琳媛和陈关荣（通讯作者）共同在《国家科学评论》（National Science Review）上在线发表了名为《Totally homogeneous networks》的新文章。作者借鉴庞加莱的"剖分"思想，从圈结构的视角出发，把网络分解为全齐性子网络，并提出向量空间作为表示网络的新方法，以此开创新的网络研究框架。这项工作将代数拓扑引入网络科学的研究中，体现了物理、数学、计算机等多学科交叉融合的价值。本文系对这一研究工作的解读。

论文原文：

Dinghua Shi, Linyuan Lü and Guanrong Chen, Totally homogeneous networks. Natl Sci Rev (April 2019) doi: 10.1093/nsr/nwz050.

https://doi.org/10.1093/nsr/nwz050

Tianlong Fan, Linyuan Lü and Dinghua Shi. Towards the cycle structures in complex network: A new perspective[J]. arXiv preprint arXiv:1903.01397, 2019.

https://arxiv.org/ftp/arxiv/papers/1903/1903.01397.pdf

网络无标度特性，或者更广泛而言网络的异质性，一直是网络研究的热点——过去是研究热点，最近是争议热点：有人对无标度本身提出质疑，也有人否认它在现实网络中的普遍性。然而网络只有异质性应该被关注？异质性对网络结构和功能真的具有人们所认为的那么重要？

人们激烈地争议着研究内容和结论，却忽视了对于研究视角的考察。或许这才是更重要的问题。越来越多的研究指出，在中观和介观尺度下，同质性的各种网络子结构，才是造成网络特性和功能差异的关键。

毫无疑问，网络具有度分布异质性，但这对于理解和研究网络远远不够。我们需要回过头来重新审视网络研究的视角，跳出桎梏，矫正视角，锋利工器，为网络研究开辟更广阔的新天地。

一、复杂网络与网络异质性

何谓“复杂网络”？

所谓复杂网络，即是将一个系统中的大量实体及它们之间的相互作用关系分别表示为节点和连边后所得到的网络表示。无论这个系统来自自然界还是人类社会，例如大量病历的分析处理、基因组测序、电力网络设计、交易数据分析和社交网络好友推荐等，都不用考虑这些实体间的交互关系在现实系统中表现出来的巨大差异，而从统一的视角对这些网络进行分析和研究。

图1 网络复杂性及其应用，来源[1]

网络科学的理论及方法让我们能够更加深入地理解复杂系统的结构特征与演化机理，并对一些复杂系统中的传统问题提供超越原有认知范畴的解决方案。

复杂网络的独特之处在于它立足（大）数据，将跨越计算机科学、生物学、物理学、社会学、经济学以及电子商务等多学科的专业概念和研究问题整合起来，所以在面对新兴的交叉科学难题时具有先天优势。

图2 不同类型的网络及其特性，来源[2]

复杂网络有何用？

网络是一种非常高效的对象化、结构化的数据存储结构。人脑是一个巨大的网络，万维网也同样构造成网状，这些都说明了网络是描述数据的一种极具灵活性的强大工具。网络科学能帮助人们设计更快、更有弹性的通信网络；能用于优化电力网络、电信网络和飞行航线等基础设施系统；可以为市场动态建模；能帮助理解生物系统中的同步；能用于分析人们之间的社会互动……

图3 不同类型的网络及其特性，来源[3]

“异质性”从何而来？

图4 网络同配异配性示例，来源[4]

当我们提及复杂网络的时候，必然绕不开节点和连边；当我们表示和计算网络的时候，必然绕不开邻接矩阵或邻接表。网络可以用邻接矩阵来描述，矩阵的阶数为网络中的节点数，节点的邻居数称为节点度。邻接矩阵的表示方法更容易使人们从节点及其邻居构成的邻域星结构的角度去研究网络，如无标度特性[5]。

所谓邻接，即直接相连。当我们研究矩阵和矩阵元素的时候，很多是在研究节点与邻居构成的邻域星型子结构，邻接表亦复如是。所以这种网络表示方式本身，赋予了我们一个“异质性”的视角——而这一点长久以来为人们所忽视。正因为我们一直是从本身具有“异质性偏见”的视角研究网络的，所以不难理解为什么长久以来异质性的度分布会获得广泛关注。但对事物的分析显然不能从单一角度进行，这样很容易产生片面甚至不正确的结论，有如一斑窥豹，所见仅为一斑[6]。

不可否认，以无标度特性为代表的网络异质性研究，在过去二十年中一直是网络研究的热点，也取得了丰硕成果。然而网络中只有异质性吗？答案显然是否定的，且近期对于无标度定义本身和相关结论争议四起[7-10]。导致这种争议产生的一个原因，就是因为越来越多的研究发现这种异质性的、低维度的视角对于更加深刻地认知网络复杂结构和行为还是远远不够的。

二、网络科学新方向

网络科学新视角：
圈结构

随着互联网技术发展及网络科学研究的深入，学者们发现基于星结构的传统认知模式已经不能满足现今各种网络和系统演化发展的现实及处理新近涌现出的科学问题，例如在线社交媒体上广泛存在的基于群组的“一对多”的信息传播模式、与人的高级认知功能相关的神经簇结构[11]、可控性网络子结构设计、局域物联网上的信息交换等等。

人们逐渐意识到网络的功能或各种动力学性质更多的与网络中的高阶拓扑结构、同质性子结构及网络的多个拓扑不变量等密切相关。由此转换现有的认知视角，探索并构建新的网络描述方法和研究框架，是为网络科学的当务之急。

受到庞加莱数学理念的启发，作者借鉴代数拓扑和拓扑图论的基本思想和工具提出了认知和描述网络的新视角——圈结构[12]，注意到这里的圈不仅包含一般意义上的封闭环状连边结构，也包括全连通结构，构成封闭空间的洞结构（图5c）。将网络的认知视角从节点度转移到圈之后，就会发现普遍存在的、同质性的全齐性子网络。这里，全齐性网络定义为各个节点度相等、周长相等、路和相等的一类网络。

全齐性网络的典型例子如图5所示。其中c为最小2-洞，g为8节点近邻规则网络，h为10节点同步最优网络。

图5 全齐性子网络示例

不同于微观尺度下的星结构，圈结构是一种中观或介观尺度下的网络结构，它超越了规模的限制，无论是三个节点构成的简单圈，还是300个节点构成的非冗余圈，亦或是基于封闭回路的更复杂圈结构，都被纳入这一视角。

网络表示新方法：
向量空间与边界算子

早在十九世纪末，庞加莱发现边界是区分圆盘、球面、轮胎面等几何体的关键。他先把几何体剖分成称为单(纯)形的基本组成部分(点，线，三角形，四面体，…)，从而引入了同调群、贝蒂数等多种工具并推导出欧拉-庞加莱公式，即单纯形的交错和等于贝蒂数的交错和。

图6 单纯形

庞加莱的这一思想实质上是对复杂的拓扑几何体做“剖分”，进而化繁为简进行求解。受此启发，作者对复杂网络的结构进行类似的“剖分”，让庞加莱的数学理论顺理成章地应用于网络科学研究。之所以可以这样做，一个重要的原因是，网络中大量存在的全齐性结构（图论称为团，拓扑学称为单纯形），很多时候也是支持网络功能的重要基础结构。基于这些骨干单元，作者用一系列二元域上的向量空间来描述网络。

例如，以连线为基的向量空间C1，空间维数是连线数目；以三角形为基的向量空间C2，空间维数是三角形数目，等等。由于三角形的边是连线，它（C2）和以连线为基的向量空间（C1）作为两个相邻的向量空间可通过边界算子D2 : C2—>C1来建立关联，并用边界矩阵来表示和进行研究。

图7 网络剖分过程示例来源[13]

图7展示了使用单纯形将网络G（左上）剖分成复形（左下，由不同维度的单纯形构成）的过程。当然，这个复形可进一步按照边界算子分解为多个单纯形。

图8 边界算子计算示例（点击图片可放大），来源[11]

边界矩阵比邻接矩阵具有更丰富的数学含义和更多的可用工具。例如，通过边界矩阵的秩可计算网络重要不变量之一的贝蒂数，即网络无关k洞的数目，从而确定网络的同调群Zk/Yk。图9给出了边界算子和相关子空间的关系示意图。

图9 一系列向量空间和边界算子以及子空间的关系，来源[5]

笔者认为，以往的星结构主要是基于静态的结构去研究网络的，网络的演化要通过不同的矩阵表现出来；而圈结构将交互关系视为网络的本质，它立足于动态的功能对网络展开研究。在一定程度上，可以说圈就是交互本身，它依托于结构但不完全等价于结构。正如它所表示的交互关系，除了体现在直接连边上，还包括圈上的非直连节点间的交互。所以，星结构与圈结构在哲学上也值得深入研究。

代数拓扑的引入，是对现有网络研究模式的重要补充，也是对当前研究窘境的重大突破。作者们从新的认知视角——圈结构，依托于新的网络描述工具——（不同维单形构成的）向量空间，立足于现有的网络科学理论和方法并借鉴拓扑剖分的思想，将在全维度上对网络科学进行更深入的探索。

三、拓扑方法的广阔应用

实际上，这一趋势已经在多个领域崭露出来，如数据挖掘领域中拓扑数据分析（Topological Data Analysis，简称TDA）的兴起，机器学习中图网络（Graph Network）的提出，以及在数据库领域图形数据库的流行等，都清楚地显现出这个席卷各个领域的浪潮的来临。

拓扑数据分析

拓扑学研究的是一些特殊的几何性质，这些性质在图形连续改变形状后还能继续保持不变，称为“拓扑性质”。而在复杂的高维数据内部也存在着类似的结构性质，我们可以形象地称之为数据的形状。

拓扑数据分析就是用拓扑学的理念方法对数据进行分析和信息挖掘。相比于主成分分析、聚类分析这些常用的方法，TDA不仅可以有效地捕捉高维数据空间的拓扑信息，还能够有效降低大规模数据处理的维度（而不丢失高维的信息）。

图10 拓扑数据分析示例，来源[14]

人们认为复杂数据中存在着内在固有的低维结构，由它们按照某种方式构成数据的高维形状。要理解数据的高维形状，就必须求助于拓扑分析。使用拓扑数据分析数据的过程，类似于拼图的过程——给你的只是拼图碎片，你要利用碎片间的关系拼出原来的完整图景。

目前这一方法已被用于基因表达数据分析，数据及图片的压缩感知，罕见病患者筛查以及解决评级缺失问题等。

点击查看相关推文：从拓扑数据分析到压缩感知——复杂数据处理新贵

图网络

图网络是机器学习与拓扑数据分析相结合的最新产物。图网络是在拓扑空间（Topological space）内按图（Graph）结构组织以进行关系推理（Relational reasoning）的函数集合，即一种基于图结构的广义人工神经网络。

图11 图卷积神经网络示例，来源[15]

众所周知，机器学习本身是一种“黑箱”，这也是用机器学习进行数据研究时所遭受的最主要批评，虽然它们能自动提供有用的答案，但是却不能给人类提供可解读的输出。因此，我们往往不能了解它们是如何做到的。但图网络的引入，为机器学习的关系归纳偏置过程提供了一个操作结构化知识和产生结构化行为的直接界面。这为机器学习中的关系推理、组合泛化以及更复杂的、可解释的推理模式奠定了基础——这有望为人工智能黑箱提供可解释性。图网络使我们能够了解神经网络如何执行分类任务，允许我们观察网络的学习方式。

这一最新的前沿方向正在节点嵌入（如Node2Vec），图嵌入（Graph embedding）（此两者均为向量空间中提取的单一维度）等方向快速发展，将对机器学习与人工智能产生深远影响。

相关推文：

图形数据库

图12 图数据库示例，来源[16]

不同于主流的MySQL, Oracle等关系型数据库，图形数据库是一种应用图形理论存储实体之间的关系信息的新型数据库。在传统的关系型数据库中用表来存储“关系型”数据，但其效果并不好，查询复杂、缓慢、超出预期。然而这些数据间的关系是现实世界中普遍且至关重要的一部分。图形数据库的独特设计恰恰弥补了这个缺陷，它将结构化的数据存储在网络上而不是表中。

图13 不同类型数据库比较，来源[17]

在图数据库中，这些联系是非常易于存储和查询的。此外，通常很多事物之间的联系（例如家庭成员之间的关系）构成分析问题的关键，使用图数据库使得问题分析变得简单。

代数拓扑不但能在关系数据库的构造中起到指导作用，也能在基于图形数据库存储的数据分析中发挥巨大作用。

除了以上方面，代数拓扑与复杂网络的结合也在其他学术和产业领域涌现出来，并正对相关领域产生深远影响。

◆ ◆ ◆

搜索公众号：集智俱乐部

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

让苹果砸得更猛烈些吧！

继续滑动看下一个