隨機圖的度數分布（the degree distribution of a random graph）

一個頂點的度數是與它相接的邊數，而度數分布是度數在圖中如何散布。它是網路局部結構最首要、最基本的描述子，也是真實世界網路與厄多斯-雷尼模型最大聲不合的單一統計量。它回答的問題是：在隨機圖中，一個典型頂點有多少鄰居，而度數又變化多大？

在 G(n,p) 中，固定頂點的度數是 n-1 個獨立指示變數之和，故它恰服從 Binomial(n-1, p)。在稀疏區間 p = lambda/n（lambda 固定）下，此二項收斂（小數律）到 Poisson(lambda) 分配：度數為 k 的頂點比例趨於 e^(-lambda) lambda^k / k!。經驗度數分布——所有 n 個頂點度數的直方圖——whp 集中於此卜瓦松律（相異頂點的度數只弱相依，第二動差／集中論證可控制直方圖）。卜瓦松的關鍵質性特徵是它輕尾：度數為 k 的機率超指數衰減（快於任何冪），故本質上沒有高度數的「樞紐」頂點，稀疏 G(n,p) 中的最大度數僅約 (log n)/(log log n)。平均度數為 (n-1)p、變異數為 (n-1)p(1-p)，而在稀疏極限中二者皆等於 lambda——均值等於變異數，卜瓦松的指紋。

度數分布之所以重要，是因為它是局部結構理論（分支啟發、組態模型、Benjamini-Schramm 極限）所建立的輸入，也因為它正是厄多斯-雷尼與現實分道揚鑣之處。多數觀測到的網路——網頁、引用圖、蛋白質交互作用、社交網路——具有重尾、常為冪律的度數分布 P(度數 = k) 正比於 k^(-gamma)，帶有少數度數極高的樞紐，而卜瓦松基本上絕不會產生。這單一的經驗失敗正是組態模型（容你規定任意度數序列）、Chung-Lu 與優先連接被發明的原因。誠實的提醒：冪律尾與卜瓦松尾是天差地別的物件——卜瓦松所有動差皆有限且最大值高度集中，而 gamma <= 3 的冪律變異數為無窮，故二模型在穩健性、傳染病與譜性質上行為截然不同。