A new paradigm for ranking pages on the world wide web

ABSTRACT

This paper describes a new paradigm for modeling traffic levels on the world wide web (WWW) using a method of entropy maximization. This traffic is subject to the conservation conditions of a circulation flow in the entire WWW, an aggregation of the WWW, or a subgraph of the WWW (such as an intranet or extranet). We specifically apply the primal and dual solutions of this model to the (static) ranking of web sites. The first of these uses an imputed measure of total traffic through a web page, the second provides an analogy of local "temperature", allowing us to quantify the "HOTness" of a page.

REFERENCES

• 1: A. Arasu, J. Novak, A. Tomkins and J. Tomlin, "PageRank Computation and the Structure of the Web: Experiments and Algorithms", Poster Proc. WWW2002, Hawaii, May 2002. http://www2002.org/CDROM/poster/173.pdf
• 2: R. Balescu, "Equilibrium and Nonequilibrium Statistical Mechanics", Wiley, NY (1975).
• 3: 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
• 4: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 5: Moses Charikar , Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, On targeting Markov segments, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.99-108, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301280]
• 6: R. S. Dembo, J. M. Mulvey and S. A. Zenios, "Large-Scale Nonlinear Network Models and Their Application", Operations Research37, 353--372 (1989).
• 7: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 8: B. C. Eaves, A. J. Hoffman, U. G. Rothblum and H. Schneider, "Line-sum-symmetric Scalings of Square Non-negative Matrices", Math. Prog. Studies 25, 124--141 (1985).
• 9: Ronald Fagin, Combining fuzzy information: an overview, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565143]
• 10: W. Feller, An Introduction to Probability Theory and its Applications, Vol 1 (3rd edition), Wiley, NY (1968).
• 11: L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, (1962).
• 12: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 13: E. Jaynes, "Information Theory and Statistical Mechanics", Physical Review 106, 620--630 (1957).
• 14: 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]
• 15: L. Page, S. Brin, R. Motwani and T. Winograd "The PageRank Citation Ranking: Bringing Order to the Web", Stanford Digital Library working paper SIDL-WP-1999-0120 of 11/11/1999). See: http://dbpubs.stanford.edu/pub/1999-66.
• 16: R. B. Potts and R. M. Oliver, Flows in Transportation Networks, Academic Press, New York (1972).
• 17: M. H. Schneider, Matrix scaling, entropy minimization, and conjugate duality (II): the dual problem, Mathematical Programming: Series A and B, v.48 n.1, p.103-124, Mar. 1990 [doi>10.1007/BF01582253]
• 18: Michael H. Schneider , Stavros A. Zenios, A comparative study of algorithms for matrix balancing, Operations Research, v.38 n.3, p.439-455, May/June 1990 [doi>10.1287/opre.38.3.439]
• 19: E. Schrödinger, Statistical Thermodynamics, Dover edition, Mineola, NY (1989).
• 20: C. E. Shannon, "A Mathematical Theory of Communication", Bell Systems Tech. J. 27, 379, 623 (1948).
• 21: John A. Tomlin, An entropy approach to unintrusive targeted advertising on the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.767-774, June 2000, Amsterdam, The Netherlands
• 22: A. G. Wilson, "Notes on Some Concepts in Social Physics", Regional Science Association: Papers, XXII, Budapest Conference, 1968.
• 23: A. G. Wilson, Entropy in Urban and Regional Modeling, Pion Press, London (1970).

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
entropy, optimization, search engines, static ranking