埃尔德什雷尼模型

埃尔德什—雷尼模型（Erdős–Rényi model）是一类在固定带标号顶点集上随机选边的图模型。常用的两种版本是独立连边的 $G(n,p)$ 和固定边数、等概率选图的 $G(n,m)$。它们可以有相同的单边边际概率，但联合分布和边数波动不同。

四个顶点共有六条可能无向边。$G(4,1/2)$ 对六个顶点对各作独立公平选择，有 $64$ 张等概率图；$G(4,3)$ 则只从恰有三条边的 $(\genfrac{}{}{0ex}{}{6}{3})=20$ 张图中均匀选择。两者每条指定边出现概率都是一半，却不是同一随机机制。

独立边与边数分布

对有限无向简单图，无自环，记可能边数为 $N=(\genfrac{}{}{0ex}{}{n}{2})$。$G(n,p)$ 令这 $N$ 个边指示变量相互独立，均以概率 $p\in [0,1]$ 为一。一个具体含 $m$ 条边的图 $H$ 在 $0<p<1$ 时有概率 $$\mathbb{P}(G=H)=p^m(1-p{)}^{N-m}.$$ 端点 $p=0,1$ 分别退化为空边图和完全图。

总边数 $M$ 是独立伯努利变量之和，所以 $$\mathbb{P}(M=m)=(\genfrac{}{}{0ex}{}{N}{m})p^m(1-p{)}^{N-m},𝔼M=Np,\mathrm{Var}M=Np(1-p).$$ 二项式系数数的是有多少张图拥有这条边数，不能把单张图概率与边数事件概率混淆。四点公平例中，$M=0,\dots ,6$ 的概率依次为 $(1,6,15,20,15,6,1)/64$，均值三、方差 $3/2$。

G(4,3) 则把全部边数概率集中在三；相同平均数不等于相同波动。

固定顶点的度为 $\mathrm{Bin}(n-1,p)$，期望 $(n-1)p$。但不同顶点的度并不独立，因为它们共享一条可能边。一个指定三角形出现要求三条独立边同时存在，概率为 $p^3$，所以全图三角形的期望数为 $(\genfrac{}{}{0ex}{}{n}{3})p^3$。主例期望三角形数为一半，这不等于图含三角形的概率，因为一张图可以含多个三角形。

固定边数与条件分布

$G(n,m)$ 要求整数 $0\le m\le N$，在所有 $(\genfrac{}{}{0ex}{}{N}{m})$ 个 $m$ 边子集中等概率选择。$N>0$ 时，每条可能边的边际概率是 $m/N$；零或一个顶点时 $N=0$，只能得到空边图，不使用这个比值。当 $N\ge 2$ 时，两条不同边同时出现的概率为 $$\frac{(\genfrac{}{}{0ex}{}{N-2}{m-2})}{(\genfrac{}{}{0ex}{}{N}{m})}=\frac{m(m-1)}{N(N-1)},$$ $m<2$ 时直接记零。$G(4,3)$ 中该概率为 $1/5$，小于两个边际概率乘积 $1/4$，体现固定总量造成的负相关；独立公平模型中则恰为 $1/4$。

两模型的准确联系是：对 $0<p<1$，将 $G(n,p)$ 条件化在 $M=m$，得到 $G(n,m)$。证明是所有含 $m$ 边的具体图原来具有同一个概率 $p^m(1-p{)}^{N-m}$，除以它们概率之和后，每张成为 $1/(\genfrac{}{}{0ex}{}{N}{m})$。这是条件化的等价，不是把参数 $p=m/N$ 直接代入后的无条件等价。

变式。 三顶点固定一边模型不可能出现三角形；若用相同边际概率 $p=1/3$ 的独立模型，三角形概率为 $1/27$，且边数仍会波动。这给出了边际相同而事件概率不同的最小例子。

模型中的均匀性与独立性是明确假设。实际网络若具有组别效应，可使用随机块模型；若希望逐点固定度数，可使用配置模型。这些模型保留不同结构，不能仅因平均度相同就互相替代。诸如连通阈值的结论还涉及 $n\to \mathrm{\infty }$ 时参数随规模的变化；某次抽样的连通或断开不构成阈值证明。