為什麼六度分隔不是巧合？從圖的直徑到譜的祕密

為什麼六度分隔不是巧合？從圖的「直徑」到譜的祕密

你或許還記得入門篇裡的一句話：圖（graph）是「點與邊」的世界。但讓我們從一個更尖銳的問題出發：為什麼全世界八十億人，任意兩人之間平均只隔著大約六層關係？這不是社會學家的浪漫修辭，而是一個關於圖結構的硬數學現象。一個擁有 $N$ 個節點、每個節點只連著少數鄰居的網路，憑什麼能讓任意兩點的最短路徑長度（也就是圖的直徑 diameter）小到只有 $O(\log N)$？

要回答這個問題，我們必須超越「點連著邊」的直觀，走進三個更深的工具：鄰接矩陣（adjacency matrix）的代數結構、圖的譜（spectrum），以及隨機圖（random graph）的相變（phase transition）。這篇文章假設你已經知道什麼是路徑、連通、度（degree），我們直接進入機制。

鄰接矩陣：把圖變成線性代數

進階圖論的第一個關鍵轉折，是意識到一張圖完全可以被一個矩陣編碼。對一張有 $n$ 個頂點的圖 $G$，定義它的鄰接矩陣 $A$ 為 $n \times n$ 的矩陣，其中

$$ A_{ij} = \begin{cases} 1, & \text{若頂點 } i \text{ 與 } j \text{ 之間有邊} \\ 0, & \text{否則} \end{cases} $$

對無向圖（undirected graph），$A$ 是對稱的，也就是 $A = A^{\top}$。這個對稱性看似平凡，卻是後面所有「譜方法」能成立的根基——因為實對稱矩陣保證有實數特徵值與正交的特徵向量。

矩陣編碼最美的地方，在於矩陣乘法直接對應到「走幾步」這件事。考慮 $A^2$ 的某個元素：

$$ (A^2)_{ij} = \sum_{k=1}^{n} A_{ik} A_{kj} $$

每一項 $A_{ik}A_{kj}$ 只有在「$i$ 連到 $k$」且「$k$ 連到 $j$」時才等於 $1$。所以 $(A^2)_{ij}$ 正好是從 $i$ 經過恰好兩步走到 $j$ 的路徑（walk）數目。推廣到一般：

$$ (A^m)_{ij} = \text{從 } i \text{ 到 } j \text{ 恰好 } m \text{ 步的途徑數} $$

這個結果立刻給了我們一個計算直徑的演算法雛形：圖的直徑就是「最小的 $m$，使得對所有 $i,j$，$(I + A + A^2 + \cdots + A^m)_{ij} > 0$」。換句話說，直徑的問題被翻譯成了矩陣冪次的問題。

看一個例子

我們取一個五頂點的環（cycle）$C_5$，頂點依序為 $1,2,3,4,5$，相鄰者連邊（含 $5$ 連回 $1$）。它的鄰接矩陣是

$$ A = \begin{pmatrix} 0&1&0&0&1\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 1&0&0&1&0 \end{pmatrix} $$

我們來算 $(A^2)_{13}$，也就是從頂點 $1$ 走兩步到頂點 $3$ 的途徑數。把第一列 $(0,1,0,0,1)$ 與第三行（即第三列，因對稱）$(0,1,0,1,0)$ 做內積：

$$ (A^2)_{13} = 0\cdot0 + 1\cdot1 + 0\cdot0 + 0\cdot1 + 1\cdot0 = 1 $$

確實如此：$1 \to 2 \to 3$ 是唯一的兩步途徑。再看 $(A^2)_{11}$（從 $1$ 出發兩步回到 $1$）：

$$ (A^2)_{11} = 0+1+0+0+1 = 2 $$

對應 $1\to2\to1$ 與 $1\to5\to1$ 兩條，這也正好等於頂點 $1$ 的度數 $\deg(1)=2$——一個普遍事實是 $(A^2)_{ii} = \deg(i)$，因為任何「出去一步再原路回來」都對應一個鄰居。

圖的譜：特徵值會說話

既然 $A$ 是實對稱矩陣，它有 $n$ 個實特徵值，習慣由大到小排列：

$$ \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n $$

這組數字稱為圖的譜（spectrum）。譜論（spectral graph theory）的核心信念是：圖的全域結構性質，被編碼在這些特徵值裡。 這聽起來很抽象，所以讓我們看幾個具體而有力的對應。

最大特徵值 $\lambda_1$ 與連通性。 由 Perron–Frobenius 定理，對連通圖，$\lambda_1$ 是單根（重數為 $1$），且對應的特徵向量可取為全正。$\lambda_1$ 夾在平均度與最大度之間：

$$ \bar{d} \leq \lambda_1 \leq \Delta $$

