机器学习Erdos Renyi随机图
orion-orion 人气:31 随机图生成简介
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与nx.binomial_graph
、nx.gnp_random_graph
作用是相同的。
而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.
[7]https://networkx.org/documentation/stable/auto_examples/graph/plot_erdos_renyi.html?highlight=renyi
加载全部内容