跳至內容

ER隨機圖

維基百科,自由的百科全書

圖論中,ER隨機圖(Erdős–Rényi random graph)是一種網絡,以概率p連接N個節點中的每一對節點。ER隨機圖以埃爾德什·帕爾阿爾弗雷德·雷尼英語Alfréd Rényi(Alfréd Rényi)的名字命名。他們在1959年發明了這種模型。[1][2]同年,Edward Gilbert獨立提出了另外一個模型。[3]

p = 0.01

在Erdős-Rényi模型中,在頂點集數目相同時,具有固定邊數的所有圖均具有同等的概率出現。在吉爾伯特(Gilbert)引入的模型中,每個邊都有固定的出現概率,並且獨立於其他邊的概率。這些模型可用於概率方法中,以證明滿足各種屬性的圖的存在,或者對幾乎所有圖具有屬性的含義提供嚴格的定義。

定義

[編輯]

ER隨機圖主要有兩種高度相關的模型。

  • G(n, M)模型中,確定的圖從具有n個頂點和M條邊的所有圖集合中等概率隨機選擇。例如,在G(3, 2)模型中,具有三個頂點和兩條邊的圖總共有3種,它們每一個都以1/3的概率出現在G(3, 2)中。當0 ≤ MN, G(n,M) 總共有種可能的確定圖,每種圖出現的概率是[4]
  • G(n, p)模型中,通過隨機連接n個獨立節點構造一個圖,每條邊出現的概率是p,且不同邊存在與否互相獨立。對於具有n個頂點和M條邊的圖,其出現的概率是。由此,p越大,G中出現邊較多的圖的概率會上升。

通常在頂點數n趨向於無窮大時研究隨機圖的性質和變化行為。儘管pM可以為固定值,但它們也可以依賴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(這意味着,若AB的子圖,並且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(np)變化行為。這些結果包括:

  • np < 1,那麼G(np)中的圖幾乎一定沒有大小大於O(log(n))的連通分支
  • np = 1,那麼G(np)中的圖幾乎一定存在一個最大的連通分支,其大小約為n2/3
  • npc > 1,c為常數,那麼G(np)中的一個圖幾乎必有唯一的包含結點有限部分的巨型連通分支,其他連通分支不會包含超過O(log(n))個頂點。
  • ,那麼G(n, p)中的一個圖幾乎必有孤立點,因此這個圖是不連通的。
  • ,那麼G(n, p)幾乎一定連通。

因此是一個鋒利閾值。

隨着n趨於無窮大,G(n,p)可以幾乎精確地描述圖的其他屬性。

滲流理論

[編輯]

完全圖上的滲流理論是ER隨機圖,這也是一種平均場論[1][2][6][7]

參考文獻

[編輯]
  1. ^ 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. ^ 2.0 2.1 Bollobás, B. Random Graphs 2nd. Cambridge University Press. 2001. ISBN 0-521-79722-5. 
  3. ^ 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) (英語). 
  4. ^ Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
  5. ^ 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. ^ 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
  7. ^ 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 (英語).