其中 $\bar{d}$ 是平均度、$\Delta$ 是最大度。對 $d$-正則圖（每個頂點度都是 $d$），全 $1$ 向量 $\mathbf{1}$ 滿足 $A\mathbf{1} = d\mathbf{1}$，所以 $\lambda_1 = d$ 恰好就是度數。

第二特徵值 $\lambda_2$ 與「擴展性」。 這是整個理論最深刻的一環。$\lambda_1$ 與 $\lambda_2$ 之間的差距 $\lambda_1 - \lambda_2$，稱為譜隙（spectral gap），它衡量這張圖有多「擴展（expanding）」——也就是隨機漫步在上面混合（mixing）得多快、訊息散播得多有效率。譜隙越大，圖越像一個「沒有瓶頸」的良好連通網路。社群網路之所以呈現六度分隔，正是因為它具有相當大的譜隙。

動手試試：用拉普拉斯算譜隙

實務上更常用的不是 $A$ 本身，而是圖拉普拉斯矩陣（graph Laplacian）：

$$ L = D - A $$

其中 $D$ 是對角度矩陣，$D_{ii} = \deg(i)$。$L$ 有幾個漂亮性質：它是半正定的（所有特徵值 $\geq 0$），最小特徵值恆為 $0$（特徵向量是全 $1$ 向量），而且——這是經典的 Fiedler 定理——

$L$ 的特徵值 $0$ 的重數，恰好等於圖的連通分量（connected component）個數。

我們驗證一下。取一個「啞鈴圖」：兩個三角形 $\{1,2,3\}$ 與 $\{4,5,6\}$，各自內部三邊全連，再用一條邊 $3\!-\!4$ 把兩團接起來。直覺上這張圖「幾乎」是兩塊，中間只靠一根橋。它的拉普拉斯第二小特徵值 $\lambda_{n-1}(L)$（稱為代數連通度 algebraic connectivity 或 Fiedler 值）會很接近 $0$，反映那個瓶頸。如果我們把橋拿掉，圖斷成兩塊，第二小特徵值就剛好掉到 $0$——因為連通分量從 $1$ 變成 $2$。

這提供了一個做圖分割（graph partitioning）的演算法：算出 Fiedler 向量（對應第二小特徵值的特徵向量），依其分量的正負號把頂點分成兩群，往往就能找到那條最弱的瓶頸切口。這就是譜分群（spectral clustering）的數學心臟，今天被廣泛用在社群偵測、影像分割與機器學習。

Cheeger 不等式：把「瓶頸」翻譯成「特徵值」

譜隙與連通結構的關係，可以被一條優美的不等式精確化。先定義圖的等周常數（Cheeger constant），又稱conductance。對一個頂點子集 $S$，令 $\partial S$ 為一端在 $S$、一端在外的邊集，則

$$ h(G) = \min_{S:\, 0 < |S| \leq n/2} \frac{|\partial S|}{|S|} $$

直觀上 $h(G)$ 越小，代表存在一個「切起來很省、但裡面點很多」的瓶頸——圖容易被截斷。對 $d$-正則圖，離散 Cheeger 不等式把這個純組合量夾在拉普拉斯第二小特徵值 $\lambda_2(L)$（這裡指非零的最小者）之間：

$$ \frac{\lambda_2(L)}{2} \leq h(G) \leq \sqrt{2\, d\, \lambda_2(L)} $$

這條不等式的威力在於：它把一個指數級難算的組合優化問題（找最佳瓶頸切口要試所有子集 $S$），夾在一個多項式時間可算的線性代數量之間。 想知道圖好不好切，不必窮舉 $2^n$ 個子集，算一個特徵值就有了上下界。這正是譜方法在演算法設計上不可取代的原因。

隨機圖：連通性是怎麼「突然發生」的

最後我們回到開頭的六度問題，引入 Erdős–Rényi 隨機圖模型 $G(n,p)$：取 $n$ 個頂點，每一對頂點獨立地以機率 $p$ 連邊。這個極簡模型藏著圖論最戲劇性的現象之一——相變（phase transition）。

Erdős 與 Rényi 在 1960 年證明：當 $n$ 很大、令 $p = \frac{c}{n}$ 時，圖的結構隨常數 $c$ 出現劇烈的門檻效應：

• 若 $c < 1$：圖幾乎必然碎裂成許多小分量，最大分量只有 $O(\log n)$ 個頂點。
• 若 $c > 1$：突然冒出一個包含正比例頂點的巨型分量（giant component）。
• $c = 1$ 是臨界點，最大分量約為 $O(n^{2/3})$。

也就是說，當每個節點平均連邊數從「略少於 $1$」跨過「略多於 $1$」的瞬間，網路從一盤散沙凝結成一個整體。這個 $c=1$ 的門檻，和水結冰、磁鐵磁化是同一類數學現象。

