Algebraic Graph Theory: Spectra and Laplacians

Algebraic graph theory translates combinatorial questions about graph structure into linear algebra. Eigenvalues of the adjacency matrix encode connectivity, coloring, and random walks.

• **PageRank (Google):** the ranking algorithm is based on the spectrum of the transition matrix; the second eigenvalue determines convergence speed
• **Image segmentation:** Shi-Malik spectral clustering uses the Fiedler vector of the Laplacian
• **Cryptographic expanders:** graphs with small lambda_2 are used for hash functions and error-correcting codes

Предварительные знания

• Generating Functions

Adjacency Matrix and Graph Spectrum

Google PageRank processes a graph of 1.9 trillion pages using spectral properties of the adjacency matrix. The second-largest eigenvalue determines the convergence rate of the random-walk algorithm.

Graph Laplacian and its Spectrum

The Shi-Malik spectral clustering algorithm (2000), used in Nvidia image segmentation systems, is built on the second eigenvector of the Laplacian. For a 512x512 image this is an eigenvalue problem for a 262144x262144 matrix.

Key ideas

• **Graph spectrum:** eigenvalues of A are real (A is symmetric); tr(A^k) counts closed walks of length k
• **Laplacian L=D-A:** quadratic form x^T L x = sum_{(i,j)} (x_i-x_j)^2; zero multiplicity = connected components
• **Fiedler number mu_2:** governs the isoperimetric number via the Cheeger inequality; mu_2 > 0 iff graph is connected
• **Expander graph:** d-regular graph with lambda_2 at most 2*sqrt(d-1) (Ramanujan bound)

Вопросы для размышления

• Why does the multiplicity of zero for the Laplacian equal the number of connected components rather than the number of degree-0 vertices?
• How does the spectral gap lambda_1 - lambda_2 relate to the mixing time of a random walk on the graph?
• For regular graphs, d-regularity implies lambda_1=d. What happens for irregular graphs?

Связанные уроки

• prob-05-independence