Inside PageRank

ABSTRACT

Although the interest of a Web page is strictly related to its content and to the subjective readers' cultural background, a measure of the page authority can be provided that only depends on the topological structure of the Web. PageRank is a noticeable way to attach a score to Web pages on the basis of the Web connectivity. In this article, we look inside PageRank to disclose its fundamental properties concerning stability, complexity of computational scheme, and critical role of parameters involved in the computation. Moreover, we introduce a circuit analysis that allows us to understand the distribution of the page score, the way different Web communities interact each other, the role of dangling pages (pages with no outlinks), and the secrets for promotion of Web pages.

REFERENCES

• 1: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 2: Monica Bianchini , Stefano Fanelli , Marco Gori, Optimal Algorithms for Well-Conditioned Nonlinear Systems of Equations, IEEE Transactions on Computers, v.50 n.7, p.689-698, July 2001 [doi>10.1109/12.936235]
• 3: Björck, A. 1996. Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics.
• 4: Immanuel M. Bomze , Walter Gutjahr, The dynamics of self-evaluation, Applied Mathematics and Computation, v.64 n.1, p.47-63, Aug. 1994 [doi>10.1016/0096-3003(94)90138-4]
• 5: Bomze, I. and Gutjahr, W. 1995. Estimating qualifications in a self-evaluating group. Qual. Quant. 29, 241--250.
• 6: Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, Proceedings of the 10th international conference on World Wide Web, p.415-429, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372096]
• 7: Brin, S., Motwani, R., Page, L., and Winograd, T. 1998. What can you do with a web in your pocket? IEEE Bulle. Techn. Comm. Data Eng., IEEE Comput. Soc. 21, 2, 37--47.
• 8: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 9: Brin, S., Page, L., Motwani, R., and Winograd, T. 1999. The PageRank citation ranking: Bringing order to the Web. Tech. Rep. 1999-66, Stanford University. Available on the Internet at http://dbpubs.stanford.edu:8090/pub/1999-66.
• 10: David Cohn , Huan Chang, Learning to Probabilistically Identify Authoritative Documents, Proceedings of the Seventeenth International Conference on Machine Learning, p.167-174, June 29-July 02, 2000
• 11: Cohn, D. and Hofmann, T. 2001. The missing link---A probabilistic model of document content and hypertext connectivity. In Neural Inf. Proc. Syst. 13.
• 12: Michelangelo Diligenti , Marco Gori , Marco Maggini, Web page scoring systems for horizontal and vertical search, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511512]
• 13: Golub, G. H. and Van Loan, C. F. 1993. Matrix computation. The Johns Hopkins University Press.
• 14: Haveliwala, T. H. 1999. Efficient computation of pagerank. Tech. Rep. 1999-66, Stanford University. Available on the Internet at http://dbpubs.stanford.edu:8090/pub/1999-66.
• 15: 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]
• 16: Monika R. Henzinger, Hyperlink Analysis for the Web, IEEE Internet Computing, v.5 n.1, p.45-50, January 2001 [doi>10.1109/4236.895141]
• 17: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 18: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.387-401, June 2000, Amsterdam, The Netherlands
• 19: Massimo Marchiori, The quest for correct information on the Web: hyper search engines, Computer Networks and ISDN Systems, v.29 n.8-13, p.1225-1235, Sep. 1997
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: Ng, A. Y., Zheng, A. X., and Jordan, M. I. 2001a. Link analysis, eigenvectors and stability. In Proceedings of International Conference on Research and Development in Information Retrieval (SIGIR 2001). ACM, New York.
• 22: Ng, A. Y., Zheng, A. X., and Jordan, M. I. 2001b. Stable algorithms for link analysis. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'2001).
• 23: Glen Pringle , Lloyd Allison , David L. Dowe, What is a tall poppy among Web pages?, Computer Networks and ISDN Systems, v.30 n.1-7, p.369-377, April 1, 1998
• 24: Richardson, M. and Domingos, P. 2002. The intellingent surfer: probabilistic combination of link and content information in pagerank. In Advances in Neural Information Processing Systems, 14. MIT Press, Cambridge, Mass.
• 25: Rumelhart, D., Hinton, G., and Williams, R. 1986. Learning representations by back-propagating errors. Nature 323, 533--536.
• 26: Seneta, E. 1981. Non-negative matrices and Markov chains. Springer-Verlag, New York, Chap. 4, pp. 112--158.
• 27: Varga, R. S. 1962. Matrix Iterative Analysis. Prentice--Hall, Englewood Cliffs, N.J.
• 28: Dell Zhang , Yisheng Dong, An efficient algorithm to rank Web resources, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.449-455, June 2000, Amsterdam, The Netherlands

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: Navigation

Keywords:
Information retrieval, Markov chains, PageRank, Web page scoring, search engines, searching the Web