Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Pagerank — where it appears

The stationary distribution of a walk that follows a link with probability alpha and jumps to a random page otherwise. It is an eigenvector for the eigenvalue one, and alpha decides how much of the answer is the graph and how much is the prior.

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

01428425670849810⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²iterationchange between iteratestwo rates, one curveα0.85λ₂(P)0.9predicted rate0.77measured0.77iterations108against the solve10⁻¹⁶the upper dashed line is αᵏthe curve is on the other one

A ranking that is an eigenvector

PageRank is the stationary vector of a walk that follows links with probability α and jumps at random otherwise. The iteration and the elimination agree to 4·10⁻¹⁷. What α is set to changes which pages come third, fourth and fifth.

graph · random walk 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 02244668811013215417610⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²iterationchange between iteratestwo rates, one curveα0.85λ₂(P)1predicted rate0.85measured0.84iterations176against the solve1.4·10⁻¹⁶the upper dashed line is αᵏthe curve is on the other one

A chain with no stationary vector

A page with no outgoing links loses forty per cent of the walker's probability in six hundred steps. A directed cycle never converges at all. And on a graph whose links only run one way, the entire rank of half the vertices is exactly one minus the teleportation parameter.

graph · random walk places settled, of 14the arithmetic14 of 14one missing link3 of 14α from 0.80 to 0.9011 of 14entries move by 4.05·10⁻¹¹entries move by 0.00443entries move by 0.00123three kinds of doubtcomparisons14smallest gap6.3·10⁻⁵largest gap0.0024arithmetic band4.1·10⁻¹¹one-link band0.0044α band0.0012the arithmetic settles nearly all of themthe data settles three

A ranking whose order is not determined

Of the fourteen adjacent comparisons in a top-fifteen, fourteen survive perturbing the arithmetic at the rounding level, eleven survive moving the teleportation parameter across its usual range, and three survive removing one link. The computation is the strongest part of the answer.

graph · perron frobenius

Named alongside it

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

Stationary distributionTeleportationDangling nodeMixing timeParameter choicePerron frobeniusPower iterationRandom walkRegularisationBackward errorBipartiteCentrality

All concepts