WEBVTT 00:00:00.035 --> 00:00:01.684 Nineteen ninety eight. 00:00:01.881 --> 00:00:06.038 The web has millions of pages on it, and somebody has to put them in order. 00:00:06.351 --> 00:00:09.207 Counting the words on a page is easy to fake. 00:00:09.404 --> 00:00:12.618 What is much harder to fake is what everybody else links to. 00:00:12.701 --> 00:00:15.187 So treat a hyperlink as a vote. 00:00:16.583 --> 00:00:18.799 Here is a web with six pages on it. 00:00:18.882 --> 00:00:22.828 Call them A through F, and every arrow is one hyperlink, 00:00:22.911 --> 00:00:26.917 pointing from the page that casts the vote to the page that receives it. 00:00:27.714 --> 00:00:29.616 A links to B and to C. 00:00:29.699 --> 00:00:33.716 B links to C and to D. C links back to A. 00:00:33.820 --> 00:00:40.090 D links to A and to E. E links to A and to F. And F links only to A. 00:00:40.887 --> 00:00:43.512 The crude way to use that is simply to count. 00:00:43.708 --> 00:00:46.992 Four arrows point at A. Two point at C. 00:00:47.075 --> 00:00:50.269 And B, D, E and F have one each. 00:00:50.465 --> 00:00:55.528 So A wins, and four pages are tied for last, which is not much of a ranking. 00:00:56.232 --> 00:00:58.262 And it is trivially cheatable. 00:00:58.345 --> 00:01:01.642 Every vote counted the same, so a link from a page nobody 00:01:01.642 --> 00:01:06.067 has ever read is worth exactly as much as a link from the front page of a newspaper. 00:01:07.281 --> 00:01:08.742 So here is the fix, 00:01:08.825 --> 00:01:12.936 and the lovely thing about it is that it stops talking about voting altogether. 00:01:13.133 --> 00:01:17.438 Imagine somebody sitting at page A who does nothing but click links at random. 00:01:17.521 --> 00:01:20.123 A has two links out, so flip a coin. 00:01:20.436 --> 00:01:22.062 It comes up C. 00:01:22.545 --> 00:01:26.284 C has only one link, so the surfer goes back to A. 00:01:26.481 --> 00:01:29.068 From A the coin says B this time. 00:01:29.151 --> 00:01:32.043 B has two links out and picks C again. 00:01:32.355 --> 00:01:34.191 C takes it back to A. 00:01:34.987 --> 00:01:36.971 Nobody is choosing anything clever there. 00:01:37.054 --> 00:01:42.358 It is all coin flips. And the surfer never arrives anywhere, because it never stops, 00:01:42.441 --> 00:01:45.356 so the question to ask is not where it ends up. 00:01:45.668 --> 00:01:49.245 It is what fraction of its time it spends on each page. 00:01:50.042 --> 00:01:53.267 Before the walk starts we know nothing at all, 00:01:53.350 --> 00:01:56.219 so give every page an equal share of the credit: 00:01:56.532 --> 00:02:00.097 one sixth each, about zero point one six seven. 00:02:00.893 --> 00:02:04.737 Now let the surfer run for a hundred steps and count where it landed. 00:02:05.189 --> 00:02:07.347 A took about forty one percent of the visits, 00:02:07.430 --> 00:02:13.619 C about twenty five, B about seventeen, and D, E and F share what little is left. 00:02:14.322 --> 00:02:17.017 Ten thousand steps, and the numbers steady. 00:02:17.120 --> 00:02:20.267 A million, and they stop moving altogether. 00:02:20.464 --> 00:02:22.636 This is what the walk settles on. 00:02:23.688 --> 00:02:28.992 A holds about thirty seven percent of the surfer's time, C twenty eight, B nineteen, 00:02:29.075 --> 00:02:34.706 and then it falls away sharply: nine, five and two percent for D, E and F. 00:02:34.903 --> 00:02:38.398 Those six numbers are the PageRank of this little web. 00:02:39.102 --> 00:02:41.329 And look at what those numbers are not. 00:02:41.412 --> 00:02:43.363 They are not the link count. 00:02:43.676 --> 00:02:46.809 B and D have exactly one arrow pointing at each of them, 00:02:46.892 --> 00:02:49.935 and yet B ends up worth twice as much as D. 00:02:50.731 --> 00:02:53.588 Look at where each of those single votes comes from. 00:02:53.692 --> 00:02:55.896 The one pointing at B comes from A, 00:02:55.979 --> 00:03:01.204 the most visited page on this web, and A splits its rank between two links. 00:03:01.401 --> 00:03:03.375 So B gets half of A. 00:03:03.479 --> 00:03:09.064 The one pointing at D comes from B, split two ways again, so D gets half of B. 00:03:09.861 --> 00:03:12.471 The same halving carries on down the chain. 00:03:12.554 --> 00:03:17.245 D hands half of what it has to E, and E hands half of that to F. 00:03:17.349 --> 00:03:21.750 That is why the last four numbers are each exactly half the one before them. 00:03:22.546 --> 00:03:26.968 So a vote from a heavily visited page is worth more than a vote from a quiet one, 00:03:27.051 --> 00:03:30.175 and a page that links to everything gives less to each. 00:03:30.627 --> 00:03:34.017 That is the whole idea, and it came out of a coin flip. 00:03:34.818 --> 00:03:36.977 What we do not have yet is a way to compute it 00:03:36.977 --> 00:03:39.544 without walking for a million steps. 00:03:40.542 --> 00:03:42.316 The surfer's rule is short. 00:03:42.399 --> 00:03:46.391 Take whatever rank you have, divide it equally among your outgoing links, 00:03:46.474 --> 00:03:47.785 and hand it on. 00:03:47.868 --> 00:03:50.257 Let's write that down one page at a time, 00:03:50.340 --> 00:03:54.184 calling the new numbers y and the old ones x. 00:03:54.667 --> 00:03:57.626 Start with B, because B is the easy one. 00:03:57.709 --> 00:04:01.239 Exactly one page points at it, and that is A. 00:04:01.343 --> 00:04:05.627 A has two links out, so A hands over half of what it has. 00:04:05.824 --> 00:04:09.494 The new value of B is half the old value of A. 00:04:10.104 --> 00:04:14.933 C is fed by two pages, A and B, and both of them have two links out, 00:04:15.016 --> 00:04:17.269 so both hand over half of theirs. 00:04:17.465 --> 00:04:20.810 The new C is half of A, plus half of B. 00:04:21.293 --> 00:04:23.453 A is fed by four pages. 00:04:23.650 --> 00:04:28.306 C and F have only one link each, so they hand over everything they have. 00:04:28.503 --> 00:04:32.216 D and E have two links each, so they hand over half. 00:04:32.299 --> 00:04:36.909 The new A is C, plus half of D, plus half of E, plus F. 00:04:37.520 --> 00:04:42.035 There are six of these, one per page, and every one of them has the same shape: 00:04:42.118 --> 00:04:46.458 a weighted sum of the old numbers, with the weights read straight off the links. 00:04:46.541 --> 00:04:49.259 Which is precisely what a matrix is for. 00:04:50.771 --> 00:04:53.431 Here is the whole web as one matrix. 00:04:53.627 --> 00:05:00.258 Six rows and six columns, one of each per page, in the order A, B, C, D, E, F. 00:05:01.054 --> 00:05:04.526 A column tells you what one page does with its rank. 00:05:04.978 --> 00:05:09.922 The column for A has two entries of one half, sitting in the B row and the C row, 00:05:10.005 --> 00:05:13.280 because A splits its vote between B and C. 00:05:14.076 --> 00:05:16.501 The column for C has a single one in it, 00:05:16.584 --> 00:05:21.287 up in the A row, because C has one link and gives everything to A. 00:05:21.600 --> 00:05:24.082 And every column adds up to exactly one, 00:05:24.165 --> 00:05:28.496 which is the bookkeeping that says rank is never created and never destroyed. 00:05:29.293 --> 00:05:33.125 Read across instead of down and you get what a page receives. 00:05:33.322 --> 00:05:38.476 The A row has four non zero entries, and they are exactly the four terms we wrote 00:05:38.476 --> 00:05:43.040 a minute ago: C, half of D, half of E, and F. 00:05:43.941 --> 00:05:47.970 So one step of the walk is one matrix times one vector. 00:05:48.062 --> 00:05:51.465 Call the numbers at step k, x sub k. 00:05:51.650 --> 00:05:55.052 Then the next lot is H times x sub k. 00:05:55.144 --> 00:05:56.863 And then you do it again. 00:05:58.248 --> 00:06:03.183 Start from the vector that knows nothing at all: one sixth on every page. 00:06:03.980 --> 00:06:07.243 Multiply once, and watch what A collects. 00:06:07.439 --> 00:06:10.912 All of C, which is zero point one six seven. 00:06:11.015 --> 00:06:16.160 Half of D, and then half of E, which is zero point zero eight three apiece. 00:06:16.356 --> 00:06:19.991 And all of F, another zero point one six seven. 00:06:20.788 --> 00:06:23.911 Rule a line under those four and add them up. 00:06:24.108 --> 00:06:26.756 A comes out at exactly one half. 00:06:27.069 --> 00:06:29.763 Which is a wildly lopsided first step: 00:06:29.867 --> 00:06:33.931 everything that pointed at A has dumped its whole share in at once. 00:06:34.843 --> 00:06:38.072 Multiply again and it swings back the other way. 00:06:38.686 --> 00:06:42.644 A gives half of that pile to B and half to C, so those two jump up, 00:06:42.727 --> 00:06:45.119 and A itself drops to a third. 00:06:46.171 --> 00:06:49.295 Do it a third time, and the numbers swing again. 00:06:49.491 --> 00:06:51.547 And a fourth, and again. 00:06:51.860 --> 00:06:56.063 They wobble, and every time round the wobble is a little smaller than it was. 00:06:56.860 --> 00:06:58.625 By about the twelfth multiplication 00:06:58.625 --> 00:07:01.688 they have stopped changing in the third decimal place, 00:07:01.771 --> 00:07:05.243 and they are the same six numbers the surfer found by walking. 00:07:05.440 --> 00:07:10.909 Three seven two on A, two seven nine on C, one eight six on B. 00:07:11.821 --> 00:07:13.529 This is the power method. 00:07:13.981 --> 00:07:18.704 Multiplying by H over and over drives any starting vector towards the one vector 00:07:18.787 --> 00:07:20.623 that H leaves alone. 00:07:20.935 --> 00:07:24.941 An eigenvector of the link matrix, with eigenvalue one. 00:07:25.738 --> 00:07:28.281 And that is genuinely how it is done. 00:07:28.478 --> 00:07:33.400 On a web of a billion pages the matrix is almost entirely zeros, so a single 00:07:33.400 --> 00:07:38.103 multiplication is cheap, and a few dozen of them is the whole computation. 00:07:38.300 --> 00:07:43.037 There is only one problem. All of that assumes the walk can always carry on. 00:07:44.170 --> 00:07:49.045 Real webs are not that tidy. Plenty of pages have no outgoing links at all: 00:07:49.128 --> 00:07:53.912 a PDF, an image, a page that simply never links anywhere. 00:07:54.015 --> 00:07:57.371 So take our web and delete the single link out of F. 00:07:57.913 --> 00:07:59.433 Now the surfer walks into F 00:07:59.433 --> 00:08:02.859 and stops dead, because there is nothing there to click on. 00:08:03.474 --> 00:08:06.818 In the matrix, that column is all zeros. 00:08:06.922 --> 00:08:10.406 F takes rank in, and hands none of it back out. 00:08:11.202 --> 00:08:13.444 Watch what that does to the numbers. 00:08:13.641 --> 00:08:17.728 At every step, whatever share is sitting on F simply vanishes. 00:08:17.831 --> 00:08:22.453 After one multiplication the total has already fallen to zero point eight three. 00:08:22.878 --> 00:08:25.712 Again, and it is down to three quarters. 00:08:25.908 --> 00:08:28.521 Again, and it keeps slipping away. 00:08:28.625 --> 00:08:29.680 Twenty steps in, 00:08:29.763 --> 00:08:33.584 there is essentially nothing left anywhere, and it is still falling. 00:08:34.380 --> 00:08:36.796 Which ranks nothing against anything. 00:08:37.109 --> 00:08:41.556 Every page has been driven towards zero, and the ordering has gone with it. 00:08:42.353 --> 00:08:44.304 Now the opposite failure. 00:08:44.500 --> 00:08:46.159 Give F a link out again, 00:08:46.242 --> 00:08:50.539 but point it at E rather than at A, and cut the link from E to A. 00:08:50.735 --> 00:08:53.592 Set the numbers back to an even sixth each. 00:08:54.505 --> 00:08:58.508 The surfer wanders in, and then it bounces between the two of them forever. 00:08:58.591 --> 00:09:04.420 There is no way out at all. That pattern has a name: a rank sink, or a spider trap. 00:09:04.845 --> 00:09:06.527 And the numbers go the other way. 00:09:06.610 --> 00:09:10.207 Instead of draining out of the web, everything piles into the pair. 00:09:10.290 --> 00:09:14.145 After enough steps E and F hold the whole thing between them, and A, 00:09:14.145 --> 00:09:17.071 B, C and D are all heading for zero. 00:09:17.554 --> 00:09:21.456 Two pages that nobody else even links to have taken the entire ranking. 00:09:21.908 --> 00:09:24.672 And both failures come from the same place: 00:09:24.868 --> 00:09:27.400 the walk cannot carry on properly. 00:09:27.597 --> 00:09:30.825 So set the numbers level again, and let's fix it. 00:09:32.477 --> 00:09:34.449 Both of them have the same one line cure, 00:09:34.532 --> 00:09:37.679 and it is the nicest idea in the whole algorithm. 00:09:38.294 --> 00:09:40.106 The surfer gets bored. 00:09:40.809 --> 00:09:45.872 Eighty five times out of a hundred, click a random link, exactly as before. 00:09:46.069 --> 00:09:49.425 The other fifteen times, stop clicking altogether: 00:09:49.621 --> 00:09:51.361 type an address straight into the bar, 00:09:51.444 --> 00:09:55.706 and jump to a page picked uniformly at random from the entire web. 00:09:56.619 --> 00:09:58.930 So the update gains a second term. 00:09:59.243 --> 00:10:03.362 Zero point eight five times H times x, which is the clicking, 00:10:03.445 --> 00:10:08.043 plus zero point one five over n on every page, which is the jumping. 00:10:08.240 --> 00:10:11.166 That first constant is the damping factor. 00:10:11.963 --> 00:10:14.286 Watch it undo both problems. 00:10:14.738 --> 00:10:15.781 From a dead end, 00:10:15.864 --> 00:10:20.950 jumping is the only move there is, so the walk carries on and nothing leaks away. 00:10:21.402 --> 00:10:25.197 From inside the trap, the surfer escapes fifteen times in a hundred, 00:10:25.280 --> 00:10:27.464 so it can never be held there forever. 00:10:28.376 --> 00:10:32.450 And every page in the web now receives at least zero point one five over n, 00:10:32.533 --> 00:10:34.310 no matter who links to it. 00:10:34.413 --> 00:10:36.664 So no rank is ever exactly zero, 00:10:36.747 --> 00:10:41.113 and the ordering always exists, whatever the link structure happens to look like. 00:10:41.910 --> 00:10:44.288 So put the original web back, with F 00:10:44.371 --> 00:10:49.933 pointing at A once more and E linking out again, and run the damped iteration on it. 00:10:50.637 --> 00:10:52.481 These are the numbers it settles on. 00:10:52.564 --> 00:10:58.311 A lands at about zero point three five, C at zero point two five, B at zero point 00:10:58.311 --> 00:11:04.082 one eight, and then D, E and F at a tenth, seven hundredths and five hundredths. 00:11:04.995 --> 00:11:07.466 Same order as the undamped walk gave us, 00:11:07.549 --> 00:11:11.207 but everything has been pulled a little way towards the flat one sixth. 00:11:11.404 --> 00:11:15.201 A has given some back, and F has more than doubled. 00:11:15.397 --> 00:11:19.462 That is the fifteen percent of ignorance mixing itself back in. 00:11:20.676 --> 00:11:22.871 So that is PageRank. 00:11:23.184 --> 00:11:24.915 A link is a vote. 00:11:25.111 --> 00:11:27.954 A vote is worth the rank of the page casting it, 00:11:28.037 --> 00:11:31.242 divided between all the links that page casts. 00:11:31.439 --> 00:11:32.809 And the ranking is the vector 00:11:32.809 --> 00:11:36.896 that stops changing when you multiply it by the damped link matrix.