Graph partitioning using the algebraic connectivity eigenvector
Graph colored by cluster
Fiedler vector components
λ₂ = — | Cut ratio = — | Accuracy = —
The normalized graph Laplacian L = D⁻¹/²(D−A)D⁻¹/² has eigenvalues 0 = λ₁ ≤ λ₂ ≤ … ≤ λ_n.
The Fiedler value λ₂ = algebraic connectivity measures how well-connected the graph is.
The Fiedler vector v₂ (corresponding eigenvector) encodes the optimal graph bisection:
partition by sign of v₂(i). For k clusters, use k smallest non-zero eigenvectors (k-means on eigenvectors).
Computed via power iteration on the deflated Laplacian.