1.4 逾渗理论与晶格模型

“逾渗”概念最早由数学家布鲁德本特和哈默斯利提出，用来描述无序介质中流体的无规则运动。无序的多孔介质并不只是存在于物理材料中，自然界中很多物质都具有无序特性。因此，在众多生物、物理、化学及社会自然现象中，逾渗概念有着重要的实际意义并且其应用范围不断扩大。在社会网络中，观点、行为的传播过程复杂多样，往往难以通过单一的模型进行准确刻画，借助逾渗理论，可以为信息级联现象的研究提供深入指导。逾渗理论的研究离不开理论模型的支撑，本节从晶格（Lattice）的角度讲解逾渗理论及其基本模型。

1.4.1 逾渗现象

逾渗（Percolation）是指系统之外的一种介质通过一定的路径进入系统内的过程[25]。实际上，逾渗现象是一种广泛存在的物理现象（不论是微观世界还是客观世界），如液体可以逾渗至有孔无序的介质。但逾渗与物理中的扩散（Diffusion）不同，扩散是指物质分子从高浓度区域向低浓度区域转移直到均匀分布的现象，而逾渗是当系统中的成分或某种意义上的密度变化达到一定值时，该系统的某些性质会发生显著的变化（类似“量变引起质变”），也即在某种特定状态下，系统某些物理现象的连续性会消失，而某些现象会突然出现。

逾渗现象在现实生活中普遍存在，如表1-1所示。逾渗现象中均存在一个状态发生变化的临界状态，一般称为“逾渗相变”（Percolation Phase Transition）：

庞大无序系统中随着某种密度、占据程度或联结程度增加（或减少）到一定程度，系统内突然出现（或消失）某种联结性，性质和状态发生突变，称为逾渗相变或尖锐的相变。

表1-1 身边的逾渗现象

逾渗相变时某种密度、占据程度或联结程度的临界值称为“逾渗阈值”（Percolation Threshold）。例如在导电复合材料中随着导电粒子浓度的增加形成连续导电逾渗网络时，相应导电粒子体积分数的临界值就称为该逾渗相变对应的逾渗阈值。逾渗相变和逾渗阈值的引入为了解逾渗现象的本质奠定了基础，逾渗理论的研究主要有如下特点：

●逾渗理论主要研究随机几何结构和强无序的系统；

●逾渗理论能与计算机模拟技术有效结合，对逾渗模型进行求解；

●逾渗理论具有特征函数，通常为逾渗概率、集团（群体）的平均大小等；

●逾渗阈值会受到各种内在因素和外在条件的影响。

目前逾渗理论已经在各个领域中有了长足的发展，尤其是在复杂网络的研究中。利用逾渗模型，一方面可以对复杂网络的动态特性进行探究，另一方面可以对网络节点状态（是否会被感染、是否会被影响等）进行研究。

1.4.2 基本逾渗模型

本小节将从键逾渗模型（Site Percolation）和座逾渗模型（Bond Percolation）两方面探究逾渗现象建模问题。

为了抽象化描述，通常逾渗模型是定义在一定类型点格上的几何模型[25]。1957年，英国著名数学家哈默斯利与布鲁德本特[26]将逾渗模型定义为一个二维方形点格，用以描述流体在无序多孔介质中的运动。如图1-10所示（正方形点格系统中共有a×a个节点），节点表示介质中的空隙，相邻的节点以概率p（0＜p＜1）相连，相连即表示流体可以穿过该空隙，将该现象定义为占据相应的边。

图1-10 逾渗模型示意图

若干个被边连接而成的节点集团称为连通集团（如图1-10中虚线圈出来的节点），其中节点的数量称为该连通集团的大小。此外，若逾渗现象能够发生，则原系统中存在一个与模型大小相当的连通集团，称为巨分量（Giant Component）。并且英国剑桥大学著名数学家杰弗里 • 格里梅特[27]已经证实，在足够大的N维逾渗模型中一定存在一个巨分量。

为了定量讨论逾渗模型，首先分析巨分量对逾渗相变的影响。在图1-10中，即便占据概率p较小，大部分节点仍有极大可能连通。然而，当整个系统的节点无限制增大时，巨分量出现的偶然性大大减少。不同p值下连通集团随系统尺度的变化如图1-11所示。

图1-11 连通集团随系统尺度变化效果图（占据概率p的影响）[28]

