隨機正則圖與隨機幾何圖（random regular and random geometric graphs）

這兩個模型位於隨機圖光譜的兩端，與厄多斯-雷尼互補。隨機 d-正則圖是每個頂點度數恰為 d 的均勻隨機圖——可能最齊次的度數序列，一個完全沒有度數漲落的模型。隨機幾何圖（RGG）則相反：頂點是隨機散布於空間的點（譬如單位方形中 n 個均勻點，或某區域中 n 個卜瓦松點），兩點只要落在固定距離 r 之內便相連——一個內建幾何、有強烈局部聚類的模型。它們回答的問題是：當我們移除度數隨機性（正則）或加入真實幾何（幾何）時，隨機圖現象會如何？

固定 d >= 3 的隨機 d-正則圖最好以條件於簡單的組態模型（所有度數皆為 d 的配對模型）生成與分析，它均勻且為簡單的機率遠離 0。對 d >= 3 它 whp 連通、甚至 d-連通，它是極佳的擴張子（其鄰接矩陣第二大特徵值接近拉馬努金界 2 sqrt(d-1)，由 Friedman 定理），它的直徑為 (log n)/(log(d-1)) 階，而其局部極限是無限 d-正則樹——故它本質上是正則樹的一塊有限、連通、擴張的部分。它沒有巨大連通分量相變（對每個固定 d >= 3 都連通）且少有短圈。隨機幾何圖受其維度與半徑支配：在 D 維、n 個點、連接半徑 r 下，平均度數約為 n 乘以半徑 r 球的體積，而連通門檻（Penrose）同樣與孤立點的消失重合，發生在使 n r^D 乘以球體積常數約為 log n 的 r。關鍵是 RGG 高度聚類——一個頂點的兩個鄰居彼此也接近、因而很可能相連——故不同於厄多斯-雷尼，它有大量三角形且不是局部樹狀的。

隨機正則圖之所以重要，是作為典範的稀疏擴張子——是編碼理論、去隨機化與馬可夫鏈快速混合理論的核心——以及作為連通性（contiguity，d-正則圖的不同構造「相通」，意指 whp 事件重合）最乾淨的測試。隨機幾何圖在凡空間為真之處都重要：無線臨機與感測器網路、空間傳染病與聚類。要保持的誠實：這兩個模型恰在要緊處與厄多斯-雷尼行為迥異。RGG 的高聚類與依維度而定的行為意味其連通性、滲流與譜性質由幾何、而非平均場分支啟發支配；且其滲流相變是連續體滲流問題，臨界密度非顯式、依維度而定。隨機正則圖反之則全無度數異質性，故即使是絕佳的數學物件，卻是真實網路的拙劣模型。