ER隨機圖

提示：此條目頁的主題不是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 ≤ M ≤ N, G(n,M) 總共有${\displaystyle {\tbinom {N}{M}}}$種可能的確定圖，每種圖出現的概率是${\displaystyle 1/{\tbinom {N}{M}}}$^[4]。
• 在G(n, p)模型中，通過隨機連接n個獨立節點構造一個圖，每條邊出現的概率是p，且不同邊存在與否互相獨立。對於具有n個頂點和M條邊的圖，其出現的概率是${\displaystyle p^{M}(1-p)^{{n \choose 2}-M}}$。由此，p越大，G中出現邊較多的圖的概率會上升。

通常在頂點數n趨向於無窮大時研究隨機圖的性質和變化行為。儘管p或M可以為固定值，但它們也可以依賴n的取值。例如，G(n, 2ln(n)/n)中的每個圖幾乎都是連通圖；隨着n趨於無窮大，G(n, 2ln(n)/n)中幾乎每個圖都被連接。

兩種模型的比較

G(n, p)的邊數期望值為${\displaystyle {\tbinom {n}{2}}p}$，因此根據大數定理，幾乎所有G(n, p)模型中的圖的邊數都會有${\displaystyle {\tbinom {n}{2}}p}$個。因此，一個粗略的想法是，如果pn² → ∞，並且${\displaystyle M={\tbinom {n}{2}}p}$，那麼隨着n的增大，G(n,p)的變化行為應該與G(n, M)類似。

在pn² → ∞假設的基礎上，我們考慮一個圖的單調性質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)中的圖邊數的平均值是${\displaystyle {\tbinom {n}{2}}p}$。任何特定頂點的度服從於二項分佈：^[5]

${\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

其中n是圖中頂點的數目。因為

${\displaystyle P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\text{ as }}n\to \infty {\text{ and }}np={\text{constant}},}$

此分佈為泊松分佈對於較大的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)中的圖幾乎一定存在一個最大的連通分支，其大小約為n^2/3。
• 若np → c > 1，c為常數，那麼G(n, p)中的一個圖幾乎必有唯一的包含結點有限部分的巨型連通分支，其他連通分支不會包含超過O(log(n))個頂點。
• 若${\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}$，那麼G(n, p)中的一個圖幾乎必有孤立點，因此這個圖是不連通的。
• 若${\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}$，那麼G(n, p)幾乎一定連通。

因此${\displaystyle {\tfrac {\ln n}{n}}}$是一個鋒利閾值。

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

滲流理論

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

參考文獻

1. Erdős, P.; Rényi, A. On Random Graphs. I (PDF). Publicationes Mathematicae. 1959, 6: 290–297. （原始內容存檔 (PDF)於2020-08-07）.
2. 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. 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 ${\displaystyle N(n)={\tbinom {n}{2}}p}$
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 （英語）.