Power iteration and ranking pages

Four pages link to each other. Watch importance flow along the links until every page’s share stops changing.

Importance flows along links

One way to rank pages imagines that importance flows along links. A page passes its importance on, split evenly among the pages it links to, and a page is important when important pages link to it. Write that flow as a matrix with the convention of Markov matrices: column $q$ says where page $q$ sends its share.

Page 1 links to pages 2 and 3, so column 1 has 0.5 in rows 2 and 3. Every column adds up to 1. The ranking is a steady state, $\mathbf{M}\mathbf{s}=\mathbf{s}$: here $\mathbf{s}=(2,3,4,0)/9$. Page 3 wins, since three pages link to it. Page 4 gets nothing, since nobody does.

Multiply and rescale

For four pages the steady state can be solved by elimination. For billions of pages it can’t. What still works is the simplest thing possible: start anywhere, and multiply by the matrix again and again.

Diagonalisation and matrix powers explains why this finds an eigenvector. Write the start as a mix of eigenvectors, $\mathbf{u}_0=c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots$. After $k$ steps

If $\lambda_1$ is larger in size than every other eigenvalue, and $c_1\neq0$, its part outgrows the rest, and the vector turns towards $\mathbf{v}_1$. The length may grow or shrink without limit, so rescale after every step:

This is power iteration. Once $\mathbf{u}_k$ has settled, the eigenvalue follows from $\lambda_1\approx\mathbf{u}_k\cdot\mathbf{A}\mathbf{u}_k$, for a unit $\mathbf{u}_k$. For a Markov matrix the largest eigenvalue is exactly 1, and rescaling to a total of 1 keeps the shares as shares.

How fast

The leftover part shrinks relative to the main one by $\lvert\lambda_2/\lambda_1\rvert$ each step, where $\lambda_2$ is the next largest in size.

For the matrix of Eigenvectors, with eigenvalues 2 and 0.5, the factor is $0.5/2=0.25$. Track the ratio $q_k$ of the arrow’s second entry to its first. One step sends it to $q_{k+1}=(0.5+q_k)/(1.5+q_k)$, and from $(1,0)$ it runs

Its distance from $\tfrac12$ goes $\tfrac12,\ \tfrac16,\ \tfrac1{22},\ \tfrac1{86},\ \tfrac1{342}$: about a quarter each time.

For the three-towns matrix of the Markov page, with eigenvalues 1, 0.6 and 0.5, the factor is 0.6, and after 10 steps $0.6^{10}$, about 0.006, of the starting error is left.

Damping

The bare link matrix has two problems. A page with no links in, like page 4, ends up with nothing, and a group of pages that only link to each other can trap all the importance or make it swing back and forth. The fix is damping: at every step a share $d$ of the importance follows the links, and the rest, $1-d$, is spread evenly over all $n$ pages. With the all-ones vector $\mathbf{1}=(1,\dots,1)$:

Every entry of this matrix is positive, so by the Markov page it has one steady state, reached from every start. With $d=0.85$, from equal shares:

• after 1 step: $(0.25,\ 0.25,\ 0.4625,\ 0.0375)$;
• after 2 steps: $(0.25,\ 0.340,\ 0.372,\ 0.0375)$;
• after 3 steps: $(0.212,\ 0.302,\ 0.449,\ 0.0375)$;
• settled: $(0.231,\ 0.313,\ 0.418,\ 0.0375)$.

Page 4 now keeps exactly the damping share, $0.15/4=0.0375$. Damping also guarantees the speed: any difference between two share vectors shrinks by at least the factor $d$ each step. That bound promises the error falls below $5\times10^{-5}$ within 61 steps; this small web gets there in 14, since the other eigenvalues of its damped matrix have size 0.425.

Worked example

1. The arrow. From $(1,0)$ under $\begin{bmatrix}1.5&1\\0.5&1\end{bmatrix}$ the ratio goes $0,\ \tfrac13,\ \tfrac5{11},\ \tfrac{21}{43},\ \dots$ towards $\tfrac12$, the direction $(2,1)$, the gap shrinking by about 0.25 each step.

2. The web without damping. $\mathbf{M}\mathbf{s}=\mathbf{s}$ gives $\mathbf{s}=(2,3,4,0)/9$. Check row 2: $\tfrac12\cdot\tfrac29+\tfrac12\cdot\tfrac49=\tfrac39$.

3. The web with damping. At $d=0.85$: $(0.231,\ 0.313,\ 0.418,\ 0.0375)$. At $d=0.5$: $(0.245,\ 0.275,\ 0.355,\ 0.125)$, flatter, since more is shared out evenly.

4. Scale. A web of $10^9$ pages with about 10 links each has $10^{10}$ links. One step costs about $10^{10}$ multiplications, one per link, and 50 steps $5\times10^{11}$. A full $10^9\times10^9$ table would have $10^{18}$ entries, which no computer could store.

Try these before you read the answers.

• What sets the speed of power iteration? $\lvert\lambda_2/\lambda_1\rvert$.
• Does $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ converge? No: its eigenvalues 1 and $-1$ tie in size, and the arrow flips back and forth.
• As $d$ approaches 1, what happens to page 4’s share? It falls towards 0.

Where you’ll meet this

Ranking. Pages, scientific papers and accounts in a social network have all been ranked by a damped steady state of this kind.

Big eigenproblems. When a matrix is too big to handle whole, power iteration still finds its dominant eigenvector: the main vibration mode of a structure, or the top principal direction of huge data, as in Principal components.

Inside eigenvalue software. General eigenvalue programs run refined versions of the same iteration, shifted and applied to many vectors at once.

Reference card