Chapter 1 随机图和网络模型

这是对Claudius Gros的教材《Complex and Adaptive Dynamical Systems: A Comprehensive Introduction》© 2024的笔记，完整的图书可以从斯普林格购买：Complex and Adaptive Dynamical Systems: A Comprehensive Introduction | Springer Nature Link

图论的基本概念

在开始介绍有关网络的概念之前，首先需要介绍的是有关图论的相关内容。

• 顶点度(Degrees of a Vertex)
  一个图由\(N\)个顶点相互连接构成，其中每个顶点的度数定义为与某个这个顶点连接的边的个数。
  
• 配位数(Corrdination Number)
  配位数指的是整张图的平均顶点度。

在这里，我们引入随机图（random graph）的概念：一个随机图指的是图中的两个顶点以概率\(p\)连接的图称为随机图。\(p\)称为随机图的连接概率(Connection Probability).

Erdős-Rényi图是一种特殊的随机图，它由\(N\)个顶点和\(\frac{Nz}{2}\)条边随机连接，因此其连接概率为：
\[ p=\frac{Nz}{2}\frac{2}{N(N-1)}=\frac{z}{N-1} \]

当构成图的元素数量趋近于无穷大的时候，此时的极限称为热力学极限。对于Erdős-Rényi图，\(N\rightarrow 0\)时候连接概率的热力学极限为\(p\rightarrow 0\).

小世界效应

定义随机图的直径\(D\)为所有可能的顶点配对组合之间的最大分离度。如果一个具有对于给定的平均度数\(z\)和顶点数\(N\)的图，\(D\)可以近似为：
\[ z^D\approx N \] 也就是说， \[ D \propto logN \]

即\(D\)正比于\(logN\)。称这样的图/网络具有小世界效应 （Small World Effect），具体而言，小世界效应指的是连接同一个网络中的两个结点的平均距离比构成该网络的结点总数小若干个数量级， 具有小世界效应的网络往往可以通过几个顶点就能够遍历绝大部分的其他结点。

• 网络中的连通分量
  在网络中，称一组连接的结点为这个网络的连通分量(cluster)，聚类系数（Clustering Coefficient） 为相邻结点之间有边的概率，对于随机图而言，其中的一个结点通常具有\(z(z-1)/2\)对相邻的结点，根据之前的推导，那么随机图聚类系数同等于Erdős-Rényi图的连接概率，即为：
  \[ C_{rand}=\frac{z}{N-1}\approx \frac{z}{N} \] ​ 聚类系数越大表明网络的连通性越强。

• 团
  在网络中，定义团(Cliques)为一组满足如下条件的顶点：

  • 每个顶点都通过一条边与其他所有顶点相连
    
  • 团外的任何顶点都不会和团内的所有顶点相连

  如果把团在社交网络中类比，那么团的意思是在这个社群中所有的人都知道对方。
  在有\(N\)结点和连接概率为\(p\)的Erdős-Rényi图中，存在大小为\(K\)的团的数量为：
  \[ C_N^Kp^{K(K-1)/2}(1-P^K)^{N-K} \] 即从\(N\)个顶点中选择\(K\)个顶点，这些顶点两两连接，并和其他结点不连接。

一些研究统计了真实的网络中的聚类系数，列表如下，其中\(C_{rand}\)表示同等情况下的随机图的聚类系数：

	\(N\)	\(C\)	\(C_{rand}\)
Movie Actors	225226	0.79	0.00027
Neural Network	282	0.28	0.05
Power Grid	4941	0.08	0.0005
Internet Domains	6242195	0.20	0.000006

可以发现，相比于随机图，真实的网络具有相当大的聚类系数，连通性要比随机图好得多，这意味着真实的网络中存在小世界效应。这是因为：

• 真实的网络中可能存在相当多的环路，然而许多随机图在达到热力学极限之后倾向于形成树图而非环路
• 现实中的网络中存在二部图（Bipartite），即一种包含两组顶点，且顶点仅在组之间存在连接。二部图的出现会增加聚类系数。

度分布

度分布函数

定义有数量为\(X_k\)的顶点中存在度数为\(k\)，那么\(p_k=X_k/N\)表示在所有的顶点中有多少个结点的度数为\(k\)。有\(\sum_kp_k=1\)。

在Erdős-Rényi图中，\(p_k\)服从二项分布：
\[ p_k=C_{N-1}^kp^k(1-p)^{N-1-k} \] 当\(N>>k\)时，这个分布退化为泊松分布，有：
\[ p_k=e^{-z}\frac{z^k}{k!} \] 根据泊松分布的性质可以求得\(p_k\)的均值和方差都为\(z\).

幂律分布和无标度网络

存在一种特殊情况是当\(k\)非常大的时候，\(p_k\)与\(k^{-\alpha}\)成正比关系，其中\(\alpha\)为一个系数，因此\(p_k\)的变化符合幂律。在这种情况下，\(p_k\)的平均值为： \[ \overline{p_k}=\frac{\alpha-1}{2-\alpha}(1+k)^{2-\alpha}|^K_0-1 \] 当\(\alpha\leq2\)的时候该式子不成立，当\(\alpha>2\)时\(\overline{p}=\frac{1}{\alpha-2}\), \(\alpha >3\)时方差为无穷大。

幂律分布具有尺度不变性（Scale Invariance）： \[ p(ak) = a^{-\alpha}p(k), \]

其中 \(a>0\) 为任意常数。可以看到，对变量进行尺度伸缩后，分布函数的形式保持不变，仅差一个归一化因子。因此，该分布不存在典型的特征尺度（Characteristic Scale）。

若网络的度分布满足幂律关系：

\[ p(k)\propto k^{-\alpha}, \]

则称该网络为无标度网络（Scale-Free Network）。无标度网络的典型特征是存在少量具有极高连接度的节点，以及大量连接度较低的普通节点。

与泊松分布对应的 Erdős–Rényi 随机图不同，无标度网络具有更强的异质性（heterogeneity）：网络中的大部分连接集中于少数节点，这些节点在信息传播、同步以及网络鲁棒性等动力学过程中通常发挥主导作用。

谱分析

下面我们进一步对随机图的性质进行谱分析。

随机图的邻接矩阵和特征值

首先要做的事情是将整个图以矩阵的形式描绘出来，以便进行线性代数域的分析。对于一个具有\(N\)个结点的图，定义其邻接矩阵为大小为\(N×N\)的矩阵，对于矩阵内部的每个元素\(A_{i,j}\)，如果对应的结点\(i\)和\(j\)相连，则\(A_{i,j}=1\)，否则为0.

设随机图 \(G=(V,E)\) 的邻接矩阵为 \[ A_{ij}= \begin{cases} 1,& (i,j)\in E\\ 0,& \text{otherwise} \end{cases} \] 邻接矩阵可以看作网络上的传播算子（propagation operator），对于某个利用这个传播的定义在每个结点上的信号\(x\)，\(x\)的符号表示信号的相位，其传播一轮之后的在图上这个信号在图上每个结点的强度为矩阵乘积 \(Ax\) ： \[ x(t+1)=Ax(t) \] 邻接矩阵的特征向量描述网络天然支持的传播模式，而对应特征值则描述该传播模式在传播过程中的放大率，其满足： \[ A\mathbf{x}=\lambda \mathbf{x} \] 因为\((A^k)_{ij}\)表示从 \(i\) 到 \(j\) 长度为 \(k\) 的路径数，当 \(k\) 很大时由最大特征值主导： \[ A^k \approx \lambda_1^k \] 所以主特征值对应网络中最容易扩散和维持的传播模式，并决定网络整体的传播能力：主特征值越大，说明图中路径增长越快，信息传播越容易。

邻接矩阵的特征向量描述网络天然支持的传播模式，而对应特征值则描述该传播模式在传播过程中的放大率。因此，主特征值对应网络中最容易扩散和维持的传播模式，并决定网络整体的传播能力。

因此这个邻接矩阵的特征值表示了若干组强连接的结点之间的连接强度，主特征值表示了强链接的一群互相连接并相互强化的节点所形成的主导结构的连接强度。换言之，从传播的角度来看，邻接矩阵的特征向量描述了网络中可能存在的传播模式（propagation modes），而对应的特征值则描述了这些传播模式在传播过程中的增长率或放大能力。

对于动力学过程\(x(t+1)=Ax(t)\)，沿着特征向量方向 \(\mathbf v_i\) 的扰动将以\(\lambda_i^t\)的速率传播。因此，特征值越大，对应模式在网络中的传播和扩散能力越强。

其中，最大特征值（主特征值）对应网络中最容易被放大和维持的传播模式，因此反映了网络整体的信息传播能力和连接强度。

谱密度函数与半圆律

设随机图邻接矩阵的特征值为

\[ \lambda_1,\lambda_2,\cdots,\lambda_N \]

其谱密度函数定义为：

\[ \rho(\lambda) = \frac{1}{N} \sum_{i=1}^{N} \delta(\lambda-\lambda_i), \qquad \int_{-\infty}^{\infty}\rho(\lambda),d\lambda=1. \]

谱密度函数描述了特征值在实轴上的统计分布情况。对于足够大的均匀随机图（例如 Erdős–Rényi 随机图，在 \(N\to\infty\) 且平均度 \(z\gg1\) 的条件下），利用格林函数（Green’s Function）方法，可以求得随机图邻接矩阵的渐近谱密度：

\[ \rho(\lambda)=\begin{cases} \sqrt{4z-\lambda^2}/(2\pi z), \lambda^2<4z\\ 0,\lambda^2>4z \end{cases} \]

其中 \(z\) 为网络的平均度。

该结果表明，大多数特征值集中分布于区间

