| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2003-17 | ||
| Submitted on | 4th of March 2003 | ||
| Author | Kamvar, Sepandar; Haveliwala, Taher; Manning, Christopher; Golub, Gene | ||
| Title | Exploiting the Block Structure of the Web for Computing PageRank | ||
| Date of publication | 2003 | ||
| Published in | Stanford University Technical Report | ||
| Citation | Kamvar, Sepandar; Haveliwala, Taher; Manning, Christopher; Golub, Gene. Exploiting the Block Structure of the Web for Computing PageRank, Stanford University Technical Report, 2003. | ||
| Number of pages | 13 | ||
| Language | English | ||
| Project | Stanford InfoLab; Database Group; Natural Language Processing Group | ||
| Type | Technical Report | ||
| Subject group | Computer Science; Databases and the Web; Miscellaneous | ||
| Abstract | 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. | ||
| Keywords | PageRank, link analysis, eigenvector, markov chain | ||
| Contact address |
sdkamvar@stanford.edu taherh@cs.stanford.edu | ||
| Sponsored by |
This paper is based on work supported in part by the National Science Foundation under Grant No.\ IIS-0085896 and Grant No.\ CCR-9971010, and in part by the Research Collaboration between NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corporation and CSLI, Stanford University (research project on Concept Bases for Lexical Acquisition and Intelligently Reasoning with Meaning). | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |