查看原文
其他

陈关荣:探讨复杂网络的高阶拓扑及其应用

​陈关荣 集智俱乐部 2022-05-09


导语


网络科学有助于我们更好地理解当今高度互联世界的演变,高阶相互作用对网络系统的动力学研究产生了重大影响,打破了原始单一类型成对交互的网络拓扑分析的局限性,为复杂网络的交互分析提供了新的思路。本文整理了陈关荣教授在2021年复杂网络学术会议中的报告,介绍了复杂网络高阶拓扑的相关概念,如何利用高阶拓扑解决网络同步问题,并且概述了高阶拓扑在脑科学、生态学、社会科学等多领域的应用。

 集智学园特邀陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华等网络科学专家作为导师,自10月16日起开展“网络科学第三期”系列在线课程,介绍复杂网络的建模与应用以及相关课题。欢迎希望进入网络科学领域、提高网络分析能力、与一线专家探讨问题的朋友报名参加!


研究领域:网络科学,高阶相互作用,网络同步问题,脑科学,生态学,社会科学

陈关荣 | 讲者

高爽 | 整理

梁金 | 审校

邓一雪 | 编辑


目录:
一、复杂网络高阶拓扑概述
二、高阶拓扑解决网络同步问题
三、高阶拓扑的多领域应用:脑科学、生态学、社会科学
四、总结展望



一、复杂网络高阶拓扑概述




在过往的研究中,人们常常用网络将许多自然、科学和技术等系统的复杂相互作用形象地描述出来。然而,从人类交流到化学反应和生态系统,相互作用的单位往往以三个或三个以上的节点组成,不能简单地用两个个体的关系来描述。近来,真实复杂系统的高阶结构逐渐被人们所关注。越来越多的证据表明,对复杂系统的高阶拓扑结构研究,可以增强我们针对复杂系统的建模能力,更好地理解、分析和预测其动态行为。在这里我们尝试用复杂网络的高阶拓扑结构,明确而又自然地描述群体之间的相互作用。


图论基本概念


度(Degree):节点的连边数;

距离(Distance):两节点之间最短路径连边数的总数;

路和(Path-sum):节点到其它节点距离的总和;

圈(Cycle):闭路径;

周长(Girth):经过某节点的最短圈长;

团(Clique):全连接的子图;团也称为单纯形或单形(Simplex),在接下来的分析过程中,以单纯形为边界的复合图形称为单纯复形。

洞(Cavity):不是团的最小无关圈。


(本文只讨论无向网络)
图1 网络结构示意图


我们可以根据网络结构,得到它的节点度矩阵 D 和表示节点-节点关系的邻接矩阵 A,以及拉普拉斯矩阵 L,它们之间的关系:L=D-A。也可以得到表示节点-连边关系的关联矩阵 M。那么针对高阶情况,我们可以研究连边-三角形、三角形-三角形、三角形-四面体以及四面体-四面体等高阶团之间的关系来构建关联矩阵,从而进行复杂网络的分析。
 

具体表示方法为:以“团”为基本单元,建立一系列二元域上的向量空间。其中:

· 以节点为基所得向量空间 C0,其维数是网络中的节点数目

· 以连边为基所得向量空间 C1,其维数是网络中的连线数目

· 以三角形为基的向量空间 C2,其维数是网络中三角形数目

· 以四面体为基的向量空间 C3,如此类推
 
在此基础上引进运算规则:二元域是整数模 2 的域,只有元素 0 和 1,满足 0+0=0, 0+1=1, 1+0=1, 1+1=0。需要注意的是,向量空间中的加法,与数的计算不同,需要用集合论的观点来理解。两向量 c、d 的加法,其和是两个子集的对称差,即 c+d=(c∪d)-(c∩d)。
 
根据上述方法,构建了维数不同的两个空间之后,便可以引入边界算子 ,建立两个向量之间的联系。这里的边界算子可以认为是一个投影算子,将高阶向量空间中一个基本单位,投影到下一阶的向量空间中,刻画它们之间的边界。 
 
这样,可以用边界算子来定义圈:如果 L 在边界算子作用后等于 0,即,那么 L 就是一个圈 。进而,我们可以清晰地理解洞的概念。洞首先是一个圈,然后是在二元域运算意义下与其他圈为线性无关的一个最小的圈,最后它不是一个团。

图2. 网络中各阶圈、团、洞、边界示意图

基于此,我们可以通过边界算子把串联起来的向量空间用边界矩阵来表示,并在二元域上进行初等行列变换,计算出矩阵的秩。根据网络的维数和秩,我们可以引入网络不变量:
 

  · 示性数:网络各阶团的数目分别记为 m0(节点数),m1(连线数),m2(三角形数),m3(四面体数)等等,则示性数公式为:

  · 贝蒂数(Betti):网络各边界矩阵的秩分别记为 r0=0(约定),r1(点线矩阵),r2(线面矩阵),r3(面体矩阵),等等。则贝蒂数公式为:

