1 00:00:00,450 --> 00:00:06,090 And now the question is how do we compute, how do we compute the eigenvector to the, 2 00:00:06,090 --> 00:00:10,990 to the, or the solution to this problem r equal N times r. 3 00:00:10,990 --> 00:00:14,700 So the way we, we proceed is the, is the following. 4 00:00:14,700 --> 00:00:17,730 So the method is called the power iteration method and 5 00:00:17,730 --> 00:00:22,089 it assumes that on the input we are given a big web graph on N nodes. 6 00:00:23,120 --> 00:00:28,150 Where nodes are red pages and directed links correspond to hyper, hyperlinks. 7 00:00:28,150 --> 00:00:33,200 And then we think we, the power iteration is a very simple iterative scheme. 8 00:00:33,200 --> 00:00:35,240 The way the, the whole thing works is the following. 9 00:00:35,240 --> 00:00:41,480 We will start with our vector r, I, I, I have this subscript r of 0, which simply 10 00:00:41,480 --> 00:00:46,220 means that this is the, this is measuring the time, how the iterations proceed. 11 00:00:46,220 --> 00:00:51,220 So r our initial guess of our ranking 12 00:00:51,220 --> 00:00:55,910 vector r is simply that all the components of it are 1 over N. 13 00:00:55,910 --> 00:00:57,610 So, where N is the number of nodes. 14 00:00:57,610 --> 00:01:01,874 So naturally the compo, the comp, the entries of r sum to 1. 15 00:01:02,920 --> 00:01:06,510 So now all we do is we iterate our, our recursive equation. 16 00:01:06,510 --> 00:01:12,180 So we say that values of r at time t plus 1 is the matrix M, the, 17 00:01:12,180 --> 00:01:18,900 the stochastic adjacency matrix, times our previous vector r, r, r t. 18 00:01:18,900 --> 00:01:20,420 And we keep iterating this. 19 00:01:20,420 --> 00:01:24,450 And basically all we are doing is we are iterating this r equals M times r. 20 00:01:24,450 --> 00:01:27,840 And we keep iterating this until r stops changing. 21 00:01:27,840 --> 00:01:31,910 So this means we keep iterating this until this sum of the, let's say, 22 00:01:31,910 --> 00:01:36,770 coordinate wise sum of the differences between the r of the current time step and 23 00:01:36,770 --> 00:01:40,150 r of the previous time step is less than epsilon. 24 00:01:40,150 --> 00:01:40,710 Right? 25 00:01:40,710 --> 00:01:45,080 So, and this is really, really all there is to the, to the page rank algorithm. 26 00:01:45,080 --> 00:01:50,750 We start with some guess of how our vector rank vector r is, 27 00:01:50,750 --> 00:01:55,600 then we multiply it with M usually around 50 or 100 times. 28 00:01:55,600 --> 00:02:00,270 And we keep monitoring how much does r change from one iteration to another, and 29 00:02:00,270 --> 00:02:02,430 when it stops changing, we stop. 30 00:02:02,430 --> 00:02:05,040 And, what we get is the page rank scores. 31 00:02:06,360 --> 00:02:11,170 So, of course if we have if we have this this algorithm, 32 00:02:11,170 --> 00:02:13,510 the question is how, how is this working? 33 00:02:13,510 --> 00:02:18,220 So let me just give you, give you an example using our old web graph idea. 34 00:02:18,220 --> 00:02:20,666 So, we have the three node web graph. 35 00:02:20,666 --> 00:02:23,286 We have, we have our matrix M here. 36 00:02:23,286 --> 00:02:28,732 We have the algorithm here on the left, a simple iteration as I mention before. 37 00:02:28,732 --> 00:02:31,008 And let me show how this would work. 38 00:02:31,008 --> 00:02:36,154 So, for example we start with r0 which is where the components of it are one-third, 39 00:02:36,154 --> 00:02:37,797 one-third, one-third. 40 00:02:37,797 --> 00:02:41,185 We multiply it with them and in the next time snap, so 41 00:02:41,185 --> 00:02:44,600 this will be r1, we would get the new vector. 42 00:02:44,600 --> 00:02:49,750 And then we could, we now compute r of, r, r of time 1 times M, 43 00:02:49,750 --> 00:02:54,760 we obtain r at time 2, and then again we would go multiply that again with M, 44 00:02:54,760 --> 00:02:57,690 would get r at time 3, and we would keep doing this. 45 00:02:57,690 --> 00:03:02,250 And at the end, r would actually converge to, to a vector that I will 46 00:03:02,250 --> 00:03:07,200 show you here where A and y nodes would 47 00:03:07,200 --> 00:03:12,290 have the importance of 6 over 15 and y would have the importance 3 over 15. 48 00:03:12,290 --> 00:03:16,100 Which is exactly the same values as we got before when we were actually trying to 49 00:03:16,100 --> 00:03:19,085 explicitly solve our system of flow equations, right? 50 00:03:19,085 --> 00:03:24,871 6 over 15 is the same as 3 3 over 3 51 00:03:24,871 --> 00:03:30,440 over 2 over 5 and 3 over 15 is 1 over 5. 52 00:03:30,440 --> 00:03:32,771 All right? So we got to the same solution as we had, 53 00:03:32,771 --> 00:03:36,370 as we got before when we were trying to solve a system of equation. 54 00:03:36,370 --> 00:03:39,810 But now we didn't really kind of solve the system of equations explicitly, 55 00:03:39,810 --> 00:03:43,810 we simply did this vector matrix multiplication multiple times. 56 00:03:43,810 --> 00:03:46,730 And the thing converge, converged somehow mira, 57 00:03:46,730 --> 00:03:49,490 miraculously to the values we wanted. 58 00:03:49,490 --> 00:03:55,160 So, so far we looked at page rank in terms of a matrix formulation. 59 00:03:55,160 --> 00:04:00,310 So we, we express the set of flow equations as a vector matrix product, and 60 00:04:00,310 --> 00:04:04,710 then we saw that, instead of solving the flow equations, we can kind of find the, 61 00:04:04,710 --> 00:04:09,940 the eigenvector of a matrix M, in this way find the page rank scores. 62 00:04:09,940 --> 00:04:12,700 So what we will do next is we will look at 63 00:04:12,700 --> 00:04:16,340 an interpretation of what the page rank scores mean. 64 00:04:16,340 --> 00:04:19,440 And this is called a random walk interpretation. 65 00:04:19,440 --> 00:04:23,700 So basically we will see that page rank scores are equivalent to 66 00:04:23,700 --> 00:04:28,290 a probability distribution of our random walker in a graph. 67 00:04:28,290 --> 00:04:32,910 So, before I tell you the details, here is, here is a way how to think about this. 68 00:04:32,910 --> 00:04:36,780 We are thinking about the web graph as a giant graph and 69 00:04:36,780 --> 00:04:40,310 we are thinking about the, the the surfer. 70 00:04:40,310 --> 00:04:44,520 So a surfer is simply a person who is basically randomly surfing this graph. 71 00:04:44,520 --> 00:04:49,520 Which means that a, a surfer comes to a given web pages, web page, looks at all 72 00:04:49,520 --> 00:04:53,920 the outgoing links, peaks one at random and, and moves to the next web page. 73 00:04:53,920 --> 00:04:57,370 And the server is kind of browsing these graph indefinitely. 74 00:04:57,370 --> 00:05:02,720 So the idea is that at some given time t, surfer is at some node i, and 75 00:05:02,720 --> 00:05:06,370 what the surfer will do in the next time step at time t plus 1, 76 00:05:06,370 --> 00:05:10,750 basically the surfer will follow an out-link from i, and 77 00:05:10,750 --> 00:05:15,740 choose this out-link uniformly at random out of all the out-links at of node i. 78 00:05:15,740 --> 00:05:16,250 Okay? 79 00:05:16,250 --> 00:05:18,750 And then, now the surfer is at node j. 80 00:05:18,750 --> 00:05:21,440 So what time t plus 1 surfer is at node j, and 81 00:05:21,440 --> 00:05:26,570 again looks at all the outgoing links of node j and follows one of them at random. 82 00:05:26,570 --> 00:05:31,570 So now what we can also think about is, we can think of this vector p of t. 83 00:05:31,570 --> 00:05:36,570 And this p of t can, we can, we, we think of this as a probability distribution over 84 00:05:36,570 --> 00:05:41,930 the nodes of the graph, which basically tells us with what probability is a given, 85 00:05:41,930 --> 00:05:44,339 is a walker at time t at the given node. 86 00:05:45,400 --> 00:05:45,970 Okay. So we 87 00:05:45,970 --> 00:05:50,130 can see that we every node in a graph has a value associated with it. 88 00:05:50,130 --> 00:05:55,210 And this value corresponds to the probability that at a given time t, 89 00:05:55,210 --> 00:05:57,730 the, the random walker is at that given node. 90 00:05:58,920 --> 00:05:59,640 Okay. 91 00:05:59,640 --> 00:06:04,330 So now that we have defined the process and we have defined the notion of p of t. 92 00:06:04,330 --> 00:06:06,270 Now the next question is to ask, 93 00:06:06,270 --> 00:06:10,070 where is the random walker going to be at time t plus 1? 94 00:06:10,070 --> 00:06:10,940 Okay? 95 00:06:10,940 --> 00:06:15,380 So given, given the probability distribution where the random walker is at 96 00:06:15,380 --> 00:06:17,308 time t, that is called p of t, 97 00:06:17,308 --> 00:06:21,960 the question is, where is the random walker going to be at the next time step? 98 00:06:21,960 --> 00:06:25,050 And the answer to this is actually very, very intuitive. 99 00:06:25,050 --> 00:06:26,190 So, we can ask, 100 00:06:26,190 --> 00:06:32,590 what is the probability that the random walker will be at node j at time t plus 1? 101 00:06:32,590 --> 00:06:35,968 So if we want to compute this, then all that for 102 00:06:35,968 --> 00:06:39,890 node j what we have to look at is what are all the nodes that point to j. 103 00:06:39,890 --> 00:06:44,090 What is the probability that the random walker was at any of these nodes i, 104 00:06:44,090 --> 00:06:45,570 that point to j? 105 00:06:45,570 --> 00:06:49,580 And at every node i, the random walker basically has to go and 106 00:06:49,580 --> 00:06:53,330 take, take this link that points towards node j. 107 00:06:53,330 --> 00:06:57,520 So this means that whatever is the, was the, was the, 108 00:06:57,520 --> 00:07:02,360 was the probability that a given node that the random walker was at a given node. 109 00:07:02,360 --> 00:07:07,460 Now the random walker has to pick the out-link that points to node j. 110 00:07:07,460 --> 00:07:11,950 So which means that, that what we are basically getting is, 111 00:07:11,950 --> 00:07:16,060 is exactly our page rank equation if you, if you want to think about it this way. 112 00:07:16,060 --> 00:07:20,140 Right so, so the probability that the random walker is at the given node. 113 00:07:20,140 --> 00:07:23,740 Is simply the sum of the probabilities that the random walker in previous time 114 00:07:23,740 --> 00:07:26,730 step was at the neighbors that point to given node. 115 00:07:26,730 --> 00:07:32,100 And from every given node, the, the random walker transitions to the node j 116 00:07:32,100 --> 00:07:37,550 with probability of 1 over the, 1 over the out degree of that given node. 117 00:07:37,550 --> 00:07:40,930 Which is exactly the page rank the page rank formulation. 118 00:07:40,930 --> 00:07:42,480 Right? So this means that the probability 119 00:07:42,480 --> 00:07:47,370 distribution of where the random walker is either time t plus 1 is simply our matrix 120 00:07:47,370 --> 00:07:52,170 M times the probability distribution where the random walker was at time t. 121 00:07:53,230 --> 00:07:56,480 So now let's suppose the following. 122 00:07:56,480 --> 00:07:57,930 Let's suppose that the, 123 00:07:57,930 --> 00:08:01,720 that the random walk reaches what is called the steady state. 124 00:08:01,720 --> 00:08:05,500 Which means the probability distribution at time t is, 125 00:08:05,500 --> 00:08:08,630 equals the probability distribution of time t plus 1. 126 00:08:08,630 --> 00:08:12,180 This means that probability, p of t is a stationary distribution. 127 00:08:12,180 --> 00:08:19,590 So, probability solution at time t plus 1 equals M times p of t equals back p of t. 128 00:08:20,760 --> 00:08:21,610 Okay? 129 00:08:21,610 --> 00:08:25,233 So what we, what we observe now is that this stationary, 130 00:08:25,233 --> 00:08:28,328 stationary probability distribution p of t is, 131 00:08:28,328 --> 00:08:33,476 is exactly what was our, our original formulation of a of a random walk. 132 00:08:33,476 --> 00:08:36,430 What before we had r equals M times r. 133 00:08:36,430 --> 00:08:40,860 Now we have p of, p of t equals M times p of t. 134 00:08:41,880 --> 00:08:45,040 Right? So this means that our rank vector r 135 00:08:45,040 --> 00:08:50,140 is a stationary distribution for this random walk process, okay? 136 00:08:50,140 --> 00:08:51,450 So, this about this a bit. 137 00:08:51,450 --> 00:08:54,310 So basically what page rank score corresponds to? 138 00:08:54,310 --> 00:08:58,410 They correspond to the probability that this random surfer, 139 00:08:58,410 --> 00:09:03,390 that infinitely long kind of walks the, walks the web graph at a given, at a, 140 00:09:03,390 --> 00:09:06,520 at some given time t resides at the given node. 141 00:09:06,520 --> 00:09:10,370 So this is what is called the page rank, the random walk interpretation of page 142 00:09:10,370 --> 00:09:15,180 rank, where we can think of a score or a rank of a given node to be the probability 143 00:09:15,180 --> 00:09:20,440 that the random walker is at that given node at some, at some fixed time t. 144 00:09:20,440 --> 00:09:24,520 So, another important consequence of this random walk interpretation is that 145 00:09:24,520 --> 00:09:27,770 there is a rich literature on random walks. 146 00:09:27,770 --> 00:09:31,990 And random walks are really called Markov processes, or first order Mark, order 147 00:09:31,990 --> 00:09:36,316 Markov processes, because basically they have very little, very little history. 148 00:09:36,316 --> 00:09:40,860 And the central, the result from the Markov processes or 149 00:09:40,860 --> 00:09:44,790 random walk literature is that under certain conditions, 150 00:09:44,790 --> 00:09:50,030 basically conditions under matrix M, the stationary distribution is unique, 151 00:09:50,030 --> 00:09:53,110 and it will eventually be reached no matter what is the, 152 00:09:53,110 --> 00:09:57,220 the initial probability dis, distribution at the time t equal 0. 153 00:09:57,220 --> 00:09:58,890 So, what does this mean? 154 00:09:58,890 --> 00:10:02,840 This means that there are certain conditions on the structure of our graph. 155 00:10:02,840 --> 00:10:05,770 On the structure of our matrix M. 156 00:10:05,770 --> 00:10:09,450 And if our matrix M satisfies these assumptions, 157 00:10:09,450 --> 00:10:12,580 then the stationary distribution we, is unique. 158 00:10:12,580 --> 00:10:17,580 Which means there is only one unique rank vec, page rank vector r. 159 00:10:17,580 --> 00:10:20,590 And this unique page rank vector r will be, 160 00:10:20,590 --> 00:10:23,950 will be achieved regardless of how we initialize it. 161 00:10:23,950 --> 00:10:29,280 Which means that our pay power iteration will always converge to the same vector, 162 00:10:29,280 --> 00:10:31,554 regardless of how we initialize it.