1 隨機圖生成簡介

1.1Gnp和Gnm

1.2 生成方法

1.3 兩種方法比較

2 Gnp隨機圖

2.1 只用n和p夠嗎？

n和p并不能完全決定一個圖。我們發(fā)現(xiàn)即使給定n和p，圖也有許多實現(xiàn)形式。如當n=10,p=1/6時，就可能產生如下的圖：

2.2 Gnp的圖屬性

二項分布的離散分布圖像如下圖所示：

當n足夠大時，二項分布可以用正態(tài)分布去近似。

• 聚類系數(shù)

我們設

• 連通分量

圖Gnp的圖結構會隨著p變化，如下圖所示：

根據(jù)模擬實驗，在Gnp中，平均度大于1時，巨大連通分量恰好出現(xiàn)。

• 平均最短路徑長度

Erdos-Renyi隨機圖即使擴展到很大，仍然可以保證節(jié)點之間只有幾跳(hops)的距離，如下所示為圖的平均最短路徑長度h¯h¯隨節(jié)點數(shù)量變化的關系圖：

可以看到平均最短路徑長度h¯隨著節(jié)點數(shù)量n增長并滿足O(logn)的增長階。

2.3真實網絡和Gnp的對比

相似點： 存在大的連通分量，平均最短路徑長度

不同點： 聚類系數(shù)，度分布

在實際應用中，隨機圖模型可能有以下問題：

• 度分布可能和真實網絡不同，畢竟真實網絡不是隨機的。
• 真實網絡中巨大連通分量的出現(xiàn)可能不具有規(guī)律性。
• 可能不存在局部的聚類結構，以致聚類系數(shù)太小。

3 代碼庫

NetworkX中內置了Erdos-Renyi隨機圖的生成函數(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)

故大家在實際使用中要注意區(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/隨機圖

[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隨機圖的資料請關注腳本之家其它相關文章！