其中β0为连通子块数目,β1为1洞的数目,β2为2洞的数目,等等。
 
这样,我们就可以根据上面所阐述的概念,通过高阶拓补结构来分析复杂网络。
 
 



二、高阶拓扑解决网络同步问题




人们已经注意到,大量现实世界中的复杂网络或其子网络具有诸多优良的动力学性质,比如动态同步性强、可控性好、抗攻击能力强、信息传输速度快、协作自然涌现等。网络同步问题已然成为研究的热点。
 

· 全齐网络是同步最优网络


全齐网络是所有节点具有相同的度(degree),路和(path-sum),周长(girth)的网络,具有对称和均匀的特点。
 
图3 全齐网络示例
 
将全齐网络和其他网络结构进行对比,可以得到一个一般规律:全齐网络的同步能力优于随机网络,再优于小世界网络,较差的为规则网络。
 
图4 不同网络的同步能力比较
D.H. Shi, G. Chen, W.W.K. Thong, X.Y. Yan, Searching for optimal network topology with best possible synchronizability, IEEE Circ. Syst. Mag. 13(1): 66-75, 2013
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6468141
 
通常在网络同步能力的比较中,谱隙和特征比越大,显示网络同步能力越好。但是因为特征比的同步域取值区间有可能是多个区间的并集,用特征比作为网络能力评判标准时,偶尔会出现不准确性。研究发现采用示性数可以十分清晰准确地表示不同网络的同步能力。于是得到以下结论:网络规模相同条件下,影响网络同步能力的关键因素是网络不变量之一的示性数,示性数越小网络越容易同步。
D. H. Shi, L. Y. Lyu, G. R. Chen, Totally homogeneous networks, National Science Review (2019)
https://arxiv.org/ftp/arxiv/papers/1903/1903.11289.pdf


· 复杂网络中的高阶组织结构


许多网络展示了丰富的、可以在单个节点级别捕获的低阶链接模式和边界信息。但是复杂网络的高阶组织结构和特性很大程度上仍然未知。下面这篇文章建立了一个通用的基于高阶连接模式的聚类网络模型,揭示了许多网络中存在的高阶组织(例如神经元网络信息传播和交通枢纽结构网络),发现网络模型通过基于高阶聚类连接模式表现出丰富的高阶组织结构,并且对于高达数十亿条边的大规模网络的集群最优性提供数学根据。
 
图5 高阶网络结构和高阶网络聚类框架
A.R. Benson, D.F. Gleich, J. Leskovec, Higher-order organization of complex networks, Science, 353: 163-166, 2016
https://www.science.org/doi/epdf/10.1126/science.aad9029
 
我们特别推荐一篇综述文章“Networks beyond pairwise interactions: Structure and dynamics”,可以从这篇文章开始了解高阶拓扑。
 
这篇综述全面介绍了新兴的超越节点对相互作用的网络领域,讨论了如何表示高阶相互作用, 并介绍描述高阶系统的框架(例如随机和增长型二分图、超图和单纯复形),介绍了高阶动力系统和拓扑动力学,研究了高阶互动与群集行为之间的关系。特别着重描述了动态过程的新现象,如扩散、同步、传播、社会动态和博弈,以及当它们扩展到超出点对相互作用时的情形,并介绍它们的相关应用。
 
图6 高阶相互作用的表现形式
F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, G. Petri, Networks beyond pairwise interactions: Structure and dynamics, Physics Reports, 847: 1-92, 2020
https://arxiv.org/abs/2006.01764v1


· 耦合高阶单纯复形上拓扑信号的同步


从大脑到社交网络,单纯复形能很好地描述复杂的底层网络拓扑和几何。代数拓扑是一个研究单纯复形高阶动力学的基本工具。考虑拓扑信号,即定义在不同的单纯形上的动态信号,发现在节点和连边之间边界耦合上定义的信号可以导致爆炸性的拓扑同步、实现相位转换和同步。发展了一个全面的理论和方法,可在全连接网络和随机网络上预测这种转变。
 
R. Ghorbanchian, J.G. Restrepo, J.J. Torres, G. Bianconi, Higher-order simplicial synchronization of coupled topological signals, Comm. Phys., 4: Paper 120, 2021
https://arxiv.org/abs/2011.00897v2


· 高维单纯复形上 Kuramoto 振子的相位同步

图7 Kuramoto 模型的推广
 
