随机图与网络模型：真实网络长什么样？

Part 3”优”结束了。从最小生成树到网络流，从匹配到着色，再到NP-hard 与近似算法——我们建立了完整的组合优化工具箱。但这些算法都有一个隐含假设：你已经有了一张图。

现在进入 Part 4”建模”的第一站。我们要面对一个更根本的问题：

真实世界的网络——社交网络、互联网、蛋白质交互网络、论文引用网络——到底长什么样？它们和你在算法课上分析的”随机图”一样吗？

答案是：完全不一样。 真实网络有一系列令人惊讶的共同统计特征——高聚类系数、短平均路径、幂律度分布——而经典的纯随机图模型无法复现这些特征。如果你的算法在均匀随机图上跑得很好，放到真实网络上可能完全不是那回事。

没有网络模型，你就：

• 无法理解为什么 BFS 在社交网络上”几步就到”但在格子图上要走很远
• 无法解释为什么社区发现在某些网络上效果好、在另一些上效果差
• 无法评估关键基础设施（电网、互联网）面对攻击的脆弱性
• 无法为算法生成合理的合成测试数据

本文沿着历史脉络介绍三个里程碑模型：Erdos-Renyi 纯随机图 (1959) → Watts-Strogatz 小世界模型 (1998) → Barabasi-Albert 无标度网络 (1999)。每个模型解决了前一个的缺陷，但也引入了新的不足。三者共同构成了理解真实网络的理论框架。

算法范式：本文偏模型/理论，不涉及具体算法范式——但三个模型的生成过程本身都是概率算法（随机采样 + 增长规则）。

真实网络的统计特征：三个”异常”

在介绍模型之前，先看真实网络的共同规律。20 世纪末，多个领域的研究者几乎同时发现：不同领域的网络竟然有惊人相似的统计特征。

三个核心发现：

1. 小世界效应（Small-world effect）：平均路径长度 $L$ 远小于节点数 $n$。社交网络的”六度分隔”（Milgram 1967）——地球上任意两人平均只需 6 步就能通过朋友关系连接——是最著名的例子。数学上，$L \sim \ln n$，甚至更短。

2. 高聚类系数（High clustering）：如果 A 认识 B，B 认识 C，那么 A 认识 C 的概率远高于随机期望。聚类系数 $C$ 的定义是：

$C(v) = \frac{\text{$v$ 的邻居之间实际边数}}{\binom{\deg(v)}{2}}$

全图的聚类系数 $C = \frac{1}{n}\sum_v C(v)$。真实网络中 $C$ 通常是 $0.1$-$0.7$，而同等密度的纯随机图中 $C \approx p$（通常 $\ll 0.01$）。

3. 幂律度分布（Power-law degree distribution）：大多数节点度数很低，但极少数”hub”节点度数极高。度分布呈：

$P(k) \sim k^{-\gamma}, \quad \gamma \in [2, 3]$

这与纯随机图的 Poisson 分布截然不同。Poisson 分布集中在均值附近，几乎不允许超高度节点存在。

这三个”异常”驱动了网络科学的诞生。 接下来我们看三个模型如何一步步逼近真实网络。

Erdos-Renyi 模型 $G(n,p)$

模型定义

1959 年，Erdos 和 Renyi 提出了最简单的随机图模型 $G(n,p)$：

• 输入：$n$ 个节点，连边概率 $p \in [0, 1]$
• 规则：对每一对节点 $(i, j)$（共 $\binom{n}{2}$ 对），独立以概率 $p$ 放一条边

就这么简单——完全由一个参数 $p$ 控制。期望边数 $\mathbb{E}[m] = p \cdot \binom{n}{2}$，期望平均度 $c = p(n-1) \approx pn$。

度分布：Poisson

在 $G(n,p)$ 中，每个节点的度 $\deg(v)$ 是 $n-1$ 个独立 Bernoulli 试验的和（每个邻居以概率 $p$ 连接），因此：

$\deg(v) \sim \text{Binomial}(n-1, p)$

当 $n$ 很大、$p$ 适中时，近似为 Poisson 分布：

