1 隨機圖生成簡介
1.1 \(G_{np}\)和\(G_{nm}\)
以下是我學習《CS224W：Machine Learning With Graphs》[1]中隨機圖生成部分的筆記，部分補充內容參考了隨機演算法教材[2]和wiki[3]，隨機圖生成演算法應用非常廣泛，在NetworkX網路資料庫中也內置的相關演算法，我覺得做圖機器學習的童鞋很有必要了解下，
Erdos-Renyi隨機圖[4]以兩位著名的匈牙利數學家P.Erd?s和A. Rényi的名字命名的，是生成隨機無向圖最簡單和常用的方法，包括以下兩種緊密相關的變體：
-
\(G_{np}\): 擁有\(n\)個節點，且邊\((u, v)\)以獨立同分布的概率\(p\)產生的無向圖
-
\(G_{nm}\): 擁有\(n\)個節點，且其中\(m\)條邊按照均勻分布采樣生成的無向圖，
(八卦：最常被討論的\(G_{np}\)其實是Gilbert[5]提出的，不過由于P.Erd?s和A. Rényi提出的\(G_{nm}\)更早一些，后來就將兩種都統稱Erdos-Renyi隨機圖了)
1.2 生成方法
- \(G_{np}\)：按某個次序考慮\(\tbinom{n}{2}\)條可能邊中的每一條，然后以概率\(p\)獨立地往圖上添加每條邊，
- \(G_{nm}\): 均勻選取\(\tbinom{n}{2}\)條可能邊中的一條，并將其添加為圖的邊，然后再獨立且均勻隨機地選取剩余\(\tbinom{n}{2}-1\)可能邊中的一條，并將其添加到圖中，直到\(m\)邊為止（可以證明，雖然是無放回采樣，但是每次采樣是獨立的，任意一種\(m\)條邊的選擇結果是等概率的），
值得一提的是，在\(G_{np}\)中，一個有\(n\)個頂點的圖具有\(m\)條邊的概率滿足分布：
\[\tbinom{\tbinom{n}{2}}{m} p^m(1-p)^{\tbinom{n}{2}-m} \]該分布式二項分布，邊的期望數為\(\tbinom{n}{2}p\)，每個頂點度的期望為\((n-1)p\)，
1.3 兩種方法比較
-
兩者的相同點：節點數量都為\(n\)，且邊數量的期望為\(p\tbinom{n}{2}\)；
-
兩者的區別：\(G_{np}\)的可能邊數量在\(\tbinom{n}{2}p\)上下波動，而\(G_{nm}\)則恒定有\(m\)條邊，
2 \(G_{np}\)隨機圖
2.1 只用\(n\)和\(p\)夠嗎？
\(n\)和\(p\)并不能完全域定一個圖，我們發現即使給定\(n\)和\(p\)，圖也有許多實作形式，如當\(n=10, p=1/6\)時，就可能產生如下的圖：
2.2 \(G_{np}\)的圖屬性
接下來我們考慮給定\(n\)和\(p\)，圖\(G_{np}\)所可能擁有的不屬性，包括度分布\(p(k)\)、聚類系數\(C\)、連通分量、平均最短路徑長度\(\bar{h}\)等，
- 度分布
\(G_{np}\)的度分布是滿足二項分布的，我們設\(p(k)\)為任意節點度數的概率分布函式，當節點數\(n\)足夠大時，\(p(k)\)可視為對度為\(k\)的節點所占比例的近似，我們有：
\[p(k)=\left(\begin{array}{c} n-1 \\ k \end{array}\right) p^{k}(1-p)^{n-1-k}\quad (k=0, 1,..., n-1) \]其中\(\left(\begin{array}{c} n-1 \\ k \end{array}\right)\)表示從\(n-1\)個節點中選\(k\)個節點，\(p\)為邊產生的概率，該分布是二項分布，所以我們有以下均值和方差：
\[\begin{aligned} & \bar{k} =(n-1)p \\ & \sigma^2 = (n-1)p(1-p) \end{aligned} \]二項分布的離散分布影像如下圖所示：
當\(n\)足夠大時，二項分布可以用正態分布去近似，
- 聚類系數
我們設
\[C_{i}=\frac{e_{i}}{\tbinom{k_i}{2}} \]此處\(e_i\)為節點\(i\)鄰居之間的邊數，\(k_i\)為節點\(i\)的度，\(\tbinom{k_i}{2}\)為節點\(i\)的鄰居間可能存在的邊總數，由于\(G_{np}\)中邊都按照概率\(p\)獨立同分布，我們有
\[\mathrm{E}(e_i)= \tbinom{k_i}{2}p \]其中\(p\)為節點\(i\)的鄰居間兩兩結合的概率，\(\tbinom{k_i}{2}\)為節點\(i\)的鄰居間可能存在的邊總數，
我們進一步可推知聚類系數：
\[C =\mathrm{E}(C_i)= \frac{\mathrm{E}(e_i)}{\tbinom{k_i}{2}}=p=\frac{\bar{k}}{n-1} \approx \frac{\bar{k}}{n} \]- 連通分量
圖\(G_{np}\)的圖結構會隨著\(p\)變化，如下圖所示：
觀察可知其中當巨大連通分量（gaint connected component）出現時，\(p = 1/(n-1)\)，此時平均度\(\bar{k} = (n-1)p=1\)，
平均度\(k=1-\varepsilon\)(即小于1)時，所有的連通分量大小為\(\Omega(\log n)\)；
平均度\(k = 1 + \varepsilon\)（即高于1）時，存在一個連通分量大小為\(\Omega(n)\)，其它的大小為\(\Omega(\log n)\)，且每個節點在期望值上至少有一條邊，
如下圖所示為\(G_{np}\)中，\(n=100000\)，\(\bar{k}=(n-1)p=0.5,..., 3\) 時的模擬實驗影像：
根據模擬實驗，在\(G_{np}\)中，平均度大于1時，巨大連通分量恰好出現，
- 平均最短路徑長度
Erdos-Renyi隨機圖即使擴展到很大，仍然可以保證節點之間只有幾跳(hops)的距離，如下所示為圖的平均最短路徑長度\(\bar{h}\)隨節點數量變化的關系圖：
可以看到平均最短路徑長度\(\bar{h}\)隨著節點數量\(n\)增長并滿足\(O(\log n)\)的增長階，
2.3 真實網路和\(G_{np}\)的對比
相似點： 存在大的連通分量，平均最短路徑長度
不同點： 聚類系數，度分布
在實際應用中，隨機圖模型可能有以下問題：
- 度分布可能和真實網路不同，畢竟真實網路不是隨機的，
- 真實網路中巨大連通分量的出現可能不具有規律性，
- 可能不存在區域的聚類結構，以致聚類系數太小，
3 代碼庫
NetworkX中內置了Erdos-Renyi隨機圖的生成函式，包括\(G_{np}\)和\(G_{nm}\)，就是需要注意\(G_{np}\)的API[6]是
erdos_renyi_graph(n, p, seed=None, directed=False)
該API與nx.binomial_graph 、nx.gnp_random_graph作用是相同的，
而\(G_{nm}\)的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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/472285.html
標籤：其他
上一篇：手動驗證 TLS 證書
下一篇：計算機語言發展史（簡單帶過）