从节点到节点簇

现在，我们回到鸡尾酒聚会，做一些随机图理论的练习。开始时，我们有大量孤立的节点，然后我们模仿客人间的随机邂逅，在节点之间随机地添加链接。如果只添加少数几个链接，唯一的结果是一些节点通过链接形成了配对。如果继续添加链接，一些配对将不可避免地连接在一起，形成包含几个节点的簇。当添加了足够多的链接使每个节点平均拥有一个链接时，奇迹出现了：一个独一无二的巨大节点簇出现了。也就是说，大多数节点都是这个节点簇的一部分，无论从哪个节点出发，沿着节点间的链接前行，都能够到达大多数其他节点。这个时刻就是你那瓶昂贵的葡萄酒不再安全的时候，因为巨大的节点簇使得葡萄酒的消息可以传递到每一个人。数学家们将这个现象称为巨大连通分量的涌现，巨大连通分量中包含了大部分的节点。物理学家把这个现象称为渗流（ percolation ），并把巨大连通分量的涌现称为相变（ phase transition ），这和水结成冰的瞬间是类似的。社会学家们会说，客人这时刚好形成了社区。