Stanford InfoLab Publication Server

Exploiting the Block Structure of the Web for Computing PageRank

Kamvar, Sepandar and Haveliwala, Taher and Manning, Christopher and Golub, Gene (2003) Exploiting the Block Structure of the Web for Computing PageRank. Technical Report. Stanford.




The web link graph has a nested block structure: the vast majority of hyperlinks link pages on a host to other pages on the same host, and many of those that do not link pages within the same domain. We show how to exploit this structure to speed up the computation of PageRank by a 3-stage algorithm whereby (1)~the local PageRanks of pages for each host are computed independently using the link structure of that host, (2)~these local PageRanks are then weighted by the ``importance'' of the corresponding host, and (3)~the standard PageRank algorithm is then run using as its starting vector the weighted aggregate of the local PageRanks. Empirically, this algorithm speeds up the computation of PageRank by a factor of 2 in realistic scenarios. Further, we develop a variant of this algorithm that efficiently computes many different ``personalized'' PageRanks, and a variant that efficiently recomputes PageRank after node updates.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:PageRank, link analysis, eigenvector, markov chain
Subjects:Computer Science
Computer Science > Databases and the Web
Related URLs:Project Homepage, Project Homepage, Project Homepage,,
ID Code:579
Deposited By:Import Account
Deposited On:03 Mar 2003 16:00
Last Modified:24 Dec 2008 10:19

Download statistics

Repository Staff Only: item control page