随机图与复杂网络：从 Erdős–Rényi 到无标度网络

2026/05/28 14:09:29

Part 0 · 引言

随机图与复杂网络的背景

在数学与物理学的交汇处，有一个问题长期吸引着研究者：真实世界中的网络——互联网的路由器层、人脑的神经元连接、蛋白质的交互网络、社交关系——其拓扑结构从何而来？确定性图论给出了完美的理想图，却无法解释为何现实网络展现出如此丰富的涌现现象。随机图理论则提供了一种全新的视角：用概率语言描述网络的生成与演化，从简单的局部规则中涌现出全局结构。

本篇文章系统梳理随机图与复杂网络的核心模型与度量方法，从经典的 Erdős–Rényi 模型出发，依次考察配置模型、小世界网络、无标度网络三大范式，并介绍主要的网络度量工具，最后讨论这些模型在真实系统中的应用与前沿研究方向。

Part 1 · 动机

为什么研究随机图

确定性图论的局限

传统的图论以完全确定的方式定义图：给定顶点集合与边集合，图的所有拓扑性质都是固定的。例如，完全图 $$K_n$$ 的度分布、平均路径长度、聚类系数都可以用精确公式表达。这种视角的优点是数学上的干净与可证明性，但缺点是无法捕捉真实网络的复杂性。

真实网络并非事先设计，而是从局部交互中涌现。一个社交网络不是按照固定蓝图构建的，而是由无数个体之间的连接行为自然形成的。确定性图论无法解释：为什么互联网呈现出高度异质的度分布？为什么蛋白质网络同时具有高聚类和短路径？为什么某些网络在遭受攻击时异常脆弱？

随机图作为 Null Model

随机图的核心思想是：定义一个在所有可能的图上均匀分布（或按某种概率权重分布）的随机过程，然后考察在这个随机过程中，哪些性质几乎总是出现，哪些性质几乎从不出现。

Erdős 和 Rényi 在 1959 年的开创性工作中，用严格的概率方法证明了：当顶点数 $$n$$ 趋于无穷时，随机图的连通性、相变直径等性质呈现尖锐的阈值行为。这种"几乎所有图都满足某性质"的表述，被称为 almost surely（几乎必然）。

一句话理解：随机图不是对真实网络的直接模拟，而是一类重要的 null model——即用来对照真实网络的基准。如果某个真实网络的性质与相应的随机图模型差异显著，则说明该性质需要额外的机制来解释，而非简单地从随机交互中涌现。

Part 2 · 经典模型

Erdős–Rényi 模型

$G(n,p)$

模型定义

Erdős–Rényi 模型存在两个等价变体：

$$G(n,M)$$ 模型：从 $$n$$ 个标注顶点、恰好 $$M$$ 条边的所有图中均匀抽样
$$G(n,p)$$ 模型：独立地以概率 $$p$$ 包含每一条可能的边

当 $$n$$ 足够大时，两种模型的性质趋于一致。学术研究中更常用 $$G(n,p)$$ ，因为边独立性允许使用浓度不等式与生成函数方法。

设 $N = \binom{n}{2}$ 为可能的边数。在 $$G(n,p)$$ 中，实际边数 $$M$$ 服从参数为 $$(N, p)$$ 的二项分布 $\text{Bin}(N,p)$ ，期望值为 $$Np$$ 。每个顶点 $$v$$ 的度 $\deg(v)$ 服从 $\text{Bin}(n-1,p)$ ，因为该顶点与其他 $$n-1$$ 个顶点之间存在 $$n-1$$ 条可能的边，每条边以概率 $$p$$ 独立存在。

度分布的 Poisson 近似

当 $n \to \infty$ 且 $np = \lambda$ 为常数时，二项分布 $\text{Bin}(n-1,p)$ 收敛到 Poisson 分布 $\text{Pois}(\lambda)$ ：

\Pr(\deg(v) = k) = \binom{n-1}{k} p^k (1-p)^{n-1-k} \to \frac{\lambda^k e^{-\lambda}}{k!}

其中 $\lambda = np$ 是平均度。这个结果非常重要：ER 模型的度分布是单峰的、集中于均值附近的 Poisson 分布，不存在显著的异质性。许多真实网络（如互联网、社交网络）的度分布却是长尾的，偏离 Poisson 分布，这恰恰说明这些网络具有超出随机性的结构机制。

相变与巨连通分量

Erdős 和 Rényi 在 1960 年的著名论文中揭示了随机图最深刻的性质：相变（phase transition）。考虑边概率 $$p = c/n$$ ，其中 $$c$$ 为常数。平均度为 $$c$$ ，与顶点数无关。

条件	平均度	连通分量性质
$$c < 1$$	$$np < 1$$	几乎所有连通分量的规模为 $O(\log n)$ ，不存在规模与 $$n$$ 同阶的连通分量
$$c = 1$$	$$np = 1$$	临界阈值，最大连通分量的规模在 $\Theta(n^{2/3})$ 量级，相变窗口宽度为 $\Theta(n^{-2/3})$
$$c > 1$$	$$np > 1$$	一个唯一的"巨分量"（giant component）涌现，其规模与 $$n$$ 成正比

相变的数学证明依赖于局部树状结构的展开：对于 $$p = c/n$$ ，从任意顶点出发的 BFS（广度优先搜索）树近似于一棵分支过程（branching process），有效分支因子为 $$c$$ 。当 $$c > 1$$ 时，分支过程超临界，以正概率无限延伸，从而产生巨连通分量。

连通性阈值

除了巨分量涌现阈值 $$p = 1/n$$ ，还有一个更尖锐的连通性阈值： $p = \frac{\ln n + \omega(n)}{n}$ 。具体来说，如果 $p = (\ln n + f(n))/n$ ：

当 $f(n) \to -\infty$ 时，图大概率不连通
当 $f(n) \to +\infty$ 时，图大概率连通

阈值函数为 $(\ln n)/n$ ，与巨分量阈值 $$1/n$$ 只差一个对数因子。这说明从"存在一个大分量"到"整个图连通"，中间隔了一个对数尺度。

配图说明：ER 模型相变图

下图展示了不同平均度 $$c$$ 下，巨连通分量规模的理论曲线。当 $$c < 1$ 时，巨分量不存在；当 $c > 1$$ 时，巨分量规模迅速增长。

ER 模型相变：巨连通分量规模 vs 平均度JSXGraph

ER 模型相变：巨连通分量规模 vs 平均度

Part 3 · 灵活扩展

配置模型（Configuration Model）

动机与定义

ER 模型产生的度分布必然趋近 Poisson，无法生成异质度序列。但在许多应用中，我们需要生成具有任意给定度分布的随机图。例如，如果经验数据显示某个蛋白质网络的度分布近似幂律 $P(k) \sim k^{-2.5}$ ，我们需要一个模型来对照该度分布下的随机基准行为。

配置模型（Configuration Model）的思想是：预先指定每个顶点的度（通过度序列 $k_1, k_2, \ldots, k_n$ ，满足 $\sum_i k_i$ 为偶数以保证可行性），然后将这些度"切分为 stubs"（半边），再随机配对所有 stub 以形成完整的边。

设度序列的总度数为 $\sum_i k_i = 2m$ 。stub 配对过程在所有 $\frac{(2m)!}{2^m m!}$ 种等可能配对方式上均匀分布。在大 $$n$$ 极限下，度分布收敛到指定的分布，度-度相关性（degree-degree correlation）趋于零（除非度序列中存在结构相关性）。

与 ER 模型的对比

特性	ER 模型 $$G(n,p)$$	配置模型
度分布	固定为 Poisson	可指定任意分布
度异质性	方差等于均值	可构造高度异质度分布
度-度相关性	趋于零	趋于零（除非度序列有结构）
聚类系数	通常很小 $\approx 1/n$	通常较小

配置模型在社会网络分析中常作为零模型使用：如果真实网络的某些统计量显著偏离配置模型预测的值，则说明该统计量反映了真实网络的特定组织原则。

Part 4 · 小世界现象

小世界网络（Small-World Networks）

现实矛盾

1998 年，Duncan Watts 和 Steven Strogatz 在《Nature》上发表论文，指出了一个悖论：许多真实网络同时表现出两种似乎矛盾的性质——

高聚类系数（High Clustering Coefficient）：如果顶点 $$v$$ 与 $$u$$ 和 $$w$$ 均相连，则 $$u$$ 与 $$w$$ 之间也往往存在连接，即"朋友的朋友也是朋友"。在规则环图（regular ring lattice）中，这一系数非常高，因为每个顶点的邻居之间互为邻居。
短平均路径长度（Short Average Path Length）：任意两个顶点之间存在相对较短的路径，即"六度分隔"。完全随机图 $$G(n,p)$$ 虽然路径短，但聚类系数极低。规则网格虽然聚类系数高，但路径长度随 $$n$$ 线性增长。

核心矛盾：ER 模型只能满足短路径，无法满足高聚类；规则格只能满足高聚类，无法满足短路径。真实网络同时具备两者，这是一个需要解释的现象。

Watts-Strogatz 模型

Watts 和 Strogatz 提出的模型从一条规则环图出发： $$n$$ 个顶点排列成环，每个顶点与左右各 $$K/2$$ 个最近邻相连（ $$K$$ 为偶数，称为"coordination number"）。规则环图的平均路径长度为 $L_{\text{ring}} \approx n/(2K)$ ，聚类系数为 $C_{\text{ring}} = 3(K-2)/(4K-2)$ ，均较高。

模型的关键步骤是随机重连（random rewiring）：对于每条边，以概率 $$p$$ 将其一个端点随机重连到另一个顶点（避免自环与重边）。参数 $$p$$ 控制从规则（ $$p=0$$ ）到随机（ $$p=1$$ ）的连续过渡。

当 $$p$$ 较小（ $p \lesssim 0.01$ ）时，大部分边保持规则，局部聚类得以保留；但少量"捷径"（shortcuts）的引入使得路径长度急剧下降。这是因为全局路径长度的瓶颈在于拓扑距离的量级——一条捷径可以跨越整个环图，将路径长度从 $$O(n)$$ 降至 $O(\log n)$ 。

聚类系数与路径长度的标度

Barthélémy 和 Amaral（1999）精确刻画了相变行为：当 $pc \approx \frac{1}{K}$ 时，Watts-Strogatz 图从"大世界"（large world）转变为"小世界"（small world）。在此阈值以上，平均路径长度迅速下降，但聚类系数仍维持在较高水平，直至 $$p$$ 接近 1。

小世界网络的量化指标由 Telesford 等人（2011）提出：

\sigma = \frac{C/C_r}{L/L_r}

其中 $$C_r$$ 和 $$L_r$$ 为同平均度的 ER 随机图对应的聚类系数与路径长度。 $\sigma > 1$ 即表明网络具有小世界性质。另一种更鲁棒的指标 $\omega$ 分别为：

\omega = \frac{L_r}{L} - \frac{C}{C_\ell}

其中 $C_\ell$ 为规则格的聚类系数， $$L_r$$ 为随机图的路径长度， $\omega \approx 0$ 时网络达到最优小世界状态。

六度分隔的数学解释：在小世界网络中，

L \propto \log N

，其中

$N$

为顶点数。这意味着从

$10^3$

到

$10^9$

的网络，路径长度仅从 3 跳增长到 9 跳，与经验观测吻合。

配图说明：小世界网络演化示意

下图展示了小世界网络从规则环图到随机图的演化过程：当随机重连概率 $$p$$ 增加时，路径长度急剧下降，而聚类系数在较宽范围内保持较高值。

