小世界現象與直徑（the small-world phenomenon and the diameter）

小世界現象是被戲稱為「六度分隔」的經驗事實：在大型真實網路中，任兩個節點都被一條出奇短的路徑連接。隨機圖理論透過直徑（任兩頂點間最短路徑距離的最大值）與典型距離（兩個隨機頂點之間的距離）將之精確化。頭條發現是：隨機圖是小世界——距離僅隨頂點數對數增長。它回答的問題是：在一張每個節點只有寥寥數條邊的圖中，頂點之間相隔幾「跳」？

理由還是分支啟發。在 G(n,p) 且 np = c > 1 時，距某固定頂點距離 r 以內的頂點數約以 c^r 增長（每一步把前緣乘上平均度數），故要觸及 n 個頂點的一個常數比例，需要約 r = log n / log c 步。嚴格化後，這給出超臨界稀疏區間中典型距離與直徑皆為 (log n)/(log(np)) 階——對固定平均度數，直徑是 Theta(log n)。對度數的依賴是關鍵轉折：距離標度為 (log n)/(log d)，其中 d 是平均度數，故越稠密的圖是越小的世界。對重尾度數的網路效果更極端：在冪律指數 gamma 介於 2 與 3 的組態模型或優先連接圖中，典型距離僅為 log log n 階——「超小世界」——因為樞紐作為捷徑，幾乎人人離它一兩步之遙。在稠密區間 p 固定時，直徑塌縮為 2（whp 任兩頂點有共同鄰居）。

此現象之所以重要，是因為它支撐著資訊、謠言與傳染病擴散的速度、點對點與路由網路的效率，以及米爾格蘭著名的實驗。值得明說的誠實微妙處有幾點。其一，「小直徑」與「高效導航」不同：Kleinberg 證明一張圖可有對數直徑，卻無法僅憑局部資訊路由，除非長程連結恰有正確的（二維中為反平方）距離分布——短路徑存在不等於它們找得到。其二，對數直徑的結果需要圖（基本上）連通且超臨界；在巨人門檻以下沒有整體直徑的概念。其三，超小的 log log n 標度是重尾的真正後果，而非小世界性質本身，且一旦 gamma 超過 3 便消失（屆時又回到 log n）。