\[ [-2\sqrt z,;2\sqrt z] \]

内，其谱密度呈现半圆形分布，因此称为半圆律（Semicircle Law）。

从几何上看，谱密度曲线在 \((\lambda,\rho)\) 平面中的轨迹对应于一个椭圆的上半部分，因此表现为半圆形状。半圆律表明：对于足够大的随机图，除去反映整体平均连接结构的主特征值之外，其余特征值主要来源于网络连接中的随机涨落。换言之，半圆部分对应随机背景（noise bulk），而偏离半圆分布的孤立特征值则往往对应网络中的真实结构，例如社区、模块、层级结构或 Hub 节点等。

因此，谱分析的一个重要思想是：

半圆律给出了“纯随机网络”的谱基线（spectral baseline）；任何显著偏离该基线的特征值，都可能反映网络中的非随机结构。

图的拉普拉斯矩阵

离散的拉普拉斯算子

在连续域中，多元函数\(f(x_1,...,x_n)\)的拉普拉斯算子是所有自变量的混合二阶偏导数之和： \[ \Delta f=\sum_{i=1}^n\frac{\partial^2f}{\partial x_i^2} \] 二元函数的拉普拉斯算子可以采用如下方法近似计算： \[ \begin{align} \Delta f&=\frac{\partial^2f}{\partial x^2}+\frac{\partial^2f}{\partial y^2}\\ &\approx \frac{f(x+\Delta x,y)+f(x-\Delta x,y)-2f(x,y)}{(\Delta x)^2}+ \frac{f(x,y + \Delta y)+f(x,y - \Delta y)-2f(x,y)}{(\Delta x)^2} \end{align} \]

对一个二元函数进行离散化采样，得到下面的矩阵： \[ \begin{bmatrix} f(x_1,y_1) & f(x_2,y_2) & \cdots & f(x_n,y_1)\\ \cdots & \cdots & \cdots & \cdots \\ f(x_n,y_1) & f(x_n,y_2) & \cdots & f(x_n,y_n)\\ \end{bmatrix} \] 点\((x_i,y_j)\)处的拉普拉斯算子可以通过离散化二元拉普拉斯算子的方法得到：
\[ \begin{align} \Delta f&\approx \frac{f(x+\Delta x,y)+f(x-\Delta x,y)-2f(x,y)}{(\Delta x)^2}+ \frac{f(x,y + \Delta y)+f(x,y - \Delta y)-2f(x,y)}{(\Delta x)^2}\\ &= f(x_{i+1},y_j)+f(x_{i-1},y_j)+f(x_i,y_{j+1})+f(x_i,y_{j-1})-4f(x_i,y_j) \end{align} \]

即\((x_i,y_j)\)相邻结点的值减去四倍的自身。

图拉普拉斯矩阵和特征值

即一个函数\(f_i\)表示一个具有\(N\)个结点的图，定义图拉普拉斯矩阵为： \[ \Lambda_{ij}=(\sum_lA_{il})\delta_{ij}-A_{ij}=\begin{cases} k_i, i=j\\ -1, i\text{ and }j\text{ are connected}\\ 0,\text{otherwise}\\ \end{cases} \] 其中\(k_i=\sum_jA_{ij}\)为顶点\(i\)的度数。

将上述式子进行归一化，得到归一化的拉普拉斯算子：
\[ L_{ij}=\begin{cases} 1,i=j\\ -\frac{1}{\sqrt{k_ik_j}},i\text{ and }j\text{ are connected}\\ 0,\text{otherwise}\\ \end{cases} \] 归⼀化图拉普拉斯算⼦的特征值可以从底层图拓扑的⻆度进⾏直观解释。不过，首先需要从图中移除所有孤⽴节点，因为这些节点不会产⽣邻接矩阵的元素，相应的\(L_{ij}\) 值将定义不明确。

对于归一化拉普拉斯矩阵可以简写为： \[ L = I - D^{-1/2} A D^{-1/2}= I-S \] 其中\(D^{-1/2}\)为归一化的度矩阵，其中内部的每个元素都是\(1/\sqrt{k_i}\)；\(I\)是单位矩阵。

令\(S\)的特征值为\(\mu\)，对于利用图传播的某个信号\(x\)，那么有\(Lx=(1-\mu)x\)，从而\(\lambda=1-\mu\)，利用Rayleigh Quotient (\(|x^TSx|\leq x^Tx\))可以求得\(S\)的特征值满足\(|\mu|\leq1\), 因此有\(\lambda\in[0,2]\),并对其排序： \[ 0=\lambda_0\le \lambda_1\le \cdots \le \lambda_{N-1}\le 2 \]

下面我们对归一化的拉普拉斯矩阵的特征值进行讨论：

