Spectral Graph Clustering via Fiedler Vector

The graph Laplacian L=D−A has a Fiedler vector (2nd smallest eigenvector, λ₂>0 iff connected). Its sign partitions nodes optimally — the algebraic connectivity λ₂ measures how well-connected the graph is.

Graph (colored by partition)

Fiedler Vector v₂

Laplacian Eigenvalue Spectrum

Nodes N

Intra-cluster p

Inter-cluster q

K clusters

λ₂ = — | Cut size: —