生物医学网络科学Biomedical Network Science
小世界与无标度网络模型02 / 17

规则网格与随机网络

阅读
约 1 分钟

先看两个容易分析的极端情形（NN 个节点，平均度 KK）：

环形规则网格（ring lattice） ER 随机网络
构造 节点排成一圈，每个节点与左右各 K/2K/2 个最近邻相连 每对节点以概率 pp 独立连边
聚集系数 CC 3(K−2)4(K−1)\dfrac{3(K-2)}{4(K-1)}，KK 较大时接近 3/43/4，与 NN 无关 ≈p=⟨k⟩/(N−1)\approx p = \langle k \rangle/(N-1)，随 NN 增大趋于 0
平均路径 LL ≈N/(2K)\approx N/(2K)，随 NN 线性增长 ≈ln⁡N/ln⁡⟨k⟩\approx \ln N / \ln \langle k \rangle，随 NN 对数增长

例如 N=1000N=1000、K=10K=10：规则网格 C≈0.67C\approx 0.67、L≈50L\approx 50；同规模随机网络 C≈0.01C\approx 0.01、L≈3L\approx 3。真实网络介于两者之间吗？Watts 和 Strogatz 1998 年给出的三组数据（LL 为实际值，LrL_r、CrC_r 为同规模随机网络的值）：

网络 LL LrL_r CC CrC_r
电影演员合作网络 3.65 2.99 0.79 0.00027
美国西部电网 18.7 12.4 0.080 0.005
秀丽隐杆线虫神经网络 2.65 2.25 0.28 0.05

三个网络都是 L≳LrL \gtrsim L_r、C≫CrC \gg C_r：路径几乎和随机网络一样短，聚集系数却高出一到三个数量级。这个组合既不属于规则网格，也不属于随机网络。

继续阅读