• 零特征值 其中最小的特征值被称为零特征值\(\lambda_0=0\)，零特征值说明了图中存在不连通的部分。零特征值的特征向量为：
  \[ \mathbf{e}(\lambda_0)=\frac{1}{\sqrt{Const}}\begin{bmatrix}\sqrt{k_1}\\ \cdots \\\sqrt{k_N}\end{bmatrix} \] 其中\(Const\)是一个归一化的常数。 需要注意的是，特征向量中的负号表示反相。

  因此，对于归一化的图拉普拉斯矩阵，其零特征值的数量说明了图中有多少个相互不连通的子图，且对于一个包含 \(a\) 个互不连通连通分量的图，其拉普拉斯矩阵具有 \(a\) 个线性无关的零特征向量。每个零特征对应的特征向量只在它自己的子图上非零，而在其它所有相互不连通的子图上均为零。

• 特征值为1
  在高度均匀且稠密的图中，除了少数描述整体结构的模态之外，大多数模式经过邻居平均后都会被迅速抵消，因此对应的归一化邻接矩阵\(S\)的特征值\(\mu\)接近 0，从而归一化拉普拉斯的大部分特征值聚集在 1 附近。

• 最大特征值（2）
  对于\(L=I-S\)，如果存在归一化拉普拉斯矩阵达到最大特征值 \(λ=2\)，有： \[ Lx=2x, \] 则\((I-S)x=2x\), 得到\(Sx=-x\)，即经过一次邻居加权平均之后，图信号 \(x\)​ 整体翻转符号。也就是说，若某个节点的值是正的，那么它的邻居平均必须是负的；若某个节点的值是负的，那么它的邻居平均必须是正的。

  因此，每条边两端都必须倾向于取相反符号。只有二部图能够在整个网络上实现这种完全交替的符号分布，因此 \[ \lambda=2 \iff \text{图为二部图}. \] 从图信号处理的角度看，\(λ=2\) 对应图上能够存在的最高频振荡模式。

渗流相变

所有图中随机性最强的是Erdös–Rényi图。我们可以适当放宽随机性的程度，构造具有任意给定度分布的随机网络。这一方法也被称为“配置模型”（Configurational model）。我们将利用配置模型来研究“渗流相变”（Percolation Transition），该相变随链接概率\(p\)的变化而发生。当图中仅包含少量链接时，图会分解为一组不相连的子图，但在链接密度较高时则不会，这种现象对应的变化即为渗流相变。

配置模型

给定顶点数 \(N\) 和目标度分布 \(p_k\)，可以按照如下步骤构造一个具有该度分布的随机图：

1. 对每个顶点 \(i\) 根据度分布 \(p_k\) 随机生成其度数 \(k_i\)，并为该顶点分配 \(k_i\) 个半边（stub）。

2. 将所有半边放入一个集合中，并随机选择两个半边进行配对，连接形成一条完整边。

3. 重复上述过程，直到所有半边均被配对完成。

当所有半边都被连接后，得到的图就是满足给定服从\(p_k\)的度序列

\[ (k_1,k_2,\dots,k_N) \]

的随机图样本。

由于边的连接方式完全随机，因此该图是所有满足该度序列的图所组成集合（ensemble）中的一个随机成员。

这个配置模型的平均度为：
\[ z=\sum_kkp_k = {\langle k\rangle} \]

配置模型的聚类系数

配置模型中的边通过随机配对半边（stub）生成，因此网络中的三角形主要由随机连接产生。

设网络平均度为\(z=\langle k\rangle\), 则网络中的总半边数约为：

\[ Nz. \]

考虑某节点的两个邻居 \(i\) 和\(j\)。节点\(i\) 平均拥有\(\langle q\rangle\) 条可继续向外连接的半边，节点 \(j\) 也是如此。因此两者随机连接形成边的概率约为

\[ C = \frac{\langle q\rangle^2} {N\langle k\rangle}= \frac{1} {N\langle k\rangle} \left( \frac{\langle k^2\rangle-\langle k\rangle} {\langle k\rangle} \right)^2 \]

可以看到，

\[ C\propto\frac1N \]

因此，当\(N\rightarrow\infty\)时，

\[ C\rightarrow0 \]

这说明配置模型虽然能够准确保持给定的度分布，但无法产生真实复杂网络中常见的大量三角形结构，因此其聚类系数通常远低于现实网络。

相邻结点的度分布

设随机选择网络中的一条边，并沿该边到达其另一端的顶点。由于度数较大的顶点拥有更多边，因此被选中的概率与其度数成正比。

若网络的度分布为\(p_k\)，则沿随机边到达的顶点，其度数为 \(k\) 的概率不再是 \(p_k\)，而是

\[ \frac{k p_k}{\sum_j j p_j} \]

其中 \(z = {\langle k\rangle}= \sum_j j p_j\) 为网络的平均度。

剩余度

当研究连通分量大小、渗流过程或网络中的环结构时，我们通常更关心从该顶点继续向外延伸的边数，而不是该顶点的总度数。

假设沿边从顶点 \(A\) 到达顶点 \(B\)：

