The PageRank Algorithm

PageRank extends the idea behind the InDegree algorithm by assigning different weights to the links. Links from high quality pages should make a stronger impact on the rank of a page. Therefore it is not only important how many incoming links a page has, but also how important the pointing pages are.

To determine the authority of internet pages PageRank simulates the behavior of a random web-surfer, by starting its walk from some random page and then following the outgoing links. The starting point is usually drawn from a uniform distribution, but other distributions can be used as well. The process of the random walk is as follows: at the starting point an outgoing link is randomly chosen and the surfer follows it with a probability 1-d. With probability d the surfer jumps to another random page without following any link (“gets bored clicking links”). The parameter d is called “the dumping factor”, its value can vary but generally it is assumed that equals 0.85.

The PageRank of a page is calculated by a formula given below:

The algorithm considers a set of interlinked pages M(p_i) with the number of elements N. PR(p_j) is the PageRank of a page p_j in the set, and L(p_j) is the number of outgoing links on that page. Each page that passes to p_i a fraction of its own PageRank depending on how many other pages it links to.

The incoming links in the set M(p_i) can be presented in a form of adjacency matrix:

Where l(p₁,p₂) equals 1 if there is a link between pages p₁ and p₂ and zero otherwise. PageRanks of all the pages in the set M(p_i) form a vector R, which is the dominant eigenvector to the adjacency matrix.

Then the PageRank formula can be written as:

PageRank values are precomputed and do not depend on search queries. When it is necessary to rank the results for some search term PageRank is used in conjunction with query specific scores. Having the PageRank scores precomputed allows faster results sorting.

References

• Borodin, A, Roberts, G.O., Rosenthal, J.S. and Tsaparas, P. ‘Finding authorities and hubs from link structures on the World Wide Web’. In Proceedings of the 10 th International World Wide Web Conference, Hong Kong, May 2001. Available at http://citeseer.ist.psu.edu/borodin01finding.html
• Wikipedia: PageRank