Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Conductance — where it appears

The weight of edges leaving a set of vertices, divided by the total degree on the smaller side. It is the quantity a spectral partition is trying to minimise, and unlike an eigenvalue it is a property of the answer rather than of the matrix.

Named by 6 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

The combinatorial Laplacian D − A and the normalised one, which conjugates it by the inverse square roots of the degrees, 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 0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The vector that has to be rounded

A spectral partition is an eigenvector, and an eigenvector is a real vector. The answer wanted is a subset. Something has to turn one into the other, and the something is a heuristic applied after the linear algebra has finished.

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

A bound with a square root in it

Cheeger's inequality brackets a graph's best cut between λ₂/2 and √(2λ₂). The lower bound is attained exactly. The upper one is loose by a factor of fourteen — on the one graph in the census with a real bottleneck, which is the shape it is always quoted about.

graph · Spectral partition 14710131619110¹indexeigenvalue of Lan eigenvalue with no vectorλ₂0.35λ₃0.35gap1.7·10⁻¹⁵partitions found3best conductance0.045worst0.045two eigenvalues, one valueand the answer is not a function of the graph

A partition decided in the last digit

On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector. Twenty-four runs with the edge weights nudged by 10⁻¹² return ten different partitions of a cycle and, on a hypercube, two different qualities of answer.

graph · Spectral partition 0173451688510211910⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.9steps measured122steps predicted131ratio0.93the dashed line is the eigenvaluethe curve is the walk

The rate is the second eigenvalue

A walk forgets where it started at a rate the graph's second eigenvalue names exactly. Across three orders of magnitude in the step count the prediction is five per cent high — and the published rate for PageRank is right for a reason nobody states, which is that a link graph is in pieces.

graph · Random walk Cheeger's band, for the circulationcirculation · arcsvertices on the smaller sidewhich of the two the theorem is aboutλ₂ of 𝓛0.066λ₂/20.033√(2λ₂)0.36circulation Φ0.12arc conductance0.04their ratio3.1the inequality holdsabout a quantity nobody counts

A conductance the arcs do not measure

Symmetrising a directed Laplacian with respect to its walk recovers everything the arrows took — a real spectrum, a sweep cut, a Cheeger inequality. What it does not recover is the quantity: the inequality bounds the probability that a step of the walk crosses the cut, which on one graph here is three times the weight of the arcs that do.

graph · Directed laplacian

Named alongside it

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

Algebraic connectivityCheeger inequalityFiedler vectorNormalised laplacianSpectral partitionGraph automorphismGraph laplacianQuadratic formRelaxationSweep cutBipartiteBound tightness

All concepts