机器学习Erdos Renyi随机图生成方法及特性

　　目录

　　1 随机图生成简介

　　1.1Gnp和Gnm

　　1.2 生成方法

　　1.3 两种方法比较

　　2 Gnp随机图

　　2.1 只用n和p够吗？

　　n和p并不能完全决定一个图。我们发现即使给定n和p，图也有许多实现形式。如当n=10,p=1/6时，就可能产生如下的图：

　　2.2 Gnp的图属性

　　二项分布的离散分布图像如下图所示：

　　当n足够大时，二项分布可以用正态分布去近似。

　　我们设

　　图Gnp的图结构会随着p变化，如下图所示：

　　根据模拟实验，在Gnp中，平均度大于1时，巨大连通分量恰好出现。

　　Erdos-Renyi随机图即使扩展到很大，仍然可以保证节点之间只有几跳(hops)的距离，如下所示为图的平均最短路径长度h¯h¯随节点数量变化的关系图：

　　可以看到平均最短路径长度h¯随着节点数量n增长并满足O(logn)的增长阶。

　　2.3真实网络和Gnp的对比

　　相似点： 存在大的连通分量，平均最短路径长度

　　不同点： 聚类系数，度分布

　　在实际应用中，随机图模型可能有以下问题：

　　3 代码库

　　NetworkX中内置了Erdos-Renyi随机图的生成函数，包括Gnp和Gnm。就是需要注意Gnp的API[6]是

　　erdos_renyi_graph(n, p, seed=None, directed=False)

　　该API与、作用是相同的。

　　而GnmGnm的API[7]是

　　nm_random_graph(n, m, seed=seed, directed=False)

　　故大家在实际使用中要注意区分。

　　参考

　　[1]http://web.stanford.edu/class/cs224w/

　　[2]

　　Mitzenmacher M, Upfal E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis[M]. Cambridge university press, 2017.

　　[3]https://zh.m.wikipedia.org/zh-hans/随机图

　　[4]

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

　　[5]

　　Gilbert E N. Random graphs[J]. The Annals of Mathematical Statistics, 1959, 30(4): 1141-1144.

　　[6]https://networkx.org/documentation/stable/reference/generated/networkx.generators.random_graphs.erdos_renyi_graph.html

　　[7]https://networkx.org/documentation/stable/auto_examples/graph/plot_erdos_renyi.html?highlight=renyi

　　以上就是机器学习Erdos Renyi随机图生成方法及特性的详细内容，更多关于机器学习Erdos Renyi随机图的资料请关注脚本之家其它相关文章！

　　您可能感兴趣的文章: