Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Dangling node — where it appears

A vertex with no outgoing links, whose column of the link matrix is empty. It loses probability at every step, so an unrepaired PageRank iteration converges to zero, and every repair is a modelling assumption about what a walker at a dead end does.

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

Named alongside it

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

PagerankPerron frobeniusRegularisationStationary distributionTeleportationCollatz wielandtIrreducibilityMixing timeParameter choicePeriodicityPower iterationRandom walk

All concepts