Spectral graph theory

Spectral graph theory studies graph properties through eigenvalues and eigenvectors of matrices associated with graphs, especially adjacency and Laplacian matrices.

Adjacency matrix: A square matrix that records which pairs of vertices in a graph are adjacent. Its eigenvalues encode structural information such as walks, connectivity, and regularity.
Algebraic connectivity: The second-smallest eigenvalue of a graph Laplacian. It measures bottlenecks and indicates how strongly the graph remains connected.
Spectral clustering: A clustering method that embeds data using eigenvectors of a graph Laplacian before partitioning it. It turns low-frequency graph structure into groups of similar vertices.
Cospectral graphs: Nonisomorphic graphs whose adjacency matrices have the same eigenvalue multiset. They show that identical spectra need not imply identical graph structure.
Graph Laplacian: A matrix formed from vertex degrees and adjacency that captures connectivity and diffusion on a graph. Its spectrum directly reveals connected components and supports many structural bounds.
Cheeger inequality: An inequality relating a graph’s edge-expansion constant to its Laplacian eigenvalues. It explains why a small Laplacian eigenvalue signals a sparse cut.
PageRank: A link-analysis algorithm that ranks web pages using a stationary distribution of a Markov process. Its ranking vector is a dominant eigenvector of a modified link matrix.
Graph invariant: A graph property unchanged by relabeling its vertices. A spectrum is one kind of invariant, but usually not a complete fingerprint.
Eigenvalue: A scalar that describes how a linear transformation scales a corresponding nonzero eigenvector. Graph spectra are collections of eigenvalues of graph-associated matrices.
Perron–Frobenius theorem: A theorem describing the positive dominant eigenvalue and eigenvector of an irreducible nonnegative matrix. It underpins interpretations of leading adjacency eigenvectors in connected graphs.

Linked from 4 pages