ER隨機圖
在圖論中,ER隨機圖(Erdős–Rényi random graph)是一種網絡,以概率p連接N個節點中的每一對節點。ER隨機圖以埃爾德什·帕爾和阿爾弗雷德·雷尼(Alfréd Rényi)的名字命名。他們在1959年發明了這種模型。[1][2]同年,Edward Gilbert獨立提出了另外一個模型。[3]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/13/Erdos_generated_network-p0.01.jpg/220px-Erdos_generated_network-p0.01.jpg)
在Erdős-Rényi模型中,在頂點集數目相同時,具有固定邊數的所有圖均具有同等的概率出現。在吉爾伯特(Gilbert)引入的模型中,每個邊都有固定的出現概率,並且獨立於其他邊的概率。這些模型可用於概率方法中,以證明滿足各種屬性的圖的存在,或者對幾乎所有圖具有屬性的含義提供嚴格的定義。
定義
[編輯]ER隨機圖主要有兩種高度相關的模型。
- 在G(n, M)模型中,確定的圖從具有n個頂點和M條邊的所有圖集合中等概率隨機選擇。例如,在G(3, 2)模型中,具有三個頂點和兩條邊的圖總共有3種,它們每一個都以1/3的概率出現在G(3, 2)中。當0 ≤ M ≤ N, G(n,M) 總共有種可能的確定圖,每種圖出現的概率是[4]。
- 在G(n, p)模型中,通過隨機連接n個獨立節點構造一個圖,每條邊出現的概率是p,且不同邊存在與否互相獨立。對於具有n個頂點和M條邊的圖,其出現的概率是。由此,p越大,G中出現邊較多的圖的概率會上升。
通常在頂點數n趨向於無窮大時研究隨機圖的性質和變化行為。儘管p或M可以為固定值,但它們也可以依賴n的取值。例如,G(n, 2ln(n)/n)中的每個圖幾乎都是連通圖;隨著n趨於無窮大,G(n, 2ln(n)/n)中幾乎每個圖都被連接。
兩種模型的比較
[編輯]G(n, p)的邊數期望值為,因此根據大數定理,幾乎所有G(n, p)模型中的圖的邊數都會有個。因此,一個粗略的想法是,如果pn2 → ∞,並且,那麼隨著n的增大,G(n,p)的變化行為應該與G(n, M)類似。
在pn2 → ∞假設的基礎上,我們考慮一個圖的單調性質P(這意味著,若A是B的子圖,並且A擁有性質P,那麼B也將擁有性質P);那麼「P對於幾乎所有G(n, p)成立」等價於「P對於幾乎所有G(n, M)成立」。但對於非單調的性質P,表述的等價性不一定成立。
事實上,G(n, p)模型是當今最常用的模型,部分原因是邊存在的獨立性簡化了許多分析。
G(n,p)的性質
[編輯]使用上面的符號,G(n, p)中的圖邊數的平均值是。任何特定頂點的度服從於二項分布:[5]
其中n是圖中頂點的數目。因為
此分布為泊松分布對於較大的n和常數np。
在1960年的論文中,Erdős和Rényi[6]對於不同的p精準地描述了G(n, p)變化行為。這些結果包括:
- 若np < 1,那麼G(n, p)中的圖幾乎一定沒有大小大於O(log(n))的連通分支。
- 若np = 1,那麼G(n, p)中的圖幾乎一定存在一個最大的連通分支,其大小約為n2/3。
- 若np → c > 1,c為常數,那麼G(n, p)中的一個圖幾乎必有唯一的包含結點有限部分的巨型連通分支,其他連通分支不會包含超過O(log(n))個頂點。
- 若,那麼G(n, p)中的一個圖幾乎必有孤立點,因此這個圖是不連通的。
- 若,那麼G(n, p)幾乎一定連通。
因此是一個鋒利閾值。
隨著n趨於無窮大,G(n,p)可以幾乎精確地描述圖的其他屬性。
滲流理論
[編輯]完全圖上的滲流理論是ER隨機圖,這也是一種平均場論。[1][2][6][7]
參考文獻
[編輯]- ^ 1.0 1.1 Erdős, P.; Rényi, A. On Random Graphs. I (PDF). Publicationes Mathematicae. 1959, 6: 290–297. (原始內容存檔 (PDF)於2020-08-07).
- ^ 2.0 2.1 Bollobás, B. Random Graphs 2nd. Cambridge University Press. 2001. ISBN 0-521-79722-5.
- ^ Gilbert, E. N. Random Graphs. The Annals of Mathematical Statistics. 1959-12, 30 (4): 1141–1144 [2020-02-10]. ISSN 0003-4851. doi:10.1214/aoms/1177706098. (原始內容存檔於2020-05-09) (英語).
- ^ Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
- ^ Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. Random graphs with arbitrary degree distributions and their applications [任意度分佈的隨機圖及其應用]. Physical Review E. 2001, 64: 026118. Bibcode:2001PhRvE..64b6118N. PMID 11497662. arXiv:cond-mat/0007235
. doi:10.1103/PhysRevE.64.026118 (英語)., Eq. (1)
- ^ 6.0 6.1 Erdős, P.; Rényi, A. On the evolution of random graphs [論隨機圖的演化] (PDF). Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. 1960, 5: 17–61 [2020-12-19]. (原始內容存檔 (PDF)於2021-02-01) (英語). The probability p used here refers there to
- ^ Bollobas, B.; Erdős, P. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society. 1976-11, 80 (3): 419–427. ISSN 0305-0041. doi:10.1017/S0305004100053056 (英語).