多层网络的动力学：从结构依赖到历史依赖
近日，中国科学技术大学的李明（第一作者）等和电子科技大学吕琳媛（通讯作者）等共同在《国家科学评论》（National Science Review）上发表了名为《History-dependent percolation on multiplex networks》的文章。作者以多层网络上的渗流模型为例，对网络动力学中的历史依赖机制进行了探讨。该工作表明由于历史依赖的存在，迭代或递归型的动力学过程的中间态是理解整个系统动力学过程的重要环节。
我们特别邀请到论文第一作者、中国科技大学工程科学学院研究员李明，在线解读这篇论文。直播交流群和参与方式见文末。
论文题目： History-dependent percolation on multiplex networks
论文地址：
https://doi.org/10.1093/nsr/nwaa029
预印本版本：
https://arxiv.org/abs/2002.08079
同样的动力学机制在不同的系统结构中往往会产生不同的结果。20年前，网络科学正是在对实际网络结构的统计分析中新兴，因而动力学与结构的关联在网络科学中的体现也尤为充分。典型的例子包括，无标度网络对随机破坏的强鲁棒性以及对蓄意攻击的极端脆弱性、“小世界”结构对合作达成的促进作用等 [1,2]。
研究动力学的最终目的是控制与利用动力学，而动力学过程有其固有机制，一般无法直接改变。因此，实际中人们往往通过调控系统结构以达到间接控制动力学的目的。例如，近期的新冠疫情中，病毒的传染性确定，但可以采取隔离等措施改变人们的接触网络进而达到控制疫情的目的。除此之外，加强防疫宣传也是一个重要的措施。而舆论与信息的传播本身也是一个动力学过程，其结果将直接影响后续的病毒传播，也就是后者依赖前者的动力学结果。
实际中，两个或多个动力学相互依赖的例子还有很多，一般以递归或迭代的机制出现在动力学建模中。这种机制很好地映射出了历史依赖特性，但却也习惯性地将关注点引向迭代的稳态。然而，真实系统在很多情况下所呈现出来的都是中间态。首先，系统达到稳态需要经历大量的迭代，特别是在大规模网络中往往需要很长一段时间，有时在可接受时间内甚至不能达到。因而很多时候所观测到的现象仅是有限迭代的结果。其次，忽略中间态也就不免失去对系统在该阶段演化规律的理解和认识，进而缺乏对稳态时系统物理性质涌现的溯源。因此，审视迭代的中间态将提供一条解答这些问题的途径。
1.网络结构与渗流模型
虽然渗流模型的提出早于复杂网络研究数十年，但其似乎与生俱来就是为复杂网络的研究所准备。简单地说，渗流模型关注的是节点在随机或者半随机的连接机制下形成的集团的大小、结构等性质[3]。显然，这些量也正是刻画网络结构所需的。
图1：方格上渗流模型示意图。
左图展示以概率1-p=0.43删除节点后的一种可能位形，右图展示以概率1-p=0.39删除节点后的一种可能位形。图中未画出被删除的节点，并且以不同颜色区分不同的连接集团。图中结果显示当概率p较小时（左图），系统由一些小集团组成；而p较大时（右图），系统中会出现一个较大的集团贯穿系统，即达到渗流状态。该图展示的是随机删点（座渗流）的情况，随机删除边（键渗流）也有类似的结果。
经典的渗流模型定义在规则格子上，当随机移除部分节点或者边后（移除比例1-p），一些连接集团将显现出来。这就是所谓的座渗流（移除节点）或键渗流模型（移除连边）。图1给出了一个方格上座渗流模型的例子。统计物理的研究更关注渗流过程所呈现的相变现象，也就是随着p值的变化系统从一种连接状态转变到另一种连接状态时所展现的特点，而对应的转变点称为临界点pc。这里的连接状态常用有无巨分支区分，即是否存在与系统大小同量级的集团。显然，当节点或连边的移除比例较大时，巨分支会被破坏。当然，有限大的系统无法直接判断一个分支是否就是巨分支，因此研究中需要考察系统对无限大的趋近行为，也就是有限尺度标度律。对于无限大的系统，巨分支也是无限大的，而其它分支都是有限大的。
在确定了临界点之后就进而可以研究相变性质，即临界现象。从字面看，所谓临界即逐渐靠近临界点。所以，临界现象即是在趋近临界点时系统所展现的行为。例如，p值逐渐靠近临界点pc时，巨分支是以怎样的形式涌现、其它有限大小的分支又符合怎样的分布规律等。物理学家在对这些问题的研究中发现很多幂律形式的特性，而这些幂律的幂指数即是所谓的临界指数。一组临界指数就确定了一个相变的特点，称为一种普适类。普适类只与系统最基本的作用方式有关，例如系统维度，而与一些模型细节无关。渗流相变的普适类在网络系统中关注较少。主要是因为复杂网络模型一般没有连接的空间限制，进而都属于平均场的普适类。当然，由于无标度网络的强异质性，也会有一些特殊的普适类存在 [4]。
渗流模型之于网络科学远不止对于相变问题的讨论，其在网络结构分析与动力学建模上有着更重要的作用。例如，把初始删除节点看成是网络的随机故障，而巨分支存在与否对应为网络功能是否仍健全，即可通过渗流模型探究网络的鲁棒性。同样，如果将删边概率映射为传播概率，渗流模型又可以用于研究网络上的传播问题。除此之外，渗流模型在网络的级联故障、社团划分、重要节点识别等问题的研究中都发挥了一定的作用 [5-8]。
2.渗流过程的迭代与多层网络
迭代或递归机制在网络渗流问题的研究中也有体现。例如，用以研究网络鲁棒性的级联故障模型。该类模型中，初始删除节点后并不直接通过考察网络的巨分支来判断网络的鲁棒性，而是依据一定的规则继续剔除节点。例如，只保留度大于等于k的节点对应于所谓的k核渗流 [9]。又如，当节点失去一定比例的边后，将该节点剔除，即对应于级联故障模型 [5]。这些模型最终都呈现出迭代的机制，即一些节点的删除会引起其它节点的删除，如此反复，直至所有节点都满足留存条件。对于渗流模型，该类迭代带来的是不连续相变，即当系统达到临界点后，巨分支会突然涌现，也就是说随着p值的增加巨分支大小与系统大小的比值不是从零开始逐渐增大的。但这些迭代过程共同构成了一个动力学过程，而并非是若干动力学的迭代与依赖。
多层网络的引入本身则包含了多个动力学相互作用的范式：同一组节点具有不同的连接层次，各层表示不同的相互作用方式 [10]。例如，舆论与疾病在社交与接触两层网络中的交互迭代作用、故障在电力网络与控制网络的交互级联等。对于前者的建模通常只考察两三次迭代的作用，系统呈现出连续渗流相变；对于后者的研究往往认为迭代会迅速完成达到稳态，呈现出不连续的渗流相变。两者同为历史依赖机制，但展现出的现象却截然不同，认知其内在原因则需要一般性的探究历史依赖过程的机理。
3.多层网络上历史依赖渗流
为了探究历史依赖机制的作用，作者提出了一个多层网络上的迭代渗流模型。如图2所示，首先使用一层连接进行渗流过程，形成若干连接集团，此即第一级渗流相变。为体现历史依赖机制，在第一级渗流的结果上，使用另一层连接在各集团内部再次实施渗流过程，即第二级渗流。依次类推，可以定义每一级的渗流相变。对于无限大的系统，这种迭代可以一直进行，理论上可以定义任意级的渗流相变。考察不同级的渗流相变，即可探究系统动力学在历史依赖机制下的演化规律。
理论与模拟均发现随级数递增，渗流相变越来越剧烈，即超过临界点之后，巨分支的大小增长的更迅速。但是，有限尺度行为的分析发现所有有限级的渗流相变都属于同一普适类，即与标准的渗流（一次迭代）本质上是相同的。这也表明有限的迭代都没有从质上改变巨分支的形成方式与结构（由一些度较大的节点决定），而只是剥落了一些小分支。
我们知道无标度网络会给出趋于零的渗流临界点，即任意比例的随机删点或删边都不会破坏巨分支。迭代渗流也没有打破这一规律，只是抑制了巨分支的增长，即任意有限迭代的渗流临界点都是零。这一发现也符合上述分析，即有限迭代只能剥落小分支，而无标度网络的hub节点始终存在，并主导了渗流相变。
对于无限大的系统，迭代可以一直进行。研究发现，这种无限的迭代最终会改变系统巨分支的涌现方式，而呈现出不连续相变。由此可见，迭代渗流模型将之前很多模型中所展现的连续相变与不连续相变联系了起来。
此外，作者们也将该迭代操作实施于由脑功能网络和形态学网络构成的双层网络中，以逐级剥落节点，进而发现了人脑网络的一些异常结构，见图3。
4.展望
4.展望
网络科学的发展与渗流过程的研究密不可分，渗流相变也在各种实证网络和模型中得到了讨论。该项研究进一步发展了相关研究，也给出了若干启示。首先，实际过程中观察到的连续渗流相变可能由若干过程迭代作用而成，并不是单一的传播或级联所致。其次，由于无限次迭代无法在有限大的系统中达成，因而真实系统中观察到的不连续渗流相变可能包含其它作用机制，或者只是有限尺度效应所致。最后，迭代过程中间态的研究具有重要意义，可用来探讨相关现象的起源与演化规律。当然，这些结论是否对所有动力学过程的迭代都普适，需要进一步的探讨。
[1]R. Albert, A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002) 47.
[2]S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys. 80 (2008) 1275–1335.
[3]D. Stauffer, A. Aharony, Introduction to percolation theory, 2nd Edition, Taylor & Francis, London, 1991.
[4]R. Cohen, D. ben Avraham, S. Havlin, Percolation critical exponents in scale-free networks, Phys. Rev. E 66 (2002) 036113.
[5]D. J. Watts, A simple model of global cascades on random networks, Proc. Natl. Acad. Sci. U.S.A. 99 (9) (2002) 5766–5771.
[6]G. Palla, I. Derényi, I. Farkas, T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435 (7043) (2005) 814–818.
[7]S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin, Catastrophic cascade of failures in interdependent networks, Nature 464 (7291) (2010) 1025.
[8L. Lü, D. Chen, X.-L. Ren, Q.-M. Zhang, Y.-C. Zhang, T. Zhou, Vital nodes identification in complex networks, Phys. Rep. 650 (2016) 1 – 63.
[9]S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, k-core organization of complex networks, Phys. Rev. Lett. 96 (2006) 040601.
[10]S. Boccaletti, G. Bianconi, R. Criado, C. del Genio, J. Gvómez-Gardeñes, M. Romance, I. Sendiña Nadal, Z. Wang, M. Zanin, The structure and dynamics of multilayer networks, Phys. Rep. 544 (2014) 1 – 122.
[11]M. Li, L. Lü, Y. Deng, M.-B. Hu, H. Wang, M. Medo, H. E. Stanley, History-dependent percolation on multiplex networks, National Science Review (2020), published online (https://doi.org/10.1093/nsr/nwaa029).
作者：李明、吕琳媛
审校：刘培源
编辑：张希妍
直播预告：
集智科学家亲述论文故事
直播时间：周二（4月21日） 19:00-20:00
入群交流：点击下方图片，长按扫码二维码加入直播交流群。或扫码加小助手微信，留言“多层网络直播”，拉你进群。
直播通道 1：集智俱乐部 B 站直播间：
https://live.bilibili.com/8091531
直播通道 2：zoom 线上会议室（可提问）
通过下方集智斑图系统报名，直播当天“集智俱乐部服务号”将通知你 zoom 房间号
扫描二维码，点击“我要听”报名zoom会议室直播
推荐阅读
Physics Reports：网络传播动力学前沿综述：共演化传播网络
Science前沿：世界上最复杂的微粒——超越自然复杂性的合成物
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！
👇点击“阅读原文”，了解更多论文信息