Spectral Gap & Graph Laplacian

Graph Laplacian & Spectral Theory

The graph Laplacian L = D − A, where D is the degree matrix and A the adjacency matrix. Key spectral facts:

Lx = λx ↔ x^T L x = Σ_{(i,j)∈E} (x_i − x_j)²

Eigenvalues 0 = λ₀ ≤ λ₁ ≤ … ≤ λ_{n-1}. The number of zero eigenvalues equals the number of connected components. The algebraic connectivity λ₁ (Fiedler value) measures how well-connected the graph is. The Fiedler vector (eigenvector of λ₁) gives the optimal bisection partition used in spectral clustering.

The Cheeger inequality bounds the edge expansion h(G) (isoperimetric constant):

λ₁/2 ≤ h(G) ≤ √(2·λ_max·λ₁)

Node colors show the Fiedler vector components — positive/negative values naturally partition the graph into communities.