Spectral Clustering — Graph Laplacian & Fiedler Vector

Nodes: 30 Communities: 3 Intra-edge p: 0.5 Inter-edge p: 0.05 New Graph λ₂ (Fiedler): —

Spectral clustering: compute the graph Laplacian L=D−A, find the Fiedler vector (eigenvector of the 2nd smallest eigenvalue λ₂). Nodes with positive/negative Fiedler components form the two clusters. The spectral embedding in 2D (eigenvectors 2 & 3) naturally separates communities.