View source for Spectral Graph Theory

'''Spectral graph theory''' studies the relationship between the algebraic properties of matrices derived from a graph — primarily the '''adjacency matrix''' and the '''Laplacian matrix''' — and the graph's combinatorial and topological structure. The eigenvalues and eigenvectors of these matrices (the ''spectrum'' of the graph) encode a remarkable amount of information about graph connectivity, diffusion dynamics, partitionability, and robustness. It is one of the most productive interfaces between linear algebra and combinatorics, and between mathematics and the science of [[complex adaptive systems|complex networks]].

The '''graph Laplacian''' L = D − A, where D is the diagonal degree matrix and A is the adjacency matrix, is the central object. Its eigenvalues are all non-negative real numbers; the smallest is always zero; the multiplicity of the zero eigenvalue equals the number of [[Graph Theory|connected components]]. The second-smallest eigenvalue, known as the '''algebraic connectivity''' or '''Fiedler value''', measures how well-connected the graph is: large Fiedler value means high connectivity and fast mixing; small Fiedler value (approaching zero) means the graph is nearly disconnected, with a bottleneck — a [[cut set]] whose removal splits the graph into near-isolated pieces.

Spectral methods underpin '''graph partitioning''' (including spectral clustering algorithms widely used in [[machine learning]]), analysis of random walks and diffusion, community detection in [[Network Theory|network science]], and the study of [[Synchronization|synchronization]] in coupled oscillator systems (where the Fiedler value determines the threshold for global synchronization). The span is extraordinary: the same matrix algebra describes the mixing time of a Markov chain, the spread of [[epidemiology|epidemics]] on a contact network, and the stability of [[power grid|power grid]] frequency.

The deep lesson of spectral graph theory is that topology has algebra, and algebra has dynamics: you can read the network's behavior off its spectrum without simulating it. This is the purest example in all of [[Systems Theory|systems science]] of structure determining function, of pattern at one level of description causally explaining pattern at another.

[[Category:Mathematics]]
[[Category:Systems]]