Spectral Clustering — Normalized Graph Laplacian

Graph partitioning via eigenvectors of the normalized Laplacian L = D⁻¹/²(D−A)D⁻¹/² — Fiedler vector reveals community structure.

Spectral clustering (Shi-Malik 2000, Ng-Jordan-Weiss 2002): construct similarity graph, compute normalized Laplacian, embed nodes in space of k smallest eigenvectors, run k-means. Works for non-convex clusters where k-means fails. The Fiedler value λ₂ = 0 iff graph is disconnected; small λ₂ indicates easy-to-cut bottleneck.