此文中的理论不仅完整地描述和揭示了迄今为止通过成对相互作用所观察到的各种现象的内在原因和机制,而且还为单纯形结构中一系列丰富而新颖的行为提供了预测。这些行为包括:在所有维度的耦合强度为正值时的不连续解的同步过渡;在所有奇数维度的零耦合处的跃迁;在部分同步状态出现时,甚至对耦合强度为负值,这种特征在成对相互作用中是不可能的。此外,该文的理论解释了涌现行为的几个方面: 系统不能从无序中达到完全同步,并且拥有极端多稳定性,因为渐近稳定状态总是依赖于初始条件。
 
结论:奇数维和偶数维的振子网络同步特性非常不一样。
 
X. Dai, K. Kovalenko, M. Molodyk, Z. Wang, X. Li, D. Musatov, A.M. Raigorodskii, A. Bittner, G.D. Cooper, G. Bianconi, S. Boccaletti, D-dimensional oscillators in simplicial structures: Odd and even dimensions display different synchronization scenarios. Chaos, Solitons Fractals, 146: 110888, 2021
https://www.sciencedirect.com/science/article/pii/S0960077921002411


· 广义网络同步的高阶相互作用新形态


这篇文章建立了一个简化集群同步模式的稳定性分析统一框架,可应用于广义网络,包括超图、多层网络和时效网络。基于分块对角化编码同步模式和网络拓扑矩阵,揭示了一种有趣的、仅在高阶相互作用时出现的复杂嵌合状态类型 。建立的统一框架可以推广到其他动力学过程,并且可以帮助在具有广义相互作用的复杂系统中发现新的突现现象。

Y. Zhang, V. Latora, A.E. Motter, Unified treatment of synchronization patterns in generalized networks with higher-order, multilayer, and temporal interactions, Comm. Phys., 4: Article 195, 2021
https://arxiv.org/pdf/2010.00613v2.pdf


· 高阶网络同步的多阶拉普拉斯算子方法


许多物理系统中存在多个群体交互的同步现象, 高阶相互作用可以明显地影响网络的新动态。该文对复杂拓扑(如超图)引入了多阶拉普拉斯算子,其频谱决定了同步的稳定性。对描述猕猴大脑连接真实数据的分析,发现大脑连接中群组的重要性,它们描述了系统中的相互作用的复杂性。多阶拉普拉斯算子有助于获得任意高阶网络中同步稳定性的完整解析表征,对超越点对相互作用的动态过程提供一种一般的处理方法。

图8 单纯复形上具有高阶相互作用的振子群

M. Lucas, G. Cencetti, F. Battiston, Multiorder Laplacian for synchronization in higher-order networks, Phys. Rev. Research, 2: 033410, 2020
https://arxiv.org/pdf/2003.09734v3.pdf


· 单纯复形网络同步的稳定性


传统耦合动力系统的网络模型中,以节点对的连接来描述相互作用。最近的研究表明,高阶多体相互作用存在于社会群体、生态系统和人类大脑中。该文建立了一个耦合动力系统的一般框架,可以描述任意顺序的相互作用。证明了完全同步作为不变解的存在性,并给出其稳定状态的必要条件。
L.V. Gambuzza, F. Di Patti, L. Gallo, S.S. Lepri, M. Romance, R. Criado, M. Frasca, V. Latora, S. Boccaletti, Stability of synchronization in simplicial complexes, Nature Comm., 12: 1255, 2021
https://www.nature.com/articles/s41467-021-21486-9.pdf

 

 



三、高阶拓扑的多领域应用:

脑科学、生态学、社会科学 




1、脑科学


· 大脑功能网络的实证研究——团和洞的重要性


这篇文章将大脑区域及其连接编码为一个由节点和连边组成的网络,捕获了许多可能的路径,信息可以通过这些路径传输并执行复杂的行为。尽管人类大脑的神经网络看上去颇为稀疏,它里面的团和洞结构却是非常稠密的。研究发现大脑皮层团和洞结构在视角和认知功能里起着重要作用。
 
从传统图论的观点来看脑网络,只能看到节点对之间的连接,而要从更深刻的层次和高度来理解大脑结构,还得从高阶代数拓扑的角度来考量。实证研究发现,周长较长的圈结构在控制大脑皮层活动中举足轻重,而且发现洞所扮演的角色尤为重要,它与大脑信息传播的模式密切相关。这些结果证明了代数拓扑的技术为结构连接组合提供了一个全新的视角,突出了环状路径作为人类大脑结构的关键特征,折射出在脑科学研究中仅仅采用经典图论的缺陷和进一步采用高阶拓扑图论的必要。
 
