复杂网络上的爆发现象综述：相变、爆发、生命起源有何共同之处_风闻
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！2019-08-14 09:49
撰文|郭瑞东
审校|刘培源****编辑|张爽
**来源：**集智俱乐部
社会运动在失控前经历了怎样的演变过程？冷门话题为何在某个时间点突然引爆社交网络？遗传变异在然显现之前必须经过长期积累？2019国际网络科学大会的一篇综述文章，从渗流和同步现象出发，详细讨论了复杂网络上爆发现象的特征、成因和应用，揭开了爆发现象的谜题一角。
谁不想一夜成名？格拉德维尔在畅销书《引爆点》中介绍了创造流行的三原则——个别人物，附着力及环境的威力。然而在复杂网络的研究中，爆发现象 (Explosive phenomena)有着不同的定义。
今年5月，在网络科学的顶会netsci2019上，展示了一篇针对复杂网络中的爆发现象的综述论文，从现象，建模，应用等多个视角，论述了对网络中的渗流（Percolation），同步（Synchronization），拥堵（congestion）等现象的研究进展。本文从该综述中选取对研究者有用，对科学爱好者有趣的内容，带你初探网络上的爆发现象，篇幅限制，这里主要谈渗流相关的现象。
论文题目：Explosive phenomena in complex networks
论文地址：https://arxiv.org/abs/1907.09957
1 何谓网络上的爆发现象
统计物理中有个很有逼格的词——“相变”（phase transitions），其实就是描述水结冰，变成蒸汽这样温度一变性质就完全变化的现象，可如果变化本身是连续的（可微分的），没有涉及形态上的剧变，就被细分成了二阶相变（second-order phase transitions），例如温度降低后变成超导体。
将相变这个统计力学的概念应用到复杂网络上，就可以用来描述那问题来了，复杂网络中是否存在相变现象了，相变是连续的还是“跃迁”式的？
复杂网络上的爆发现象，就是一种网络的相变。在09年，Achlioptas首次开启了对网络中爆发现象的探索。之后的研究指出，网络中的爆发现象不止和生命的诞生相关，还有诸如“怎样最高效地控制虚假信息在网络中传播”这样实际的应用。
网络中的爆发现象，不论其场景如何，其成因的本质在于微观演化中的动力学，会阻碍宏观现象的出现。也就是说，不同的网络初始结构和网络中连接的生成机制，会影响网络中各个局部区域变化及连接生长的方式，而当节点互相争抢额外的连接机会时，就会暂时让网络整体不呈现特定的宏观上的特征，例如整个网络中所有节点完全连接。但暂时的阻碍毕竟不会持久，总会有一个时刻，网络发生了相变，上述现象，就被称为网络中的爆发现象。
2 网络中的渗流与爆发现象
图1：网络上的渗流现象示意图，来源：http://www.johnkerl.org/rcm/doc/about_rsp.html
渗流最初的场景是液体在一个随机无序多孔的介质中，如何扩展和流动，后来被用于描述在各类网络，信息如何传播。渗流听起来好专业啊，但看了上面的动图，你可以形象地理解何为渗流。
图2a：网络渗流的生成机制（Product Rule）示意图
图2b：展示网络随时间演变下宏观特征变化
图2c：为Product Rule生成的网络举例
而所谓网络渗流中的爆发现象，上图给出了一个最简单易懂的例子。中间的图b，横轴是用于生成该网络的当前已用时间，纵轴是网络中连接最多节点的组件（component）的节点个数，与网络中全部节点个数的比值，也是我们关注的网络的宏观特征。其中的蓝色和黑色分别代表的是ER（Erdos-R´enyi）和BF（Bohman Frieze），这是用于生成随机网络的两种经典模型，其中ER方法是以概率p连接N个节点中的每一对节点，而PR（Product rule）是一种新的生成随机网络的方式。可以很直观地看到，PR模型下，变化看起来是不连续的，突发的。
什么样的规则，能产生上述的爆发现象呢？总体来看，这个规则，要使用全局信息来指导局部连接的生成，以阻止网络中节点数较大的组件的诞生。据此，就有了左边图a展示的规则，在当前网络中随机连接两组点，每组两个，然后分别计算每组两个点相连的网络组件（componment）的节点数的乘积，选择该乘积较小的点，如果乘积相同，则随机选择一个，上图A的例子中，图中就选了e2（2×2）而不是e1（3×12）作为加入节点的边。
3 更多的网络生成模型
接下来读者可以发挥想象力，看看基于上述的原则，还能设计出怎样的网络生成规则。不同的网络生成规则，代表了对不同现实中各类现象，以不同的侧重点进行的通用简化，也是用来和真实现象进行对比的空模型（Null model），并不只是数学家的智力游戏。
图3：网络生成模型示例：dCDGM 模型
上图展示了dCDGM 模型，每步选取随机2个包含m个组件的集合，对两个集合中节点数最少的组件，随机添加一条边，将其连起来。
图4：网络生成模型示例：DS 模型
另一种Devil’s staircase（DS） 模型，随机选择k条边，然后选择k条边中连接的组件节点个数最相近的那个，如上图中，k为3，选择了实线而非虚线的边。
也不是所有的生成都需要网络中局部结构之间的互动，例如高斯模型，就是随机在网络中增加一条边，如果该边会增加网络中最大组件的节点数，该边就按高斯定律，有一定的可能被抹去。
但不管生成模型是怎样的，我们关注的都是网络宏观的特征，下表整理了各种网络中的生成模型，图中最右边一栏指出了当网络趋于无限大时，依据数学推演出的，在网络无穷大时的网络演变（最大组件节点所占比）折线图，由于网络中的爆发现象会导致网络具有不可均一性（后文会详细论述），因此比较有限网络和无限网络的演变曲线的区别，可以用来评价模型在小数据集上的代表性。
图5：各类网络生成模型的对比
4 真实世界中和渗流有关的爆发现象
在社交网络和国际贸易网络中，出现类似上述模型描述的爆发现象并不奇怪，真正有意思的是在蛋白质的相似性网络中，也存在着爆发现象。
HPHN（Human Protein Homology Network） 是对人类体内的蛋白质，按照其相似性连接，组成的网络，描述了蛋白质通过复制和突变，能怎样一步步地从一种形态变为另一种形态，该网络的结构，决定了生命进化的路径。而真实的蛋白质相似网络，是先形成一个个大小相似，但互不连接（无法通过突变转化）的多个组件，之后再通过类似社交网络中的“弱连接”让组件连接起来。
图6：通过对比根据蛋白质相似性排序组成的HPHN网络和不同生成模型，说明HPHN网络呈现爆发现象
如图所示，纵轴是最大组件节点数占全网络总节点数的比例，红色和蓝色分别代表了上述的PR模型及ER模型，黑色是将蛋白质按相似度高到低连接起来形成的网络，可以看出图中黑线更接近红线。这说明生物的进化过程中，蛋白质要从一种功能进化到另一个功能，花了很多时间，累计突变，看似没用，但却是在为爆发做准备。
上述通用的现象，也可以解释为何癌症的发现往往没有前兆：有害突变的积累，最终导致了蛋白质网络中的某两个点，最终连接到了，也就是通过突变成为致癌蛋白。
5 爆发现象呈现的非自我均一性（Non-self average）
管中窥豹说的是从一个局部无法推出整体的性质，学术界将其称为非自我均一性。而展现出爆发现象的网络，也无法根据从中抽取的一个子网络的性质，来预估网络整体的性质。在这样的网络上，当观察的子网络变大，观察得出的统一值，例如平均值、最大值、最小值，不会趋近于整个网络的对应值。也就是说，对于展现爆发现象的网络，你取其中10%的节点来分析，我取其中90%的节点来分析，两人分析的结果从理论上，在对网络真实的状况的代表性上没有好坏之分。
图7：展示不同大小的网络在多次随机模拟中呈现的最大组件大小的不稳定性
上图中的横轴是时间，纵轴是最大组件节点数占总节点数的比例在多次模拟中的方差，图中不同的颜色代表不同大小的网络。可以看到在爆发现象出现之前，不同大小的网络，在多次模拟中，其最大节点的变异性随时间有显著的波动，直观地看，红线和蓝线的差距，与绿线和蓝线的差距，并没有显著的区别，这说明了在前文所述的DS生成模型下，网络呈现非自我均一性。
图8：碱基链通过自催化而连接的过程，来源：https://journals.aps.org/pre/abstract/10.1103/PhysRevE.98.022408
生命从原始汤（primordial soup）中诞生的过程，在理论模拟中，也展示了爆发现象。例如，碱基链通过自催化（autocatalysis）而连接（ligation）。
而在模拟环境下，不同碱基链组成的连接网络，网络中最大的组件节点数所占的比例呈现爆发现象。
图9：碱基连接网络的宏观特征，来源：https://journals.aps.org/pre/abstract/10.1103/PhysRevE.98.022408
如上图所示，该研究还观察到了碱基连接网络展现了如非自我均一性等和爆发现象有关的宏观特征，由此推断，早期的可自我复制的分子是持续涌现出的多个有限大小的碱基序列，之后爆发式的产生连接多串序列的复杂大分子。这项研究说明自我复制这一和生命诞生有密切联系的特征，与网络中的爆发现象有关。
6 研究网络中的爆发现象的实际应用
社交网络中传递的虚假信息，对于保持社会稳定有巨大的危害，颜色革命的爆发看似没有征兆，但若是了解了网络渗流中的爆发现象，就可以将其看成是假信息传播累积带来的必然会发生的“相变”。
通过对网络进行模拟，例如讲PR模型中用于判断是否加入一条边的规则由节点数乘积较小改为节点数之和较小（Sum Rule），可以模拟社交网络中的信息的传递，从而可以预估网络中爆发现象出现的时间，以提前进行预警。相近的应用场景是通过模拟，找出预期能够更高效的阻止网络中最大组件组件变大的节点。
这类似本文开头提到的《引爆点》这本书提到的个别人物原则，只是书中是用来引爆潮流，而这里是如何高效的让网络获得对某种谣言或病菌的“抗体”，让网络具有群体免疫力。除了对特定节点进行干预，爆发行为的研究，对如何最高效的将网络拆分成多个部分，也有指导意义。
7 网络中的爆发现象还有哪些？
除了渗流，网络中的节点振荡的频率同步随时间的变化，也会由于局部节点的相互作用，展现出爆发现象，也就是突然间网络中的节点都同步了。目前已有很多模型，对其进行建模，也有很多具体应用场景。例如大脑中神经元网络在自发同步过程中展示的爆发现象，和意识的产生有关，而心跳节律的维持，也和网络中的爆发现象有关。电网中不同节点间，也会出现爆发性的同步现象，从而更好的理解与同步有关的爆发现象，有助于能源的调控。
在交通网络中，拥堵来得悄无声息，这想必很多人都有所体会。而传染病的突然流行，则是疾病传播场景下的爆发现象。而在多层网络上，例如不同类型的交通工具（飞机、大巴、火车）共同组成的交通网，也会出现爆发现象，如下图所示：
图10：航空、公路、铁路交通网络中的爆发现象对比
回顾这项研究工作，首先要指出，爆发现象是复杂网络中普遍存在的一种现象，就如同标度不变性（scale-free）一样。透过这个角度，可以对不同类型的网络，进行统一的建模，从中找出不同学科的共有逻辑。其次要强调的是，当前的研究，尚且缺少对爆发现象程度的定量分析，也没有对网络中局部接受到多少全局信息和网络中爆发现象的激烈程度进行关联，这是未来研究的重点。
网络中的爆发行为背后，都是来自局部网络节点间微小但持续的改变，由于节点的选择，导致了看起来没有效果，但累积终会带来爆发这一现象，这正应了“功不唐捐”这个词，也就是所谓的“勿以善小而不为，勿以恶小而为之”。人类社会的诸多行为表象，背后深层规律都在网络科学中。
本文经授权转载自微信公众号“集智俱乐部”。
特 别 提 示
1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。
2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。
相关阅读