ER随机图的度分布
2016-12-09 本文已影响0人
鹿生鲜
20世纪50年代末由两位匈牙利数学家Erdos和Renyi建立的随机图理论(Random graph theory)被公认是在数学上开创了复杂网络拓扑结构的系统性分析。
其中Erdos是一位颇具传奇色彩的数学家,他一生巡回世界,每到一个地方就跟当地的数学家讨论研究,写文章。他先后发表过一千多篇数学论文,被称为最多产的数学家。
ErdosER随机图有两种构建方式:
(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.03ER随机图的度分布:
度分布很好理解,一个点的度为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随机图的度分布可以由泊松分布来刻画。