Analysis of iterative methods in PageRank computation

Abstract

PageRank is one of the basic metric used in web search technology to rank the web pages. It uses power method to compute principal eigenvector of the web matrix of several billion nodes. PageRank method incorporates a parameter α called damping factor that plays a major role in PageRank computation. In this study, we have observed experimentally the efficiency of various iterative methods on hyperlink graph for different value of α. We conclude from experiment that Power method is effective and more competitive for the well condition problem i.e. small value of α. However, for α → 1 Power method becomes more complex, and other methods such as Aitken-Power, SOR, and Gauss-Seidel are more efficient than it in respect of CPU time as well as the number of iteration needed for convergence.

Keywords:

• PageRank method
• Iterative methods
• Extrapolation methods
• Large and Sparse linear system
• Web search engine

Mathematics Subject Classification 2010:

• 68U35
• 65F10