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

这篇“机器学习Erdos Renyi随机图生成方法及特性是什么”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“机器学习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与nx.binomial_graph、nx.gnp_random_graph作用是相同的。

而GnmGnm的API[7]是

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

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

以上就是关于“机器学习Erdos Renyi随机图生成方法及特性是什么”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注亿速云行业资讯频道。