Estimating the global pagerank of web communities

ABSTRACT

Localized search engines are small-scale systems that index a particular community on the web. They offer several benefits over their large-scale counterparts in that they are relatively inexpensive to build, and can provide more precise and complete search capability over their relevant domains. One disadvantage such systems have over large-scale search engines is the lack of global PageRank values. Such information is needed to assess the value of pages in the localized search domain within the context of the web as a whole. In this paper, we present well-motivated algorithms to estimate the global PageRank values of a local domain. The algorithms are all highly scalable in that, given a local domain of size n, they use O(n) resources that include computation time, bandwidth, and storage. We test our methods across a variety of localized domains, including site-specific domains and topic-specific domains. We demonstrate that by crawling as few as n or 2n additional pages, our methods can give excellent global PageRank estimates.

REFERENCES

• 1: Ricardo Baeza-Yates , Carlos Castillo , Mauricio Marin , Andrea Rodriguez, Crawling a country: better strategies than breadth-first for web page ordering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062768]
• 2: P. Boldi, M. Santini, and S. Vigna. Do your worst to make the best: paradoxical effects in pagerank incremental computations. Workshop on Web Graphs, 3243:168--180, 2004.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceeding of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
• 5: Yen-Yu Chen , Qingqing Gan , Torsten Suel, Local methods for estimating pagerank values, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031248]
• 6: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Proceedings of the seventh international conference on World Wide Web 7, p.161-172, April 1998, Brisbane, Australia
• 7: T. H. Haveliwala and S. D. Kamvar. The second eigenvalue of the Google matrix. Technical report, Stanford University, 2003.
• 8: T. Joachims, F. Radlinski, L. Granka, A. Cheng, C. Tillekeratne, and A. Patel. Learning retrieval functions from implicit feedback. http://www.cs.cornell.edu/People/tj/career.
• 9: S. D. Kamvar, T. H. Haveliwala, C. D. Manning, and G. H. Golub. Exploiting the block structure of the web for computing pagerank. World-Wide Web Conference, 2003.
• 10: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 11: A. N. Langville and C. D. Meyer. Deeper inside pagerank. Internet Mathematics, 2004.
• 12: Amy N. Langville , Carl D. Meyer, Updating Markov Chains with an Eye on Google's PageRank, SIAM Journal on Matrix Analysis and Applications, v.27 n.4, p.968-987, 2006 [doi>10.1137/040619028]
• 13: P. Lyman, H. R. Varian, K. Swearingen, P. Charles, N. Good, L. L. Jordan, and J. Pal. How much information 2003? School of Information Management and System, University of California at Berkely, 2003.
• 14: Frank McSherry, A uniform approach to accelerated PageRank computation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060829]
• 15: C. D. Meyer, Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems, SIAM Review, v.31 n.2, p.240-272, June 1989 [doi>10.1137/1031050]
• 16: US News and World Report. http://www.usnews.com.
• 17: Dmoz open directory project. http://www.dmoz.org.
• 18: Nutch open source search engine. http://www.nutch.org.
• 19: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 20: Sriram Raghavan , Hector Garcia-Molina, Crawling the Hidden Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.129-138, September 11-14, 2001
• 21: Thanh Tin Tang , David Hawking , Nick Craswell , Kathy Griffiths, Focused crawling for both topical relevance and quality of medical information, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099583]
• 22: Y. Wang and D. J. DeWitt. Computing pagerank in a distributed internet search system. Proceedings of the 30th VLDB Conference, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Experimentation

Keywords:
Markov chain, page rank, stochastic complementation