随机图

随机图（random graph）是按照指定概率机制生成的图。它不是某张图“看起来杂乱”的描述，而是一个以图为取值的随机对象：需要先说明顶点集、哪些边可以出现，以及各种边集合被选中的概率。

最常用的模型之一为 $G(n,p)$：顶点固定为 $1,\dots ,n$，每对不同顶点之间的边独立地以概率 $p$ 出现，其中 $0\le p\le 1$。例如 $G(4,1/2)$ 有六条可能边，每条各掷一次独立公平硬币决定是否出现，因此共有 $2^6=64$ 个等概率的有标号图。

模型与样本空间

令 $N=(\genfrac{}{}{0ex}{}{n}{2})$ 为可能边数。对某个具体有标号简单图 $H$，若其边数为 $m$，独立性给出 $$Pr(G(n,p)=H)=p^m(1-p{)}^{N-m}.$$ 这表示指定哪些边出现、哪些不出现的概率，而不是“边数等于 $m$”的概率。后一事件包含 $(\genfrac{}{}{0ex}{}{N}{m})$ 个不同边集合，故随机边数 $M$ 满足 $$Pr(M=m)=(\genfrac{}{}{0ex}{}{N}{m})p^m(1-p{)}^{N-m},m=0,\dots ,N.$$ 因此 $M\sim \mathrm{Bin}(N,p)$。当 $p=1/2$ 时所有有标号图等概率；一般 $p$ 下边数不同的图通常不等概率。

中间边数更常见，因为能产生它的不同边集合更多；每个具体有标号图仍各有1/64概率。

主例中指定三角形 $123$ 加孤立点四这一张图，概率为 $1/64$；边数恰为三的概率却为 $(\genfrac{}{}{0ex}{}{6}{3})/64=20/64=5/16$。两者的区别在于有没有固定每条边的身份。

指示变量与期望

为每条可能边 $e$ 定义指示变量 $X_e$，出现时取一，否则取零。则 $M=\sum _e{X}_e$，每项期望为 $p$，所以由期望的线性性， $$𝔼[M]=\sum _e𝔼[X_e]=Np.$$ 不同边独立使协方差为零，故 $$\mathrm{Var}(M)=\sum _e\mathrm{Var}(X_e)=Np(1-p).$$ 期望的求和本身不需要独立；把方差直接求和才使用独立性。$G(4,1/2)$ 的平均边数为三，方差为 $6\cdot \frac{1}{2}\cdot \frac{1}{2}=3/2$。

固定顶点 $v$ 的度为与它接触的 $n-1$ 个独立指示变量之和，因此 $\mathrm{deg}(v)\sim \mathrm{Bin}(n-1,p)$，期望为 $(n-1)p$。对主例期望为 $3/2$，方差为 $3/4$。不同顶点的度却不独立，因为它们共享一条可能边。

三角形计数及依赖

令 $T$ 为三角形数量。对每个三顶点集合 $S$，定义其构成三角形的指示变量 $Y_S$。三条不同边独立，故 $𝔼[Y_S]=p^3$；再求和得到 $$𝔼[T]=(\genfrac{}{}{0ex}{}{n}{3})p^3.$$ 主例为 $4\cdot (1/2{)}^3=1/2$。平均数为半个并不表示一次取样会出现半个三角形；每张样本图的三角形数仍是整数，分数描述重复抽样的期望。

不能因此把三角形事件也视为互相独立。三角形 $123$ 与 $124$ 共享边 $12$，二者同时出现只需要五条不同边，概率为 $p^5$；若它们独立则应为 $p^3{p}^3=p^6$。当 $0<p<1$ 时二者不同，协方差为 $p^5-p^6>0$；主例中为 $1/64$。

固定边数模型与条件变式

另一个模型 $G(n,m)$ 在所有具有恰好 $m$ 条边的有标号图中均匀抽取，边数固定，不同边的出现通常不独立。对 $0<p<1$，将 $G(n,p)$ 条件化于事件 $M=m$，每个 $m$ 边图的原概率都相同，所以条件分布正是 $G(n,m)$。

变式。 在四顶点、恰好一条边的均匀模型中，任一指定边出现的概率为 $1/6$，任意两条不同边同时出现的概率为零，而非 $(1/6{)}^2$。若把它误写成 $G(4,1/6)$，虽平均边数也为一，却会允许零条、两条乃至更多边，得到另一个分布。

边界与建模范围

当 $p=0$ 时图必无边，$p=1$ 时必为完全图；$n=1$ 时没有可能边。$G(n,p)$ 中各顶点地位对称，边独立，不能自动反映现实网络的社群、空间限制、重尾度数或边之间的依赖。若只用观测边密度估计 $p$，也只是确定这个模型的一个参数，不能证明独立边假设成立。