厄多斯-雷尼隨機圖（Erdos-Renyi random graph）
/ AIR-dosh REN-yee /
厄多斯-雷尼隨機圖是整個領域的奠基物件：一張在 n 個有標號頂點上、純由機運生成的圖。有兩個密切相關的版本。在 G(n,p) 中，每一條可能的邊（共 C(n,2) 條）各自獨立地以機率 p 被納入，因此整張圖是一連串獨立投擲銅板的乘積。在 G(n,m) 中，則從所有恰有 m 條邊的圖中均勻隨機選一張。此模型回答的問題是：一張「典型」的大圖長什麼樣，而它的整體特徵（連通嗎？含三角形嗎？最大團塊多大？）又如何依賴它有多稠密？
此模型的威力在於：幾乎每個有趣的性質隨 n 增長都服從零一律——對某類固定的問題，G(n,p) 具有該性質的機率會趨於 0 或 1，而切換發生在 p 越過某門檻之時。當 m 約等於 p 乘以 C(n,2) 時，兩個模型基本上可互換：G(n,m) 就是對邊數取條件後的 G(n,p)，而由於邊數高度集中（它是獨立指示變數之和，期望為 p C(n,2)），任何合理性質的結果都可在兩者間轉移。自然的尺度是把 p = p(n) 寫成 n 的函數；p = c/n（平均度數為常數 c）這個區間是劇烈結構相變所在之處，而 p = (log n)/n 則是連通性的尺度。「高機率」（whp）一詞意指機率隨 n 趨於無窮而趨於 1，本領域幾乎所有定理都是 whp 敘述。
厄多斯與雷尼於 1959 至 1960 年引入此模型，發現隨機圖並非無定形，而是隨著邊的加入經歷一系列界線分明的階段——巨大連通分量的誕生、孤立頂點的被吞沒、連通性的開始——每一個都發生在各自的門檻處。這正是此模型遠超組合學意義的原因：它是真實網路的虛無模型（null model）、機率方法的試驗場，也是能徒手證明相變的最簡單場景。一個誠實的提醒：真實世界的網路幾乎從不被 G(n,p) 良好描述——它們的度數分布是重尾的、有大量三角形與社群結構——因此 G(n,p) 最好被視為基準與技術來源，而非寫實模型，這也正是後來發展出組態模型、優先連接與區塊模型的原因。
取 n = 1000、p = 0.5/n = 0.0005，故平均度數約為 0.5（次臨界）。whp 最大的連通片只有約 O(log n) 個頂點——寥寥數個——整張圖是一堆細小、樹狀的小團。現把 p 提到 2/n：平均度數為 2（超臨界），而 whp 會出現單一巨大連通分量，含全部 1000 個頂點中的一個常數比例，使其餘每一片都相形見絀。
把邊密度加倍越過平均度數 1，整張圖就從塵埃翻轉為巨人：相變的一張數值圖像。
G(n,p) 與 G(n,m) 近乎等價（靠邊數的集中性），但並不全同：例如某個機率恰好繫於邊數為偶的性質就能區分二者。對單調性質而言它們可互換。