Inside Google: PageRank Algorithm Explained by Rachid Guerraoui

[00:00:03]what happens if you google Michael Jackson you will get dozens of pages about Michael Jackson these pages will all talk about the popstar it's very likely that you won't be surprised you would find that the normal because it's likely that that's what you were expecting but if you think about it you might be surprised why because there are thousands of Jackson's in the world and maybe there are actually hundreds of Michael Jackson's with web pages the taxi driver the architect the engineer why don't we ever get any of these why do we get the popstar Michael Jackson and as I pointed out we want to be surprised because this is very likely what we want the reason is that Google has a way of scoring the pages such that those that are considered important are returned first and the success of Google is an algorithm that is called PageRank that measures this importance rank is for ranking and page for both the pages on the web as well as the name of one of the founder of the company Larry Page so I'm gonna explain intuitively how Google ranks pages and how this algorithm performs in order to understand the PageRank algorithm it's important to recall that the web is a set of pages and these pages have links or pads that connect them so when PageRank decides which page is considered the most important it exploits these paths between them today we estimate that there are about ten to twelve pages indexed on the web so index it means we consider it the important keywords in these pages and we classified them according to those index typical index is Michael Jackson so one day we may reach the famous Google map number so how does PageRank exploit these paths I will explain that in four steps the first thing to understand when we try to compute the PageRank of a page P is the following we sum all the link of all the paths from pages to the page P so if a page here P has one link then the first step in our reasoning says that the page rank of P would be 1 if there are 2 links towards this page this would be 2 and so forth intuitively the idea is the following if somebody ends up in a given page here then the existent of this path means that this user is likely to walk towards the page P so we think of it as a random walk and these paths model somehow the fact that the user will has some probability of ending up in the page P this is the first step the second step in this reasoning is the following assume somebody's a random worker is here if there is a single path from this page to this page then this page is likely more likely to be reached than if there is another link from this page to this page so the number of outgoing links from a page just decreases if this number is high the probability of ending up in page P so the second step in the reasoning is that we need to divide this number here by the number of outgoing links from the page P I that points to page P now an important factor and this is the third step on a reasoning is the following a page P is more likely to be reached if there is a path to this page from a page that is already that already has a big page rank itself which means that there is a high probability of which in this page and this is captured in this equation but by the recursive function that says that the score or the patriarch of a page P is the sum of the page ranks of the page P I have a path to page P divided by the outcome outgoing links from people so this is the third step but there is still one missing point so the last step in this reasoning consists in accounting for the fact that this random walk will he worker here could not only go to this page P on this page P prime but could also be teleported or fly to another page cube and this is captured by what we call sometimes a damping factor and the actual formula to compute the page rank of a page P accounting for the ability of a random worker to go somewhere else is that to be the following and D is typically considered to be 0.85 which actually says that after every six pages that we reach through pads we may go to another page chosen at random this number n denotes the total number of considerable pages and the nice thing about this formula is that if we sum all the scores we will end up with one which actually means that the scores represent probability distribution so I'm gonna illustrate here how we compute these scores or these page ranks on a single simple example consider a very simple case of two pages a and B which point into the other one computing their page rank consists in solving the following equation page rank of a equals 1 minus D remember that D was 0.85 so which 1.15 over the total number of pages considered plus D which is five times the page rank of be added by one the total number of outgoing links from the same thing for page rank of P exactly the same so if we solve this system of equations we end up with PR of a which is 0.5 and the PR of P which is 0.5 they all have the same score or they have all have the same importance so page rank will return both of them if they have the same index and this index correspond to the quality it's important to see here that no matter how we start from page rank of a and the page rank of P as long as their sum equals 1 we will end up with 0.5 in both cases this is because we apply the fixed point theorem which ensure that no no matter where we start we'll end up with a single solution to the problem so for instance if we start from the air of a equals zero and P are of B equals one then after a first iteration we will compute for instance that PR of B equals 0.15 over 2 which is 0 75 and PR of a will be 0.0 75 plus 0 85 which is 0 9 25 or if we want 1 minus 0 0 75 7 iteration and that we can quickly here will yield the art of equals 0 87 and be part of be roughly 13 after a few into iteration we will end up with 0.5 for a and 0.5 for B so now assume a slightly more sophisticated scenario where we add another page C and assume for instance that C has a path to a in this case PR of a will be 0.15 over 3 because we consider three pages plus 0.85 times the number of pages that point a which is P part of B over the number of outgoing links from P which is 1 plus P R of C which is the number of outgoing links from C which is 1 same thing of PR of be 0.15 power 3 0.85 times the number of pages that points to P which is PR of a times the outcome links from a and finally the RFC will be 0.15 over to know page has a path to see so here the way we could solve this problem is starting from page rank of a equals 0.5 page rank of B equals 0.5 and page rank of C equals 0 the sum equals 1 after a few iteration we will end up with PR of a which is 0 that 496 PR be equal to 0.40 3 and PR of C 0 dot 0 the sum again equals one and what's not surprising is that PR of C is pretty small PR of B and PR of a are roughly the same with the slight advantage to PR of a because there is not going linked to a but the outgoing links comes from a page with a very small page running so the difference between a and B is roughly the same we can of course consider a slightly more complicated scenario for instance if after some point B points to C so there is a path from B to C and a also points to see in this new scenario the page rank of a of course changes because here the number of outgoing links from B becomes to the page rank of B also changes because the number of outgoing links from a is now 2 and the page rank of C also changes because now see has two links pointing to it so we need to account for the page rank of a over 2 plus the page rank of B over 2 so the new scores we end up with are the page rank of a and you can check this out of situations the paid page rank of a of 0 that 432 page rank of B 0 but 233 and the page rank of C 0 it might be obvious to see why the page rank of C is significantly higher than that of B this is B because b has one link point into it and C has two but one one mate wonder why the page rank of C is lower than that of a and this is because of this link this link is much more important than the link from A to C because a has two links to outgoing links one from B one towards B and one towards C and these the existence of two links dilute a little bit the power of this one whereas he has only one link towards a and that's why a ends up with the highest score so if Google has to choose it will choose this a to return to the Googler so for instance if this is Michael Jackson and this is Michael Jackson and this is Michael Jackson so Google will interpret this as the most important link the most important page and it's very likely that this will be the pop star