文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-04-02 19:55

关注

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_graphnx.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.

[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随机图的资料请关注编程网其它相关文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