随机图的奇妙世界：探索相变现象与复杂网络的涌现

发表于2025-07-24|更新于2025-07-26|科技前沿

|浏览量:

作者：qmwneb946

引言：从物理相变到网络结构巨变

想象一下，你面前有一杯水。当你逐渐加热它，水分子开始活跃起来；当温度达到100摄氏度时（在标准大气压下），水会沸腾，转化为蒸汽。这是一个我们再熟悉不过的“相变”现象——物质状态从液态到气态的剧烈改变。这种现象的迷人之处在于，微观层面分子的持续运动变化，在宏观层面累积到某个临界点时，会引发系统性质的非线性、跳跃式改变。

在数学和计算机科学领域，尤其是在图论和复杂网络研究中，我们也观测到了类似的“相变”现象，但这回，转变的主角不再是水分子，而是网络结构本身。当网络中的连接数量逐渐增加时，它的拓扑结构会经历一系列惊人的、突发性的变化，从一个由零散小碎片组成的集合，突然“凝结”成一个庞大的、相互连接的“巨型连通分量”。这种现象，被称为“随机图的相变”。

本文将带你深入随机图的奇妙世界，特别是Erdos-Renyi（ER）模型，探索这些美妙的相变现象。我们将理解：

什么是随机图，以及它是如何建模的。
物理学中相变的概念如何为我们理解图结构变化提供灵感。
ER模型中最核心的几个相变点，例如孤立点的消失、巨型连通分量的诞生，以及整个网络的连通。
支撑这些发现的强大数学工具和思想。
随机图相变理论在理解真实世界复杂网络中的应用和延伸。
最后，我们将通过Python代码模拟这些现象，亲身体验随机图的魔力。

准备好了吗？让我们一同踏上这段从数学定理到现实世界的探索之旅！

什么是随机图？——Erdos-Renyi 模型 $G(n, p)$

要理解随机图的相变，我们首先需要理解随机图本身。在众多的随机图模型中，最经典、最基础，也是我们本文关注的焦点，是由保罗·埃尔德什（Paul Erdos）和阿尔弗雷德·雷尼（Alfred Renyi）在1959年引入的 $G(n, p)$ 模型。

$G(n, p)$ 模型的定义

$G(n, p)$ 随机图的构建规则异常简洁明了：

顶点集合（Vertices）：我们有 $n$ 个独立的顶点，通常标记为 $V = \{v_1, v_2, \dots, v_n\}$ 。这些顶点可以代表任何事物，例如社交网络中的个体、互联网中的路由器、生物系统中的蛋白质等。
边（Edges）的生成：对于任意一对不同的顶点 $v_i$ 和 $v_j$ (其中 $i \neq j$ )，我们以独立的概率 $p$ 在它们之间创建一条边。换句话说，每对潜在的边 $(v_i, v_j)$ 都会被“抛一枚硬币”，以 $p$ 的概率被选中成为实际的边。

这里的 $p$ 是一个介于 0 和 1 之间的实数 ( $0 \le p \le 1$ )。

举个例子，如果 $n=3$ ， $p=0.5$ ，那么有 $\binom{3}{2} = 3$ 条潜在的边： $(v_1, v_2)$ 、 $(v_1, v_3)$ 和 $(v_2, v_3)$ 。对于每一条潜在的边，我们都以 $0.5$ 的概率决定是否添加它。最终的结果可能是任何一种包含 0 到 3 条边的图，每种图出现的概率不同。

为什么 $G(n, p)$ 模型如此重要？

尽管 $G(n, p)$ 模型在某些方面可能无法完美地复制真实世界的复杂网络（例如，它没有“无标度”特性或“小世界”特性那么强的聚类），但它依然具有不可替代的基础地位：

理论分析的基石：其简单的构造规则使得我们可以利用强大的概率论工具对其进行严格的数学分析，从而揭示出许多通用的图结构特性。
理解复杂网络的起点：它是理解更复杂随机图模型（如Watts-Strogatz小世界模型和Barabasi-Albert无标度模型）的基础。通过对比ER模型与真实网络行为的差异，我们可以更好地理解真实网络的独特之处。
涌现现象的典范：它清楚地展示了“从简单规则中涌现复杂行为”的现象，这在科学的许多领域都普遍存在。
基准模型：在许多应用中，ER图被用作一个基准，以便于评估特定算法或网络结构性能的优劣。

