How Hyperlinks Become Votes: The PageRank Algorithm

Nineteen ninety eight. The web has millions of pages on it, and somebody has to put them in order. Counting the words on a page is easy to fake. What is much harder to fake is what everybody else links to. So treat a hyperlink as a vote. Here is a web with six pages on it. Call them A through F, and every arrow is one hyperlink, pointing from the page that casts the vote to the page that receives it. A links to B and to C. B links to C and to D. C links back to A. D links to A and to E. E links to A and to F. And F links only to A. The crude way to use that is simply to count. Four arrows point at A. Two point at C. And B, D, E and F have one each. So A wins, and four pages are tied for last, which is not much of a ranking. And it is trivially cheatable. Every vote counted the same, so a link from a page nobody has ever read is worth exactly as much as a link from the front page of a newspaper. So here is the fix, and the lovely thing about it is that it stops talking about voting altogether. Imagine somebody sitting at page A who does nothing but click links at random. A has two links out, so flip a coin. It comes up C. C has only one link, so the surfer goes back to A. From A the coin says B this time. B has two links out and picks C again. C takes it back to A. Nobody is choosing anything clever there. It is all coin flips. And the surfer never arrives anywhere, because it never stops, so the question to ask is not where it ends up. It is what fraction of its time it spends on each page. Before the walk starts we know nothing at all, so give every page an equal share of the credit: one sixth each, about zero point one six seven. Now let the surfer run for a hundred steps and count where it landed. A took about forty one percent of the visits, C about twenty five, B about seventeen, and D, E and F share what little is left. Ten thousand steps, and the numbers steady. A million, and they stop moving altogether. This is what the walk settles on. A holds about thirty seven percent of the surfer's time, C twenty eight, B nineteen, and then it falls away sharply: nine, five and two percent for D, E and F. Those six numbers are the PageRank of this little web. And look at what those numbers are not. They are not the link count. B and D have exactly one arrow pointing at each of them, and yet B ends up worth twice as much as D. Look at where each of those single votes comes from. The one pointing at B comes from A, the most visited page on this web, and A splits its rank between two links. So B gets half of A. The one pointing at D comes from B, split two ways again, so D gets half of B. The same halving carries on down the chain. D hands half of what it has to E, and E hands half of that to F. That is why the last four numbers are each exactly half the one before them. So a vote from a heavily visited page is worth more than a vote from a quiet one, and a page that links to everything gives less to each. That is the whole idea, and it came out of a coin flip. What we do not have yet is a way to compute it without walking for a million steps.

The surfer's rule is short. Take whatever rank you have, divide it equally among your outgoing links, and hand it on. Let's write that down one page at a time, calling the new numbers y and the old ones x. Start with B, because B is the easy one. Exactly one page points at it, and that is A. A has two links out, so A hands over half of what it has. The new value of B is half the old value of A. C is fed by two pages, A and B, and both of them have two links out, so both hand over half of theirs. The new C is half of A, plus half of B. A is fed by four pages. C and F have only one link each, so they hand over everything they have. D and E have two links each, so they hand over half. The new A is C, plus half of D, plus half of E, plus F. There are six of these, one per page, and every one of them has the same shape: a weighted sum of the old numbers, with the weights read straight off the links. Which is precisely what a matrix is for. Here is the whole web as one matrix. Six rows and six columns, one of each per page, in the order A, B, C, D, E, F. A column tells you what one page does with its rank. The column for A has two entries of one half, sitting in the B row and the C row, because A splits its vote between B and C. The column for C has a single one in it, up in the A row, because C has one link and gives everything to A. And every column adds up to exactly one, which is the bookkeeping that says rank is never created and never destroyed. Read across instead of down and you get what a page receives. The A row has four non zero entries, and they are exactly the four terms we wrote a minute ago: C, half of D, half of E, and F. So one step of the walk is one matrix times one vector. Call the numbers at step k, x sub k. Then the next lot is H times x sub k. And then you do it again. Start from the vector that knows nothing at all: one sixth on every page. Multiply once, and watch what A collects. All of C, which is zero point one six seven. Half of D, and then half of E, which is zero point zero eight three apiece. And all of F, another zero point one six seven. Rule a line under those four and add them up. A comes out at exactly one half. Which is a wildly lopsided first step: everything that pointed at A has dumped its whole share in at once. Multiply again and it swings back the other way. A gives half of that pile to B and half to C, so those two jump up, and A itself drops to a third. Do it a third time, and the numbers swing again. And a fourth, and again. They wobble, and every time round the wobble is a little smaller than it was. By about the twelfth multiplication they have stopped changing in the third decimal place, and they are the same six numbers the surfer found by walking. Three seven two on A, two seven nine on C, one eight six on B. This is the power method. Multiplying by H over and over drives any starting vector towards the one vector that H leaves alone. An eigenvector of the link matrix, with eigenvalue one. And that is genuinely how it is done. On a web of a billion pages the matrix is almost entirely zeros, so a single multiplication is cheap, and a few dozen of them is the whole computation. There is only one problem. All of that assumes the walk can always carry on.

Real webs are not that tidy. Plenty of pages have no outgoing links at all: a PDF, an image, a page that simply never links anywhere. So take our web and delete the single link out of F. Now the surfer walks into F and stops dead, because there is nothing there to click on. In the matrix, that column is all zeros. F takes rank in, and hands none of it back out. Watch what that does to the numbers. At every step, whatever share is sitting on F simply vanishes. After one multiplication the total has already fallen to zero point eight three. Again, and it is down to three quarters. Again, and it keeps slipping away. Twenty steps in, there is essentially nothing left anywhere, and it is still falling. Which ranks nothing against anything. Every page has been driven towards zero, and the ordering has gone with it. Now the opposite failure. Give F a link out again, but point it at E rather than at A, and cut the link from E to A. Set the numbers back to an even sixth each. The surfer wanders in, and then it bounces between the two of them forever. There is no way out at all. That pattern has a name: a rank sink, or a spider trap. And the numbers go the other way. Instead of draining out of the web, everything piles into the pair. After enough steps E and F hold the whole thing between them, and A, B, C and D are all heading for zero. Two pages that nobody else even links to have taken the entire ranking. And both failures come from the same place: the walk cannot carry on properly. So set the numbers level again, and let's fix it. Both of them have the same one line cure, and it is the nicest idea in the whole algorithm. The surfer gets bored. Eighty five times out of a hundred, click a random link, exactly as before. The other fifteen times, stop clicking altogether: type an address straight into the bar, and jump to a page picked uniformly at random from the entire web. So the update gains a second term. Zero point eight five times H times x, which is the clicking, plus zero point one five over n on every page, which is the jumping. That first constant is the damping factor. Watch it undo both problems. From a dead end, jumping is the only move there is, so the walk carries on and nothing leaks away. From inside the trap, the surfer escapes fifteen times in a hundred, so it can never be held there forever. And every page in the web now receives at least zero point one five over n, no matter who links to it. So no rank is ever exactly zero, and the ordering always exists, whatever the link structure happens to look like. So put the original web back, with F pointing at A once more and E linking out again, and run the damped iteration on it. These are the numbers it settles on. A lands at about zero point three five, C at zero point two five, B at zero point one eight, and then D, E and F at a tenth, seven hundredths and five hundredths. Same order as the undamped walk gave us, but everything has been pulled a little way towards the flat one sixth. A has given some back, and F has more than doubled. That is the fifteen percent of ignorance mixing itself back in. So that is PageRank. A link is a vote. A vote is worth the rank of the page casting it, divided between all the links that page casts. And the ranking is the vector that stops changing when you multiply it by the damped link matrix.