$P(k) \approx \frac{e^{-c} c^k}{k!}$

其中 $c = p(n-1)$ 是平均度。

逐项拆解：

• $e^{-c}$：归一化因子，确保所有概率之和为 1
• $c^k$：度数恰好为 $k$ 的”有利情形”计数（取对数后是线性的）
• $k!$：排列去重（选哪 $k$ 个邻居的顺序不重要）

关键特征：Poisson 分布在均值 $c$ 附近呈钟形，尾巴以指数速度衰减。这意味着不可能出现度数远超均值的 Hub 节点。

数值例子：$n = 1000$, $p = 0.004$, $c = 4$。度为 4 的概率 $P(4) = e^{-4} \cdot 4^4 / 24 \approx 0.195$。度为 20 的概率 $P(20) = e^{-4} \cdot 4^{20} / 20! \approx 8.4 \times 10^{-9}$——几乎为零。但在真实社交网络中，拥有几千个”好友”的用户比比皆是。

相变现象（Phase Transition）

ER 模型最深刻的数学结果是相变——图的宏观结构在特定阈值附近发生突变。

两个关键阈值：

阈值 1：巨组件出现 ($p = 1/n$，即 $c = 1$)

当 $c < 1$ 时（亚临界），所有连通分量都很小，最大分量大小 $O(\ln n)$。当 $c > 1$ 时（超临界），突然出现一个巨组件（giant component），包含 $\Theta(n)$ 个节点——即图中节点的固定比例。

这是一个锐利相变：$c$ 从 $0.99$ 变到 $1.01$，图的结构发生了质的飞跃。

阈值 2：连通性 ($p = \ln n / n$，即 $c = \ln n$)

当 $p = \frac{\ln n + \omega(n)}{n}$ 且 $\omega(n) \to +\infty$ 时，$G(n,p)$ 几乎确定连通（即连通概率趋于 1）。

精确结果（Erdos-Renyi 1960）：设 $p = \frac{\ln n + c_0}{n}$，则：

$\Pr[G(n,p) \text{ 连通}] \to e^{-e^{-c_0}}$

当 $c_0 \to +\infty$ 时，连通概率 $\to 1$；当 $c_0 \to -\infty$ 时，$\to 0$。

数值例子：$n = 1000$，连通阈值 $p^* = \ln(1000)/1000 \approx 0.0069$。如果 $p = 0.01 > p^*$，图几乎一定连通；如果 $p = 0.003 < p^*$，图几乎一定不连通。

ER 模型的聚类系数

$G(n,p)$ 的聚类系数：

$C_{\text{ER}} = p$

因为：$v$ 的任意两个邻居 $u, w$ 之间有边的概率就是 $p$（独立性！），与 $v$ 无关。

在稀疏图中 $p \ll 1$，所以 $C_{\text{ER}} \approx 0$。这与真实网络的高聚类系数（$C > 0.1$）完全不符。

ER 模型小结

特征	ER 模型	真实网络	匹配？
度分布	Poisson（钟形）	幂律（重尾）	不匹配
聚类系数	$\approx p$（很低）	高（$0.1$-$0.7$）	不匹配
平均路径	$\sim \ln n$（短）	短	匹配
Hub	不存在	存在	不匹配

ER 模型的价值在于：(1) 数学上高度可分析（相变理论）；(2) 提供了”随机基线”——真实网络偏离 ER 预测的地方，正是需要解释的结构。

但它三项不匹配，说明真实网络不是”每条边独立随机”那么简单。

Watts-Strogatz 小世界模型 (1998)

问题与动机

1998 年，Duncan Watts 和 Steven Strogatz 在 Nature 发表了一篇开创性论文，提出一个关键问题：为什么真实网络同时具有高聚类和短路径？

• 规则格子（如环上每个节点连 $K$ 个最近邻）：聚类系数高（邻居的邻居很可能也是邻居），但平均路径很长（$L \sim n/K$）。
• ER 随机图：平均路径短（$L \sim \ln n$），但聚类系数低（$C = p$）。

能不能两者兼得？ 答案是：只需在规则格子上做很少量的随机重连。

