20世纪50年代末由两位匈牙利数学家Erdos和Renyi建立的随机图理论（Random graph theory）被公认是在数学上开创了复杂网络拓扑结构的系统性分析。
其中Erdos是一位颇具传奇色彩的数学家，他一生巡回世界，每到一个地方就跟当地的数学家讨论研究，写文章。他先后发表过一千多篇数学论文，被称为最多产的数学家。
Erdos
ER随机图有两种构建方式：
（1）G(N,M)，先确定N个点，然后向这N个点之间撒M条边；
（2）G(N,p)，也是先确定N个点，任意两个不同的节点之间的连边概率是p；
随机图可以通过Python下的一个编程包实现（不止随机图了，很多复杂网络的算法都有包括，下载地址：https://pypi.python.org/pypi/networkx/）
100个节点，p=0.03
100个节点，p=0.03
ER随机图的度分布：
度分布
很好理解，一个点的度为k的概率（有k个点与之相连），就在除它本身之外的（N-1）个点选k个和它相连，剩下（N-1-k）和它不连。所以是个二项分布。
二项分布可以由泊松分布近似：
二项分布泊松近视
这里的<k>=p(N-1)，为度的均值。
用Python出四个图，<k>=15的时候对应100个节点，1000个节点，10000个节点和100000个节点的情况。
代码
nodes=100
nodes=1000
nodes=10000
nodes=100000
在10000个节点的时候已经非常接近了，数量级达到100000的时候就非常契合了。
在N非常大（大于10000）的时候，ER随机图的度分布可以由泊松分布来刻画。
网友评论