导游词

最近，中国科学技术大学的帅气绿茶(第一作者)等和电子科学技术大学的快乐裙)通讯作者)等共同在《国家科学评论》 ) nationalsciencereview )上发表了《History-dependent percolation on multiplex networks》这篇文章。 作者以多层网络上的渗流模型为例，讨论了网络动力学中的历史依赖机理。 这项工作表明，由于历史依赖的存在，迭代或递归动力学过程的中间状态是理解整个系统动力学过程的重要环节。

我们特别邀请论文第一作者、中国科学技术大学工程科学学院研究员英俊的绿茶，在线解读这篇论文。 现场通讯组和参加方法见文末。

论文主题：历史-从属关系网络论文地址： https://doi.org/10.1093/NSR/NWaA 029预印本版本： https://arry

相同的动力学机制往往在不同的系统结构中产生不同的结果。 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所示，首先使用一层连接进行渗流过程，形成若干连接集团，此即第一级渗流相变。为体现历史依赖机制，在第一级渗流的结果上，使用另一层连接在各集团内部再次实施渗流过程，即第二级渗流。依次类推，可以定义每一级的渗流相变。对于无限大的系统，这种迭代可以一直进行，理论上可以定义任意级的渗流相变。考察不同级的渗流相变，即可探究系统动力学在历史依赖机制下的演化规律。

图2：历史依赖渗流过程示意图。（a）同一组节点具有A、B两层连接，用灰色直线隔开；（b）利用A层接连，节点可形成一个集团位形，记为C1；（c）在位形C1的各集团内，利用B层连接形成新位形，记为C2；（d）在位形C2的各集团内，再次利用A层连接形成新位形，记为C3；（e）在位形C3的各集团内，再次利用B层连接形成新位形，记为C4。由于示例系统较小，第三级迭代后位形不再变化。调节初始位形（删边比例），在每一级位形上都可以定义相应的渗流相变。对于无限大的系统，迭代可以无限地进行下去，即可以定义任意级的渗流，而每一级的渗流都依赖于前一级的渗流结果 [11]。

理论与模拟均发现随级数递增，渗流相变越来越剧烈，即超过临界点之后，巨分支的大小增长的更迅速。但是，有限尺度行为的分析发现所有有限级的渗流相变都属于同一普适类，即与标准的渗流（一次迭代）本质上是相同的。这也表明有限的迭代都没有从质上改变巨分支的形成方式与结构（由一些度较大的节点决定），而只是剥落了一些小分支。

我们知道无标度网络会给出趋于零的渗流临界点，即任意比例的随机删点或删边都不会破坏巨分支。迭代渗流也没有打破这一规律，只是抑制了巨分支的增长，即任意有限迭代的渗流临界点都是零。这一发现也符合上述分析，即有限迭代只能剥落小分支，而无标度网络的hub节点始终存在，并主导了渗流相变。

对于无限大的系统，迭代可以一直进行。研究发现，这种无限的迭代最终会改变系统巨分支的涌现方式，而呈现出不连续相变。由此可见，迭代渗流模型将之前很多模型中所展现的连续相变与不连续相变联系了起来。

此外，作者们也将该迭代操作实施于由脑功能网络和形态学网络构成的双层网络中，以逐级剥落节点，进而发现了人脑网络的一些异常结构，见图3。

图3：图3 由脑功能网络和形态学网络构成的双层网络在迭代渗流作用下稳态时在略大于临界点的位置得到的网络结构图。(a)健康人。(b)抑郁症患者 [11]。

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. 默默的小天鹅 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).

作者：英俊的绿茶、愉快的裙子

审校：忧心的金毛

编辑：zxdqd