BrowseRank: letting web users vote for page importance

ABSTRACT

This paper proposes a new method for computing page importance, referred to as BrowseRank. The conventional approach to compute page importance is to exploit the link graph of the web and to build a model based on that graph. For instance, PageRank is such an algorithm, which employs a discrete-time Markov process as the model. Unfortunately, the link graph might be incomplete and inaccurate with respect to data for determining page importance, because links can be easily added and deleted by web content creators. In this paper, we propose computing page importance by using a 'user browsing graph' created from user behavior data. In this graph, vertices represent pages and directed edges represent transitions between pages in the users' web browsing history. Furthermore, the lengths of staying time spent on the pages by users are also included. The user browsing graph is more reliable than the link graph for inferring page importance. This paper further proposes using the continuous-time Markov process on the user browsing graph as a model and computing the stationary probability distribution of the process as page importance. An efficient algorithm for this computation has also been devised. In this way, we can leverage hundreds of millions of users' implicit voting on page importance. Experimental results show that BrowseRank indeed outperforms the baseline methods such as PageRank and TrustRank in several tasks.

REFERENCES

• 1: Brian Amento , Loren Terveen , Will Hill, Does “authority” mean quality? predicting expert quality ratings of Web documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.296-303, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345603]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Monica Bianchini , Marco Gori , Franco Scarselli, Inside PageRank, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.92-128, February 2005 [doi>10.1145/1052934.1052938]
• 4: Paolo Boldi , Massimo Santini , Sebastiano Vigna, PageRank as a function of the damping factor, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060827]
• 5: 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
• 6: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 7: Z. Gyongyi and H. Garcia-Molina. Web spam taxonomy, 2005.
• 8: 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
• 9: T. Haveliwala. Efficient computation of pageRank. Technical Report 1999-31, 1999.
• 10: T. Haveliwala and S. Kamvar. The second eigenvalue of the google matrix, 2003.
• 11: T. Haveliwala, S. Kamvar, and G. Jeh. An analytical comparison of approaches to personalizing pagerank, 2003.
• 12: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 13: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 14: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 16: A. N. Langville and C. D. Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335--400, 2004.
• 17: 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]
• 18: 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.
• 19: J. A. Rice. Mathematical Statistics and Data Analysis (2nd ed.). Duxbery Press, 1995.
• 20: M. Richardson and P. Domingos. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank. In Advances in Neural Information Processing Systems 14. MIT Press, 2002.
• 21: S. E. Robertson. Overview of okapi projects. Journal of Documentatioin, 53(1):3--7, 1997.
• 22: W. J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton, N,J., 1994.
• 23: Z. K. Wang and X. Q. Yang. Birth and Death Processes and Markov Chains. Springer-Verlag, New York, 1992.
• 24: Ryen W. White , Mikhail Bilenko , Silviu Cucerzan, Studying the use of popular destinations to enhance web search interaction, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277771]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia

General Terms:
Algorithms, Experimentation, Theory

Keywords:
PageRank, Q-matrix, continuous-time Markov process, user behavior data, user browsing graph