$G(n, p)$ 的基本性质

在深入相变之前，让我们快速了解 $G(n, p)$ 的几个基本性质：

边的数量：给定 $n$ 个顶点，总共有 $\binom{n}{2}$ 条可能的边。因此，随机图 $G(n, p)$ 中边的期望数量是 $E[\text{边数}] = p \binom{n}{2} = p \frac{n(n-1)}{2}$ 。
度分布（Degree Distribution）：对于任意一个顶点 $v_i$ ，它与任何其他 $n-1$ 个顶点之间都可能存在边。每条边的存在是独立的事件。因此，一个顶点的度（即与它相连的边的数量）服从二项分布 $B(n-1, p)$ 。当 $n$ 很大时，这个分布可以近似为泊松分布 $Pois(\lambda)$ ，其中 $\lambda = (n-1)p \approx np$ 。

正是 $p$ 这个参数的微小变化，将引导我们进入随机图相变的奇妙世界。当 $p$ 从 0 缓慢增加到 1 的过程中，图的拓扑结构会经历一系列惊人的“跃迁”。

相变现象：物理学的启发

在深入随机图的具体相变之前，我们有必要简要回顾一下物理学中的“相变”概念，它为我们理解图结构的变化提供了绝佳的类比和深刻的洞察。

什么是相变？

相变是指物质在某个临界点（如温度、压强、磁场强度等）发生剧烈变化的现象。最经典的例子是水在特定温度下从液态变为固态（结冰）或气态（沸腾）。

临界点（Critical Point）：引发相变的关键参数值。在水沸腾的例子中，就是100摄氏度。
序参量（Order Parameter）：一个量化系统宏观状态的物理量，它在相变前后会发生显著改变。例如，对于磁性材料，磁化强度就是序参量；对于水，密度或蒸汽压可以看作序参量。在相变发生时，序参量往往从零变为非零，或经历一个剧烈跳跃。
第一类相变（First-Order Phase Transition）：相变过程中伴随着序参量的不连续跳跃（例如，水沸腾时密度骤降）。通常伴有潜热（能量吸收或释放）。
第二类相变（Second-Order Phase Transition）：序参量在临界点处是连续的，但其导数（或更高阶导数）不连续。通常没有潜热。例如，磁性材料在居里温度下的顺磁-铁磁转变。

相变在随机图中的映射

那么，这些概念如何映射到随机图呢？

控制参数：在 $G(n, p)$ 模型中，控制参数就是边的存在概率 $p$ 。我们通过逐渐增加 $p$ 来“加热”或“连接”我们的图。
系统规模：物理相变通常发生在宏观尺度上，当 $n$ 趋于无穷大时，相变现象才变得“尖锐”和“清晰”。在随机图中，我们通常也关注 $n \to \infty$ 时的渐近行为。
序参量：随机图的序参量可以是许多宏观结构属性，例如：
- 图中是否存在孤立顶点（度为0的顶点）。
- 图是否完全连通。
- 最大的连通分量占总顶点数的比例。
- 图中是否包含循环（Cycle）。

随机图的相变通常是第二类相变。例如，最大的连通分量的大小（作为序参量）在临界点是连续变化的，但其导数可能不连续，呈现出“涌现”的特性。这种类比不仅富有启发性，更提供了强大的数学工具来分析图的结构变化。

理解了这些背景，我们现在可以深入探讨Erdos-Renyi模型中最著名的几个相变点。

Erdos-Renyi 模型中的核心相变

当 $n$ 足够大时，ER图 $G(n, p)$ 的结构会随着 $p$ 的变化经历一系列惊人的、阈值效应般的转变。这些转变发生在 $p$ 达到某个“临界概率”时。我们将 $p$ 视为 $n$ 的函数，通常表示为 $p(n)$ 。

孤立点的消失

临界概率： $p \sim \frac{\ln n}{n}$

首先，让我们关注图中最简单的元素：孤立顶点（isolated vertices），即那些没有与任何其他顶点相连的顶点。当 $p$ 很小的时候，图中的大部分顶点都是孤立的。随着 $p$ 的增加，这些孤立点会逐渐被连接起来。那么，当 $p$ 达到多大时，图中几乎不再有孤立顶点呢？