若 \(B\) 的总度数为 \(k+1\)，则其中有一条边已经用于连接 \(A\)，因此剩余可继续探索的边数为\(k\).

定义随机边到达顶点后的剩余度（Excess Degree）分布为

\[ q_k, \]

则有

\[ q_k = \frac{(k+1)p_{k+1}} {\sum_j j p_j} = \frac{(k+1)p_{k+1}} {\langle k\rangle}. \]

这里的 \(q_k\) 表示：沿随机选择的一条边到达某顶点后，该顶点还剩下 \(k\) 条可继续向外探索的边的概率分布。因此，\(q_k\) 描述的是网络局部扩张能力（branching process）的统计性质，在渗流理论、随机图连通性分析以及无标度网络研究中具有重要作用。

那么在一个度分布为\(p_k\)的网络中，与一个顶点连接的另一个顶点\(B\)向外延伸的平均边数为，即顶点\(A\)的平均剩余度为：
\[ {\langle q\rangle} = \sum_{k=0}^\infty kq_k = \frac{\sum_{k=0}^\infty k(k+1)p_{k+1}}{\sum_j j p_j} = \frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle} \]

其中\({\langle k^2 \rangle}=\sum_kk^2p_k\)，是\(k\)的二阶矩。

相邻结点的数量

现在定义\(z_m\)表示与某个结点相距\(m\)的结点的平均个数，从上面的式子中可以知道与\(A\)一条边连接的结点\(B\)向外的平均边数为\(\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}\),那么与\(A\)距离为2的结点的平均个数为\(B\)结点的数量与这个值的乘积： \[ z_2=\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}\times{\langle k\rangle}={\langle k^2\rangle}-{\langle k\rangle}=\sum_kk^2p_k-\sum_kkp_k \]

由于与\(A\)通过两条边相连，因此称为二阶相邻点。

Erdös–Rényi图的\(z_2\)

对于Erdös–Rényi图而言，其度分布函数符合泊松分布，因此将\(p_k=e^{-z}z^k/k!\)带入上式中，得到: \[ z_2=z^2={\langle k\rangle}^2 \] 因此，在Erdös–Rényi图中，某个顶点的二阶相邻顶点的数量为其一阶相邻结点的平方。

那么，对于距离结点\(A\)的任何阶\(m\)的相邻结点的数量，可以通过\(m-1\)的时候的相邻结点数与二阶剩余度相乘递推得到： \[ \begin{align} z_m&=\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}z_{m-1}=\frac{z_2}{z_1}z_{m-1}\\ &=\left[\frac{z_2}{z_1}\right]^{m-1}z_1 \end{align} \] 那么就可以通过\(z_2/z_1\)来判断从某个结点触发，这个图是在扩张还是在缩小：
\[ \lim_{m \rightarrow \infty} z_m = \begin{cases} \infty,\text{if }z_2>z_1\\ 0,\text{if }z_2<z_1\\ \end{cases} \]

渗流阈值

那么其中的阈值点自然发生在\(z_1=z_2\)的时候，

• 当小于这个渗流转变点的时候，所有的邻居的总数可以通过等比数列求得： \[ \sum_mz_m=\frac{z_1^2}{z_1-z_2} \]

  可以发现此时与初始结点连接的总结点数始终是一个有限值，这说明成一个点出发可以到达的结点数就是有限的，那么图中还存在着从这个点出发到不了的孤立点。并且此时顶点和顶点之间的距离不可能无穷大，整个图会被分解为若干个不相连的子图。

• 当高于这个渗流阈值的时候，这个级数呈现发散状态，形成一个巨大的连通块，称为巨型连通分量（Giant Connected Component）.

下面重点来讨论通过配置模型导出的渗流阈值下的情况。将\(z_1=z_2\)稍作变换就可以得到： \[ {\langle k^2\rangle}-2{\langle k\rangle}=0 \leftrightarrow \sum_{k=0}^\infty k(k-2)p_k=0 \] 可以发现，在渗流阈值下度数为0和度数为2的顶点不会对这个式子产生任何影响，因此度数为0或2的顶点的数量既不会影响渗流转变，也不会影响巨型连通分量的存在与否。对上面这个式子的完整讨论如下：

• 度数为0的顶点未与任何其他节点相连，因此不会对网络拓扑产生影响。
• 度数为1的顶点是满足渗流条件的唯一负面因素。当到达度数为1的节点时，将无法继续寻找路径。
• 度数为2的顶点充当两个其他节点之间的中介。移除度数为2的顶点不会改变图的拓扑结构。

因此，移除（或添加）度数为2或0的顶点不会影响巨型连通分量的存在。

概率生成函数