模型定义

WS 模型 $\text{WS}(n, K, p)$ 的生成过程：

1. 起点：$n$ 个节点排成环，每个节点连接左右各 $K$ 个最近邻（每个节点度数 $= 2K$）。总边数 $nK$。注意 NetworkX 的 watts_strogatz_graph(n, k, p) 中 k 表示总度数 $2K$。
2. 重连：对每条边，以概率 $p$ 将一个端点重连到一个随机选择的节点（避免自环和重边）。
3. $p = 0$：纯规则格子。$p = 1$：完全随机。$p \in (0,1)$：介于两者之间。

关键发现：当 $p$ 从 $0$ 增大时：

• 平均路径 $L$ 在 $p \approx 0.01$ 时就急剧下降（几条”捷径”就够了）
• 聚类系数 $C$ 在 $p \approx 0.1$ 时才开始明显下降

存在一个宽广的 $p$ 区间（大约 $0.01$-$0.1$），在这个区间内 $L$ 已经很短而 $C$ 仍然很高——这就是小世界区域。

数学分析

聚类系数：在规则格子上（$p = 0$），$C(0) = \frac{3(K-1)}{2(2K-1)}$。当 $K = 2$ 时 $C(0) = 1/2$。重连概率 $p$ 小时：

$C(p) \approx C(0)(1 - p)^3$

所以少量重连几乎不影响聚类。

平均路径：在规则格子上 $L(0) \sim \frac{n}{4K}$，与 $n$ 线性增长。重连后的路径下降非常快——只需 $O(\ln n)$ 条”捷径”就能把 $L$ 从 $O(n)$ 缩短到 $O(\ln n)$。

直觉：把格子想象成一个环形城市。平时你只能走到相邻街区（路径长），但如果城市里随机开了几条”虫洞”（快速通道），你就能在几步内到达任何地方。

WS 模型解决了什么、没解决什么

特征	WS 模型	真实网络	匹配？
度分布	近似 Poisson（窄）	幂律（重尾）	不匹配
聚类系数	高	高	匹配
平均路径	短 $\sim \ln n$	短	匹配
Hub	不存在（度均匀）	存在	不匹配

WS 模型漂亮地解决了”高聚类 + 短路径”的共存问题，但度分布仍然是窄的——所有节点度数差不多，没有 hub。这是因为起始格子的度是均匀的，少量重连不会产生超高度节点。

Barabasi-Albert 无标度模型 (1999)

问题与动机

1999 年，Albert-Laszlo Barabasi 和 Reka Albert 在 Science 发表了另一篇里程碑论文。他们注意到真实网络有一个 ER 和 WS 都无法解释的特征：幂律度分布。

$P(k) \sim k^{-\gamma}$

这意味着度分布在双对数坐标下是一条直线。没有”典型尺度”——从度 1 到度 10000 都可能出现——所以叫”无标度”（scale-free）。

他们提出了两个生成幂律的关键机制：

1. 网络是增长的（Growth）：节点不是同时出现，而是逐步加入。
2. 新节点优先连接高度节点（Preferential Attachment）：连接概率与现有节点的度成正比。

模型定义

BA 模型 $\text{BA}(n, m_0)$ 的生成过程：

1. 初始状态：$m_0$ 个节点组成一个完全图（或其他小连通图）。
2. 增长：每个时间步，一个新节点加入，连接 $m_0$ 条边到已有节点。
3. 优先连接：新节点连接到节点 $v$ 的概率为：

$\Pi(v) = \frac{\deg(v)}{\sum_{u} \deg(u)}$

度越高的节点，吸引新连接的概率越大——“富者越富”（rich-get-richer）。

幂律度分布的推导

通过均场近似（mean-field approximation）可以推导 BA 模型的度分布。

设节点 $v$ 在时间 $t_v$ 加入网络。在时间 $t$，$v$ 的度的期望增长率为：

$\frac{\partial \deg(v, t)}{\partial t} = m_0 \cdot \frac{\deg(v, t)}{2m_0 t} = \frac{\deg(v, t)}{2t}$

