Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

PART I WORLD WIDE WEB > Chapter 3 The Second Eigenvalue of the Google Matrix - Pg. 15

Chapter Three The Second Eigenvalue of the Google Matrix 3.1 INTRODUCTION Before attempting to accelerate the computation of PageRank, it is useful first to prove some results regarding the convergence rate of the standard PageRank algorithm. In this chapter, we determine analytically the modulus of the second eigenvalue for the Web hyperlink matrix used by Google for computing PageRank. This has implications for the convergence rate of the standard PageRank algo- rithm as the Web scales, for the stability of PageRank to perturbations to the link structure of the Web, for the detection of Google spammers, and for the design of algorithms to speed up PageRank. For the purposes of accelerating PageRank, perhaps the most useful result that comes out of this chapter is that the convergence rate of the standard PageRank algorithm is already very fast, and will remain so as the Web scales. Since the Web matrix is highly sparse, and since we show here that the number of iterations k that the Power Method takes to converge is much less than the dimensionality n of the