ER 随机网络

模型定义

注意 $N$ 和 $p$ 并不唯一决定一张图：同样的参数，每次生成的网络都不同。我们研究的是这一类网络的统计性质，以及当 $N\to\infty$ 时“几乎必然”成立的性质。

边数：$\binom N2$ 个节点对各以概率 $p$ 连边，故边数服从二项分布，期望 $\langle M\rangle=p\,N(N-1)/2$，平均度 $\langle k\rangle=2\langle M\rangle/N=p(N-1)$。

度分布

每个节点与其余 $N-1$ 个节点各以概率 $p$ 相连，因此度服从二项分布，在 $N\to\infty$、$\langle k\rangle$ 固定时趋于泊松分布

$$P(k) = \binom{N-1}{k} p^k (1-p)^{N-1-k} \;\xrightarrow{N\to\infty,\ \langle k\rangle \text{固定}}\; e^{-\langle k\rangle}\frac{\langle k\rangle^k}{k!},$$

其中 $\langle k\rangle = p(N-1)$。泊松分布的方差等于均值，标准差为 $\sqrt{\langle k\rangle}$，相对宽度 $\sigma_k/\langle k\rangle=1/\sqrt{\langle k\rangle}$：平均度越大，节点的度越集中在平均值附近，几乎不存在枢纽。

最大度与最小度

要求“度不小于 $k_{\max}$ 的节点期望只有一个”：$N\,P(K\ge k_{\max})\approx1$；同理 $N\,P(K\le k_{\min})\approx1$。Barabási 书中以 $N=10^9$、$\langle k\rangle=1000$（粗略对应全球熟人网络）为例：数值求解得 $k_{\max}$ 约 $1.2\times10^3$（书中用级数近似得 1185）、$k_{\min}\approx816$。也就是说，即使在十亿规模的随机社会中，“最受欢迎的人”的朋友也只比平均多约 20%。真实社交网络中存在朋友数比平均多几个数量级的人，这本身就否定了随机网络模型。

聚集系数

节点 $i$ 的任意两个邻居之间是否连边，与其他边无关，概率仍为 $p$，所以 $C_{\text{rand}} \approx p = \langle k\rangle/(N-1)$。在平均度固定时，$C_{\text{rand}}$ 随 $N$ 增大按 $1/N$ 趋于 0，并且 $C(k)$ 与 $k$ 无关。真实网络的平均聚集系数则大体与规模无关（Barabási 书图 3.13）。

平均路径长度

$L_{\text{rand}} \approx \ln N/\ln \langle k\rangle$，只随 $N$ 对数增长：即便有几十亿个节点，平均路径也只有几步到十几步。推导与修正见小世界性与平均距离。

巨连通分支

逐渐增大 $p$，ER 网络会经历一个相变（phase transition）：$\langle k\rangle<1$ 时只有小碎片，$\langle k\rangle=1$ 时巨连通分支出现，$\langle k\rangle>\ln N$ 时整个网络几乎必然连通。巨分支所占比例 $S$ 满足 $S = 1 - e^{-\langle k\rangle S}$。四个区间的细节见ER 网络的演化与相变，各结果的推导见数学推导与算法。本专题页面的 ER 演示可以拖动 $p$ 观察这一过程。