Introduction
PageRank, the ranking method Sergey Brin and Lawrence Page described in 1998, gives every web page a score based on the scores of the pages linking to it (Brin and Page 1998). The idea is easiest to see on a web small enough to compute by hand. This reading ranks a three-page web, first by passing scores along links round by round, then by solving directly for the scores that stop changing. It ends with the full table of scores.
The Starting Point
The web has three pages, A, B, and C, and four links. Each link is one-way:
- A links to B and to C.
- B links to C.
- C links to A.
Every page starts with the same score, \tfrac{1}{3}, so the scores add up to 1. The question is which page is most important, in PageRank's sense: which one a surfer clicking links at random would end up on most often.
Count the incoming links first, because it's tempting to stop there. C has two incoming links, from A and from B. A has one, from C. B has one, from A. By counting alone, C wins and A and B tie. Watch how the answer changes when links are weighted.
This example leaves out the damping factor, the adjustment for random jumps that Brin and Page usually set to 0.85 (Brin and Page 1998). Leaving it out keeps the arithmetic exact. The effect of adding it is described under Key Considerations.
Walking Through the Score Passing
Step 1: Write the passing rule
In each round, every page divides its current score equally among the pages it links to.
- A has two outgoing links, so it sends half its score to B and half to C.
- B has one outgoing link, so it sends all its score to C.
- C has one outgoing link, so it sends all its score to A.
Each page's new score is the total it receives. Written as equations, with A, B, and C standing for the scores:
\text{new } A = C, \qquad \text{new } B = \tfrac{1}{2}A, \qquad \text{new } C = \tfrac{1}{2}A + B
The same rule can be written as a matrix acting on the score vector (A, B, C):
\begin{pmatrix} 0 & 0 & 1 \\ \tfrac{1}{2} & 0 & 0 \\ \tfrac{1}{2} & 1 & 0 \end{pmatrix}
Each column shows where one page's score goes. The first column says A sends nothing to itself, half to B, and half to C. Every column adds up to 1, so no score is created or lost.
Step 2: Pass once
Start from A = B = C = \tfrac{1}{3} and apply the rule:
- New A = C = \tfrac{1}{3}
- New B = \tfrac{1}{2} \cdot \tfrac{1}{3} = \tfrac{1}{6}
- New C = \tfrac{1}{2} \cdot \tfrac{1}{3} + \tfrac{1}{3} = \tfrac{1}{6} + \tfrac{2}{6} = \tfrac{1}{2}
After one pass, the scores are \tfrac{1}{3}, \tfrac{1}{6}, and \tfrac{1}{2}. They still add to 1. C leads, because it collected from two pages.
Step 3: Pass three more times and watch
Apply the same rule to each new set of scores.
- Pass 2: A = \tfrac{1}{2}, B = \tfrac{1}{2} \cdot \tfrac{1}{3} = \tfrac{1}{6}, C = \tfrac{1}{2} \cdot \tfrac{1}{3} + \tfrac{1}{6} = \tfrac{1}{3}.
- Pass 3: A = \tfrac{1}{3}, B = \tfrac{1}{2} \cdot \tfrac{1}{2} = \tfrac{1}{4}, C = \tfrac{1}{4} + \tfrac{1}{6} = \tfrac{5}{12}.
- Pass 4: A = \tfrac{5}{12}, B = \tfrac{1}{2} \cdot \tfrac{1}{3} = \tfrac{1}{6}, C = \tfrac{1}{6} + \tfrac{1}{4} = \tfrac{5}{12}.
The scores swing. A jumps to the lead after pass 2, then C is ahead again, then they tie. The swings get smaller each time. If you keep going, A and C drift toward 0.4 and B toward 0.2: after twelve passes, the scores are about 0.401, 0.198, and 0.401.
Settling like this, by repeating the rule until nothing changes, is how PageRank is computed on a real web. Brin and Page note that it corresponds to finding the principal eigenvector of the link matrix: the vector that the matrix leaves unchanged (Brin and Page 1998).
Step 4: Solve for the steady state directly
A small web lets you skip the repetition. The steady state is the set of scores the passing rule leaves unchanged. So the new scores must equal the old ones:
A = C, \qquad B = \tfrac{1}{2}A, \qquad C = \tfrac{1}{2}A + B
The third equation adds nothing new: put B = \tfrac{1}{2}A into it and you get C = A, which the first already says. One more fact pins the scores down. They must add to 1:
A + B + C = A + \tfrac{1}{2}A + A = \tfrac{5}{2}A = 1
So A = \tfrac{2}{5}, then C = \tfrac{2}{5} and B = \tfrac{1}{5}. Check: \tfrac{2}{5} + \tfrac{1}{5} + \tfrac{2}{5} = 1. Pass these scores once more and they come back unchanged: A receives all of C's \tfrac{2}{5}, B receives half of A's, which is \tfrac{1}{5}, and C receives \tfrac{1}{5} + \tfrac{1}{5} = \tfrac{2}{5}.
Step 5: Interpret the ranking
C ties A for first place. It receives half of A's score and all of B's. A also scores high, though it has only one incoming link, because that link comes from C, a top-scoring page that gives A everything it has. B ranks last. It's linked only by A, and it gets only half of A's score, because A splits its score two ways.
Key Considerations
The common mistake: counting links instead of weighting them. Counting incoming links ranked C first and tied A with B. Weighting each link by the linking page's score changes the result: A rises to tie C, and B falls to half their score. A link from an important page that links to little else is worth more than a link from a page that spreads its score thinly. That weighting is what separates PageRank from a vote count.
The damping factor. Real PageRank mixes the link-passing with random jumps, weighted by the damping factor. If you add a damping factor of 0.85 to this example, the scores shift a little: C edges just ahead of A, and B rises slightly, since random jumps give every page some share. The damping factor also keeps the scores from getting trapped in small loops on a large web (Brin and Page 1998).
Why the scores swing. Score travels around two loops: A to C and back to A takes two rounds, while A to B to C and back to A takes three. Early on, score sloshes back and forth along these loops, which produces the swings. Because 2 and 3 share no common factor bigger than 1, the swings don't line up from round to round, and they die out. On a web whose loop lengths all shared a common factor, such as a web with a single loop, the scores could keep cycling forever, which is one more problem the random jumps of the damping factor fix.
What a small example can't show. Three pages settle in a dozen rounds. The web has billions of pages, and computing their steady state takes careful engineering. The method, though, is the same.
Summary
Passing scores along links swings at first and then settles into a steady state, which you can also find by solving a small system of equations. Here is the full record:
| Round | A | B | C |
|---|
| Start | 1/3 | 1/3 | 1/3 |
| Pass 1 | 1/3 | 1/6 | 1/2 |
| Pass 2 | 1/2 | 1/6 | 1/3 |
| Pass 3 | 1/3 | 1/4 | 5/12 |
| Pass 4 | 5/12 | 1/6 | 5/12 |
| Steady state | 2/5 | 1/5 | 2/5 |
- Every row adds to 1, because the passing rule moves score around without creating or losing any.
- The steady state satisfies A = C and B = \tfrac{1}{2}A, with the three scores adding to 1.
- C and A tie for first, and B ranks last, even though counting links alone would put C ahead of both.
References
- Brin, Sergey, and Lawrence Page. 1998. "The Anatomy of a Large-Scale Hypertextual Web Search Engine." Computer Networks and ISDN Systems 30 (1–7): 107–117.