Local approximation of pagerank and reverse pagerank

ABSTRACT

We consider the problem of approximating the PageRank of a target node using only local information provided by a link server. This problem was originally studied by Chen, Gan, and Suel (CIKM 2004), who presented an algorithm for tackling it. We prove that local approximation of PageRank, even to within modest approximation factors, is infeasible in the worst-case, as it requires probing the link server for Ω(n) nodes, where n is the size of the graph. The difficulty emanates from nodes of high in-degree and/or from slow convergence of the PageRank random walk.

We show that when the graph has bounded in-degree and admits fast PageRank convergence, then local PageRank approximation can be done using a small number of queries. Unfortunately, natural graphs, such as the web graph, are abundant with high in-degree nodes, making this algorithm (or any other local approximation algorithm) too costly. On the other hand, reverse natural graphs tend to have low in-degree while maintaining fast PageRank convergence. It follows that calculating Reverse PageRank locally is frequently more feasible than computing PageRank locally.

We demonstrate that Reverse PageRank is useful for several applications, including computation of hub scores for web pages, finding influencers in social networks, obtaining good seeds for crawling, and measurement of semantic relatedness between concepts in a taxonomy.

REFERENCES

• 1: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece [doi>10.1145/380752.380810]
• 2: A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.
• 3: P. Berkhin. A survey on PageRank computing. Internet Mathematics, 2(1):73--120, 2005.
• 4: Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
• 5: A. Z. Broder , R. Lempel , F. Maghoul , J. Pedersen, Efficient PageRank approximation via graph aggregation, Information Retrieval, v.9 n.2, p.123-138, March 2006 [doi>10.1007/s10791-006-7146-1]
• 6: Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X]
• 7: Ran Canetti , Guy Even , Oded Goldreich, Lower bounds for sampling algorithms for estimating the average, Information Processing Letters, v.53 n.1, p.17-25, Jan. 13, 1995 [doi>10.1016/0020-0190(94)00171-T]
• 8: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1623-1640, May 17, 1999
• 9: 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]
• 10: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Computer Networks and ISDN Systems, v.30 n.1-7, p.161-172, April 1, 1998
• 11: Anirban Dasgupta , Arpita Ghosh , Ravi Kumar , Christopher Olston , Sandeep Pandey , Andrew Tomkins, The discoverability of the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242630]
• 12: Jason V. Davis , Inderjit S. Dhillon, Estimating the global pagerank of web communities, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150419]
• 13: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1467-1479, May 17, 1999
• 14: Stephen Dill , Ravi Kumar , Kevin S. Mccurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the web, ACM Transactions on Internet Technology (TOIT), v.2 n.3, p.205-223, August 2002 [doi>10.1145/572326.572328]
• 15: D. Fogaras. Where to start browsing the Web? In IICS, pages 65--79, 2003.
• 16: E. Gabrilovich and S. Markovitch. Computing semantic relatedness using wikipedia-based explicit semantic analysis. In Proc. 20th IJCAI, pages 250--257, 2007.
• 17: Zoltán Gyöngyi , Hector Garcia-Molina , Jan Pedersen, Combating web spam with trustrank, Proceedings of the Thirtieth international conference on Very large data bases, p.576-587, August 31-September 03, 2004, Toronto, Canada
• 18: Taher H. Haveliwala, Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search, IEEE Transactions on Knowledge and Data Engineering, v.15 n.4, p.784-796, July 2003 [doi>10.1109/TKDE.2003.1208999]
• 19: T. H. Haveliwala and S. D. Kamvar. The second eigenvalue of the Google matrix. Technical report, Stanford University, 2003.
• 20: A. Java, P. Kolari, T. Finin, and T. Oates. Modeling the spread of influence on the Blogosphere. Technical report, University of Maryland, Baltimore County, 2006.
• 21: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 22: S. Kamvar, H. Haveliwala, and G. Golub. Adaptive methods for the computation of PageRank. Linear Algebra and its Applications, 386:51--65, 2004.
• 23: C. Kohlschütter, P. A. Chirita, and W. Nejdl. Efficient parallel computation of PageRank. In Proc. 28th ECIR, pages 241--252, 2006.
• 24: G. Kollias and E. Gallopoulos. Asynchronous computation of PageRank computation in an interactive multithreading environment. In Web Information Retrieval and Linear Algebra Algorithms, 2007.
• 25: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 26: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, The Web and Social Networks, Computer, v.35 n.11, p.32-36, November 2002 [doi>10.1109/MC.2002.1046971]
• 27: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 28: Josiane Xavier Parreira , Debora Donato , Sebastian Michel , Gerhard Weikum, Efficient and decentralized PageRank approximation in a peer-to-peer web search network, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 29: R. Rada, H. Mili, E. Bicknell, and M. Blettner. Development and application of a metric on semantic nets. IEEE Trans. on Systems, Man and Cybernetics, 19(1):17--30, 1989.
• 30: M. Ángeles Serrano , Ana Maguitman , Marián Boguñá , Santo Fortunato , Alessandro Vespignani, Decoding the structure of the WWW: A comparative analysis of Web crawls, ACM Transactions on the Web (TWEB), v.1 n.2, p.10-es, August 2007 [doi>10.1145/1255438.1255442]
• 31: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 32: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 33: M. Strube and S. P. Ponzetto. WikiRelate! computing semantic relatedness using Wikipedia. In AAAI 2006, pages 1419--1424, 2006.
• 34: Yuan Wang , David J. DeWitt, Computing pagerank in a distributed internet search system, Proceedings of the Thirtieth international conference on Very large data bases, p.420-431, August 31-September 03, 2004, Toronto, Canada
• 35: Y. Wu. Subgraphrank: PageRank approximation for a subgraph or in a decentralized system. VLDB PhD workshop, 2007.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
local approximation, lower bounds, pagerank, reverse pagerank