Ranking Pages by Following Links

A search engine wants to rank $n$ web pages by importance, where a page is important if important pages link to it. That sounds circular — and an eigenvector is exactly what resolves it.

Picture a surfer clicking around. At every step they:

with probability $d$ (the damping factor), follow one of the current page's links, chosen uniformly — or, if the page has no links at all, jump to any of the $n$ pages uniformly;
with probability $1 - d$ , get bored and jump to any of the $n$ pages uniformly.

If $r_i$ is the probability the surfer is on page $i$ , one step produces the new scores

r_j^{\text{new}} = \frac{1-d}{n} \;+\; d\sum_{i \to j} \frac{r_i}{L_i} \;+\; d\sum_{i \text{ has no links}} \frac{r_i}{n}

where the first sum runs over the pages $i$ that link to page $j$ , and $L_i$ is the number of links on page $i$ .

That update is a matrix–vector product $r^{\text{new}} = G\,r$ for one fixed $n \times n$ matrix $G$ . The ranking is the score vector that a further step leaves unchanged, $G\,r = r$ : an eigenvector of $G$ with eigenvalue $1$ . Every other direction shrinks each time $G$ is applied, so you can find it by power iteration — start from equal scores and apply the update again and again.

Task: write pagerank(links, d).

links[i] is the list of pages that page i links to. Pages are numbered 0 to n - 1; no page links to itself or lists the same target twice.
Start from $r_i = 1/n$ for every page, and repeat the update until no score changes by more than $10^{-10}$ in a single step.
Return the final scores as a list, each rounded to 4 decimal places.

Ranking Pages by Following Links

Examples

Hints