機(jī)器學(xué)習(xí)Erdos?Renyi隨機(jī)圖生成方法及特性
1 隨機(jī)圖生成簡介
1.1Gnp和Gnm
1.2 生成方法
1.3 兩種方法比較
2 Gnp隨機(jī)圖
2.1 只用n和p夠嗎？
n和p并不能完全決定一個圖。我們發(fā)現(xiàn)即使給定n和p，圖也有許多實(shí)現(xiàn)形式。如當(dāng)n=10,p=1/6時，就可能產(chǎn)生如下的圖：
2.2 Gnp的圖屬性
二項(xiàng)分布的離散分布圖像如下圖所示：
當(dāng)n足夠大時，二項(xiàng)分布可以用正態(tài)分布去近似。
- 聚類系數(shù)
我們設(shè)
- 連通分量
圖Gnp的圖結(jié)構(gòu)會隨著p變化，如下圖所示：
根據(jù)模擬實(shí)驗(yàn)，在Gnp中，平均度大于1時，巨大連通分量恰好出現(xiàn)。
- 平均最短路徑長度
Erdos-Renyi隨機(jī)圖即使擴(kuò)展到很大，仍然可以保證節(jié)點(diǎn)之間只有幾跳(hops)的距離，如下所示為圖的平均最短路徑長度h¯h¯隨節(jié)點(diǎn)數(shù)量變化的關(guān)系圖：
可以看到平均最短路徑長度h¯隨著節(jié)點(diǎn)數(shù)量n增長并滿足O(logn)的增長階。
2.3真實(shí)網(wǎng)絡(luò)和Gnp的對比
相似點(diǎn)： 存在大的連通分量，平均最短路徑長度
不同點(diǎn)： 聚類系數(shù)，度分布
在實(shí)際應(yīng)用中，隨機(jī)圖模型可能有以下問題：
- 度分布可能和真實(shí)網(wǎng)絡(luò)不同，畢竟真實(shí)網(wǎng)絡(luò)不是隨機(jī)的。
- 真實(shí)網(wǎng)絡(luò)中巨大連通分量的出現(xiàn)可能不具有規(guī)律性。
- 可能不存在局部的聚類結(jié)構(gòu)，以致聚類系數(shù)太小。
3 代碼庫
NetworkX中內(nèi)置了Erdos-Renyi隨機(jī)圖的生成函數(shù)，包括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)
故大家在實(shí)際使用中要注意區(qū)分。
參考
[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/隨機(jī)圖
[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
以上就是機(jī)器學(xué)習(xí)Erdos Renyi隨機(jī)圖生成方法及特性的詳細(xì)內(nèi)容，更多關(guān)于機(jī)器學(xué)習(xí)Erdos Renyi隨機(jī)圖的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Python數(shù)據(jù)可視化Pyecharts庫的使用教程
pyecharts是一個用于生成echarts圖表的類庫。echarts是百度開源的一個數(shù)據(jù)可視化庫，用echarts生成的圖可視化效果非常棒。使用pyechart庫可以在python中生成echarts數(shù)據(jù)圖。本文將詳細(xì)介紹一下Pyecharts庫的使用，需要的可以參考一下2022-02-02
Python+OpenCV實(shí)現(xiàn)圖像融合的原理及代碼
這篇文章主要介紹了Python+OpenCV實(shí)現(xiàn)圖像融合的原理及代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值，需要的朋友可以參考下2018-12-12
這篇文章主要介紹了python安裝gdal的兩種方法,每種方法給大家介紹的都非常詳細(xì)，具有一定的參考借鑒價值，需要的朋友可以參考下2019-10-10
解決Python 中JSONDecodeError: Expecting value:&n
這篇文章主要介紹了解決Python 中JSONDecodeError: Expecting value: line 1 column 1 (char 0)錯誤問題，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-03-03
解決安裝torch后,torch.cuda.is_available()結(jié)果為false的問題
這篇文章主要介紹了解決安裝torch后,torch.cuda.is_available()結(jié)果為false的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
python實(shí)現(xiàn)圖片轉(zhuǎn)字符畫
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)圖片轉(zhuǎn)字符畫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-02-02
Python數(shù)據(jù)可視化Pyecharts庫實(shí)現(xiàn)桑葚圖效果
這篇文章主要介紹了Python數(shù)據(jù)可視化如何使用Pyecharts庫來實(shí)現(xiàn)桑葚圖效果圖，文中給出實(shí)現(xiàn)的示例代碼，有需要的朋友可以借鑒參考想，希望能夠有所幫助2021-09-09
python中關(guān)于CIFAR10數(shù)據(jù)集的使用
這篇文章主要介紹了python中關(guān)于CIFAR10數(shù)據(jù)集的使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
Python3 字典dictionary入門基礎(chǔ)附實(shí)例
Python字典是另一種可變?nèi)萜髂Ｐ?，且可存儲任意類型對象，如字符串、?shù)字、元組等其他容器模型，字典由鍵和對應(yīng)值成對組成，字典也被稱作關(guān)聯(lián)數(shù)組或哈希表2020-02-02
在Debian下配置Python+Django+Nginx+uWSGI+MySQL的教程
這篇文章主要介紹了在Debian下配置Python+Django+Nginx+uWSGI+MySQL的教程,Debian系統(tǒng)和Nginx服務(wù)器皆是高性能的選擇,需要的朋友可以參考下2015-04-04