逐项解释：

• $m_0$：新节点每步带来的边数
• $\frac{\deg(v, t)}{2m_0 t}$：优先连接概率（总度数为 $2m_0 t$，因为 $t$ 步后有 $m_0 t$ 条边）
• 分子 $\deg(v, t)$：$v$ 的当前度——度越高，增长越快

这是一个自增强过程。解这个 ODE：

$\deg(v, t) = m_0 \left(\frac{t}{t_v}\right)^{1/2}$

早加入的节点（$t_v$ 小）度增长更快。由此推导出稳态度分布：

$P(k) \sim 2m_0^2 k^{-3}$

即 $\gamma = 3$。这是 BA 模型的标志性结果——幂律指数恰好为 3。

Hub 的脆弱性

幂律度分布产生了少数超高度的 Hub 节点。Albert, Jeong & Barabasi (2000) 在 Nature 上展示了一个深刻的结果：

随机故障 vs 定向攻击：

• 随机移除节点：因为大多数节点度数低，随机移除几乎不影响网络连通性。即使移除 $5\%$ 的节点，巨组件仍然完整。无标度网络对随机故障极其健壮。
• 定向移除 Hub：只需移除少量最高度节点（$1\%$-$5\%$），网络就会碎片化——巨组件迅速缩小，平均路径急剧增长。无标度网络对定向攻击极其脆弱。

这对现实有重大意义：互联网的少数核心路由器、航空网络的枢纽机场、电网的关键变电站——保护这些 Hub 对维持网络运行至关重要。

BA 模型的局限

特征	BA 模型	真实网络	匹配？
度分布	幂律 $P(k) \sim k^{-3}$	幂律 $\gamma \in [2,3]$	基本匹配
聚类系数	低 $\sim (\ln n)^2 / n$	高	不匹配
平均路径	超短 $\sim \ln n / \ln \ln n$	短	匹配
Hub	有	有	匹配

BA 模型成功解释了幂律度分布和 hub 现象，但聚类系数仍然很低。原因：优先连接只关心度数，不关心”三角形”——新节点连接两个高度节点时，这两个高度节点之间未必有边。

度分布对比

三种模型的度分布在线性坐标和双对数坐标下呈现截然不同的形态：

• Poisson（ER）：在双对数坐标下弯曲并急剧下降——尾巴以指数速度衰减。
• 幂律（BA）：在双对数坐标下是一条直线——尾巴以多项式速度衰减，远远”更重”。

这意味着什么？在 $n = 10^6$ 的网络中：

• ER 模型（$c = 10$）：度超过 30 的节点几乎不存在
• BA 模型（$\gamma = 3$）：度超过 1000 的 hub 是意料之中的

你的算法在 Poisson 度分布上的分析，不适用于幂律度分布的真实网络。

三种模型对比总览

没有一个模型完美。每个模型捕捉了真实网络的部分特征：

• ER：提供数学基线和相变理论
• WS：解释高聚类 + 短路径的共存
• BA：解释幂律度分布和 hub 现象

理解这三个模型的长处和短板，就是理解”你的图算法跑在什么样的图上”的第一步。

交互探索：三种模型的图结构

下面的交互组件让你在 ER、WS、BA 三种模型之间切换，观察生成的图结构和度分布直方图的差异。注意 BA 模型的度分布是如何”拖出长尾”的。

选择模型：ERWSBA重新生成

Erdos-Renyi G(n,p)

n=20, p=0.15 | 每条边独立随机

算法复杂度与图类型的关系

了解网络模型不是纸上谈兵——它直接影响算法的实际性能。

BFS/最短路径：在小世界网络上，BFS 从任意起点出发，$O(\ln n)$ 层就能覆盖大部分节点。但在稀疏规则格子上，覆盖相同比例需要 $O(n)$ 层。

社区发现：Louvain 算法在具有明确社区结构的网络上效果最好——而小世界网络和真实社交网络恰好具有高聚类（社区的信号）。在纯 ER 随机图上，没有真正的社区结构，Louvain 会给出噪声性的划分。