数学直觉：
一个特定的顶点 $v$ 是孤立的，意味着它与所有其他 $n-1$ 个顶点都没有边相连。每个边存在的概率是 $p$ ，不存在的概率是 $(1-p)$ 。由于边是独立生成的，所以顶点 $v$ 是孤立的概率是 $(1-p)^{n-1}$ 。
图中有 $n$ 个顶点，因此孤立顶点的期望数量是 $E[\text{孤立顶点数}] = n \cdot (1-p)^{n-1}$ 。

我们知道，当 $x \to 0$ 时， $(1-x)^k \approx e^{-kx}$ 。所以，如果 $p$ 很小，那么 $(1-p)^{n-1} \approx e^{-p(n-1)} \approx e^{-pn}$ 。
因此， $E[\text{孤立顶点数}] \approx n e^{-pn}$ 。

当 $p$ 小于 $\frac{\ln n}{n}$ 时，例如 $p = \frac{c}{n}$ ，其中 $c < \ln n$ ：
如果 $p = \frac{c}{n}$ ， $E[\text{孤立顶点数}] \approx n e^{-cn}$ 。这个表达式仍然趋于零，因为 $c$ 可以是任意常数。
我们需要更精确的分析。当 $p = \frac{\ln n + c}{n}$ 时：
$E[\text{孤立顶点数}] \approx n \cdot e^{-(\ln n + c)} = n \cdot e^{-\ln n} \cdot e^{-c} = n \cdot \frac{1}{n} \cdot e^{-c} = e^{-c}$ 。

这意味着，当 $p = \frac{\ln n + c}{n}$ 时，孤立顶点的期望数量趋于一个常数 $e^{-c}$ 。

如果 $c \to \infty$ （即 $p$ 远大于 $\frac{\ln n}{n}$ ），那么 $e^{-c} \to 0$ ，几乎没有孤立顶点。
如果 $c \to -\infty$ （即 $p$ 远小于 $\frac{\ln n}{n}$ ），那么 $e^{-c} \to \infty$ ，有很多孤立顶点。

这个临界点 $p \sim \frac{\ln n}{n}$ 标志着 $G(n,p)$ 中几乎所有顶点都将至少有一条边连接。这是一个相对较高的 $p$ 值，说明要完全消除孤立点，需要相当密集的连接。

巨型连通分量的诞生

临界概率： $p_c = \frac{1}{n}$

这是Erdos-Renyi随机图最著名、也最具“戏剧性”的相变，通常被称为“大爆炸”（Big Bang）。当 $p$ 达到 $1/n$ 附近时，图中会突然涌现一个包含绝大多数顶点的连通分量，我们称之为“巨型连通分量”（Giant Component, GC）。

理解巨型连通分量的概念：
一个连通分量是图中的一个子图，其中任意两个顶点之间都有路径相连，且这个子图不能再被其他顶点扩展。在ER图中，当 $p$ 很小的时候，所有的连通分量都是“小”的，这意味着它们的大小是 $O(\log n)$ 或者更小，远小于总顶点数 $n$ 。而一个巨型连通分量，其顶点数是 $O(n)$ ，即与总顶点数 $n$ 成线性比例。

数学直觉：平均度 $np$
理解这个相变的关键在于平均度 $np$ 。在 $G(n,p)$ 中，每个顶点的期望度是 $\lambda = (n-1)p \approx np$ 。

阶段一：亚临界区 ( $p \ll \frac{1}{n}$ , 即 $np \ll 1$ )
- 在这一区域，平均度很小（例如，每个顶点平均连不到一条边）。
- 图中的所有连通分量都是小的，通常是树形结构或非常简单的循环。
- 最大的连通分量的大小是 $O(\ln n)$ 。
- 图看起来像是由许多小“岛屿”组成的群岛。
阶段二：临界点 ( $p = \frac{1}{n}$ , 即 $np = 1$ )
- 这是相变发生的精确点。平均度为1。
- 在这个点，图的结构变得非常复杂和不稳定。
- 许多小连通分量开始合并，形成一些稍大的分量。
- 最大的连通分量大小通常是 $O(n^{2/3})$ 。
阶段三：超临界区 ( $p \gg \frac{1}{n}$ , 即 $np \gg 1$ )
- 当 $p$ 超过 $1/n$ 之后，平均度开始大于1。
- 奇迹发生了：一个巨型连通分量迅速形成，并吞噬了大部分的顶点。
- 随着 $p$ 的继续增加，这个巨型连通分量会变得越来越大，最终包含几乎所有的顶点，只剩下少数孤立点或小分量。
- 巨型连通分量的大小通常是 $(1 - e^{-np})n$ 。例如，当 $np=2$ 时，巨型连通分量就包含了大约 $1 - e^{-2} \approx 86.5\%$ 的顶点。

