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

目录
  • 1 随机图生成简介
    • 1.1Gnp和Gnm
    • 1.2 生成方法
    • 1.3 两种方法比较
  • 2 Gnp随机图
    • 2.1 只用n和p够吗？
    • 2.2 Gnp的图属性
    • 2.3真实网络和Gnp的对比
  • 3 代码库
  • 参考

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)

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

参考

[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随机图的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • python绘制随机网络图形示例

    如下所示: #Copyright (c)2017, 东北大学软件学院学生 # All rightsreserved #文件名称:a.py # 作 者:孔云 #问题描述: #问题分析:.代码如下: import networkx as ne #导入建网络模型包,命名ne import matplotlib.pyplot as mp #导入科学绘图包,命名mp #erdos renyi graphy rg=ne.erdos_renyi_graph(20,0.8) ps=ne.shell_layout

  • python生成随机图形验证码详解

    使用python生成随机图片验证码,需要使用pillow模块 1.安装pillow模块 pip install pillow 2.pillow模块的基本使用 1.创建图片 from PIL import Image #定义使用Image类实例化一个长为400px,宽为400px,基于RGB的(255,255,255)颜色的图片 img1=Image.new(mode="RGB",size=(400,400),color=(255,255,255)) #把生成的图片保存为"pi

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

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

    目录 1 随机图生成简介 1.1Gnp和Gnm 1.2 生成方法 1.3 两种方法比较 2 Gnp随机图 2.1 只用n和p够吗? 2.2 Gnp的图属性 2.3真实网络和Gnp的对比 3 代码库 参考 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的图属性 二项分布的离散分布图像如

  • php简单随机字符串生成方法示例

    本文实例讲述了php简单随机字符串生成方法.分享给大家供大家参考,具体如下: <?php function rand_str($length,$p='all'){ $nums = '0123456789'; $lowers = 'abcdefghijklmnopqrstuvwxyz'; $uppers = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; if ($p == 'all') { $src = $nums.$lowers.$uppers; } else { $src = '

  • Python生成不重复随机值的方法

    本文实例讲述了Python生成不重复随机值的方法.分享给大家供大家参考.具体分析如下: 这里从一列表中,生成不重复的随机值 算法实现如下: import random total = 100 li = [i for i in range(total)] res = [] num = 20 for i in range(num): t = random.randint(i,total-1) res.append(li[t]) li[t], li[i] = li[i], li[t] print re

  • Python生成随机数组的方法小结

    Python生成随机数组的方法小结

    本文实例讲述了Python生成随机数组的方法.分享给大家供大家参考,具体如下: 研究排序问题的时候常常需要生成随机数组来验证自己排序算法的正确性和性能,今天把Python生成随机数组的方法稍作总结,以备以后查看使用. 一.使用random模块生成随机数组 python的random模块中有一些生成随机数字的方法,例如random.randint, random.random, random.uniform, random.randrange,这些函数大同小异,均是在返回指定范围内的一个整数或浮点

  • JavaScript生成随机字符串的方法

    本文实例讲述了JavaScript生成随机字符串的方法.分享给大家供大家参考.具体分析如下: 这里使用JavaScript生成一个随机字符串,可以指定字符串的长度. 复制代码 代码如下: function RandomString(length) {     var str = '';     for ( ; str.length < length; str += Math.random().toString(36).substr(2) );     return str.substr(0, l

  • PHP生成各种随机验证码的方法总结【附demo源码】

    PHP生成各种随机验证码的方法总结【附demo源码】

    本文实例总结了PHP生成各种随机验证码的方法.分享给大家供大家参考,具体如下: 验证码在WEB应用中非常重要,通常用来防止用户恶意提交表单,如恶意注册和登录.论坛恶意灌水等.本文将通过实例讲解使用PHP生成各种常见的验证码包括数字验证码.数字+字母验证码.中文验证码.算术验证码等等以及其Ajax验证过程. 点击此处本站下载示例源码. PHP生成验证码图片 PHP生成验证码的原理:使用PHP的GD库,生成一张带验证码的图片,并将验证码保存在Session中.PHP生成验证码的大致流程有: 1.产生

  • php使用指定字符列表生成随机字符串的方法

    本文实例讲述了php使用指定字符列表生成随机字符串的方法.分享给大家供大家参考.具体如下: <?php function randomString($len) { srand(date("s")); $possible="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890!@#$%^&*()"; $str=""; while(strlen($str)<$

  • PHP动态生成指定大小随机图片的方法

    本文实例讲述了PHP动态生成指定大小随机图片的方法.分享给大家供大家参考,具体如下: <?php $image_width = 100; $image_height = 100; $image_str = ''; if (isset($_GET['w'])) { $image_width = intval($_GET['w']); } if (isset($_GET['h'])) { $image_height = intval($_GET['h']); } if (isset($_GET['s

  • python生成随机密码或随机字符串的方法

    本文实例讲述了python生成随机密码或随机字符串的方法.分享给大家供大家参考.具体实现方法如下: import string,random def makePassword(minlength=5,maxlength=25): length=random.randint(minlength,maxlength) letters=string.ascii_letters+string.digits # alphanumeric, upper and lowercase return ''.joi

  • C#生成随机ArrayList的方法

    本文实例讲述了C#生成随机ArrayList的方法.分享给大家供大家参考.具体实现方法如下: public static void RandomizeArrayList(ArrayList arrayList, Random random) { if(arrayList == null) { return; } int count = arrayList.Count; for(int i=0;i<count;i++) { Object tmp = arrayList[i]; arrayList.

随机推荐