PageRank / 中心性：在无标度网络上，PageRank 的分布也呈幂律——少数 Hub 的 PageRank 远超其他节点。在 ER 图上，PageRank 分布相对均匀，排名区分度低。

图着色：贪心着色在均匀度图上接近最优（$\chi \approx c$），但在无标度网络上需要更多颜色（Hub 的高度迫使其邻域使用更多不同颜色）。

应用场景

流行病建模

COVID-19 的传播不是在均匀随机网络上——而是在有 Hub（超级传播者）的无标度社交网络上。这解释了为什么少数超级传播事件贡献了大部分感染。流行病学家使用 BA 模型和更复杂的网络模型来模拟疫情传播，指导疫苗分配策略——优先给 Hub 接种比随机接种效率高得多。

在无标度网络上，经典 SIR 模型的传播阈值趋于零（$\beta_c \to 0$），意味着任何传染率都可能导致大规模爆发——这与 ER 模型上存在正阈值的结论截然不同。

互联网与基础设施韧性

互联网的 AS（Autonomous System）级拓扑近似无标度网络。Albert et al. (2000) 的研究表明，随机移除 $5\%$ 的路由器几乎不影响连通性，但定向移除最高度的 $1\%$ 路由器就能让网络碎片化。这一发现直接影响了互联网冗余设计和关键节点保护策略。

总结

本文是 Part 4”建模”的第一站。我们沿着历史脉络，建立了理解真实网络的三个理论支柱：

• Erdos-Renyi $G(n,p)$（1959）：最简单的随机图模型——每条边独立以概率 $p$ 存在。数学上优雅（相变理论），但度分布是 Poisson、聚类系数极低、没有 Hub——三方面都与真实网络不符。它的价值是提供”随机基线”。
• Watts-Strogatz 小世界（1998）：在规则格子上做少量随机重连。成功解释了”高聚类 + 短路径”的共存——只需 $p \sim 0.01$-$0.1$ 的重连就够了。但度分布仍然窄，没有 Hub。
• Barabasi-Albert 无标度（1999）：通过”增长 + 优先连接”生成幂律度分布 $P(k) \sim k^{-3}$。解释了 Hub 现象和”富者越富”效应。但聚类系数低。
• 无标度网络的双面性：对随机故障极其健壮，对定向攻击极其脆弱。这一发现对基础设施保护、疫情防控有直接应用价值。

关键教训：你的算法跑在什么图上？如果你只在 ER 随机图上测试，你可能严重低估了 Hub 节点对算法性能的影响。了解真实网络的统计特征，是设计高效图算法的前提。

本文建立了”图长什么样”的理论基础。下一篇 Art. 17: 概率图模型 将从”描述网络结构”转向”用图做概率推断”——节点是随机变量，边是依赖关系，图结构决定了推断的复杂度。而 Art. 18: 图嵌入与 GNN 将展示如何用神经网络直接在图上学习表征。

实现指引

模型/功能	库	函数/方法
ER $G(n,p)$	NetworkX	nx.erdos_renyi_graph(n, p)
ER $G(n,m)$	NetworkX	nx.gnm_random_graph(n, m)
Watts-Strogatz	NetworkX	nx.watts_strogatz_graph(n, k, p)
Newman-Watts-Strogatz	NetworkX	nx.newman_watts_strogatz_graph(n, k, p)
Barabasi-Albert	NetworkX	nx.barabasi_albert_graph(n, m)
幂律聚类图	NetworkX	nx.powerlaw_cluster_graph(n, m, p)
度分布	NetworkX	nx.degree_histogram(G)
聚类系数	NetworkX	nx.average_clustering(G)
平均最短路径	NetworkX	nx.average_shortest_path_length(G)
连通分量	NetworkX	nx.connected_components(G)
Configuration Model	NetworkX	nx.configuration_model(degree_sequence)
Stochastic Block Model	NetworkX	nx.stochastic_block_model(sizes, probs)
图生成	igraph	ig.Graph.Erdos_Renyi(n, p), ig.Graph.Barabasi(n, m)
图生成	graph-tool	gt.random_graph(N, deg_sampler)