●p值较小时，系统尺度的增大会导致连通集团数量的增多，但是大小不会发生明显变化，无巨分量出现。

●p值较大时，系统尺度的增大会导致系统中某个连通集团的尺度发生显著变化，出现巨分量。

定义逾渗相变的序参量来表征系统中是否存在巨分量，其中N表示整个系统的大小、n为最大连通集团大小：

当系统中不存在巨分量时，各连通集团的大小为较小的定值，序参量δ趋近于0；当系统中存在一个巨分量时，其大小随系统大小的增大而增大，序参量δ收敛到一个小于1的定值。因此序参量是否为0可以衡量整个系统中是否存在巨分量。另外系统的第二大连通分量在δ从0变至非0值的临界点处取得最大值，因为一旦δ变为非0值时系统会因巨分量的出现而发生逾渗相变，全部键被占据，第二大连通分量的大小逐渐减至0。

研究人员对二维方形点格上的逾渗类型做了进一步的区分。由于点格中存在点（称为座）和边（称为键）两种基本元素，因此逾渗模型分为键逾渗模型和座逾渗模型两类[29]，如图1-12 a所示。

●键逾渗：所有的座是连通的，每条键或以占据概率p连通，或以概率（1-p）断开。

●座逾渗：所有的键是连通的，每个座或以占据概率p联结，或以概率（1-p）堵塞。

在键逾渗模型中，若键被占据则相邻的键处于联结状态。键是否连通由占据概率p决定，且p与相邻键的状态无关。判断两条键是否属于同一集团时，只要观察两条键是否有共同的连接点可构成一条相互连接路径即可，若可构成路径，则两条键在同一集团。图1-10中介绍的模型即为键逾渗。在座逾渗模型中，常用座是否被占据表示某种密度对逾渗过程变化的影响，若座被占据则相邻的座彼此联结。其联结过程同样也由占据概率p决定，同键逾渗类似，占据概率与周围座是否联结无关。判断两个座是否属于同一集团时，需观察两个相邻座是否都被占，如图1-12 c所示。

设想一个无限尺度的平面点格，点格上的各个键（图1-12 b）以概率p被占据（粗实线）或者以概率（1-p）被删除（细实线），彼此相邻的被占键构成一个连通集团。如图1-12 b所示的平面点格中包含3个连通集团，自左至右分别有n=8、n=2及n=2个被占键。图1-12 c中每个座以占据概率p被占据（实心圆圈）或者以概率（1-p）被清除（空心圆圈），已占座点形成一个连通集团。图1-12 c中共包含3个连通集团，自左至右分别有n=7、n=3及n=3个被占座。根据序参量的定义，假设存在一个临界概率或密度pc，使得当p＜pc时系统中只存在有限大小n的连通集团（n=1，2，…），当p≥pc时系统中存在巨分量使得它可以从点格的一“边”渗透至另一“边”，发生逾渗相变。令P∞表示逾渗概率，即一个被占座或被占键属于巨分量的概率，易知p＜pc时P∞（p）≡0；只要p＞0，P∞（p）为一个较小的非零值。对于方形点格的键逾渗现象，已知其临界概率pc近似为0.5，其与逾渗概率的关系如图1-13所示。

图1-12 键逾渗与座逾渗示意图

图1-13 逾渗概率与占据概率（或密度）的关系[30]

对于方形点格的座逾渗现象，其临界概率pc尚未求出精确解，不过通过计算机蒙特卡罗模拟可得出pc近似为0.592746。此外，研究人员通常根据pc将逾渗过程分为三个区域：p＞pc时处于上临界相，p=pc时处于临界相，p＜pc时处于下临界相。逾渗过程在该相的主要表现为“指数衰减”[31]。

图1-14显示了不同占据概率p（分别为0.45，0.55，0.59，0.65）下逾渗现象发生的过程，被占据的座为灰色，属于巨分量的座为黑色，而未被占据的座为白色。易知当p≥0.59时，网络中出现了巨分量，使得几乎整个网络的座均属于巨分量，发生了逾渗相变。

图1-14 占据概率对逾渗的影响[32]

1.4.3 晶格模型

本节对基本逾渗模型讲解的过程是以二维方格为例的，实际上对逾渗过程的建模有多种多样的几何模型，记为晶格（Lattice）[33]。在物理学中，晶格表示原子在晶体中排列规律的空间格架，而在社会网络中用晶格泛指晶体的空间格子这一几何图形。

