Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Degree sequence — where it appears

The sorted list of how many edges meet at each vertex. It is not determined by the Laplacian spectrum, so it separates graphs a spectrum cannot, and it costs one pass over the edge list.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph

Two Laplacians of one graph

D − A and D^{-1/2}(D − A)D^{-1/2} are built from the same object, are not similar to each other, and answer different questions. On a graph whose degrees are equal they coincide. On one whose degrees span an order of magnitude their second eigenvalues are sixteen times apart.

graph · graph laplacian 19172533414911.251.51.752indexsample ÷ originalkept, and not keptedges kept344of1225eigenvalue ratio, low0.43high1.7degree ratio, low0.56high1.5diameter, after3filled dots are eigenvaluesopen dots are degrees

A graph with a tenth of the edges

Keeping 344 of 1,225 edges, sampled by effective resistance and reweighted, preserves every eigenvalue of the Laplacian to within a factor of 1.7. It preserves no degree — half of them are wrong by more than a third — and it takes the diameter from one to three.

graph · effective resistance

Named alongside it

The objects these essays reach for when they reach for this one.

Graph laplacianQuadratic formAlgebraic connectivityConductanceDiagonal scalingEffective resistanceFoster theoremImportance samplingNormalised laplacianRandomisedSimilarity transformationSpectral sparsification

All concepts