这个相变点 $p_c = \frac{1}{n}$ 是随机图理论中最引人入胜的发现之一。它表明，即使每个边出现的概率 $p$ 看起来非常小（当 $n$ 很大时），只要它达到 $1/n$ ，整个网络的连接性就会发生质的飞跃。

连通性与直径的变化

临界概率： $p \sim \frac{\ln n}{n}$

我们前面提到了孤立点的消失也发生在 $p \sim \frac{\ln n}{n}$ 。实际上，当 $p$ 达到这个值时，不仅仅是孤立点消失了，整个图也几乎必然变得完全连通，即只有一个连通分量，并且所有顶点都在这个连通分量中。

数学直觉：
为了使图完全连通，它必须首先没有孤立点。因此，消除孤立点的条件是图完全连通的必要条件。事实上，它们发生的临界概率是相同的。

当 $p \ll \frac{\ln n}{n}$ 时，图通常不连通，有多个连通分量（包括孤立点和小分量）。
当 $p \approx \frac{\ln n}{n}$ 时，图从不连通状态“跳跃”到几乎必然连通。这意味着图中的所有顶点都属于同一个巨型连通分量。

直径的变化：
一旦图变得连通，我们就可以讨论其直径——图中任意两点之间最短路径的最大长度。ER图的直径在 $p$ 达到 $\frac{\ln n}{n}$ 之后会非常小，通常是 $O(\ln n / \ln (np))$ 。这正是“小世界”现象的一种体现：尽管图是随机构建的，但任何两点之间似乎都只有“六度分离”，通过相对较少的中间步骤就可以连接起来。

小结：ER图相变时间轴

我们可以将 $p$ 从 0 到 1 的增加过程看作一个“时间轴”，描绘出随机图的演化历程：

$p < \frac{1}{n}$ ：早期
- 图由许多小的、孤立的连通分量组成，通常是树或简单的循环。
- 最大的连通分量大小为 $O(\ln n)$ 。
- 图是高度不连通的，包含大量孤立顶点。
$p = \frac{1}{n}$ ：大爆炸
- 一个巨型连通分量开始形成，其大小从 $O(\ln n)$ 突然跃升到 $O(n)$ 。
- 图的结构发生质变。
$\frac{1}{n} < p < \frac{\ln n}{n}$ ：巨型连通分量的扩张
- 巨型连通分量继续增长，吞噬越来越多的小连通分量。
- 图仍然可能包含一些孤立点或非常小的独立分量。
- 尽管有巨型分量，但图整体上仍可能不完全连通。
$p = \frac{\ln n}{n}$ ：完全连通
- 图几乎必然变得完全连通，即所有顶点都属于同一个巨型连通分量。
- 几乎没有孤立顶点。
- 图的直径开始变得很小。
$p > \frac{\ln n}{n}$ ：稠密图
- 图变得越来越稠密，边越来越多。
- 所有顶点都高度连通，直径非常小。
- 随着 $p \to 1$ ，图趋近于一个完全图（complete graph）。

这些阈值现象是随机图理论最深刻和美丽的发现之一，它揭示了从简单的随机过程如何涌现出复杂的宏观结构。

数学工具与证明思想

随机图相变的发现并非偶然，而是基于一系列精巧的概率论和组合数学工具。了解这些工具和思想，对于理解这些现象的“为什么”至关重要。

概率方法（Probabilistic Method）

概率方法是Erdos本人开创的一种非构造性证明方法。它的核心思想是：要证明某个具有特定性质的图存在，只需要证明随机生成一个图时，它具有这种性质的概率大于0即可。虽然 $G(n,p)$ 模型的分析更为具体，但概率方法贯穿其始终。它强调了随机性在构造具有特定性质的结构（或证明其存在性）中的强大力量。

