读《网络科学引论》：随机，为什么仍能产生结构？

这篇文章根据此前的阅读笔记整理。随机图最吸引我的地方，是它让“没有精心安排的局部连接”，也能表现出清晰的整体规律。

先分清两种随机

在 $G(n,m)$ 中，节点数和边数固定，从所有满足条件的简单图中等概率选择一张。在 $G(n,p)$ 中，每一对不同节点独立地以概率 $p$ 连边，边数本身也是随机变量。

对无向简单图 $G(n,p)$ ，边数的期望为 $\binom{n}{2}p$ ，平均度的期望为 $(n-1)p$ 。区分模型之后，公式才有明确的适用对象。

一个节点的度服从二项分布。在节点数趋于无穷、连边概率随之缩小，并使平均度趋于常数 $c$ 的稀疏极限下，度分布趋于泊松分布：

P(k)=e^{-c}\frac{c^k}{k!}.

这里不能省略稀疏极限的条件。将“随机图的度分布是泊松分布”当作无条件结论，会把有限规模和其他参数区间的差异抹掉。

在这个稀疏模型的渐近讨论中，当 $c>1$ 时会出现占据正比例节点的巨型连通分量。其比例 $S$ 满足

S=1-e^{-cS}.

刚越过阈值时，它并不会立刻包含几乎所有节点。“出现宏观连通结构”与“整张图连通”是两件事，这也是回看原笔记时需要特别澄清的地方。

独立连边的假设让模型容易分析，却也限制了它。现实网络中的枢纽、群落、三角闭合和连接相关性，并不都能由这个模型解释。

所以，随机图更适合作为比较的起点：如果观测到的结构明显偏离基准，就可以继续追问，哪些生成机制被独立连边的假设忽略了。

这也让阅读自然接到了研究上。一个模型值得反复读，既因为它给出了答案，也因为它帮助我们把尚未解释的问题说得更清楚。