Erdős–Rényi 随机图 | Codeboy's Blog

形式陈述

固定标号顶点集 $[n]=\{1,\ldots,n\}$ ，共有 $N=\binom n2$ 条候选无向边。模型 $G(n,p)$ 为每条候选边 $e$ 取相互独立的指示变量 $X_e\sim\operatorname{Bernoulli}(p)$ ，并令

E(G)=\{e:X_e=1\}.

因此每个含 $m$ 条边的标号简单图 $H$ 出现的概率是 $p^m(1-p)^{N-m}$ ，总边数服从 $\operatorname{Bin}(N,p)$ ；任一固定顶点的度服从 $\operatorname{Bin}(n-1,p)$ ，期望为 $(n-1)p$ 。

模型 $G(n,m)$ 则在全部 $\binom Nm$ 个含恰好 $m$ 条边的标号简单图中均匀取一个。它的边数恒为 $m$ ，各边边缘概率都是 $m/N$ ，但边指示变量不独立。两种模型在合适的参数尺度下可对许多单调性质给出相近渐近结论，却不是同一个有限分布，也不能逐个样本视为相等。

若固定简单图 $F$ 有 $v$ 个顶点、 $e$ 条边， $G(n,p)$ 中标号嵌入数的期望为 $(n)_v p^e/|\operatorname{Aut}(F)|$ ；这个公式来自对每个候选顶点像使用指示变量并应用期望线性性，不要求不同副本彼此独立。

直觉

$G(n,p)$ 可以看成同时拨动 $N$ 个独立开关，每个开关决定一条边是否存在。模型只在最底层边选择上独立；连通、出现三角形、存在孤立点等全局事件共享大量开关，通常强烈相关。 $G(n,m)$ 则先锁定开关总数再随机选择位置：选中一条边会略微降低另一条边被选中的条件概率，这正是固定总量带来的依赖。

随机图的阈值描述的是随 $n$ 增大、参数 $p=p(n)$ 改变时，某个单调性质从高概率不出现转为高概率出现的尺度。它不是声称有限 $n$ 上存在没有过渡区的物理相变，也不是每个性质都共享同一阈值。

例子与边界

三角形数可写为

T=\sum_{\{i,j,k\}\in\binom{[n]}3}X_{ij}X_{ik}X_{jk}, \qquad \mathbb E T=\binom n3p^3.

固定顶点成为孤立点的概率是 $(1-p)^{n-1}$ ，所以孤立点数 $I$ 满足 $\mathbb E I=n(1-p)^{n-1}$ 。这两个计算展示同一阶矩工具的不同作用： $\mathbb ET<1$ 可帮助证明存在无三角形样本，孤立点期望接近零则提示连通性阈值附近的障碍，但单凭期望很大并不能保证变量以高概率为正，通常还需要二阶矩或集中论证。

两条相邻边在 $G(n,p)$ 中独立，但“三角形 $123$ 出现”和“三角形 $124$ 出现”共享边 $12$ ，并不独立。在 $G(n,m)$ 中，任意两条不同边 $e,f$ 满足

\Pr(f\in E\mid e\in E)=\frac{m-1}{N-1},

通常不等于 $m/N$ 。退化参数 $p=0,1$ 分别给出空图和完全图，仍是合法模型。这里默认标号、简单、无向图；无标号随机图或允许自环、重边的模型拥有不同样本空间。

推论与应用

Erdős–Rényi 模型是概率方法中最基本的随机组合对象。一阶矩可排除稀有坏结构，二阶矩处理多个候选结构间的依赖，图连通性、巨分量、着色数与固定子图出现都可据此研究各自的渐近尺度。

模型还提供算法与网络的平均情形基线，但真实网络若有重尾度分布、聚团或社区结构，就不应因边缘密度相同而直接套用 $G(n,p)$ 。选择模型时应先问独立边与同质顶点是否符合机制，再解释由模型得到的概率结论。

参考资料

Béla Bollobás, Random Graphs, 2nd ed., Cambridge University Press, 2001, Chapters 1–4.
Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016, Chapters 1–4.

形式陈述 ​

直觉 ​

例子与边界 ​

推论与应用 ​

反向链接

形式陈述

直觉

例子与边界

推论与应用