例如，如果我们想证明当 $p > \frac{\ln n}{n}$ 时，图中几乎没有孤立顶点，我们可以计算孤立顶点数大于零的概率，并证明其在 $n \to \infty$ 时趋于零。

期望与方差（Expectation and Variance）

这是分析随机图最常用的量化工具。

第一矩方法（First Moment Method）

用来证明某个事件几乎必然发生或几乎必然不发生。
对于一个非负随机变量 $X$ (例如，图中孤立顶点的数量，或包含特定子图的数量)，如果 $E[X] \to 0$ 当 $n \to \infty$ 时，那么根据马尔可夫不等式：
$P(X \ge 1) \le E[X]$
如果 $E[X] \to 0$ ，那么 $P(X \ge 1) \to 0$ ，这意味着事件 $X \ge 1$ 几乎必然不发生。也就是说，事件 $X = 0$ 几乎必然发生。

示例：孤立顶点的消失
我们已经计算过孤立顶点的期望数量 $E[X] = n(1-p)^{n-1}$ 。
当 $p = \frac{\ln n + \omega(n)}{n}$ 时，其中 $\omega(n) \to \infty$ 任意慢：
$E[X] = n(1-p)^{n-1} \approx n e^{-p(n-1)} \approx n e^{-(\frac{\ln n + \omega(n)}{n})(n-1)} \approx n e^{-(\ln n + \omega(n))} = n \cdot \frac{1}{n} \cdot e^{-\omega(n)} = e^{-\omega(n)}$ 。
由于 $\omega(n) \to \infty$ ，所以 $e^{-\omega(n)} \to 0$ 。
根据第一矩方法， $P(\text{存在孤立顶点}) \le E[X] \to 0$ 。所以，图中几乎必然没有孤立顶点。

第二矩方法（Second Moment Method）

第一矩方法只能证明某事件发生的概率很小。如果 $E[X] \to \infty$ ，我们不能直接得出结论说 $X$ 几乎必然不为零。这时就需要第二矩方法。
第二矩方法通常用于证明事件发生的概率趋于 1。它基于切比雪夫不等式：
$P(|X - E[X]| \ge t) \le \frac{Var[X]}{t^2}$
或者更常用的形式：
$P(X=0) \le \frac{Var[X]}{E[X]^2}$
如果 $Var[X]/E[X]^2 \to 0$ （即方差相对于期望的平方足够小），那么 $P(X=0) \to 0$ ，这意味着 $X$ 几乎必然不为零。

示例：孤立顶点的存在
当 $p = \frac{\ln n - \omega(n)}{n}$ 时，其中 $\omega(n) \to \infty$ 任意慢：
$E[X] \approx e^{\omega(n)} \to \infty$ 。
通过计算孤立顶点数的方差 $Var[X]$ ，并证明 $Var[X]/E[X]^2 \to 0$ ，我们可以得出结论：图中几乎必然存在孤立顶点。
结合第一矩和第二矩方法，我们可以精确地定位相变点。

分支过程（Branching Processes）

分支过程是一种描述个体繁殖或传播的随机过程。在随机图中，它被用来分析连通分量的大小分布，特别是巨型连通分量的形成。
想象我们从一个随机顶点 $v$ 开始，寻找它的连通分量。我们检查 $v$ 的邻居，然后检查这些邻居的邻居，以此类推。这就像一个“疾病传播”的过程。
在一个 $G(n,p)$ 图中，如果一个顶点有 $k$ 个邻居，那么平均而言，在 $n$ 很大的情况下，这 $k$ 个邻居中的每个又会与约 $np$ 个其他顶点相连。这个 $np$ 的值是关键。

如果 $np < 1$ （亚临界区），就像一个平均生育率低于1的种群，分支过程最终会灭绝，这意味着连通分量会很小。
如果 $np > 1$ （超临界区），就像一个平均生育率大于1的种群，分支过程有非零概率持续下去，形成一个无限大的（在随机图中就是 $O(n)$ 大小的）分支，这对应着巨型连通分量的形成。
这是巨型连通分量相变 $p_c=1/n$ 背后的核心思想。

图遍历算法：BFS/DFS

