機(jī)器學(xué)習(xí)Erdos?Renyi隨機(jī)圖生成方法及特性
1 隨機(jī)圖生成簡(jiǎn)介
1.1Gnp和Gnm
1.2 生成方法
1.3 兩種方法比較
2 Gnp隨機(jī)圖
2.1 只用n和p夠嗎？
n和p并不能完全決定一個(gè)圖。我們發(fā)現(xiàn)即使給定n和p，圖也有許多實(shí)現(xiàn)形式。如當(dāng)n=10,p=1/6時(shí)，就可能產(chǎn)生如下的圖：
2.2 Gnp的圖屬性
二項(xiàng)分布的離散分布圖像如下圖所示：
當(dāng)n足夠大時(shí)，二項(xiàng)分布可以用正態(tài)分布去近似。
- 聚類系數(shù)
我們?cè)O(shè)
- 連通分量
圖Gnp的圖結(jié)構(gòu)會(huì)隨著p變化，如下圖所示：
根據(jù)模擬實(shí)驗(yàn)，在Gnp中，平均度大于1時(shí)，巨大連通分量恰好出現(xiàn)。
- 平均最短路徑長(zhǎng)度
Erdos-Renyi隨機(jī)圖即使擴(kuò)展到很大，仍然可以保證節(jié)點(diǎn)之間只有幾跳(hops)的距離，如下所示為圖的平均最短路徑長(zhǎng)度h¯h¯隨節(jié)點(diǎn)數(shù)量變化的關(guān)系圖：
可以看到平均最短路徑長(zhǎng)度h¯隨著節(jié)點(diǎn)數(shù)量n增長(zhǎng)并滿足O(logn)的增長(zhǎng)階。
2.3真實(shí)網(wǎng)絡(luò)和Gnp的對(duì)比
相似點(diǎn)： 存在大的連通分量，平均最短路徑長(zhǎng)度
不同點(diǎn)： 聚類系數(shù)，度分布
在實(shí)際應(yīng)用中，隨機(jī)圖模型可能有以下問(wèn)題：
- 度分布可能和真實(shí)網(wǎng)絡(luò)不同，畢竟真實(shí)網(wǎng)絡(luò)不是隨機(jī)的。
- 真實(shí)網(wǎng)絡(luò)中巨大連通分量的出現(xiàn)可能不具有規(guī)律性。
- 可能不存在局部的聚類結(jié)構(gòu)，以致聚類系數(shù)太小。
3 代碼庫(kù)
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ī)圖的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
python進(jìn)階collections標(biāo)準(zhǔn)庫(kù)使用示例詳解
這篇文章主要為大家介紹了python進(jìn)階collections標(biāo)準(zhǔn)庫(kù)使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
Python自動(dòng)化辦公之定時(shí)發(fā)送郵件的實(shí)現(xiàn)
python中的schedule模塊可以使我們方便簡(jiǎn)單的使用定時(shí)任務(wù)，即在特定的時(shí)間自動(dòng)的執(zhí)行一些任務(wù)的功能，本文將用這一模塊實(shí)現(xiàn)郵件自動(dòng)發(fā)送，需要的可以參考一下2022-05-05
Python API 自動(dòng)化實(shí)戰(zhàn)詳解(純代碼)
今天小編就為大家分享一篇Python API 自動(dòng)化實(shí)戰(zhàn)詳解(純代碼)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-06-06
這篇文章介紹了python解析.pyd文件的詳細(xì)代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考2021-12-12
使用Pycharm為項(xiàng)目創(chuàng)建一個(gè)虛擬環(huán)境完整圖文教程
這篇文章主要給大家介紹了關(guān)于使用Pycharm為項(xiàng)目創(chuàng)建一個(gè)虛擬環(huán)境的相關(guān)資料,我們?cè)谑褂胮ycharm做項(xiàng)目時(shí),最好給每一個(gè)工程都創(chuàng)建一個(gè)虛擬環(huán)境,將對(duì)應(yīng)的安裝包放在該虛擬環(huán)境中,避免項(xiàng)目與項(xiàng)目之間產(chǎn)生關(guān)系或沖突,便于管理,需要的朋友可以參考下2023-09-09
這篇文章主要介紹了Python中異常的捕獲與處理詳解,調(diào)試Python程序時(shí)，經(jīng)常會(huì)報(bào)出一些異常，異常的原因一方面可能是寫(xiě)程序時(shí)由于疏忽或者考慮不全造成了錯(cuò)誤，這時(shí)就需要根據(jù)異常Traceback到出錯(cuò)點(diǎn)，進(jìn)行分析改正,需要的朋友可以參考下2023-08-08
字符串的格式化方法分為兩種，分別為占位符(%)和format方式。這篇文章主要介紹了Python3 中的字符串格式化語(yǔ)法問(wèn)題,需要的朋友可以參考下2020-01-01
python中獲得當(dāng)前目錄和上級(jí)目錄的實(shí)現(xiàn)方法
這篇文章主要介紹了python中獲得當(dāng)前目錄和上級(jí)目錄的實(shí)現(xiàn)方法,需要的朋友可以參考下2017-10-10
這篇文章主要介紹了淺談Python的異常處理的相關(guān)資料,需要的朋友可以參考下2016-06-06
使用EduBlock輕松學(xué)習(xí)Python編程
今天小編就為大家分享一篇關(guān)于使用EduBlock輕松學(xué)習(xí)Python編程的文章，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-10-10