生物医学网络科学Biomedical Network Science
网络结构指标与随机图15 / 19

真实网络与随机网络的比较

阅读
约 2 分钟

以 2006 年微软即时通信网络为例（Leskovec 与 Horvitz 2008 的分析，约 1.8 亿用户、13 亿条边，两人有过对话即连边）：

指标 真实网络 同规模 ER 网络
平均度 14.4 14.4（按定义相同）
度分布 高度右偏、重尾 泊松，集中在 14 附近
平均路径长度 6.6 ln⁡N/ln⁡⟨k⟩≈7\ln N/\ln\langle k\rangle \approx 7
聚集系数 0.11 ⟨k⟩/N≈8×10−8\langle k\rangle/N \approx 8\times10^{-8}

比较结果有一致也有反常：

  1. 路径长度：二者同样短。随机网络能解释“小世界”中“路径短”的那一半；
  2. 聚集系数：真实网络比随机网络高出约 6 个数量级。随机网络完全无法解释；
  3. 度分布：真实网络是重尾分布，有枢纽；随机网络没有。随机网络同样无法解释。

把本专题各页的结论汇总为逐项对照（参照 Barabási 书第 3 章小结的思路）：

性质 ER 模型的预测 真实网络的典型情况 结论
度分布 泊松，kmaxk_{\max} 只比 ⟨k⟩\langle k\rangle 高若干个 ⟨k⟩\sqrt{\langle k\rangle} 常为重尾，存在度高出平均几十倍以上的枢纽 不符，需要无标度模型等机制
连通性 ⟨k⟩>1\langle k\rangle>1 有巨分支；⟨k⟩<ln⁡N\langle k\rangle<\ln N 时碎裂 都有巨分支；许多 ⟨k⟩<ln⁡N\langle k\rangle<\ln N 的网络仍连通 部分符合
平均距离 ln⁡N/ln⁡⟨k⟩\ln N/\ln\langle k\rangle 多数量级一致；空间网络偏长，重尾网络可更短 大体符合
聚集系数 ⟨k⟩/N\langle k\rangle/N，随 NN 趋于 0；C(k)C(k) 与 kk 无关 高出几个数量级，与 NN 大体无关；C(k)C(k) 常随 kk 下降 不符，需要小世界模型与层次模块
度–度相关 无相关 社会网络常同配，生物与技术网络常异配 不符，见度相关性
中心性分布 各节点中心性相近，集中于平均值 少数节点占据大部分介数与 PageRank 不符

小世界性（small-world property）：网络的平均路径长度与同规模随机网络相近（L≈LrandL \approx L_{\text{rand}}），而聚集系数远高于随机网络（C≫CrandC \gg C_{\text{rand}}）。小世界系数 σ\sigma、ω\omega 等量化方法见小世界与无标度的统计判别。

那么，既然 ER 模型“错”了，为什么还要研究它？因为它是零模型（null model）：它告诉我们“如果连接完全随机，某个指标应该是多少”。真实网络与零模型的偏离，才是需要解释的、可能有生物学意义的结构。ER 模型只保留 NN 与 MM，因而无法区分“由度分布引起”的性质与“超出度分布”的性质；保持度序列的随机化网络（配置模型、双边交换）是更严格的零模型，见小世界与无标度的统计判别与零模型与空模型。

继续阅读