虽然不是严格意义上的数学证明工具，但广度优先搜索（BFS）和深度优先搜索（DFS）是理解和实际计算图中连通分量的核心算法。在模拟随机图相变时，我们就是通过运行BFS或DFS来找到并计算每个连通分量的大小，从而验证理论预测。

这些数学工具的结合，使得Erdos和Renyi能够对 $G(n,p)$ 模型的行为进行如此精确的预测，揭示了其令人惊叹的相变特性。

随机图相变的应用与延伸

随机图的相变理论不仅仅是纯粹的数学美学，它对理解真实世界的复杂系统具有深远的意义。虽然ER模型本身是简化的，但其揭示的普适性原理为我们研究更复杂的网络提供了基础。

复杂网络研究的基石

真实世界的网络，如社交网络、互联网、生物分子网络等，通常被称为“复杂网络”。它们往往具有ER图所不具备的特性，例如：

小世界效应（Small-World Effect）：许多真实网络都具有较短的平均路径长度（像ER图），但同时又具有较高的聚类系数（ER图的聚类系数非常低）。Watts和Strogatz提出的“小世界模型”就是为了捕捉这一特性。
无标度特性（Scale-Free Property）：许多真实网络的度分布遵循幂律（Power-Law）分布，这意味着少数节点（“枢纽节点”或“富节点”）拥有极其高的度，而大多数节点的度很低。ER图的度分布是泊松分布，没有这种“无标度”特性。Barabasi和Albert提出的“无标度网络模型”通过“优先连接”机制解释了这一现象。

尽管有这些差异，ER模型的相变理论仍然是理解这些复杂网络的出发点。例如：

网络鲁棒性与脆弱性：ER图的巨型连通分量相变研究启发了对网络鲁棒性的研究。例如，当随机删除节点或边时（类似于改变 $p$ ），网络何时会从连通状态突然分裂成许多小碎片？这在分析互联网中断、疾病传播或电网故障时至关重要。这被称为“渗流理论”（Percolation Theory），与随机图相变紧密相关。
信息传播与级联失效：理解信息、谣言或病毒如何在网络中传播，以及何时会发生大规模的级联失效，都可以从ER图的相变思想中汲取灵感。传播的速度和范围往往取决于网络的平均度，这正是与 $p$ 相关的参数。

流行病学建模

随机图相变的概念在流行病学中有着直接的应用。我们可以将个体视为顶点，将接触视为边。疾病的传播概率 $p$ 类似于ER图中的边连接概率。

如果感染者与健康个体接触的平均人数（类似于平均度 $np$ ）低于1，那么疾病通常会自行消退，不会引发大流行。
一旦这个平均接触人数超过1（即 $np > 1$ ），疾病就会有很大的概率爆发，并蔓延到大部分人群中，形成一个“巨型感染分量”。
这个临界点为公共卫生政策（如疫苗接种率、社交距离措施）提供了理论依据，帮助我们确定阻止疾病大流行的最小干预阈值。

机器学习与图神经网络（GNNs）

近年来，图神经网络（GNNs）在处理图结构数据方面取得了巨大成功。理解图的拓扑特性对于GNN的设计和性能至关重要。

随机图作为一种合成图数据，可以用于测试GNN模型在不同连接密度下的表现。
研究随机图的相变有助于我们理解GNN在不同稀疏程度或连通性图上的学习能力。例如，当图处于相变点附近时，其结构复杂性最高，这可能对GNN的训练提出更高的要求。

人工智能与生成式模型

一些生成式模型，例如生成对抗网络（GANs）或变分自编码器（VAEs），正在被研究用于生成具有特定拓扑属性的图。理解随机图的相变，能够帮助我们指导这些模型生成符合预期连接模式的图，例如生成一个恰好处于巨型连通分量相变点附近的图，来模拟临界状态下的复杂系统。

总而言之，随机图的相变现象是网络科学中的一个核心概念，它不仅仅是理论上的突破，更是理解、预测和设计复杂系统的强大工具。它以优雅的方式告诉我们，简单的局部规则如何能够催生出宏观层面的复杂和涌现行为。

Python 模拟与可视化

理论很美，但亲手实践才能真正感受其魅力。让我们使用Python的 networkx 库来模拟 Erdos-Renyi 随机图的构建，并观察巨型连通分量的诞生过程。