图9 小团体是大脑结构网络中的局部社区的特征
A.E. Sizemore, C. Giusti, A. Kahn, J.M. Vettel, R.F. Betzel, D.S. Bassett, Cliques and cavities in the human connectome. J. Comput. Neurosci. 44(1): 115-145, 2018
https://link.springer.com/content/pdf/10.1007/s10827-017-0672-6.pdf
 
对神经网络结构与其功能涌现之间联系认知的缺失阻碍了我们对大脑如何处理信息的理解。这里考虑了现有通过突触传递信息的因素,构建了反映信息流方向的网络图,并使用代数拓扑来分析这些有向图。此方法应用于新皮质中的局部神经元网络,揭示了一个非常复杂且以前突触连接看不见的拓扑结构。其中突触网络包含大量束缚在空腔中的神经元,这些空腔引导着相关活动的出现。在对刺激的反应中,相关的活动将突触连接的神经元绑定到功能性的小团体和空洞中,这些小团体以一种固定的顺序进化到极端复杂性。该文认为大脑通过形成越来越复杂的功能团和腔来处理刺激功能。
束缚在空腔中的神经元
M.W. Reimann, M. Nolte, M. Scolamiero, K. Turner, R. Perin, G. Chindemi, P. Dłotko, R. Levi, K. Hess, H. Markram, Cliques of neurons bound into cavities provide a missing link between structure and function, Frontiers in Comput. Neurosci., 11: paper 48, 2017
https://www.frontiersin.org/articles/10.3389/fncom.2017.00048/full
 

2、生态学
 

· 物种的高阶相互作用决定生态系统的多样性


物种之间的高阶相互作用的多样性和系统的稳定性一般来说是对立的。虽然随着物种数量的增加,群落个体两两之间的相互作用变得更加敏感,但对三个个体相互作用的敏感性却保持不变。实际上,其敏感性到四个个体时的相互作用反而会减少。因此,它们的群体组合中存在数量有下限和上限的物种。这些发现表明物种高阶相互作用决定了自然生态系统的多样性。
E. Bairey, E.D. Kelsic, R. Kishony, High-order species interactions shape ecosystem diversity, Nature Comm., 7: Article 12285, 2016
https://www.nature.com/articles/ncomms12285.pdf


· 生态系统中的高阶相互作用和群落稳定性


生态学家长期以来一直在寻找对自然界中观察到的生物多样性的合理解释。目前简单的相互作用竞争者模型不能保证非常大的生态群落的持久稳定性,现有的中性模型也解释不了物种不相互作用时产生的多样性。最近发现,由于高阶相互作用的稳定性,非常多样化的社团可以持续存在。高阶相互作用对封闭生态群落模型有强大影响,能不断引进新物种到社团中,并且高阶相互作用还可以帮助模型的参数化并进行验证。
J. Grilli, G. Barabás, M.J. Michalska-Smith, S. Allesina, Higher-order interactions stabilize dynamics in competitive network models, Nature, 548: 210-213, 2017
https://www.nature.com/articles/nature23273.pdf


· 秀丽隐杆线虫的高阶神经网络结构与功能


了解动物神经系统的连通性对于理解其功能至关重要。这里建立了包含从感觉输入到末端器官输出的所有连边的定量邻接矩阵。发现不同性别线虫(C. elegans)的神经系统在多个层面上是不同的,连接强度也不相同。高阶定量邻接矩阵包括所有的连接数据,是理解复杂系统的适应性行为如何产生的基础。

图10 成年秀丽隐杆线虫神经系统链接图
S.J. Cook, et al., Whole-animal connectomes of both Caenorhabditis elegans sexes, Nature, 571: 63-71, 2019
https://www.nature.com/articles/s41586-019-1352-7.pdf
 

3、社会科学

· 社会网络中的高阶相互作用发展动力学

人们在网络中生活和合作,但初等图论连接只允许两节点间的互动,该框架只适用于二元博弈而不适用于群组博弈。进化动力学在社会系统中通过公共物品博弈(Public Good Game)具有高阶相互作用。均匀超图上的博弈对应于充分混合极限下的复制动力学,是网络群体合作的理论基础。该文中发现了枢纽群体的存在以及它们与不同规模群体的相互作用都会影响合作的发展。通过实际科学和技术领域的数据,分析了群体合作如何依赖于群体规模,可以提供一种促进社会团体合作的有效方法。

图11 高阶相对于成对相互作用
U. Alvarez-Rodriguez, F. Battiston, G.F. de Arruda, Y. Moreno, M. Perc, V. Latora, Evolutionary dynamics of higher-order interactions in social networks, Nature Human Behaviour, 5: 586-595, 2021
https://www.nature.com/articles/s41562-020-01024-1
 

4、其他新应用场景


· 计算拓扑学开始进入复杂网络研究领域——寻找高阶拓扑特征