graph LR
    A["规则环图
p = 0"] --> B["少量重连
p ≈ 0.001"]
    B --> C["小世界网络
p ≈ 0.01"]
    C --> D["接近随机
p ≈ 1"]

    style A fill:#e0f2fe,stroke:#0ea5e9,stroke-width:2px
    style B fill:#fef9c3,stroke:#ca8a04,stroke-width:2px
    style C fill:#dcfce7,stroke:#16a34a,stroke-width:3px
    style D fill:#fce7f3,stroke:#db2777,stroke-width:2px

重连概率 $$p$$	路径长度 $$L$$	聚类系数 $$C$$	网络类型
$$p = 0$$	$$O(n)$$	$C_{\text{ring}} \approx 3/4$	规则格
$p \approx 0.001$	急剧下降	接近 $C_{\text{ring}}$	小世界形成
$p \approx 0.01$	$O(\log n)$	仍较高	小世界网络
$p \approx 1$	$O(\log n)$	$$O(1/n)$$	随机图

Part 5 · 无标度特性

无标度网络（Scale-Free Networks）

动机：为什么需要新的模型

ER 模型和 Watts-Strogatz 模型产生的度分布都是集中于均值附近的窄分布。1999 年，Barabási 和 Albert 在分析万维网（World Wide Web）拓扑时发现：入度分布显著偏离 Poisson，而是遵循幂律 $P(k) \sim k^{-\gamma}$ ，其中 $\gamma \approx 2.1$ 。类似的现象在互联网自治系统层、引用网络、电话通话网络等多种系统中广泛存在。这些观察促使 Barabási 和 Albert 提出了无标度网络（Scale-Free Networks）的概念。

Barabási-Albert 模型

BA 模型的核心假设只有两个：

增长（Growth）：网络从 $$m_0$$ 个初始顶点开始，每个时间步添加一个新顶点，该顶点与 $$m$$ 个已有顶点建立连接（ $m \leq m_0$ ，通常 $m \geq 1$ ）。
优先连接（Preferential Attachment）：新顶点连接到已有顶点 $$i$$ 的概率，与 $$i$$ 的当前度 $$k_i$$ 成正比： $\Pi_i = \frac{k_i}{\sum_{j=1}^{N(t)} k_j}$

这正是 Price 早在 1965 年研究引文网络时提出的"富者愈富"（rich-get-richer）机制，在社会学中称为 Matthew 效应。

幂律度分布的推导

Barabási 和 Albert 通过连续介质理论（continuum theory）推导出度分布。考虑时间 $$t$$ 时添加的节点，其度 $$k(t)$$ 随时间演化的微分方程为：

\frac{\partial k}{\partial t} = m \frac{k}{\int_0^t k(t') dt'} = \frac{1}{2mt}

其中分母为 $$2mt$$ （因为总度数为 $$2mt$$ ）。求解得：

k(t) = m \sqrt{\frac{t}{t_i}}

其中 $$t_i$$ 为节点 $$i$$ 的加入时间。节点 $$i$$ 的度与 $t_i^{-1/2}$ 成正比，这意味着先加入的节点更可能积累高连接度。

度 $$k$$ 的累积分布为 $P(k) \sim k^{-3}$ ，指数 $\gamma = 3$ 。这一结果与具体选择的 $$m$$ 无关（只要 $m \geq 1$ ）。实证中许多真实网络的指数在 2 到 3 之间，说明 BA 模型给出了幂律产生的定性机制，但具体指数取决于更多细节（如初始吸引度、非线性优先连接、退化/老化效应等）。

鲁棒性与脆弱性的双重性

无标度网络面临两种不同性质的失效：

鲁棒性 vs 脆弱性

鲁棒性（Robustness to random failures）：随机移除顶点时，高度节点被选中的概率与 $k^{-\gamma}$ 成正比，因此高度 hub 被选中的概率极低。网络在大部分顶点被随机移除后仍能保持连通性——这解释了互联网在路由器随机故障下的强韧性。
脆弱性（Vulnerability to targeted attacks）：如果攻击者按度从高到低依次移除顶点（即"精确打击" hub），则网络会迅速分解为孤立分量，因为高度节点在介数中心性和信息流中扮演不可替代的角色。去除前 5% 的高度节点可能使网络碎片化。

这种"鲁棒又脆弱"（robust yet fragile）的双重性质在基础设施设计、流行病防控策略上有重要启示：对无标度网络的免疫策略需要优先保护 hub 而非随机接种。

配图说明：无标度网络度分布

下图展示了幂律度分布在双对数坐标下的直线特征，与 Poisson 分布的钟形曲线形成鲜明对比。幂律分布的重尾特性意味着少数 hub 节点连接了大量节点。

幂律分布 vs Poisson 分布（双对数坐标）JSXGraph

幂律分布 vs Poisson 分布（双对数坐标）

Part 6 · 度量工具

网络度量

度分布（Degree Distribution）

度 $$k_i$$ 是顶点 $$i$$ 的邻居数目。度分布 $$P(k)$$ 描述了随机选取一个顶点恰好有 $$k$$ 个邻居的概率。ER 模型的 $$P(k)$$ 服从 Poisson 分布，均值与方差相等。无标度网络的 $$P(k)$$ 服从幂律，在双对数坐标下呈直线，尾部缓慢衰减（重尾分布）。

聚类系数（Clustering Coefficient）

局部聚类系数 $$C_i$$ 衡量顶点 $$i$$ 的邻居之间的互联程度：

C_i = \frac{2e_i}{k_i(k_i - 1)}

其中 $$e_i$$ 为顶点 $$i$$ 的 $$k_i$$ 个邻居之间的实际边数。全局聚类系数为各局部系数的平均值：

C = \frac{1}{n} \sum_{i=1}^n C_i = \frac{1}{n} \sum_{i=1}^n \frac{2e_i}{k_i(k_i - 1)}

在规则环图中 $C \approx 3/4$ （当 $K \to \infty$ 时），在 ER 随机图中 $C \approx 1/n$ ，量级极小。

介数中心性（Betweenness Centrality）

顶点 $$v$$ 的介数中心性定义为：

BC(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}

其中 $\sigma_{st}$ 为从 $$s$$ 到 $$t$$ 的最短路径总数， $\sigma_{st}(v)$ 为经过 $$v$$ 的最短路径数。介数中心性衡量顶点在信息流、物质流中的"中介"地位。在社交网络中，高介数中心性的节点是连接不同社群的桥梁。在互联网中，高介数中心性的路由器是关键的中转节点。

PageRank

PageRank 由 Page 和 Brin（1998）提出，原本用于网页排名，后被广泛应用于任意网络。PageRank 值 $$PR(i)$$ 通过迭代定义：

PR(i) = \frac{1-d}{N} + d \sum_{j \in M_i} \frac{PR(j)}{k_j^{\text{out}}}

其中 $d \in (0,1)$ 为阻尼系数（通常取 $$d = 0.85$$ ）， $$M_i$$ 为指向 $$i$$ 的页面集合， $k_j^{\text{out}}$ 为页面 $$j$$ 的出度。PageRank 可理解为随机游走者在平稳状态下停留在各顶点的概率，高 PageRank 值意味着该顶点是随机游走的"陷阱"——通常是高连接度的 hub 或连接不同区域的桥梁节点。

社区结构（Community Structure）

社区结构指网络内部顶点形成稠密内部连接、稀疏跨社区连接的分组模式。社区检测的经典算法包括 Louvain 方法（基于模块度优化）、谱聚类、标签传播等。模块度（Modularity）定义为：

Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)

其中 $A_{ij}$ 为邻接矩阵元素， $$k_i, k_j$$ 为度， $$m$$ 为总边数， $\delta(c_i, c_j)$ 在顶点 $$i,j$$ 同社区时为 1 否则为 0。模块度衡量社区内部实际边数相对于零模型（配置模型）的超出程度。

Part 7 · 例题

例题与计算

例题 1：判断随机图的连通性

题目：设 $$n = 1000$$ ，考虑 $$G(n,p)$$ 模型，其中 $$p = 0.003$$ 。判断该图是否几乎必然连通，并说明理由。

计算平均度：平均度 $c = (n-1)p \approx 1000 \times 0.003 = 3$ ， $$c > 1$$ ，满足巨分量存在的条件。
连通性阈值判断：连通性阈值约为 $(\ln n + \omega(n))/n = (\ln 1000 + 1)/1000 \approx (6.91 + 1)/1000 \approx 0.00791$ 。实际 $$p = 0.003 < 0.00791$$ ，因此图大概率不连通。
结论：尽管巨分量存在（ $$c > 1$$ ），但图几乎必然不连通。这是因为连通要求所有顶点都与巨分量相连，需要更高的边概率。

答案：该图几乎必然不连通。虽然平均度 $$c = 3 > 1$$ 满足巨分量涌现条件，但连通性阈值 $(\ln n)/n \approx 0.0069$ 高于实际边概率 $$0.003$$ ，因此图大概率由大量不相连的连通分量组成。

易错点：混淆巨分量阈值

$1/n$

与连通性阈值

(\ln n)/n

。巨分量存在不等于图连通——连通需要所有顶点都通过路径与主分量相连。

例题 2：计算网络的聚类系数

题目：考虑一个包含 5 个顶点的简单图，顶点度序列为 $$(4, 3, 2, 2, 1)$$ 。计算该图的平均聚类系数。

计算每个顶点的局部聚类系数：
- 度为 4 的顶点： $$e_i = 6$$ （其 4 个邻居形成完全图）， $C_1 = \frac{2 \times 6}{4 \times 3} = 1$
- 度为 3 的顶点：假设其 3 个邻居之间有 3 条边， $C_2 = \frac{2 \times 3}{3 \times 2} = 1$
- 两个度为 2 的顶点：各 $$e_i = 1$$ ， $C_3 = C_4 = \frac{2 \times 1}{2 \times 1} = 1$
- 度为 1 的顶点： $$e_i = 0$$ ， $C_5 = \frac{0}{0}$ （定义不存在，或设为 0）
计算平均值： $C = \frac{1+1+1+1+0}{5} = 0.8$

答案：该图的平均聚类系数为 $$0.8$$ 。这表明该网络具有较高的局部聚类特性。

易错点：度为 1 的顶点的聚类系数按定义不存在（或为 0），因为分母

$k_i(k_i-1) = 0$

。计算全局聚类系数时需要正确处理这种情况。

Part 8 · 应用

应用与前沿

社交网络分析

社交网络的拓扑特征（高聚类、小世界、异质度分布）深刻影响信息传播、观点形成与行为扩散。级联效应（cascading behavior）——一条信息如何通过社交网络迅速扩散——与网络的度分布和社区结构密切相关。在均匀网络中，传播阈值由平均度决定；在异质网络中，传播阈值由最高度顶点主导，使得疾病或信息在存在超级传播者（super-spreaders）时更易爆发。

互联网拓扑

互联网的自治系统（AS）层拓扑被广泛研究为无标度网络的实例。Floyd 等人（2002）的测量结果表明，互联网的度分布近似幂律 $P(k) \sim k^{2.2}$ ，hub 路由器连接了大量边缘设备。这一拓扑特征对互联网鲁棒性设计有直接影响：路由协议需要处理大规模汇聚流量，同时避免单点故障。

生物网络

蛋白质交互网络（Protein-Protein Interaction，PPI）：酵母的 PPI 网络展示出小世界性质与社区结构，同一生物通路的蛋白质在网络中形成局部聚类。PPI 网络的度分布近似幂律，意味着少数 hub 蛋白质调控大量生物功能——这些 hub 蛋白质往往是疾病基因的关键靶点。
脑网络（Brain Connectome）：利用扩散张量成像（dMRI）构建的脑结构网络表现出小世界拓扑，与信息的高效整合和分离密切相关。功能磁共振（fMRI）数据的时序分析揭示了功能连接网络的动态重配置，其拓扑变化与认知任务和神经疾病状态相关。

流行病传播模型

经典的 SIR（易感-感染-康复）和 SIS（易感-感染-易感）模型被推广到任意网络上。网络的拓扑结构直接影响传播阈值——在度异质的网络上，SIS 的临界点被显著降低，意味着即使是低传播率的疾病也能维持持续感染。接触网络（contact network）上的免疫策略需要结合度分布与社区结构来设计：针对高介数中心性节点的有目标免疫比随机免疫更有效。

当前的前沿方向包括多层网络（multiplex networks）上的传播动力学、网络重构（network inference）——从有限的观测数据推断网络的生成机制，以及利用图神经网络（GNN）对大规模网络进行表示学习与预测。

Part 9 · 总结

总结与展望

从 Erdős–Rényi 的相变理论，到 Watts-Strogatz 对局部聚类与全局连通性的统一解释，再到 Barabási-Albert 的增长与优先连接机制，网络科学在过去六十年间经历了从数学游戏到跨学科工具的深刻转变。这些模型构成了理解真实复杂系统的基础语言，其影响力已扩展至生物学、社会学、物理学与计算机科学的各个角落。

当前的研究前沿包括：时变网络（temporal networks）与多层网络的建模；网络的因果推断与可控制性；结合深度学习的网络嵌入与预测；以及网络科学与其他交叉学科（如计算社会科学、计算生物学）的深度融合。图论基础的坚实基础将继续支撑这一领域的进一步发展，而图神经网络则代表了将网络结构知识转化为可计算工具的重要技术路径。

理解随机图的数学本质，是把握复杂网络真面目的前提。概率与结构的对话、网络拓扑与动力学行为的耦合，构成了这一领域最富生命力的研究方向。

复习速查

ER 模型： $$G(n,p)$$ ，度分布趋于 Poisson，相变阈值 $$c=1$$ ，连通阈值 $(\ln n)/n$
配置模型：指定度序列，随机 stub 配对，可生成任意度分布
小世界网络：高聚类 + 短路径，WS 模型通过随机重连实现， $\sigma > 1$ 为小世界特征
无标度网络：BA 模型（增长 + 优先连接），度分布 $P(k) \sim k^{-\gamma}$ ，幂律指数通常 2~3
核心度量：度分布、聚类系数、介数中心性、PageRank、模块度

参考来源

Erdős, P., & Rényi, A. (1959). On Random Graphs. Publicationes Mathematicae, 6, 290–297. PDF
Watts, D. J., & Strogatz, S. H. (1998). Collective Dynamics of 'Small-World' Networks. Nature, 393(6684), 440–442. Link
Barabási, A. L., & Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509–512. arXiv
Newman, M. E. J. (2003). The Structure and Function of Complex Networks. SIAM Review, 45(2), 167–256. arXiv
Albert, R., & Barabási, A. L. (2002). Statistical Mechanics of Complex Networks. Reviews of Modern Physics, 74(1), 47–97. arXiv
Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
Boccaletti, S., et al. (2006). Complex Networks: Structure and Dynamics. Physics Reports, 424(4–5), 175–308. arXiv