我们将执行以下步骤：

定义一个函数来生成 $G(n, p)$ 随机图。
对一系列不同的 $p$ 值，生成随机图。
计算每个图中最大的连通分量的大小。
将最大的连通分量相对大小（与总顶点数 $n$ 的比值）绘制成 $p$ 的函数，以可视化相变。
在相变点附近，我们还会可视化几个图，直观感受结构变化。

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import random

# 设置matplotlib中文显示
plt.rcParams['font.sans-serif'] = ['SimHei'] # 指定默认字体
plt.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的问题

def generate_er_graph(n, p):
    """
    生成一个 G(n, p) Erdos-Renyi 随机图。
    n: 顶点的数量
    p: 边的存在概率
    """
    G = nx.Graph()
    G.add_nodes_from(range(n)) # 添加n个顶点

    # 遍历所有可能的边对，并根据概率p添加边
    for i in range(n):
        for j in range(i + 1, n): # 避免重复和自环
            if random.random() < p:
                G.add_edge(i, j)
    return G

def get_largest_component_size(G):
    """
    计算图中最大连通分量的大小。
    G: networkx 图对象
    """
    if not G.nodes():
        return 0
    # nx.connected_components 返回一个迭代器，包含每个连通分量的节点集合
    components = nx.connected_components(G)
    # 找到最大的连通分量
    largest_component = max(components, key=len)
    return len(largest_component)

# --- 模拟参数设定 ---
n = 1000 # 顶点数量，相对较大，以便观察清晰的相变
p_values = np.linspace(0, 5 / n, 100) # p值范围，从0到 5/n，覆盖临界点 1/n
# np.linspace(start, stop, num) 生成等间隔的数字序列
# 5/n 是一个合适的上限，确保我们能看到巨型分量的形成

largest_component_sizes = [] # 存储不同p值下最大连通分量的大小

print(f"开始模拟 G({n}, p) 随机图的相变过程...")
for p in p_values:
    G = generate_er_graph(n, p)
    gc_size = get_largest_component_size(G)
    largest_component_sizes.append(gc_size / n) # 记录相对大小
    # print(f"p = {p:.5f}, 最大连通分量相对大小 = {gc_size / n:.3f}")

print("模拟完成，开始绘图...")

# --- 结果可视化 ---
plt.figure(figsize=(10, 6))
plt.plot(p_values * n, largest_component_sizes, 'b-') # x轴显示np值，更容易看到临界点
plt.axvline(x=1.0, color='r', linestyle='--', label=r'$np = 1$ 临界点') # 标记理论上的临界点 np=1

plt.xlabel(r'平均度 $np$', fontsize=14)
plt.ylabel('最大连通分量相对大小', fontsize=14)
plt.title(f'G({n}, p) 随机图的巨型连通分量相变', fontsize=16)
plt.grid(True, linestyle=':', alpha=0.7)
plt.legend(fontsize=12)
plt.show()

print("\n--- 关键P值下的图结构可视化 ---")
# 可视化几个关键P值附近的图
num_nodes_vis = 50 # 用于可视化的图顶点数量减小，以便清晰显示
p_critical = 1 / num_nodes_vis # 临界点 p = 1/n

p_visualize = [
    0.5 * p_critical,  # 亚临界区
    1.0 * p_critical,  # 临界点
    1.5 * p_critical,  # 超临界区
    3.0 * p_critical   # 远超临界区
]

titles = [
    f'亚临界区 ($np = {p_visualize[0]*num_nodes_vis:.2f}$)',
    f'临界点 ($np = {p_visualize[1]*num_nodes_vis:.2f}$)',
    f'超临界区 ($np = {p_visualize[2]*num_nodes_vis:.2f}$)',
    f'远超临界区 ($np = {p_visualize[3]*num_nodes_vis:.2f}$)'
]

fig, axes = plt.subplots(1, 4, figsize=(20, 5))
fig.suptitle(f'G({num_nodes_vis}, p) 随机图在不同p值下的结构', fontsize=16)

