论随机图的演化 · 生物医学网络科学

一句话看懂

把 $n$ 个点之间的边一条一条随机地加进去，图的许多性质不是慢慢变化的，而是在某个边数附近从“几乎不可能”跳到“几乎必然”。最著名的例子是：边数约为 $n/2$ （平均度为 1）时，一个包含有限比例节点的巨连通分支突然出现。

研究背景与问题

在 Erdős 与 Rényi 之前，图论主要研究一张具体的、确定的图有什么性质。他们在 1959 年的论文中开始考虑“随机选出的图”，并给出了连通性的阈值。1960 年这篇长文换了一个视角：把边数 $N$ 看作随时间增长的量，研究图随 $N$ 增大如何“演化”。作者在引言中提到，这种演化可以看作通信网络（如铁路、电网）逐步建设过程的简化模型。

核心问题是：对给定的结构（某种树、圈、完全子图、大连通分支、整体连通），边数需要增长到多大量级，它才几乎必然出现？

核心思想与方法

论文使用的模型是在 $n$ 个带标号的节点上、从 $\binom{n}{2}$ 条可能的边中等概率地选出 $N$ 条，记为 $\Gamma_{n,N}$ 。这就是今天的 $G(N,M)$ 模型；ER 随机网络中的 $G(N,p)$ 模型在 $N$ 很大时与之等价，平均度 $\langle k\rangle = 2N/n$ 。

阈值函数（threshold function）：对某个图性质 $A$ ，若存在函数 $A(n)$ ，使得当 $N(n)/A(n)\to0$ 时具有性质 $A$ 的概率趋于 0，而当 $N(n)/A(n)\to\infty$ 时该概率趋于 1，则称 $A(n)$ 为性质 $A$ 的阈值函数。

用这个语言，论文按边数从少到多梳理了图的演化：

含有 $k$ 个节点的树，阈值为 $n^{(k-2)/(k-1)}$ ：先出现孤立边，再出现 3 个节点的路径，依次类推；
圈的阈值是 $n$ 的量级； $k$ 个节点的完全子图，阈值为 $n^{2-2/(k-1)}$ ；
当 $N\sim cn$ 时，行为由常数 $c$ 决定， $c=\tfrac12$ 是分界点。

方法上主要是计数和概率论中的矩方法：计算某类子图个数的期望与方差，证明其在阈值两侧分别趋于 0 或集中在期望附近。

主要发现

子图的逐级出现：随着边数增加，复杂度更高的结构依次出现，每一种都有清晰的阈值。这把“随机图里什么时候出现什么”变成了可以精确回答的数学问题。
巨连通分支的相变： $N\sim cn$ 时，若 $c<\tfrac12$ ，所有连通分支都是树或只含一个圈，最大分支只有 $O(\ln n)$ 个节点；若 $c=\tfrac12$ ，最大分支约为 $n^{2/3}$ 的量级；若 $c>\tfrac12$ ，出现一个包含约 $G(c)\,n$ 个节点的巨分支，其余分支仍然很小。 $c=\tfrac12$ 正对应平均度 $\langle k\rangle=1$ 。
巨分支比例的方程：作者给出了 $G(c)$ 的隐式表达。换成平均度写法，就是ER 随机网络中的 $S=1-e^{-\langle k\rangle S}$ 。
“双跳”：最大分支的规模从 $\ln n$ 量级跳到 $n^{2/3}$ ，再跳到 $n$ 的量级，这一现象被称为 double jump。
连通性：要使整张图连通，边数需达到 $\tfrac12 n\ln n$ 的量级（即平均度约为 $\ln n$ ），远多于巨分支出现所需的边数。这一结果在 1959 年的论文中已经给出，本文把它放进了完整的演化图景中。

怎样读这篇论文

这是一篇约 40 页的纯数学论文，原刊没有 DOI，网上可找到扫描版。不必逐条读证明。建议：

先读引言，理解“演化”的设定和阈值函数的定义；
跳到讨论 $N\sim cn$ 的部分，重点看 $c<\tfrac12$ 、 $c=\tfrac12$ 、 $c>\tfrac12$ 三种情形的结论；
关于各类子图计数的定理可以只看结论，把它们画成一条“边数轴”，标出每种结构出现的位置。

读的时候可以同时打开网络结构指标与随机图中的 ER 演示，拖动 $p$ ，对照文中的结论。

局限与后续工作

模型过于均匀：ER 图的度分布是泊松分布，聚集系数约为 $\langle k\rangle/n$ ，几乎为零。Watts 与 Strogatz（1998）和 Barabási 与 Albert（1999）正是在与 ER 图比较时发现了真实网络的高聚类和重尾度分布。
推广到任意度分布：Molloy 与 Reed（1995）给出了给定度序列的随机图出现巨分支的判据；Newman、Strogatz 与 Watts（2001）用生成函数系统地处理了这类模型。网络可控性与稳定性专题中 $f_c$ 的推导（见数学推导与算法）就建立在这条路线上。
临界窗口的精细结构：后来的概率论研究（如 Bollobás、Łuczak 等）细致刻画了 $c=\tfrac12$ 附近的“临界窗口”。
从结构相变到动力学阈值：ER 图的巨分支相变与渗流、SIR 最终规模、相互依存网络的崩溃等问题在数学上同源，这一思想贯穿了网络上的传播与免疫、网络可控性与稳定性等动力学专题。

关联知识

ER 随机网络：模型定义、泊松度分布、巨连通分支在 $\langle k\rangle=1$ 处涌现，都直接来自本文和 1959 年的论文。
小世界与无标度网络模型：小世界与无标度网络都是在与 ER 图对照时被识别出来的；ER 图也是判断“小世界”时最基本的零模型。
结构鲁棒性与数学推导与算法：Molloy–Reed 判据是 ER 巨分支条件在任意度分布上的推广，随机删点的鲁棒性分析本质上是渗流问题。

延伸思考

用“分支过程”的直觉解释巨分支为什么恰在 $\langle k\rangle=1$ 时出现：从一个节点沿边向外探索，每一步平均能发现几个新节点？
巨分支出现只需要平均度约为 1，而整张图连通需要平均度约为 $\ln n$ 。在一个 2 万个蛋白质的 PPI 网络中，这两个数分别约是多少？这对理解“PPI 网络中常有孤立小片段”有什么启发？
ER 图的阈值现象是在 $n\to\infty$ 的极限下陈述的。对一个只有 100 个节点的脑区网络，你还能看到“突然”的相变吗？应该怎样用模拟来检验？