代数拓扑研究的持久同调特性被用来计算不同空间的分辨率, 在多重空间尺度上检测到更多持久的拓扑特征, 因而更能代表底层空间研究对象的本质。对时间序列数据构成的功能网络的研究, 揭示了功能网络中的团和洞的结构比普通的点对连接结构具有更高阶的一些内在特性, 能够提供一些更为有用的信息。对Kuramoto 振子同步和大脑核磁共振数据的研究, 发现持久同调特性可以清晰地区分大脑在学习过程中的一些同步规律和现象, 揭示一些常规信号采样和噪声分析看不清楚的特性(例如, 常规的基于点对连接的网络分析, 不能提供社团之间强同步与弱同步的一些相异特征以及人在学习过程中脑功能网络的一些重要变化)。持久同调特性可用于拓扑数据分析, 从加权、 噪声污染、 非匀采样的复杂数据中揭示局部、 中尺度及全局数据多种特征(在脑电图数据分析中已得到验证)
B.J. Stolz, A.H. Heather, M.A. Porter, Persistent homology of time-dependent functional networks constructed from coupled time series. Chaos 27: 047410, 2017
https://arxiv.org/pdf/1605.00562.pdf
E. Ibanez-Marcelo, L. Campioni, A. Phinyomark, G. Petri, E.L. Santarcangelo, Topology highlights mesoscopic functional equivalence between imagery and perception. NeuroImage 200: 437-449, 2019
https://www.researchgate.net/publication/344952631_Topology_highlights_mesoscopic_functional_equivalence_between_imagery_and_perception


· 识别超图中的高阶相互作用信息


网络互动不仅限于二元组,还经常涉及三个或更多。这些数据可以用超图很好地描述,其中超链描述了节点组之间的高阶相互作用,可以通过识别超链来发现相关的高阶相互作用。数据分析表明,更多的超链可以比用二元组方法获得更大量的信息。
F. Musciotto, F. Battiston, R.N. Mantegna, Detecting informative higher-order interactions in statistically validated hypergraphs, Comm. Phys., 4: Paper 218, 2021
https://www.nature.com/articles/s42005-021-00710-4.pdf


· 高阶相互作用改善网络群集行为的优化


群集行为在生理、生物和神经系统功能中起着关键作用。高阶相互作用指在复杂网络中有多个独立单元相互作用的结构。实证研究揭示了,它们普遍存在于各种复杂系统之中。研究网络中群集行为的优化,可行方法包括复合拉普拉斯矩阵和多阶相互作用如二元和三元的耦合。通过加宽复合拉普拉斯矩阵的特征值谱,可以改进最优群集行为并拓宽可能的行为范围。在约束优化场景中,一个非平凡的、理想的成对和高阶相互作用的平衡导致最强的群集行为。优化系统不同类型的平衡或扩大其动态行为范围,可望应用于自我调节系统(如大脑)
P.S. Skardal, D. Taylor, L.A rola-Fernandez, A. Arenas, Higher-order interactions improve optimal collective dynamics on networks, arXiv 2021


· 高阶团网络与渗流过程


这篇文章研究了以团为基础的网络局部结构对网络渗流过程的影响。比较了带局部社团结构的随机图模型和带局部树状结构的随机图模型。发现了网络的平均度数越大,其局部树状结构对渗流过程的影响就越小。在高阶团网络上,与树状网络比较,渗流的不同行为几乎可以完全归因于度序列而不是社团结构的差异。

例子:Kuramoto 振子网络
C. Stegehuis, T. Peron, Network processes on clique-networks with high average degree: the limited effect of higher-order structure, arXiv 2021
https://www.researchgate.net/publication/351279057_Network_processes_on_clique-networks_with_high_average_degree_the_limited_effect_of_higher-order_structure


· 复杂网络中的洞与鲁棒性


节点的高阶聚合结构可用单纯复形来建模描述。节点的移除会影响拓扑不变量的值(如量化的高阶洞的数量和贝蒂数)。渗流理论和方法可以用来描述某些节点的移除导致新的洞出现。复杂网络鲁棒性和同调性之间的关系可以通过对网络特征和拓扑不变量的联系加以研究。通过模拟对网络的随机故障和恶意攻击,发现鲁棒性的网络特征变化是不同攻击策略下各个集群中洞的数量分布出现了差异而带来的后果。拓扑不变量的研究有助于进一步理解复杂网络上发生的动态变化。
A.D. Zhou, S. Maletić, Y. Zhao, Robustness and percolation of holes in complex networks, Physica A, 502: 459-468, 2018
https://www.sciencedirect.com/science/article/pii/S0378437118302188


· 科学与技术知识网络中的高阶拓扑结构


