ER随机图的度分布

2016-12-09  本文已影响0人  鹿生鲜

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随机图的度分布可以由泊松分布来刻画。

上一篇下一篇

猜你喜欢

热点阅读