网络科学新视角:圈结构
随着互联网技术发展及网络科学研究的深入,学者们发现基于星结构的传统认知模式已经不能满足现今各种网络和系统演化发展的现实及处理新近涌现出的科学问题,例如在线社交媒体上广泛存在的基于群组的“一对多”的信息传播模式、与人的高级认知功能相关的神经簇结构、可控性网络子结构设计、局域物联网上的信息交换等等。
人们逐渐意识到网络的功能或各种动力学性质更多的与网络中的高阶拓扑结构、同质性子结构及网络的多个拓扑不变量等密切相关。由此转换现有的认知视角,探索并构建新的网络描述方法和研究框架,是为网络科学的当务之急。
受到庞加莱数学理念的启发,作者借鉴代数拓扑和拓扑图论的基本思想和工具提出了认知和描述网络的新视角——圈结构,注意到这里的圈不仅包含一般意义上的封闭环状连边结构,也包括全连通结构,构成封闭空间的洞结构(图5c)。将网络的认知视角从节点度转移到圈之后,就会发现普遍存在的、同质性的全齐性子网络。这里,全齐性网络定义为各个节点度相等、周长相等、路和相等的一类网络。 不同于微观尺度下的星结构,圈结构是一种中观或介观尺度下的网络结构,它超越了规模的限制,无论是三个节点构成的简单圈,还是300个节点构成的非冗余圈,亦或是基于封闭回路的更复杂圈结构,都被纳入这一视角。
网络表示新方法:向量空间与边界算子
早在十九世纪末,庞加莱发现边界是区分圆盘、球面、轮胎面等几何体的关键。他先把几何体剖分成称为单(纯)形的基本组成部分(点,线,三角形,四面体,…),从而引入了同调群、贝蒂数等多种工具并推导出欧拉-庞加莱公式,即单纯形的交错和等于贝蒂数的交错和。 庞加莱的这一思想实质上是对复杂的拓扑几何体做“剖分”,进而化繁为简进行求解。受此启发,作者对复杂网络的结构进行类似的“剖分”,让庞加莱的数学理论顺理成章地应用于网络科学研究。之所以可以这样做,一个重要的原因是,网络中大量存在的全齐性结构(图论称为团,拓扑学称为单纯形),很多时候也是支持网络功能的重要基础结构。基于这些骨干单元,作者用一系列二元域上的向量空间来描述网络。
例如,以连线为基的向量空间C1,空间维数是连线数目;以三角形为基的向量空间C2,空间维数是三角形数目,等等。由于三角形的边是连线,它(C2)和以连线为基的向量空间(C1)作为两个相邻的向量空间可通过边界算子D2 : C2—>C1来建立关联,并用边界矩阵来表示和进行研究。 图7展示了使用单纯形将网络G(左上)剖分成复形(左下,由不同维度的单纯形构成)的过程。当然,这个复形可进一步按照边界算子分解为多个单纯形。 边界矩阵比邻接矩阵具有更丰富的数学含义和更多的可用工具。例如,通过边界矩阵的秩可计算网络重要不变量之一的贝蒂数,即网络无关k-洞的数目,从而确定网络的同调群Zk/Yk。图9给出了边界算子和相关子空间的关系示意图。
以往的星结构主要是基于静态的结构去研究网络的,网络的演化要通过不同的矩阵表现出来;而圈结构将交互关系视为网络的本质,它立足于动态的功能对网络展开研究。在一定程度上,可以说圈就是交互本身,它依托于结构但不完全等价于结构。正如它所表示的交互关系,除了体现在直接连边上,还包括圈上的非直连节点间的交互。所以,星结构与圈结构在哲学上也值得深入研究。
代数拓扑的引入,是对现有网络研究模式的重要补充,也是对当前研究窘境的重大突破。作者们从新的认知视角——圈结构,依托于新的网络描述工具——(不同维单形构成的)向量空间,立足于现有的网络科学理论和方法并借鉴拓扑剖分的思想,将在全维度上对网络科学进行更深入的探索。
拓扑方法的广阔应用
实际上,这一趋势已经在多个领域崭露出来,如数据挖掘领域中拓扑数据分析(Topological Data Analysis,简称TDA)的兴起,机器学习中图网络(Graph Network)的提出,以及在数据库领域图形数据库的流行等,都清楚地显现出这个席卷各个领域的浪潮的来临。
1.拓扑数据分析
拓扑学研究的是一些特殊的几何性质,这些性质在图形连续改变形状后还能继续保持不变,称为“拓扑性质”。而在复杂的高维数据内部也存在着类似的结构性质,我们可以形象地称之为数据的形状。
拓扑数据分析就是用拓扑学的理念方法对数据进行分析和信息挖掘。相比于主成分分析、聚类分析这些常用的方法,TDA不仅可以有效地捕捉高维数据空间的拓扑信息,还能够有效降低大规模数据处理的维度(而不丢失高维的信息)。 人们认为复杂数据中存在着内在固有的低维结构,由它们按照某种方式构成数据的高维形状。要理解数据的高维形状,就必须求助于拓扑分析。使用拓扑数据分析数据的过程,类似于拼图的过程——给你的只是拼图碎片,你要利用碎片间的关系拼出原来的完整图景。
目前这一方法已被用于基因表达数据分析,数据及图片的压缩感知,罕见病患者筛查以及解决评级缺失问题等。
2.图网络
图网络是机器学习与拓扑数据分析相结合的最新产物。图网络是在拓扑空间(Topological space)内按图(Graph)结构组织以进行关系推理(Relational reasoning)的函数集合,即一种基于图结构的广义人工神经网络。
众所周知,机器学习本身是一种“黑箱”,这也是用机器学习进行数据研究时所遭受的最主要批评,虽然它们能自动提供有用的答案,但是却不能给人类提供可解读的输出。因此,我们往往不能了解它们是如何做到的。但图网络的引入,为机器学习的关系归纳偏置过程提供了一个操作结构化知识和产生结构化行为的直接界面。这为机器学习中的关系推理、组合泛化以及更复杂的、可解释的推理模式奠定了基础——这有望为人工智能黑箱提供可解释性。图网络使我们能够了解神经网络如何执行分类任务,允许我们观察网络的学习方式。
这一最新的前沿方向正在节点嵌入(如Node2Vec),图嵌入(Graph embedding)(此两者均为向量空间中提取的单一维度)等方向快速发展,将对机器学习与人工智能产生深远影响。
3.图形数据库 不同于主流的MySQL, Oracle等关系型数据库,图形数据库是一种应用图形理论存储实体之间的关系信息的新型数据库。在传统的关系型数据库中用表来存储“关系型”数据,但其效果并不好,查询复杂、缓慢、超出预期。然而这些数据间的关系是现实世界中普遍且至关重要的一部分。图形数据库的独特设计恰恰弥补了这个缺陷,它将结构化的数据存储在网络上而不是表中。 在图数据库中,这些联系是非常易于存储和查询的。此外,通常很多事物之间的联系(例如家庭成员之间的关系)构成分析问题的关键,使用图数据库使得问题分析变得简单。
代数拓扑不但能在关系数据库的构造中起到指导作用,也能在基于图形数据库存储的数据分析中发挥巨大作用。
除了以上方面,代数拓扑与复杂网络的结合也在其他学术和产业领域涌现出来,并正对相关领域产生深远影响。
相关工作
作者们的探索最早源于2002年由汪小帆和陈关荣发现的网络同步准则。那么,什么样的网络最容易同步呢?2013年,史定华,陈关荣和阎小勇等通过优化引入了全齐性网络,发现周长越长、路和越短的全齐性网络在网络规模相同情况下同步能力最优。2016年,吕琳媛和周涛等借助H算子建立了节点的度,H-指数和核数的内在联系,即网络的DHC定理。
在研究圈数指标的过程中,新近一项重要工作是Bassett研究组的Sizemore等人于2018年发表的对大脑功能网络的实证研究,他们发现了网络中团和洞的特殊重要性。
2019年,范天龙,吕琳媛和史定华提出圈结构的网络研究新视角,并对基于圈的指标进行了系统研究,提出刻画网络圈结构的圈数矩阵和衡量节点重要性的圈指标。
同年,史定华,吕琳媛和陈关荣提出向量空间与边界算子,定义了网络中的拓扑运算与拓扑不变量。
一路走来,从源于物理的网络同步准则,经由优化导出了全齐性网络,其重要性得到大脑网络的实证检验,最终归结为代数拓扑的不变量指标。这一系列的成果本身就体现了物理、生物、数学等多学科交叉融合的意义和网络科学的价值,也预示着网络科学在代数拓扑的加持下,将重新焕发更耀眼的光彩。
参考资料:http://swarma.blog.caixin.com/archives/206178