科学技术的发展是一个重组过程,其中新的发现和发明是根据先验知识构建的。使用代数拓扑工具可以描述跨尺度科学技术知识网络的高阶结构。观察到很多科学和技术领域知识的高阶结构的增长,而这种增长是使用传统的网络测量无法观察到的。证明了高阶结构与低阶结构相吻合,并且在某种程度上高阶结构的增加与更好的结果相关(如论文和专利的新颖性和影响力)。在科学技术本质下产生的高阶制度表现出更大的语言抽象性和更大的知识流。
T. Gebhart, R.J. Funk, The emergence of higher-order structure in scientific and technological knowledge networks, arXiv 2020
https://arxiv.org/pdf/2009.13620v1.pdf


· 最优高阶网络模型及其数据分析应用


丰富的数据表明,基于节点对相互作用的模型无法捕获网络节点之间的复杂依赖关系。高阶网络模型超越了这些限制,为理解复杂系统提供了新视角。网络描述节点对的相互作用,可以解释系统拓扑的基本特征,并为统计分析和推理提供理论基础。越来越明显的社会、技术和生物系统数据表明,获取复杂路径和相互作用的信息需要先进的建模技术。最优高阶网络模型包含有多层、组合和非马尔可夫过程,丰富了网络科学的研究方式。
R. Lambiotte, M. Rosvall, I. Scholtes, From networks to optimal higher-order models of complex systems, Nature Physics, 15: 313–320, 2019
https://www.nature.com/articles/s41567-019-0459-y.pdf


· 复杂系统高阶相互作用的物理学原理


复杂网络已成为相互作用系统动力学建模的主要范式。然而,网络本质上仅限于描述节点对的相互作用,而现实世界的复杂系统通常以高阶为特征,涉及三个或更多个单元组的相互作用。高阶结构(如超图和单纯复形)是描绘许多社会、生物和人造系统等真实组织更为有效的工具,提供了由高阶相互作用引起的群体行为的最新证据。该文还概述了物理学的三个关键挑战性高阶系统。
F. Battiston et al., The physics of higher-order interactions in complex systems, Nature Physics, 17: 1093–1098, 2021
https://www.nature.com/articles/s41567-021-01371-4.pdf


· 计算复杂网络中的高阶团和洞


寻找所有团(或最大团)是NP-完全问题,更不必说高阶洞。本文(《计算复杂网络中的高阶团和洞》)通过 k-核分解来决定网络的计算可行性。设计了寻找各阶团的可行算法,可同时获得 Euler 示性数和 Betti 数。对线虫(C. elegans)真实大数据找到所有各阶团和部分高阶洞。
D.H. Shi*, Z.F. Chen, X. Sun, Q.H. Chen, C. Ma, Y. Lou, G.R. Chen*, Computing cliques and cavities in networks, Comm. Phys., accepted, 2021
https://arxiv.org/vc/arxiv/papers/2101/2101.00536v1.pdf





四、总结展望




本次报告详细介绍了复杂网络高阶拓扑的相关概念,并通过大量文献举例,在网络同步问题、脑科学网络、生态系统等分析以及网络动力学研究中,展示了高阶拓扑的应用。经验表明,当考虑到更现实的相互作用模式时,利用高阶相互作用分析可能会引出新的研究问题和对象。
 
对具有高阶相互作用的网络系统研究仍处于初级阶段,还有许多开放的和未探索的方向。我们列出其中的一些供读者探讨:

· 高阶结构的度量

在复杂网络中,时效、演化和多层次的网络度量方法,有很大的探索空间。例如,虽然对振荡器网络模型中节点之间的同步已有一个清晰的理解,但要以两节点交互的观点和方法来理解它们以团为单位的内外强弱同步的状态是困难的。正确定义能够捕获这些状态的度量将是描述分析其作用及影响的一个必要步骤。

· 高阶结构的生成模型

能够刻画高阶结构的各种特征的模型是至关重要的。开发新的度量和生成模型对于确定我们观察到的模式背后的基本机制是非常重要的。目前单纯复形的随机模型很少。一些现有的单纯复形模型再现了局部连接模式,但没有一个能够再现更精细的拓扑结构。考虑到高阶相互作用的时间和多重结构的网络拓扑模型还有待研究。

· 数据推断

在许多复杂系统中,交互作用尚未确定,需要从数据中推断出来。如果可能,我们需要什么类型的数据来区分低阶和高阶相互作用呢?事实上,对于数据已经以集合的形式出现的系统,提取高阶相互作用因素并测量其强度是很简单的。但是在实际情况下,由于各种原因,高阶相互作用很少被数据直接反映出来。关于具有或不具有高阶相互作用的动力学模型的数据缺失使得人们无法为高阶相互作用的存在、性质和强度引出适当的分析方案。
 