for i, p_val in enumerate(p_visualize):
    G_vis = generate_er_graph(num_nodes_vis, p_val)
    pos = nx.spring_layout(G_vis, seed=42) # 使用固定布局种子，以便对比

    # 获取连通分量，并为每个分量分配不同的颜色
    components = list(nx.connected_components(G_vis))
    node_colors = ['#%06x' % random.randint(0, 0xFFFFFF) for _ in components] # 随机颜色
    color_map = []
    for node in G_vis.nodes():
        for comp_idx, component in enumerate(components):
            if node in component:
                color_map.append(node_colors[comp_idx])
                break

    nx.draw(G_vis, pos, ax=axes[i], with_labels=False, node_size=50, alpha=0.8, width=0.5, node_color=color_map)
    axes[i].set_title(titles[i], fontsize=12)
    axes[i].set_xticks([])
    axes[i].set_yticks([])

plt.tight_layout(rect=[0, 0.03, 1, 0.9]) # 调整子图布局，避免标题重叠
plt.show()

代码解析：

generate_er_graph(n, p)：
- 这个函数根据 $G(n, p)$ 的定义，创建一个包含 $n$ 个顶点的图。
- 然后，它遍历所有可能的 $\binom{n}{2}$ 条边对。
- 对于每对顶点 $(i, j)$ ，它生成一个0到1之间的随机数。如果这个随机数小于 $p$ ，就意味着这条边“被选中”，然后添加到图中。
- networkx 是一个强大的Python库，用于创建、操作和研究图结构。
get_largest_component_size(G)：
- 这个函数利用 networkx.connected_components(G) 来获取图中所有的连通分量。它返回一个迭代器，其中每个元素都是一个连通分量中所有顶点的集合。
- max(components, key=len) 用于从这些集合中找到包含顶点数量最多的那个，并返回其大小。
模拟过程：
- 我们设置 n = 1000。这个数量足够大，可以清晰地观察到相变现象。
- p_values 使用 np.linspace 在 0 到 $5/n$ 之间均匀取 100 个点。为什么是 $5/n$ ？因为巨型连通分量的相变发生在 $p=1/n$ ，而完全连通发生在 $p=\ln n/n$ 。对于 $n=1000$ ， $\ln n \approx 6.9$ ，所以 $1/n = 0.001$ ， $\ln n/n \approx 0.0069$ 。我们只关注巨型连通分量的相变，所以 $p$ 取到 $5/n = 0.005$ 左右就足够了，它会覆盖 $np=1$ 临界点。
- 循环遍历每个 $p$ 值，生成图，计算最大连通分量的大小，并将其相对于 $n$ 的比值存储起来。
可视化结果：
- 我们绘制 largest_component_sizes（y轴）对 p_values * n（x轴，即平均度 $np$ ）的图。
- 使用 plt.axvline(x=1.0, ...) 在 $np=1$ 处绘制一条红色的垂直虚线，清晰地标记出理论上的相变临界点。
- 这张图应该会清晰地显示一个S形曲线，在 $np=1$ 附近急剧上升，完美地展现了巨型连通分量的“涌现”。
- 第二个可视化部分，我们选择一个更小的 num_nodes_vis = 50，以便图能够被直观地画出来。我们选择亚临界、临界、超临界和更超临界四个 $p$ 值进行对比，并为每个连通分量涂上不同的颜色，直观地展示在 $p$ 增加时，小分量如何合并成大分量。

运行这段代码，你将亲眼见证随机图如何在平均度 $np=1$ 附近，从一个由零散小碎片组成的集合，突然生长出一个巨大的、连接着绝大多数顶点的“骨架”。这是数学之美、统计物理之美和编程实践之美的高度融合！

结论：简单规则，无限复杂

随机图的相变现象是概率论、组合数学和统计物理学交叉领域中最迷人和富有洞察力的成果之一。它以最简洁的模型——Erdos-Renyi $G(n, p)$ ——揭示了复杂系统如何从简单的局部规则中涌现出宏观的、非线性的结构变化。

从微不足道的边概率 $p$ 逐渐增加，到 $p$ 达到 $1/n$ 时，一个“大爆炸”发生了，一个容纳绝大多数顶点的巨型连通分量骤然诞生。紧接着，当 $p$ 达到 $\ln n/n$ 时，图整体变得完全连通，并展现出“小世界”的特性。这些精确的阈值，以及它们背后期望、方差和分支过程等数学工具的运用，无不体现着科学的严谨与美妙。