假设一个一维晶格模型，其中无限长的等距的座排列成一条直线，并且每个座依概率p被占据，依概率（1-p）被删除，如图1-15所示。其中包含一个大小为5的连通分量，一个大小为2的连通分量，三个大小为1的连通分量。令∏（p，L）表示长度为L的一维晶格在占据概率为p的情况下发生逾渗的概率，当L→∞时，根据逾渗相变定义有：

图1-15 一维晶格占座示例

当L为有限长时，易知∏（p，L）=pL。令pc=1，利用计算机模拟不同长度的一维晶格发生逾渗的概率，结果如图1-16所示。当L→∞时，∏（p，L）逐渐收敛为不连续的阶跃函数。

图1-16 线性大小为L的一维晶格发生逾渗的概率

为便于了解和掌握不同晶格模型的逾渗阈值，本节将常见晶格类型在座逾渗和键逾渗两种状态下的逾渗阈值总结为表1-2。表1-2中第二列表示每个晶格的最近邻数，或者配位数（晶体结构中某质点周围与该质点直接相连的质点数）。其中一维晶格的座逾渗与键逾渗阈值均为1，二维方格的键逾渗阈值为1/2，座逾渗阈值经过计算机蒙特卡罗模拟可得到近似值为0.592 7。此外，在给定维度内，不管是座逾渗阈值还是键逾渗阈值，均随着最近邻数量（配位数）的增加而减小。在高维超立方晶格中，若晶格内不存在闭环，则其座逾渗阈值接近Bethe晶格的座逾渗阈值1/（z-1）[34]。

表1-2 不同类型晶格逾渗阈值

Bethe晶格是一类比较特殊的晶格，其中每个座有z个相邻座，这样每个分支都会产生（z-1）个其他分支。图1-17表示z=3的Bethe晶格，每个座均有三个邻居，并且每个邻居会产生z-1=3-1=2个分支。为便于理解，图1-17中处在几何中心位置的“座”可暂时认为是中心座（Center Site），由中心座向外延伸的邻居实际上构成了一个个“环”（Ring），每个环上的座称为一“代”（Generation），记为g，表示每“代”的座与中心座的距离。图1-17中由三个座组成的第一个“环”属于第一代，即g=1。由六个座组成的第二个“环”属于第二代。值得注意的是，在Bethe晶格中，所有的座都是同等地位的，因此“中心座”的概念不应从字面上来理解。根据Bethe晶格的特征，一维晶格实际上也是z=2的Bethe晶格，一维晶格中每个座都是独立的，并且每个座都有2个邻居，每个邻居产生z-1=1个方向的分支。

图1-17 z=3的Bethe晶格示例

逾渗问题可以用一维晶格或无限维晶格解析求解，而无限维晶格的情况则与Bethe晶格类似。超立方晶格（维度d→∞）[37]存在如下特性：

●晶格表明座的数量与晶格所含座总数的比值趋近于一个常数；

●晶格中的邻座不会形成闭环。

由于Bethe晶格具备这样的特性，通常用Bethe晶格类比无限维晶格。对于第一个特征，Bethe格的座总数Ntotal可以计算为

Bethe格表面座的数量Nsurface=3×2g-1（即最后一代），则有：

同理，可计算对于配位数为z的Bethe格，当g→∞时，有Nsurface/Ntotal→（z-2）/（z-1）。因此，Bethe晶格满足第一个特征。

对于Bethe格中是否存在闭环，依然可证明在超立方晶格中，当维数d→∞时晶格内具有环的概率接近0，即从中心座向外延伸，永远不会存在路径再次回到起点。例如，在维度为d的超立方晶格中的一条链式位置放置四个粒子，当第一个粒子被放置后，有2d个最近邻座可供放置第二个粒子。然而，对于第三和第四个粒子，只有（2d-1）个可能的座可放置粒子，则所有可能的链共有Nchain=2d（2d-1）2条。通过计算将四个粒子放置在一个闭环中，可得出由四个座构成的闭环有Nloop=2d（2d-2）×1种，则当d→∞时：

因此，无穷维晶格中不存在闭环。综上，逾渗现象可以通过Bethe晶格建模，进而对逾渗阈值进行求解。