随机图理论
20 世纪 60 年代,由两位匈牙利数学家建立了
ER 随机图理论,被公认为是在数学上开创了复杂
网络理论的系统性研究。
20 世纪的后 40 年中,随机图理论一直是研究
复杂网络的基本理论。
在 ER 随机图模型中,任意两个节点之间有一
条边相连接的概率都为 p ,几乎每一个 ER 随即图
都具有某种性质 Q ,如果当 N 趋于无穷大时产生
具有这种性质 Q 的 ER 随机图的概率为 1 。 ER 随
机图的许多重要的性质都是突然涌现的。也就是说,
对于任一给定的概率 P ,要么几乎每一个图都具有
某个性质 Q ,要么几乎每个图都不具有该性质。
4