{"id":516,"date":"2008-12-12T17:54:32","date_gmt":"2008-12-12T21:54:32","guid":{"rendered":"http:\/\/michaelnielsen.org\/blog\/?p=516"},"modified":"2008-12-12T19:55:44","modified_gmt":"2008-12-12T23:55:44","slug":"the-pagerank-distribution-for-the-web","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/the-pagerank-distribution-for-the-web\/","title":{"rendered":"The PageRank distribution for the web"},"content":{"rendered":"

The PageRank for a webpage is a probability between 0 and 1. The general idea<\/a> is that PageRank quantifies the importance of the page: the bigger the probability the more important the page. I was curious about what the PageRank distribution is across the web as a whole, and so I built a very simple model to investigate the question.<\/p>\n

Here’s the three assumptions that went into the model. <\/p>\n

1. I use just 200 webpages. The qualitative results don’t seem to vary much as the number of webpages increases further, and the results get both harder to interpret and harder to generate, so 200 seems like a good size.<\/p>\n

2. I assume that the number [tex]L[\/tex] of inbound links to any given webpage is governed by a Pareto probability distribution [tex]p(L) \\propto 1\/L^a[\/tex], with [tex]a = 2[\/tex]. This assumption is based on a paper by Adamic and Huberman<\/a>. Note that the data in that paper is a decade old, and more recent data should really be used. (An independently interesting question is how that exponent is changing over time, and why it changes.)<\/p>\n

3. I assume that the number of inbound links to each webpage is an independent random variable.<\/p>\n

With these assumptions, the histogram of PageRanks for a typical random web looks like this:<\/p>\n

<\/p>\n

Aggregating over multiple runs gives:<\/p>\n

<\/p>\n

There are a few notable things about these histograms.<\/p>\n

First, most pages have PageRank near the minimal possible value of [tex]0.15 * 1\/200 = 0.00075[\/tex] (see here<\/a> for an explanation of why that’s the minimal possible value.<\/p>\n

Second, the distribution of PageRanks drops off very fast. Because there are 200 webpages, and the PageRanks must sum to one (being probabilities), the “average” PageRank must be [tex]0.005[\/tex]. You can see from the histograms that the distribution has already dropped off quite a bit by the time you get to this PageRank: most pages have a PageRank quite a bit below the average. It’s a few very high PageRank pages that restore the average. <\/p>\n

Third, the page with the highest PageRank had a PageRank approximately 20 times higher than average PageRank.<\/p>\n

I haven’t done the analysis, but it looks pretty likely that the distribution of PageRanks for this model is itself approximated by a power law distribution. Curious.<\/p>\n

This post is part of an ongoing series<\/a> about the Google Technology Stack, covering technologies such as PageRank, MapReduce, the Google File System, and Bigtable. Posts appear on this blog once a week; there is an associated FriendFeed room<\/a> for discussion.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

The PageRank for a webpage is a probability between 0 and 1. The general idea is that PageRank quantifies the importance of the page: the bigger the probability the more important the page. I was curious about what the PageRank distribution is across the web as a whole, and so I built a very simple… Continue reading The PageRank distribution for the web<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[57],"tags":[],"class_list":["post-516","post","type-post","status-publish","format-standard","hentry","category-gts","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/516","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=516"}],"version-history":[{"count":0,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/516\/revisions"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=516"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=516"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=516"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}