随机图模型

数学家是一种把咖啡变成定理的机器。
Alfred Renyi

A mathematician is a machine for turning coffee into theorems.
Alfred Renyi

随机图的历史

在 1959 和 1968 年期间，数学家 Paul Erdos 和 Alfred Renyi 发表了关于随机图（ Random Graph ）的一系列论文，在图论的研究中融入了组合数学和概率论，建立了一个全新的数学领域分支—随机图论。

随机图的案例 p=0.01

随机图的定义

本文只关注无向图的场景。顾名思义， 随机图（Random Graph） 就是将一堆顶点随机的连接上边。好比在地上撒了一堆豆子，而豆子之间是否用线来相连是根据某个概率值来确定的。通常来说，对于随机图而言有两种定义方式

随机图的度

随机图的连通分支

图的平均度的临界点

随机图的六度分离

六度分离 又称为 小世界现象 ，它的含义是在地球上任意选择两个人，他们之间最多相隔 个相识关系。换言之，来自世界上任何地方的两个人都可以通过不超过 个相识关系所连接起来。

The Six Degrees of Larry Stone

参考文献

1. Erdos Renyi Model：https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model

2. Giant Component：https://en.wikipedia.org/wiki/Giant_component

3. Erdős P, Rényi A. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci, 1960, 5(1): 17-60.

4. Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of modern physics, 2002, 74(1): 47.

5. 《巴拉巴西网络科学》，艾伯特-拉斯洛·巴拉巴西（Albert-LászlóBarabási），2020.