Spectral Clustering & Community Detection

Graph nodes clustered using eigenvectors of the graph Laplacian. The Fiedler vector (2nd eigenvector) reveals the natural community split.

Nodes: 40 Communities: 3 Modularity: — Cut edges: —
Nodes: 40
Communities k: 3
Intra-density: 0.5
Inter-density: 0.05

Spectral Clustering via Graph Laplacian

The graph Laplacian L = D − A (degree matrix minus adjacency matrix) encodes graph connectivity. Its eigenvectors reveal structure: the smallest eigenvalue (λ₁=0) is trivial; the second (Fiedler value λ₂) measures connectivity. The k eigenvectors corresponding to the k smallest eigenvalues form a k-dimensional embedding of nodes. K-means in this spectral space finds communities that minimize the normalized cut. Nodes with similar spectral coordinates have similar connectivity patterns — they end up in the same cluster.