描述一張圖的兩個矩陣
給 n 個節點編號。鄰接矩陣 A 在 i 與 j 相連時取 A[i,j] = 1（或邊權）。度矩陣 D 是對角陣，對角元是每個節點的總連接權重。圖拉普拉斯矩陣是 L = D - A。它看似樸素，但圖的幾何就藏在它的譜裡。
譜直接讀出連通性
由於 x^T L x 是平方和，L 是對稱半正定的，所以由譜定理其特徵值都是非負實數：0 = lambda_1 <= lambda_2 <= ... <= lambda_n。全 1 向量讓每條邊上的 x_i - x_j = 0，所以 lambda_1 = 0 總成立。一個漂亮的定理：零特徵值的個數等於連通分量的個數。
因此若圖是一整塊，lambda_2 就是第一個非零特徵值。它的大小就是代數連通度：很小意味著圖幾乎是被一座細橋連起來的兩塊。它對應的特徵向量——Fiedler 向量——正指向那座橋的兩側。
用 Fiedler 向量切割圖
在保持 x 與全 1 向量正交且單位長度的前提下最小化 x^T L x，恰好是一個瑞利商問題，其解就是 Fiedler 向量。直觀上它給每個節點一個數，使相連的節點拿到相近的數——而最便宜的非常數分配方案正好沿著薄弱接縫把圖劈開。按它的符號取閾值，你就得到兩個簇。
# Two triangles joined by a single edge 3--4
# nodes 1,2,3 fully connected ; 4,5,6 fully connected ; edge 3-4
# Laplacian eigenvalues come out like:
# 0, 0.something (small!), 3, 3, 3, ...
# Fiedler vector v2 (the small one) looks like:
# node: 1 2 3 4 5 6
# v2 : -.4 -.4 -.3 +.3 +.4 +.4
# sign split: {1,2,3} | {4,5,6} <- the obvious two communities譜聚類：不止兩個組
- 構造拉普拉斯矩陣 L（常用歸一化版本 D^{-1/2} L D^{-1/2}）。
- 取最小的 k 個特徵值對應的特徵向量，按行堆成一個 n×k 矩陣。
- 現在每個節點成了 R^k 中的一個點；對這些點跑 k-means 得到 k 個簇。