Spectral clustering finds groups that ordinary distance-based clustering (k-means) cannot, because it clusters by connectivity on a graph instead of by straight-line distance in the original space.
1. Similarity: W_ij = exp(-‖xi - xj‖² / 2σ²) kept only for each
point's k nearest neighbours (sparse graph)
2. Degree: D_ii = Σ_j W_ij
3. Laplacian: L = D - W (unnormalized graph Laplacian)
4. Eigen: L v_m = λ_m v_m , 0 = λ₁ ≤ λ₂ ≤ … ≤ λ_K
5. Embedding: each point i → (v₂(i), v₃(i), …, v_K(i)) ∈ R^(K-1)
6. Cluster: run k-means on that low-dimensional spectral embedding
Step 4 is the whole trick: this simulator diagonalises the live Laplacian with the classic cyclic Jacobi eigenvalue algorithm (repeated Givens rotations that zero the largest off-diagonal entry each sweep) — no external linear-algebra library, computed from scratch every time you press Run. The second-smallest eigenvalue λ₂ is the Fiedler value: it measures how weakly connected the graph is (near 0 means the graph is almost split into K disconnected pieces already, which is exactly when spectral clustering shines).
- Shape — moons and rings are non-convex: their clusters wrap around each other, so a Euclidean centroid (plain k-means) cuts straight through them. Blobs are convex, so both methods agree.
- σ (bandwidth) — controls how fast similarity decays with distance in the Gaussian kernel; too large and the whole graph blurs into one component, too small and it fragments.
- k-NN — each point keeps an edge only to its k closest neighbours, which is what lets the graph "unroll" curved clusters instead of connecting every pair of points.
- Show plain k-means — runs ordinary k-means directly on the 2D coordinates for comparison; watch it fail on moons/rings while the spectral result on the left succeeds.
Real-world use: spectral clustering is standard for image segmentation, community detection in social/citation graphs, and any dataset where "close" means "reachable through a chain of similar neighbours" rather than "nearby in a straight line".