描述一张图的两个矩阵
给 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 个簇。