Graph Theory and Spectral Methods

A map of the graph toolkit: write the network as matrices, read its spectrum for structure, then pick the method that matches the question you asked.

A three-node path drawn as a graph, written as adjacency and Laplacian matrices, resolves into the spectrum 0, 1, 3 whose middle eigenvector cuts the chain

Why Does This Exist?

Graph questions arrive in different languages. Is this network connected? Which nodes matter? Where should it split? How does information spread? Each question has a method, and beginners either reach for the wrong one or re-derive one from scratch. This page is the map: what each representation captures, which spectrum answers which question, and where the deep treatments live.

The representations come from graph fundamentals: adjacency $A$ for direct connections, degrees $D$ for local density. The spectra come from eigenvalues and eigenvectors applied to those matrices. The Laplacian consequences are worked fully in graph Laplacian views. Nothing here replaces those pages; it routes among them.

The one idea you need first

A graph with $n$ nodes becomes $n \times n$ matrices, and matrix spectra describe global structure. Powers of $A$ count walks, eigenvalues of $L = D - A$ describe connectivity, and eigenvectors give coordinates and cuts. That translation is the whole game.

Think of It Like This

A city surveyed three ways

A mayor asks three questions about one city. The road atlas (the graph) shows which junctions join: good for routes. The census table (the matrices) lists each junction's connections as numbers: good for arithmetic. The vibration test (the spectrum) shakes the city-as-springs and listens: the lowest hum says whether it is one piece, the next hum says where it would split.

No survey replaces the others. You would not run a vibration test to give driving directions, and you would not trace routes by eye across a billion junctions. Spectral methods earn their keep exactly where tracing fails: global structure of large graphs.

Where the analogy stops: real spectra come from exact decompositions with guarantees, not from shaking anything.

How It Actually Works

Three representations, three spectra, five method families:

Representations. $A$ stores edges (or weights). $D$ stores degrees on its diagonal. $L = D - A$ stores the difference, with zero row sums. Normalize by degree ( $D^{-1}A$ , $D^{-1/2}LD^{-1/2}$ ) when degrees vary wildly.

Spectra. Eigenvalues of $A$ govern walk growth and spreading speed. Eigenvalues of $L$ govern connectivity: count of zeros equals components, smallest nonzero ( $\lambda_2$ ) measures the bottleneck. Eigenvectors give embeddings (low ones as coordinates) and cuts (Fiedler sign pattern).

Methods. Connectivity and cuts from Laplacian spectra; influence from centrality and walk stationary states; spreading from walk dynamics and diffusion; smoothing and filtering from graph Fourier modes; embedding from low eigenvectors. Walks, signals, centrality, partitioning, and shortest paths each get their own page; this map says which to open.

Worked example

Three nodes in a line $1 - 2 - 3$ . Degrees are $1, 2, 1$ :

A = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \qquad L = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{bmatrix}

Trace check: $\mathrm{tr}(L) = 1 + 2 + 1 = 4$ . The Laplacian eigenvalues are $0$ , $1$ , $3$ , summing to $4$ . One zero means one component. The Fiedler value $1$ with vector $(0.707, 0, -0.707)$ changes sign between the ends while the middle sits at zero: the chain's weak point is its middle, and thresholding the ends against each other cuts it there. $A^2$ counts two-step walks: $(A^2)_{1,1} = 1$ (there and back), $(A^2)_{1,3} = 1$ (across in two hops).

Watch Out For

Reading a spectrum without checking which matrix it came from

Adjacency, Laplacian, normalized Laplacian, and random-walk spectra live on different scales with different theorems: adjacency eigenvalues can be negative and large, Laplacian ones start at zero, normalized ones cap at 2. A "spectral gap" of 2 means excellent connectivity for a normalized Laplacian and something else entirely for an adjacency matrix.

Symptom: comparing $\lambda_2$ across papers or libraries and concluding one graph is better connected when the matrices differ. Fix: name the matrix every time ( $L$ , $L_{\mathrm{sym}}$ , $P$ ), and convert before comparing.

Storing a real graph densely because the theory is written densely

Theory writes $n \times n$ matrices; a million-node social graph as a dense matrix is 4 TB. The methods that scale touch the graph only through neighbour operations (matrix-vector products, scatter-gather), never by materializing $A$ or $L$ .

Symptom: code that works on the tutorial graph exhausts memory on the real one. Fix: store edge lists or sparse formats, use iterative eigensolvers for the few smallest or largest eigenpairs, and reason about cost in edges $|E|$ , as the fundamentals page warns.

The Quick Version

Graphs become matrices ( $A$ , $D$ , $L$ ); spectra of those matrices answer global questions.
Zero Laplacian eigenvalues count components; the Fiedler vector cuts at the bottleneck.
On the 3-node path the Laplacian spectrum is 0, 1, 3 and the Fiedler signs split the ends.
Walks count paths, centrality ranks nodes, partitioning cuts, signals filter, embeddings coordinatize.
Name the matrix before quoting a spectrum, and store sparse at scale.