目前的困难不单是方法论问题,还需要将高阶拓扑理论在更广泛的主题中找到具体的应用。我们可以设想在生物学、生态学、人类行为动力学、神经科学和计算社会科学等方向,利用高阶拓扑为进一步的深入研究提供新途径。
 

参考文献

1、网络同步问题


全齐网络是同步最优网络

D.H. Shi, G. Chen, W.W.K. Thong, X.Y. Yan, Searching for optimal network topology with best possible synchronizability, IEEE Circ. Syst. Mag. 13(1): 66-75, 2013

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6468141

 

D. H. Shi, L. Y. Lyu, G. R. Chen, Totally homogeneous networks, National Science Review (2019)

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

 

复杂网络中的高阶组织结构

A.R. Benson, D.F. Gleich, J. Leskovec, Higher-order organization of complex networks, Science, 353: 163-166, 2016

https://www.science.org/doi/epdf/10.1126/science.aad9029

 

超出节点对间相互作用的网络:结构与动力学(综述)

F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, G. Petri, Networks beyond pairwise interactions: Structure and dynamics, Physics Reports, 847: 1-92, 2020

https://arxiv.org/abs/2006.01764v1

 

耦合高阶单纯复形上拓扑信号的同步

R. Ghorbanchian, J.G. Restrepo, J.J. Torres, G. Bianconi, Higher-order simplicial synchronization of coupled topological signals, Comm. Phys., 4: Paper 120, 2021

https://arxiv.org/abs/2011.00897v2

 

高维单纯复形上 Kuramoto 振子的相位同步

X. Dai, K. Kovalenko, M. Molodyk, Z. Wang, X. Li, D. Musatov, A.M. Raigorodskii, A. Bittner, G.D. Cooper, G. Bianconi, S. Boccaletti, D-dimensional oscillators in simplicial structures: Odd and even dimensions display different synchronization scenarios. Chaos, Solitons Fractals, 146: 110888, 2021

https://www.sciencedirect.com/science/article/pii/S0960077921002411

 

广义网络同步的高阶相互作用新形态

Y. Zhang, V. Latora, A.E. Motter, Unified treatment of synchronization patterns in generalized networks with higher-order, multilayer, and temporal interactions, Comm. Phys., 4: Article 195, 2021

https://arxiv.org/pdf/2010.00613v2.pdf

 

高阶网络同步的多阶拉普拉斯算子方法

M. Lucas, G. Cencetti, F. Battiston, Multiorder Laplacian for synchronization in higher-order networks, Phys. Rev. Research, 2: 033410, 2020

https://arxiv.org/pdf/2003.09734v3.pdf

 

单纯复形网络同步的稳定性

L.V. Gambuzza, F. Di Patti, L. Gallo, S.S. Lepri, M. Romance, R. Criado, M. Frasca, V. Latora, S. Boccaletti, Stability of synchronization in simplicial complexes, Nature Comm., 12: 1255, 2021

https://www.nature.com/articles/s41467-021-21486-9.pdf

 

2、脑科学、生态学、社会科学

 

大脑功能网络的实证研究:团和洞的重要性

A.E. Sizemore, C. Giusti, A. Kahn, J.M. Vettel, R.F. Betzel, D.S. Bassett, Cliques and cavities in the human connectome. J. Comput. Neurosci. 44(1): 115-145, 2018

https://link.springer.com/content/pdf/10.1007/s10827-017-0672-6.pdf

 

束缚在空腔中的神经元团提供了结构和功能之间缺失的联系

M.W. Reimann, M. Nolte, M. Scolamiero, K. Turner, R. Perin, G. Chindemi, P. Dłotko, R. Levi, K. Hess, H. Markram, Cliques of neurons bound into cavities provide a missing link between structure and function, Frontiers in Comput. Neurosci., 11: paper 48, 2017

https://www.frontiersin.org/articles/10.3389/fncom.2017.00048/full

 

物种的高阶相互作用决定生态系统的多样性

E. Bairey, E.D. Kelsic, R. Kishony, High-order species interactions shape ecosystem diversity, Nature Comm., 7: Article 12285, 2016

https://www.nature.com/articles/ncomms12285.pdf

 

生态系统中的高阶相互作用和群落稳定性

J. Grilli, G. Barabás, M.J. Michalska-Smith, S. Allesina, Higher-order interactions stabilize dynamics in competitive network models, Nature, 548: 210-213, 2017

https://www.nature.com/articles/nature23273.pdf

 

秀丽隐杆线虫的高阶神经网络结构与功能

S.J. Cook, et al., Whole-animal connectomes of both Caenorhabditis elegans sexes, Nature, 571: 63-71, 2019