为了进行后续推导，需要先引入概率生成函数（Probability Generating Function）。 定义， \[ G_0(x)=\sum_{k=0}^\infty p_kx^k \] 为\(p_k\)的概率生成函数，其中\(x\)只是一个形式变量。\(p_k\)的所有信息可以通过对\(G_0\)求导得到： \[ p_k=\frac{1}{k!}\frac{d^kG_0}{dx^k}|_{x=0} \] 那么对于一阶剩余度分布\(q_k=(k+1)p_{k+1}/z\)也同样可以如此定义，那么就可以得到： \[ G_1(x)=\sum_{k=0}^\infty q_kx^k=\frac{G'_0(x)}{z} \]

子图的大小

对于低于渗流阈值（Percolation Threshold）的情况，网络中不存在巨型连通分量（Giant Component），因此所有连通分量均为有限大小。此时我们关心的是随机图中有限连通分量的大小分布。 在低于渗流阈值时，定义：

\[ H_1(x)=\sum_m h^{(1)}_m x^m \]

表示沿一条指定边到达顶点 \(j\) 后，其所属有限连通分量大小的概率生成函数。其中 \(h^{(1)}_m\) 表示该有限连通分量恰好包含 \(m\) 个节点的概率。

从顶点 \(j\) 伸出的剩余边数 \(k\) 由剩余度分布 \(q_k\) 描述。由于配置模型在大规模极限下局部近似为树状结构（Locally Tree-like Approximation），有限连通分量中闭环出现的概率极低，因此从顶点 \(j\) 出发的不同剩余边通常通向彼此独立的分支。

若每个分支的大小分布均由 \(H_1(x)\) 描述，则根据概率生成函数的乘法性质，\(k\) 个独立分支大小之和的生成函数为

\[ [H_1(x)]^k \]

因此，局部树状结构是该推导成立的关键：正因为不存在闭环，不同分支不会重新汇合到同一节点，从而可以视为相互独立，并直接利用生成函数的乘法性质计算整个连通分量的大小分布。

我们实际上想要知道的是我们进入的这个结点\(j\)所属的连通分量的大小的分布情况，在这里我们做如下的推论：

• 从随机一个结点发出的边的数量服从度分布\(p_k\)
• 每个边最后都会连接到一个符合由\(H_1(x)\)生成的大小分布的连通分量

因此定义对于一个完整的连通分量，其大小分布的概率生成函数为：
\[ H_0(x)=x\sum_{k=0}^\infty p_k[H_1(x)]^k=xG_0(H_1(x)) \] 这个连通分量的平均大小可以通过这个函数导出： \[ \langle s\rangle = H_0'(1)=1+G'_0(1)H'_1(1) \] 其中\(G_0(1)=H_1(1)=H_0(1)=1\)，且\(H'_1(1)\)可以通过复合函数求导得到为\(H'_1(1)=\frac{1}{1-G'_1(1)}\)，那么上面的式子可以改写为： \[ \langle s\rangle=1+\frac{G'_0(1)}{1-G_1'(1)}=1+\frac{z_1^2}{z_1-z_2} \] 可以发现这个式子会在渗流条件\(z_1=z_2\)时，平均有限连通分量大小发散。这表明系统到达渗流临界点。

巨型连通分量的大小

那么相应地，在高于渗流阈值的情况下，我们对巨型连通分量占据整个网络结点数的比例\(S\)更感兴趣。在这种情况下我们可以把概率生成函数分成两部分，一部分描述巨型连通分量的生成，另一部分描述其他连通分量： \[ H_0(x)\rightarrow H^*_0(x)+H_0(x)， H_0^*(1)=S,H_0(1)=1-S=G_0(u) \] 描述其他连通分量的部分和之前的推导不变，有\(u=H_1(1)=G_1(u)\).

对于Erdös–Rényi而言，有\(G_1(x)=G_0(x)=exp(z(x-1))\), 那么： \[ 1-S=u=e^{z(u-1)}=e^{-zS},S=1-e^{-zS} \] 对上面的式子进行泰勒展开，有： \[ S\approx zS-\frac{(eS)^2}{2}, S(z)\approx \frac{2(z-1)}{z^2} \] 可以发现，在渗流区域内\(S(z)\)线性增长，当度数\(z\)很大时，巨型分量会以指数级的速度吞噬整个网络，有\(\lim_{z\rightarrow \infty}S\rightarrow 1\).

随机网络的鲁棒性

现实世界网络的度分布通常具有“厚尾”特征，这是一个定义较为模糊的概念，指当度值增大时，该分布的衰减速度很慢。一般而言，肥尾特性增强了网络的鲁棒性。也就是说，即使移除一定数量的顶点或边，网络仍能保持功能。例如，即使有相当数量的互联网路由器发生故障，互联网依然能够正常运行。

那么现在网络中的结点存在关闭或者开启状态，现在定义\(b=b_k\)表示度数为\(k\)的结点处于开启状态的概率，其概率生成函数会在原来的生成函数的基础上再考虑\(b_k\)： \[ F_0(x)=\sum_{k=0}^\infty p_kb_kx_k \] 但是这样的话\(F_0(1)=\sum_kp_kb_k\leq1\)不等于1,这个问题可以通过增加一项\(1-\sum_kp_kb_k\)来解决： \[ F_0(x)=\sum_{k=0}^\infty p_kb_kx_k+\left(1-\sum_kp_kb_k\right) \] 可以得到\(F_1(x)\)： \[ F_1(x)=\frac{\sum_kkp_kb_kx^{k-1}}{\sum_k kp_k}=\frac{F'_0(x)}{z} \] 同理根据上一小节的推论也可以得到： \[ H_0(x)=1-F_0(1)+xF_0(H_1(x)),H_0(1)=1\\ H_1(x)=1-F_1(1)+xF_1(H_1(x)),H_1(1)=1 \]

随机顶点失效

首先先考虑最一般的情况：如果一个顶点失效的概率\(1-b_k\)是一个常数，与度数等等没有任何关系，那么上面的式子可以改写为： \[ F_0=bG_0(x)\\ F_1(x)=bG_1(x)\\ H_0(x)=1-b+bxG_0(H_1(x))\\ H_1(x)=1-b+bxG_1(H_1(x)) \] 那么此时连通分量的大小期望为： \[ \langle s\rangle = H_0'(1)=b+bG_0'(1)H_0'(1)=b+\frac{b^2z_1^2}{z_1-bz_2} \] 可以发现当\(b=\frac{z_1}{z_2}\)的时候分母不存在，发生渗流相变，记此时的\(b\)为\(b_c\)，那么如果\(b<b_c\)则不存在巨型连通分量；此时连接路径进存在于小型的、孤立的顶点群内部而不存在长距离连接，这通常对网络而言是致命的。然而，对于具有厚尾分布的网络，我们预计次近邻的数量 \(z_2\) 远大于最近邻的数量 \(z_1\)，因此 \(b_c\) 相应地较小。该网络具有鲁棒性，因为必须移除相当一部分节点，网络才会失效。

偏置的顶点失效

那么如果有一些更重要的结点更容易受到攻击被下线呢？比如网络黑客只会攻击互联网中具有高度数的结点，现在来模拟这种情况，记： \[ b_k=\theta(k_c-k)\\ \theta(x)=\begin{cases}0,x>0\\ 1,x\geq0\\ \end{cases} \] 对\(H_1(x)\)求导可以发现： \[ H'(1)=\frac{F_1(1)}{1-F'_1(1)} \] 当\(F'_1(1)=1\)时上式发散，发生渗流相变。

小世界模型

在前面的小节中提到过，与现实中的网络不同的是，在达到热力学上限之后随机图不存在任何的连通分量。因此，我们有必要找到一种方法来生成具有有限聚类系数和具有小世界效应性质的图，即小世界模型。

晶格模型

晶格模型(Lattice Models)和随机图是两种网络模型的极端情况。下图展示了一维的两个晶格模型：

一维晶格模型的聚类系数为： \[ C=\frac{3(z-2)}{4(z-1)} \] 当\(z\)非常大时\(C\)趋近于0.75.

对于\(d\)维的晶格模型，其聚类系数为： \[ C=\frac{3(z-2d)}{4(z-d)} \] 对\(d\)维的晶格模型，如果其大小为\(L\),那么一共有\(N=L^d\)条连接，那么顶点到顶点的距离可以估算为 \[ \mathcal{l}\approx N^{1/d} \] 然而之前的章节中已经分析过小世界效应要求顶点到顶点的距离应当正比于\(logN\)，晶格模型并不具备小世界效应。

Watts and Strogatz 模型

接下来我们从晶格模型开始修改，让其成为具有小世界效应的随机图，具体方法如下：

对一个晶格模型：

• 以\(p_{new}\)概率选择晶格模型中的所有边
• 对于每一条被选中的边其需要重新连接到其他随机的顶点上，这个动作需要重复\(N\)次

如下图所示：

可以发现，在重新连接之后，整个图的平均度数\(z\)不会发生改变，但是对于模型中的某个结点来说其度数不再等于\(z\). 如下图所示，在逐条边重新连接的过程中，聚类系数变成了一个关于网络直径的函数。重新该几步就会大幅度缩短原来晶格模型中的平均距离，同时，聚类系数仍然维持在非常高的水平。

无标度图

前文中的小世界模型只考虑了固定数量的结点，然而大多数真实的网络结点数量在不断地增多。根据简单的推理不难得出结论，新加入网络的结点更容易连接到网络中已有的高度数结点上，如此会导致网络的平均度数在不断的升高，这种现象被称为优先连接（Preferential Connectivity/Preferential Attachment）：在新节点加入网络时，它会优先与那些已经拥有较多连接（即度数高）的现有节点建立链接。

Barabási–Albert 模型

Barabási–Albert模型是一种利用优先连接性来生成随机无标度图的方法。假设在\(t=0\)的时刻存在\(N(0)=N_0\)个未连接的结点，通过两步就可以生成一个无标度的随机图：

• 在每个时间节点上，加入一个新的顶点并且该顶点和\(m\leq N_0\)个现存结点连接。

• 将新的顶点上的\(m\)个半边以\(\Pi(k_i)\)的概率与度数为\(k_i\)的结点连接，其中： \[ \Pi(k_i)=\frac{k_i+\text{Offset}}{a(t)}, a(t)=2m(t-1)+\text{Offset}(N_0+t-1) \]

可以发现\(\Pi(k_i)\)基本上是随着已有的连接数线性增加的。在\(t\)时间后，这两个步骤会产生一个具有\(N(t)=t+N_0\)个顶点、\(mt\)条边的网络，这种连接方式会让\(p_k\)满足幂律条件： \[ p_k \propto k^{-\gamma},\gamma=3+\frac{\text{Offset}}{m} \]

时变的度数

可以通过平均场方法从解析上计算给定顶点的度随时间的变化情况。由于上述式子在 \(k → ∞\) 的极限下才成立，只有度数较大的节点才重要，因此，我们可以假设 \(k_i\) 是连续的，在这种假设下度数的增长律： \[ \Delta k_i(t) \approx\frac{\partial k_i}{\partial t}=A\Pi(k_i)=A\frac{k_i+\text{Offset}}{a(t)}\approx\frac{m}{2m+\text{Offset}}\frac{k_i+\text{Offset}}{t} \] 其中\(A\)是一个归一化常数。解这个微分方程，得到： \[ k_i(t)=(m+\text{Offset})\left(\frac{t}{t_i}\right)^{m/(2m+\text{Offset})}-\text{Offset} \] 其中\(t_i\)是顶点\(i\)加入到网络中的时间点，对\(t<t_i\)有\(k_i(t)=0\).

在\(\text{Offset}=0\)的情况下（其余情况可以同理推出），对结点\(i\)，在加入网络的时候其应当具有\(m=k_i(t_i)\)条连接，那么上述式子有： \[ k_i(t)=m\left(\frac{t}{t_i}\right)^{0.5}\rightarrow t_i=t\frac{m^2}{k_i^2} \] 也就是说，对于在\(t_i\)时刻前加入网络的结点他们的度数增长会快于\(t_i\)时刻后加入网络的结点，换言之，网络存在马太效应：结点加入网络的时刻越早，其度数的增长速度就越快。

现在回过头来再看度分布函数，其可以写作微分形式并且解出： \[ p_k=\frac{\partial P(k_i(t)<k)}{\partial k}=\frac{2m^2t}{N_0+t}\frac{1}{k^3} \] 这个式子中可以发现\(\gamma=3\)完全独立于表示优先连接性质的前项（正指数项），这表明优先连接性才是让整个网络的度分布服从幂律的关键因素。

非优先连接的增长

我们考察了仅靠采用随机连接而非优先连接是否能够产生无尺度度分布。在这种情况下我们假设在时间\(t\)上随机的会有\(m\)条边连接到已经有的\(N_0+t-1\)，那么在在这种情况下度数的增长函数为： \[ \frac{\partial k_i}{\partial t}=\frac{m}{N_0+t} \] 用初始状态\(k_i(t_i)=m\)反解上述微分方程，得到： \[ k_i=m\left[ln\left(\frac{N_0+t}{N_0+t_i}\right)+1\right] \] 然后建立概率密度函数，得到： \[ P(k_i(t)<k)=P(t_i>(N_0+t)e^{1-k/m}-N_0)=\frac{1}{N_0+t}\left[t-((N_0+t)e^{1-k/m}+N_0)\right] \] 假设加入顶点是时间均匀的，对于很大的时间，有： \[ p_k=\frac{\partial P(k_i(t)<k)}{\partial k}=\frac{e}{m}e^{-\frac{k}{m}} \] 可以发现这不符合幂律分布。

优先连接模型

我们来可以将优先连接模型进行泛化：

• 每个时间步骤都会添加一个新的顶点。
• 每个时间步骤都会添加新的\(m\)条边。
• 在概率\(r ∈[0, 1]\)下，以概率\(∝Π(k_i)\)选择现有顶点\(i\)，与新顶点建立连接，这个连接属于添加的\(m\)条新边中的任意一条。
• 以概率\(1 − r\)，以概率\(∝ Π(k_i )Π(k_j )\)选择两个现有顶点\(i\)和\(j\)，并在它们之间添加一条连接，这个连接属于添加的\(m\)条新边中的任意一条。

如此方法建立的网络模型服从幂律分布： \[ p_k\propto\frac{1}{k^\gamma}, \gamma=1+\frac{1}{1-r/2} \] 当\(r=1\)时上述式子退化为最开始分析的优先连接模型。对许多真实世界的网络，\(r\)非常的小，这意味着许多连接的建立是在内部结点中。