下载掌阅APP，畅读海量书库
立即打开
键逾渗与座逾渗模型统称为各向同性逾渗模型（Isotropic Percolation），即逾渗过程中不存在一个特定的方向。除了各向同性逾渗模型外，还存在其他类型的变体，一般是对系统中占座或占键进行约束使其更加贴近实际。本节从复杂网络中的逾渗模型讲起，重点介绍 定向逾渗模型 （Directed Percolation） [36] 、 首达逾渗模型 （First-Passage Percolation） [37] 以及 爆发性逾渗模型 （Explosive Percolation） [38-39] 。
现有逾渗理论的研究多在统计物理、材料学领域，而本书主要探究网络、群体背后的机制，因此本节略去了复杂的物理公式，从复杂网络的角度阐述经典逾渗模型。
ER随机网络（1959年由匈牙利数学家埃尔德斯和瑞利提出 [40] ）是复杂网络中最简单的网络模型，其中任意两个节点依概率 p 连接。由此看来，ER网络可以利用键逾渗过程进行分析。与1.3.2节的键逾渗稍有不同，此时构成连通集团的键不仅限于相邻节点之间的键，网络中任意两个节点都可能形成连键。假设ER随机图中共有 N 个节点，易知键的总数为 p [ N （ N -1）/2]，每个节点平均连键 p （ N -1）个；当 N →∞时，每个节点平均连键近似为 pN ，即该网络的平均度为 pN 。研究人员发现当ER网络的平均度 pN ＞1时出现巨分量，即 ER网络的逾渗阈值 p c =1/ N [27] 。此外，在上临界相内，网络中连通集团的大小处于 N 量级；临界相内，网络中连通集团的大小处于 N 2/3 量级；下临界相内，网络连通集团大小处于ln N 量级 [28] 。当 p 值较小时，在量级为 N -1 的稀疏网络中呈现为如图1-18所示的树形结构。实际上在该树形网络中，相邻各层节点数之比为 pN ，节点间的平均最短连接边为ln N 。这也间接地体现了真实网络下的小世界特性，即在一个较大的网络中节点依然可以保持较短的距离。
图1-18 ER随机网络层次结构示例 [28]
同样，可以借助键逾渗模型对疫情传播进行分析。传统的传染病模型假设确诊患者和无症状感染者以一定概率将新冠病毒传播给群体中的其他人，经典的动力学微分方程假设个体能够实现完全混合，即每个新冠病毒携带者都有相同的概率将病毒传给群体中的所有人。现实生活中该假设是不合理的，每个人的社交距离是有限的，因此能接触到的易感人群也是有限的。在给定网络中，令节点表示每个易感个体，连边表示病毒可以在两个个体之间进行传播，未占据的边表示新冠病毒不会在两个个体之间传播，则键逾渗中的键占据概率 p 即为病毒传播概率。若网络中存在巨分量，一旦新冠病毒进入该连通集团，巨分量中所有个体均会患病（包含无症状感染者），网络进入疫情暴发阶段；若不存在巨分量，疫情显然不会大范围流行。当然，疫情的暴发也与初始患病者的数量有关。
假设存在有限个传染源，并且不会出现环境传人现象，那么人际关系将成为疫情传播的主要影响因素。复杂网络中通常用度分布衡量一个网络的结构，在此借助度分布来衡量人际接触网络结构。定义度分布为整个网络中所有节点的度的分布，有如下结论 [41] ：
真实网络的度分布符合幂律，即 P （ k ）∝ k - γ ，又可称为无标度 （Scale-Free，SF） 网络 [1] 。对于较大规模的无标度网络，幂指数通常为2≤ γ ≤3。
SF网络可以通过生成函数等方法求出逾渗阈值 p c →0，说明即使新冠病毒的传染性很弱，也可能引起疫情的流行。可以看出，这一结果给现实生活中疫情的防治带来了巨大的挑战。实际上SF网络中的绝大部分节点相对度很低，只有个别节点度值相对较高，称为中心（Hub）节点。正如群体中只有部分人有广泛的社交关系，可能因外出参会、家庭聚会、观看话剧等原因在短时间内接触到大量朋友。一旦这些人携带病毒，病毒会迅速扩散开来，形成“超级传染源”。常用KAPPA值衡量病毒的超级传播现象，对于新冠病毒而言这一值为0.1，即10%的人会成为超级传播者，正如SF网络中Hub节点的数量是有限的。因此，保护Hub节点、保护好潜在的“超级传播者”将有助于抑制疫情的进一步传播。然而，通常并不知道谁有可能成为网络中的Hub节点，而且逾渗理论无法分析病毒是如何经过一个个节点进行传播的。 这是逾渗理论的一个缺陷，即它只能分析网络的稳定状态，无法逐步分析网络的变化过程 [28] 。
键逾渗在疾病预防、信息传播等方面具有指导作用，而座逾渗模型也可以用来评估网络的鲁棒性。座逾渗模型中未被占据的座，或者以（1- p ）的概率被删除的座均可以被视作遭受外力攻击或因内部故障而毁坏的节点，则删除特定的占座是否还能发生逾渗现象成为衡量网络鲁棒性或抗毁性 [42] 的重要标志，同时也是发现网络节点重要性的策略 [43] 。对于SF网络，座逾渗的逾渗阈值同样也接近0，说明无标度网络足够鲁棒，即便大部分节点被毁坏，网络也能保证连通性，也会存在一个巨分量。实际上SF网络的高鲁棒性是由Hub节点决定的，Hub节点度相对较高但是数量很少。若随机选取网络中的节点进行破坏将很难选到Hub节点。然而，若对Hub节点进行蓄意攻击，则整个系统的连通性将会受到较大影响。
定向逾渗（Directed Percolation） [36] 为包含特定方向的逾渗过程。假设上一节讨论的方形点格不再以任意方向占键，而是以特定的方向形成连键，例如单向导电二极管。若每一条键都表示导电二极管，假设当该键的水平向只能自左向右导电，当该键的垂直向只能自上向下导电，反向均不导电。通过对方向的限定，在方形点格中定义了定向逾渗模型。同键逾渗和座逾渗模型相比，定向逾渗模型中格点之间的连通更加困难，节点加入连通集团的先后顺序至关重要，即定向逾渗过程引入了时间维度。
以特定风向下的森林火灾为例： t 0 时刻，森林中一棵树 a 0 因气候干燥并且长时间被阳光照射而局部起火；环境中此时盛行西北风，则 a 0 的燃烧状态将以概率 p 传递给 a 0 东侧和南侧的其他树木（假设树木以如图1-19所示的方形点格的形式排列）；随着时间的推移，新燃烧的树木，仍会沿着东、南方向以概率 p 引燃其他树木，如图1-19所示，直至出现逾渗相变。
图1-19 定向逾渗模型示例（右侧箭头表示时间线）
此外，定向逾渗模型处于下临界相、临界相和上临界相时，巨分量的形成过程具有明显的方向性。
首达逾渗（First-Passage Percolation）模型继续增强了对时间维度的限制，主要研究从一个固定初始点开始沿着图形的边前进，哪些点可以在规定时间内连通的问题。该逾渗模型由英国著名数学家约翰·哈默斯利于1965年提出 [37] 。
具体地，假设一个 d 维点格 Z d ，初始点记为0点。若 Z d 上的两个格点 u =[ u （1）， u （2），…， u （ d ）]和 v =[ v （1）， v （2），…， v （ d ）]满足如下关系，则格点 u 与 v 互为邻居：
当且仅当两个格点是邻居时，可以形成连键{ u，v }，记所有键的集合为 ∊ 。点格 Z d 上的一条路径定义为一个序列 u 1 ， u 2 ，…， u n ，序列中相邻节点 u i 与 u i +1 （ i =1，2，…， n -1）一定是邻居。如果对于 i ≠ j ，有 u i ≠ u j ，则这样的路径为自规避路径（Self-Avoiding Path）。此外，由键组成的序列（ e 1 ， e 2 ，…， e m ）也可以称为一条路径，其中 e k 与 e k +1 （ k =1，2，…， m -1）具有共同格点。首达逾渗模型的基本组成单元定义为一个随机变量族 t （ e ）： e ∊ ， t （ e ）为通过键 e 的时间。假设通过每个键的时间是独立同分布的， l =（ v 1 ， v 2 ，…， v n ）是 Z d 上的一条路径，通过时间为
格点 A 和格点 B 之间的通过时间定义为（inf{·}表示下确界）：
则形式化首达逾渗模型目标如公式（1-11）所示，即一个从原点出发在时间间隔 t 内可以到达的格点的集合：
爆发性逾渗（Explosive Percolation）模型本质上是对ER随机网络具有连续相变性质的随机增长模型（Random Growth，RG）的动力学修正而得到的。2009年由希腊雅典大学的阿克利奥塔斯等人 [38] 提出，值得注意的是在爆发性逾渗模型中疑似出现了非连续相变 [39] 。
首先回顾一下ER网络上的RG模型。在节点总数为 N 的ER网络上任取一个孤立节点，每一个时间步内以相同的概率随机选取两个节点占键（节点间的距离无限制），迭代该过程；若某个时间步ER网络中已有 t 条连键，则占键概率 p = t / N 。随着网络中占键的增加，各连通集团的规模逐渐增大，相邻的连通集团不断合并，导致网络中的第一大连通集团 G max （未发生逾渗相变前暂不称其为“巨分量”）进行动态演化。研究表明， 当ER网络的节点数 N →∞时， G max 在 p =1/2处会发生一个连续相变 [32] 。
爆发性逾渗模型基于对RG模型的如下修正：首先随机选择两条键作为候选占键集合，然后根据一定的规则选中其中一条键进行占据，而未被选中的另一条键则被舍弃，如图1-20所示。阿克利奥塔斯采取最小乘积法则（Product Rule，PR）挑选被占键，即挑选候选键中即将连接的两个连通集团的尺寸的乘积最小的键。图1-20 a为初始状态下网络中存在的连通集团，下一时间步（图1-20 b）预挑选键 e 1 和 e 2 形成新的连通集团（注 e 1 与 e 2 并非特指）：对于 e 1 ，即将连接的两个连通集团大小乘积2×5=10；对于 e 2 ，即将连接的两个连通集团大小乘积为3×2=6。由于6＜10，则挑选 e 2 进行占键，形成图1-20 c中的连通集团。下一时间步继续挑选占键候选集 e 1 与 e 2 ： e 1 即将连接的两个连通集团大小乘积为2×5=10， e 2 即将连接的两个连通集团大小乘积为3×5=15。由于10＜15，则选择 e 1 进行占键，形成如图1-20 d所示的连通集团。
图1-20 爆发性逾渗连通集团演化示意图
最小乘积法则优先连接尺寸较小的连通集团，会导致系统中各连通集团大小分布趋于均匀，无形中对第一大连通集团 G max 的生长增加了延迟。然而，当系统中的连通集团逐渐逼近逾渗阈值时，任意被占据的1到2条键就能导致 G max 的尺寸呈爆炸式增加，所以将该逾渗模型称为爆发性逾渗模型，有时也称为PR模型。
爆发性逾渗模型还应掌握相变宽度的概念，其定义如下：
最大连通集团
G
max
的大小从
增大至0.5
N
的过程中占键概率
p
的增量与节点总数的比值，即Δ
p
/
N
。
实际上当系统尺寸趋于无穷大时，传统RG模型的相变宽度趋近于一个非零常数，而爆发性逾渗模型的相变宽度趋近于0，因此相变性质存在本质的不同。
[1] 无标度指概率分布函数 F （ x ）对于任意给定常数 a ，存在一个常数 b 使得 F （ ax ）= bF （ x ）；幂律分布是唯一满足无标度条件的概率分布函数。