2. The PageRank Algorithm (continued)

The Iterative Computation of PageRank

Because of the size of the actual web, the Google search engine uses an approximative, iterative computation of PageRank values. This means that each page is assigned an initial starting value and the PageRanks of all pages are then calculated in several computation circles based on the equations determined by

the PageRank algorithm. The iterative calculation shall again be illustrated by our three-page example, whereby each page is assigned a starting PageRank value of 1.

Iteration 0 1 2 3 4 5 6 7 8 9 10 11 12	PR(A) 1 1 1.0625 1.07421875 1.07641602 1.07682800 1.07690525 1.07691973 1.07692245 1.07692296 1.07692305 1.07692307 1.07692308	PR(B) 1 0.75 0.765625 0.76855469 0.76910400 0.76920700 0.76922631 0.76922993 0.76923061 0.76923074 0.76923076 0.76923077 0.76923077	PR(C) 1 1.125 1.1484375 1.15283203 1.15365601 1.15381050 1.15383947 1.15384490 1.15384592 1.15384611 1.15384615 1.15384615 1.15384615

We see that we get a good approximation of the real PageRank values after only a few iterations. According to publications of Lawrence Page and Sergey Brin, about 100 iterations are necessary to get a good approximation of the PageRank values of the whole web.

Also, by means of the iterative calculation, the sum of all pages' PageRanks still converges to the total number of web pages. So the average PageRank of a web page is 1. The minimum PageRank of a page is given by (1-d). Therefore, there is a maximum PageRank for a page which is given by dN+(1-d), where N is total number of web pages. This maximum can theoretically occur, if all web pages solely link to one page, and this page also solely links to itself.

Next Article Segment
3. The Implementation of PageRank

This article reproduced with permission of eFactory.
© 2002 eFactory Internet-Agentur KG Online-Marketing - written by Markus Sobek
PageRank and Google are trademarks of Google Inc., Mountain ViewCA, USA.
PageRank is protected by US Patent 6,285,999.