Friday, November 24, 2006

Getting Technical: PageRank and Random Surfers

The PageRank formula can be thought of as a model of user behavior of "random surfers." Such a random surfer visits a random web page, keeps clicking links randomly, never clicking the back button, and eventually gets bored enough to visit a new random page by typing in the web address into the browser. The probability that the random surfer visits a particular page is its PageRank. The probability at each page that the random surfer will get bored and request a new random page is called the damping factor¸ represented by d in the formula.

Put this way, the PageRank for a specific web page can clearly be calculated by going through all the inbound links to a page, calculating the PageRanks of all these pages, backing up to calculate the inbound links in turn to the new set of pages, and so on, all the way back until there are no more inbound links. A little more technically, a web page's PageRank can be calculated by iterating recursively through all of its inbound linked pages. This is the fundamental method behind Google's search engine, although in the real world (as you likely know if you've read this far in this sidebar) there are usually non-recursive techniques that calculate results more quickly than the corresponding recursive algorithm.

The original formula for PageRank with further explanation is contained in the Brin and Page page at Stanford University (http://wwwdb.stanford.edu/~backrub/google.html). Here it is (PR stands for PageRank; A stands for a random page, identified as Page A; T1. . .Tn signifies all the pages that link to Page A; C(A) represents the number of Page A's outbound links):

PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + d(PR(Tn)/C(Tn)

PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks is one.

The formula for PageRank has, of course, evolved since this formulationand, as I've mentioned, now involves more than 100 variablesand its exact nature is part of Google's proprietary technology. It's still the case that the best insight for SEO purposes into how Google works come from this early academic formulation.

0 comments:

Back Page Next Page Back to homepage