Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Inside PageRank
Bianchini M., Gori M., Scarselli F. ACM Transactions on Internet Technology5 (1):92-128,2005.Type:Article
Date Reviewed: May 2 2005

Web searching continues to be a popular topic, of both commercial and academic interest. This paper presents an in-depth mathematical analysis of the properties of Google’s PageRank algorithm, which relies on the topological structure of the Web to calculate the relative value of a given Web page. In addition to the rigorous mathematical treatment, the paper provides insights into the implications of these calculations, and how they impact stability, computability, convergence, maintenance, and vulnerability.

The PageRank algorithm exploits the inherent properties of the Markovian matrices that represent the Web’s structure to calculate individual page ranks. The authors go on to show that it is possible to perform an optimal computation, based on the limited precision requirements imposed by the PageRank formula. This result is an important factor for the scalability of the PageRank algorithm. However, as pointed out by Langville and Meyer [1], “if the holy grail of real-time personalized search is ever to be realized, then drastic speed improvements must be made...”

The authors also introduce the notion of energy, and demonstrate the mathematical properties of this concept through the use of circuit analysis on a subgraph or community of Web pages. This analysis leads to some interesting properties, including the energy loss introduced by “dangling” pages, and “outlinks” from a given community. Following this line, the authors also detail mechanisms by which the PageRank can be increased (or decreased), to influence the relative ranking of the pages within the ranking system.

Indeed, one of the authors’ findings is the fact that the energy of a given target community can be driven to grow linearly with the growth of a “promoting community.” This results in a promotion mechanism that is very difficult to detect.

Another nugget suggested by this research is that hyperlinks to outside pages should be placed in pages with a small PageRank, in addition to a large number of internal links. This property, as well as others discussed by the authors, can be exploited to retain as much energy as possible in a given community, and may provide some insights for site designers.

With this paper, the authors provide a valuable resource for those interested in analyzing the behavior of, and optimizing, large-scale ranking algorithms, such as the one used by Google. The math should keep those interested in the theory busy, while the conclusions provide some practical advice for practitioners in the field.

Reviewer:  Kipp Jones Review #: CR131189 (0510-1146)
1) Langville, A.; Meyer, D. Deeper inside PageRank. Internet Mathematics 1, 3(2004), 335–400.
Bookmark and Share
  Featured Reviewer  
 
Computations On Discrete Structures (F.2.2 ... )
 
 
Information Filtering (H.3.3 ... )
 
 
Navigation (H.5.4 ... )
 
 
Hypertext/ Hypermedia (H.5.4 )
 
 
Information Search And Retrieval (H.3.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Computations On Discrete Structures": Date
The performance of algorithms for colouring planar graphs
Williams M., Milne K. The Computer Journal 27(2): 165-170, 1984. Type: Article
May 1 1985
A separator theorem for graphs of bounded genus
Gilbert J., Hutchinson J., Tarjan R. (ed) Journal of Algorithms 5(3): 391-407, 1984. Type: Article
May 1 1985
On the computational complexity of path cover problems
Ntafos S., Gonzalez T. Journal of Computer and System Sciences 29(2): 225-242, 1984. Type: Article
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy