{"id":511,"date":"2008-12-09T15:34:14","date_gmt":"2008-12-09T19:34:14","guid":{"rendered":"http:\/\/michaelnielsen.org\/blog\/?p=511"},"modified":"2008-12-09T15:55:14","modified_gmt":"2008-12-09T19:55:14","slug":"lectures-on-the-google-technology-stack-2-building-our-pagerank-intuition","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/lectures-on-the-google-technology-stack-2-building-our-pagerank-intuition\/","title":{"rendered":"Lectures on the Google Technology Stack 2: Building our PageRank Intuition"},"content":{"rendered":"

This is one in a series of posts about the Google Technology Stack – PageRank, MapReduce, and so on – based on a lecture series I’m giving in 2008 and 2009. If you’d like to know more about the series, please see the course syllabus<\/a>. There is a FriendFeed room for the series here<\/a>. <\/p>\n

In today’s lecture, we’ll build our intuition about PageRank. We’ll figure out the minimal and maximal possible values for PageRank; study how PageRank works for a web with a random link structure, seeing a sort of “central limit theorem” for PageRank emerge; and find out how spammers can spam PageRank, and how to defeat them. <\/p>\n

Building our PageRank Intuition<\/h2>\n

In the last lecture we defined PageRank, but we haven’t yet developed a deep understanding. In this lecture we’ll build our intuition, working through many basic examples of PageRank in action, and answering many fundamental questions.<\/p>\n

The minimal and maximal values for PageRank<\/h3>\n

Recall from last lecture that the PageRank vector [tex]q[\/tex] is an [tex]N[\/tex]-dimensional probability distribution, with the probability [tex]q_j[\/tex] measuring the importance of webpage [tex]j[\/tex]. Because [tex]q[\/tex] is a probability distribution, the total of all the probabilities must add up to one, and so the average PageRank is [tex]1\/N[\/tex].<\/p>\n

It’s interesting that we can get this precise value for the average PageRank, but what we’d really like is more detailed information about the way PageRank behaves for typical pages. Let’s start by studying the minimal<\/em> and maximal<\/em> possible values for PageRank.<\/p>\n

Intuitively, we expect that the minimal value for PageRank occurs when a page isn’t linked to by any other page. This intuition can be made more rigorous as follows. Recall our definition of PageRank using a websurfer randomly surfing through webpages. At any given step of their random walk, the crazy websurfer has a probability at least [tex]t P_j[\/tex] of teleporting to vertex [tex]j[\/tex], and thus we must have<\/p>\n

[tex] q_j \\geq t P_j [\/tex]<\/p>\n

for all pages [tex]j[\/tex]. Furthermore, it’s possible for the PageRank to be equal to this value if, for example, no other pages link to page [tex]j[\/tex]. Thus [tex]tP_j[\/tex] is the minimal value for the PageRank of page [tex]j[\/tex]. A more algebraic way of putting this argument is to recall from the last lecture that [tex]tP = (I-sG)q[\/tex], and thus [tex]t P_j = q_j – s(Gq)_j \\leq q_j[\/tex], since [tex](Gq)_j \\geq 0[\/tex]. For the original PageRank algorithm, [tex]P_j = 1\/N[\/tex], and so the minimal PageRank is [tex]t\/N[\/tex] for all webpages, a factor [tex]t[\/tex] smaller than the average PageRank.<\/p>\n

Exercises<\/h3>\n