Spectral Clustering via Graph Laplacian

The Fiedler vector (2nd eigenvector of the graph Laplacian L=D-A) bipartitions a graph by sign. Nodes colored by partition; cut quality vs random baseline shown. Algebraic connectivity λ₂ measures graph cohesion.

λ₂ = — | Cut = — | Random cut = — | Ratio = —