The PageRank algorithm

Overview

Recall questions on the idea behind PageRank, dividing a page's vote among its links, the damping factor and the random surfer, iterative computation, calculating ranks by hand, and why PageRank alone cannot order results.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is the central idea of PageRank?

   Model answer

   That the importance of a page can be judged from the importance of the pages that link to it. A link is treated as a vote of confidence: if many pages link to a page, that suggests it is worth reading. Crucially, the votes are weighted by the voter's own importance, so the calculation is recursive - a page's rank depends on the ranks of the pages linking to it, which depend in turn on the ranks of the pages linking to them. It measures standing in the web's link structure, which is independent of what the searcher typed, so it can be computed in advance and combined with relevance at query time.

2. 2

   Why should a link from a highly ranked page count for more than a link from an obscure one?

   Model answer

   Because the value of a recommendation depends on who is making it. Anybody can create a page and link to their own site, so if all links counted equally, importance could be manufactured by making thousands of worthless pages that all point at one target. Weighting the vote by the voter's own rank makes that pointless, because those worthless pages have almost no rank to pass on. A link from a page that is itself widely and reputably linked to is hard to obtain and therefore carries real information.

3. 3

   A page's vote is divided among its outgoing links. Why?

   Model answer

   Because a page has a fixed amount of standing to distribute, and linking to more places does not create more of it. If a page could pass its full rank to every page it linked to, a directory linking to ten thousand sites would confer as much on each as a page recommending one carefully chosen source, and anyone could inflate the whole web by adding links. Dividing the rank among the outgoing links means a link from a page with few outgoing links is worth more than a link from the same page if it linked to hundreds - which matches the intuition that a selective recommendation means more than being one entry in a long list. It also keeps the total amount of rank in the system stable rather than growing every time someone adds a link.

4. 4

   State the PageRank calculation in words.

   Model answer

   A page's rank is a small fixed amount that every page receives regardless, plus a share of the rank passed to it by the pages that link to it. Each linking page contributes its own current rank divided by the number of links leaving it, and those contributions are added together. That sum is then multiplied by the damping factor, and the fixed amount is one minus the damping factor. Written out for a page A linked to by pages T1 to Tn: PR(A) = (1 - d) + d x ( PR(T1)/C(T1) + ... + PR(Tn)/C(Tn) ), where C(T) is the number of links leaving page T and d is the damping factor, conventionally 0.85. A variant in common use divides the fixed part by the total number of pages, so that all the ranks sum to 1; this changes the scale of the numbers but not the ordering or the principle, and the form given above is the one used throughout this guide.

5. 5

   What does the damping factor represent?

   Model answer

   It models a random surfer. Imagine somebody browsing by clicking links at random: at each page there is a probability d that they follow one of the links on it, and a probability 1 - d that they get bored, abandon the trail and jump to some page chosen at random. A page's rank is then the long-run probability of finding that surfer on it. The damping factor is that probability of continuing to click rather than jumping, conventionally set at about 0.85, so roughly speaking the surfer follows about six links before starting again somewhere new.

6. 6

   Why is a damping factor needed at all? What goes wrong without one?

   Model answer

   Without it, rank drains into traps. A group of pages that link only to one another - deliberately as a link farm, or accidentally - would keep passing the same rank round the loop and steadily accumulate all the rank in the system, while everything outside it fell to nothing. A page with no outgoing links would absorb rank and pass none on, so rank would leak out of the system entirely. And a page that nothing linked to would have a rank of exactly zero and could never be compared with any other such page. The damping factor fixes all three: because the surfer always has a chance of jumping to a random page, every page receives the fixed minimum whether anything links to it or not, no group can trap rank forever since the surfer escapes any loop, and the calculation is guaranteed to settle to a stable set of values.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.