小世界性与平均距离

推导：$\langle d\rangle\approx\ln N/\ln\langle k\rangle$

从一个节点出发，在稀疏、局部近似为树的网络中：1 步可达约 $\langle k\rangle$ 个节点，2 步约 $\langle k\rangle^2$ 个，$d$ 步以内总共

$$N(d)\approx1+\langle k\rangle+\langle k\rangle^2+\cdots+\langle k\rangle^d=\frac{\langle k\rangle^{d+1}-1}{\langle k\rangle-1}\approx\langle k\rangle^d .$$

可达节点数不能超过 $N$。令 $\langle k\rangle^{d_{\max}}\approx N$，得

$$d_{\max}\approx\frac{\ln N}{\ln\langle k\rangle}.$$

这个估计严格说是“搜索覆盖全网所需的步数”，更接近直径；但直径受少数极端路径支配，实际数据中它对平均距离 $\langle d\rangle$ 的近似反而更好，因此小世界性通常写作 $\langle d\rangle\approx\ln N/\ln\langle k\rangle$。关键在于 $\langle d\rangle$ 与 $N$ 呈对数关系：$N$ 增大 10 倍，平均距离只增加 $\ln10/\ln\langle k\rangle$ 步。

推导中隐含的假设

1. 局部树状：第 $d$ 层发现的节点都是“新”的。高聚类会让朋友的朋友大量重复，扩张变慢（见小世界现象）；
2. 分支因子等于 $\langle k\rangle$：严格地说，第二层以后的扩张因子是剩余度均值 $\langle k^2\rangle/\langle k\rangle-1$，ER 网络中它恰好等于 $\langle k\rangle$。对任意度分布的随机网络，Newman、Strogatz 与 Watts（2001）给出 $\ell\approx\ln(N/z_1)/\ln(z_2/z_1)+1$，$z_1=\langle k\rangle$、$z_2=\langle k^2\rangle-\langle k\rangle$ 分别为一阶、二阶邻居的平均数。度分布越重尾，$z_2$ 越大，距离越短，无标度网络因此可以是“超小世界”（见无标度网络）；
3. 有限规模：当 $\langle k\rangle^d$ 接近 $N$ 时扩张必然放慢，粗略公式低估距离。Fronczak 等（2004）对 ER 网络得到更精确的平均距离 $\langle d\rangle\approx(\ln N-\gamma_E)/\ln\langle k\rangle+1/2$，$\gamma_E\approx0.5772$ 为欧拉常数。代码示例中 $\langle k\rangle=6$、$N=16000$ 时，模拟值 5.61，粗略公式 5.40，修正公式 5.58。Barabási 书进阶专题 3.G 还讨论了直径的修正：在临界点附近网络呈长链状的树结构，直径远大于 $\ln N/\ln\langle k\rangle$ 的预测。

与真实网络的对照

Barabási 书表 3.2 比较了 10 个真实网络的 $\langle d\rangle$ 与 $\ln N/\ln\langle k\rangle$，摘录几例：