而連通性本身（不只是有巨型分量，而是全圖連成一塊）的門檻更高一點，落在 $p = \frac{\ln n}{n}$ 附近：當 $p = \frac{\ln n + c_n}{n}$ 時，若 $c_n \to +\infty$ 則圖幾乎必然連通，若 $c_n \to -\infty$ 則幾乎必然有孤立點。一旦連通且度數夠高，直徑就被壓到 $O\!\left(\frac{\ln n}{\ln(np)}\right)$ 的量級——這就是六度分隔的數學根源：只要每人平均認識的人數遠大於 $1$，最短路徑就以對數速度壓縮。

看一個例子：估計門檻

設一個社群有 $n = 10^6$ 人。連通門檻在 $p \approx \frac{\ln n}{n} = \frac{\ln 10^6}{10^6} \approx \frac{13.8}{10^6}$，對應每人平均度約 $np \approx 13.8$。也就是說，只要每人平均認識約 $14$ 人（在均勻隨機的理想模型下），百萬人網路就幾乎必然連成一塊。此時直徑約為

$$ \frac{\ln n}{\ln(np)} \approx \frac{13.8}{\ln 13.8} \approx \frac{13.8}{2.62} \approx 5.3 $$

驚人地接近那個傳說中的「六」。當然真實社群網路並非均勻隨機（有群聚、有 hub），但這個粗估抓住了核心機制：稀疏連結 + 對數直徑。

重點回顧

• 鄰接矩陣 $A$ 把圖代數化：$(A^m)_{ij}$ 等於從 $i$ 到 $j$ 的 $m$ 步途徑數，使「走幾步可達」變成矩陣冪次問題。
• 圖的譜（特徵值）編碼全域結構：最大特徵值關聯度與連通，譜隙 $\lambda_1 - \lambda_2$ 衡量擴展性與混合速度。
• 拉普拉斯 $L = D - A$ 的零特徵值重數＝連通分量數；第二小特徵值（Fiedler 值）是代數連通度，驅動譜分群。
• Cheeger 不等式把組合上難算的瓶頸常數 $h(G)$，夾在可多項式時間計算的特徵值之間。
• 隨機圖 $G(n,p)$ 在 $p = 1/n$ 出現巨型分量相變、在 $p = \ln n / n$ 跨過連通門檻；對數直徑正是六度分隔的根源。

深入探討（研究所視角）

若你想再往前推，幾條主線值得追：

Ramanujan 圖與最優擴展子（optimal expanders）。 對 $d$-正則圖，Alon–Boppana 定理給出第二大特徵值絕對值的下界：$\lambda \geq 2\sqrt{d-1} - o(1)$。達到這個下界（即所有非平凡特徵值滿足 $|\lambda_i| \leq 2\sqrt{d-1}$）的圖稱為 Ramanujan 圖，它們是「擴展性最強」的稀疏圖。Lubotzky–Phillips–Sarnak 用數論（模形式、Ramanujan 猜想）顯式構造了這類圖；而 Marcus–Spielman–Srivastava 在 2013 年用交錯多項式（interlacing polynomials）證明了任意度數的二部 Ramanujan 圖存在，這項工作也順帶解決了 Kadison–Singer 問題，是近十年組合學的里程碑。

混合時間與隨機漫步。 在圖上做隨機漫步，其分布收斂到平穩分布的速度由鬆弛時間（relaxation time） $\tau \approx \frac{1}{1 - \lambda_2}$ 控制（$\lambda_2$ 為轉移矩陣第二大特徵值）。這把譜隙、Cheeger 常數、混合時間三者綁在一起，是 Markov chain Monte Carlo（MCMC）取樣演算法收斂分析的理論基礎，也連結到 PageRank 這類網頁排序算法的數學。

圖同構與譜的不完備性。 一個自然問題是：譜能不能唯一決定一張圖？答案是不能——存在同譜非同構（cospectral non-isomorphic）圖，它們的特徵值完全相同卻不同構。這提醒我們譜是強大但有損的摘要。如何用更精細的不變量（如 Weisfeiler–Lehman 演算法、圖神經網路的表達力上界）區分圖，是當代理論機器學習與圖論交會的活躍前沿。

超圖與高階推廣。 真實世界的許多關係不是兩兩配對，而是多元同時發生（一篇論文多位作者、一場反應多種分子）。把邊推廣為含多個頂點的超邊（hyperedge），就得到超圖（hypergraph）。其譜論需要藉助張量（tensor）特徵值或拉普拉斯的非線性推廣，理論遠比矩陣情形複雜，也是拓撲資料分析（topological data analysis）與高階網路科學的核心工具。