https://www.nature.com/articles/s41586-019-1352-7.pdf

 

社会网络中的高阶相互作用发展动力学

U. Alvarez-Rodriguez, F. Battiston, G.F. de Arruda, Y. Moreno, M. Perc, V. Latora, Evolutionary dynamics of higher-order interactions in social networks, Nature Human Behaviour, 5: 586-595, 2021

https://www.nature.com/articles/s41562-020-01024-1

 

3、新应用场景:其他

 

计算拓扑学开始进入复杂网络研究领域(寻找高阶拓扑特征)

B.J. Stolz, A.H. Heather, M.A. Porter, Persistent homology of time-dependent functional networks constructed from coupled time series. Chaos 27: 047410, 2017

https://arxiv.org/pdf/1605.00562.pdf

 

E. Ibanez-Marcelo, L. Campioni, A. Phinyomark, G. Petri, E.L. Santarcangelo, Topology highlights mesoscopic functional equivalence between imagery and perception. NeuroImage 200: 437-449, 2019

https://www.researchgate.net/publication/344952631_Topology_highlights_mesoscopic_functional_equivalence_between_imagery_and_perception

 

识别超图中的高阶相互作用信息

F. Musciotto, F. Battiston, R.N. Mantegna, Detecting informative higher-order interactions in statistically validated hypergraphs, Comm. Phys., 4: Paper 218, 2021

https://www.nature.com/articles/s42005-021-00710-4.pdf

 

高阶相互作用改善网络群集行为的优化

P.S. Skardal, D. Taylor, L.A rola-Fernandez, A. Arenas, Higher-order interactions improve optimal collective dynamics on networks, arXiv 2021

https://arxiv.org/abs/2108.08190

 

高阶团网络与渗流过程

C. Stegehuis, T. Peron, Network processes on clique-networks with high average degree: the limited effect of higher-order structure, arXiv 2021

https://www.researchgate.net/publication/351279057_Network_processes_on_clique-networks_with_high_average_degree_the_limited_effect_of_higher-order_structure

 

复杂网络中的洞与鲁棒性

A.D. Zhou, S. Maletić, Y. Zhao, Robustness and percolation of holes in complex networks, Physica A, 502: 459-468, 2018

https://www.sciencedirect.com/science/article/pii/S0378437118302188

 

科学与技术知识网络中的高阶拓扑结构

T. Gebhart, R.J. Funk, The emergence of higher-order structure in scientific and technological knowledge networks, arXiv 2020

https://arxiv.org/pdf/2009.13620v1.pdf

 

最优高阶网络模型及其数据分析应用

R. Lambiotte, M. Rosvall, I. Scholtes, From networks to optimal higher-order models of complex systems, Nature Physics, 15: 313–320, 2019

https://www.nature.com/articles/s41567-019-0459-y.pdf

 

复杂系统高阶相互作用的物理学原理

F. Battiston et al., The physics of higher-order interactions in complex systems, Nature Physics, 17: 1093–1098, 2021

https://www.nature.com/articles/s41567-021-01371-4.pdf

 

计算复杂网络中的高阶团和洞

D.H. Shi*, Z.F. Chen, X. Sun, Q.H. Chen, C. Ma, Y. Lou, G.R. Chen*, Computing cliques and cavities in networks, Comm. Phys., accepted, 2021

https://arxiv.org/vc/arxiv/papers/2101/2101.00536v1.pdf


(参考文献可上下滑动查看)



网络科学集智课堂第三期报名中

从数学建模到多学科应用


从现实社会的关系网到虚拟的互联网,从线下到线上,我们的生活始终没有脱离复杂网络。真实的复杂网络从其诞生开始就不断地演化着。网络节点不断地增加,节点之间的连接不断地增长。然而,复杂网络的形成机制是什么?具有什么样的演化规律?它们的演化机制对网络的功能和动力学行为有什么影响?为了回答这些问题,科学家们对复杂网络的探索从未停止。

网络科学是一个蓬勃发展的崭新交叉学科,可以看做复杂系统的骨架,核心是研究各种大型复杂网络之间的共性和处理它们的普适方法,其研究对于发展复杂系统的基本理论及构建产生了极大的推动作用。

网络科学的第三个十年,已经过去了几年。从国内外网络科学研究的发展趋势来看,各种各样的更复杂的网络模型和结构以及高阶相互作用动力学引起了人们的极大兴趣。为了回应这种迫切需求, 我们网络科学第三期课程将围绕复杂网络的数学建模与应用进行多角度的介绍。

集智学园特邀陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华加入打造第三期课程,欢迎你的加入。


详情请点击:
从数学建模到多学科应用——网络科学·集智课堂全新升级


推荐阅读



点击“阅读原文”,报名课程

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存