Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We analyze the traffic-weighted Web host graph obtained from a large sample of real Web users over about seven months. A number of interesting structural properties are revealed by this complex dynamic network, some in line with the well-studied boolean link host graph and others pointing to important differences. We find that while search is directly involved in a surprisingly small fraction of user clicks, it leads to a much larger fraction of all sites visited. The temporal traffic patterns display strong regularities, with a large portion of future requests being statistically predictable by past ones. Given the importance of topological measures such as PageRank in modeling user navigation, as well as their role in ranking sites for Web search, we use the traffic data to validate the PageRank random surfing model. The ranking obtained by the actual frequency with which a site is visited by users differs significantly from that approximated by the uniform surfing/teleportation behavior modeled by PageRank, especially for the most important sites. To interpret this finding, we consider each of the fundamental assumptions underlying PageRank and show how each is violated by actual user behavior

REFERENCES

• 1: L. Adamic and B. Huberman. Power-law distribution of the World Wide Web. Science, 287:2115, 2000.
• 2: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 3: R. Albert, H. Jeong, and A.-L. Barabási. Diameter of the World Wide Web. Nature, 401(6749):130--131, 1999.
• 4: E. Almaas, B. Kovacs, T. Vicsek, Z. N. Oltvai, and A.-L. Barabasi. Global organization of metabolic fluxes in the bacterium escherichia coli. Nature, 427(6977):839--843, 2004.
• 5: Ricardo A. Baeza-Yates , Felipe Saint-Jean , Carlos Castillo, Web Structure, Dynamics and Page Quality, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.117-130, September 11-13, 2002
• 6: M. Barthelemy, B. Gondranb, and E. Guichardc. Spatial structure of the internet traffic. Physica A, 319:633--642, March 2003.
• 7: Krishna Bharat , Bay-Wei Chang , Monika Rauch Henzinger , Matthias Ruhl, Who Links to Whom: Mining Linkage between Web Sites, Proceedings of the 2001 IEEE International Conference on Data Mining, p.51-58, November 29-December 02, 2001
• 8: P. Boldi, M. Santini, and S. Vigna. Do your worst to make the best: Paradoxical effects in pagerank incremental computations. Internet Mathematics, 2(3):387--404, 2005.
• 9: 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]
• 10: 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
• 11: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 12: Lara D. Catledge , James E. Pitkow, Characterizing browsing strategies in the World-Wide Web, Computer Networks and ISDN Systems, v.27 n.6, p.1065-1073, April 1995
• 13: Junghoo Cho , Sourashis Roy, Impact of search engines on page popularity, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988676]
• 14: A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. Technical report, arXiv:0706.1062v1 {physics.data-an}, 2007.
• 15: What do web users do? An empirical analysis of web use, International Journal of Human-Computer Studies, v.54 n.6, p.903-922, June 2001 [doi>10.1006/ijhc.2001.0459]
• 16: 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]
• 17: D. Donato, L. Laura, S. Leonardi, and S. Millozzi. Large scale properties of the webgraph. Eur. Phys. J. B, 38:239--243, 2004.
• 18: Jeffrey Erman , Anirban Mahanti , Martin Arlitt , Carey Williamson, Identifying and discriminating between web and peer-to-peer traffic in the network core, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242692]
• 19: S. Fortunato and A. Flammini. Random walks on directed networks: the case of pagerank. International Journal of Bifurcation and Chaos, 2007. Forthcoming.
• 20: S. Fortunato, A. Flammini, and F. Menczer. Scale-free network growth by ranking. Phys. Rev. Lett., 96(21):218701, 2006.
• 21: S. Fortunato, A. Flammini, F. Menczer, and A. Vespignani. Topical interests and the mitigation of search engine bias. Proc. Natl. Acad. Sci. USA, 103(34):12684--12689, 2006.
• 22: M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork. On near-uniform URL sampling. In Proc. 9th International World Wide Web Conference, 2000.
• 23: O. Herfindahl. Copper Costs and Prices: 1870--1957. John Hopkins University Press, Baltimore, MD, 1959.
• 24: A. Hirschman. The paternity of an index. American Economic Review, 54(5):761--762, 1964.
• 25: Lucas Introna , Helen Nissenbaum, Defining the Web: The Politics of Search Engines, Computer, v.33 n.1, p.54-62, January 2000 [doi>10.1109/2.816269]
• 26: M. Kendall. A new measure of rank correlation. Biometrika, 30:81--89, 1938.
• 27: 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]
• 28: J. Luxenburger and G. Weikum. Query-Log Based Authority Analysis for Web Information Search, volume 3306 of Lecture Notes in Computer Science, pages 90--101. Springer Berlin/Heidelberg, 2004.
• 29: Mark Meiss , Filippo Menczer , Alessandro Vespignani, On the lack of typical behavior in the global Web traffic network, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060820]
• 30: Bamshad Mobasher , Robert Cooley , Jaideep Srivastava, Automatic personalization based on Web usage mining, Communications of the ACM, v.43 n.8, p.142-151, Aug. 2000 [doi>10.1145/345124.345169]
• 31: Abbe Mowshowitz , Akira Kawaguchi, Bias on the web, Communications of the ACM, v.45 n.9, September 2002 [doi>10.1145/567498.567527]
• 32: Marc Najork , Janet L. Wiener, Breadth-first crawling yields high-quality pages, Proceedings of the 10th international conference on World Wide Web, p.114-118, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371965]
• 33: F. Qiu, Z. Liu, and J. Cho. Analysis of user web traffic with a focus on search activities. In A. Doan, F. Neven, R. McCann, and G. J. Bex, editors, Proc. 8th International Workshop on the Web and Databases (WebDB), pages 103--108, 2005.
• 34: Matthew Richardson , Amit Prakash , Eric Brill, Beyond PageRank: machine learning for static ranking, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135881]
• 35: 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]
• 36: Marcin Sydow, Can link analysis tell us about web traffic?, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062815]
• 37: Q. Yang and H. H. Zhang. Web-log mining for predictive web caching. IEEE Trans. on Knowledge and Data Engineering, 15(4):1050--1053, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

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

General Terms:
Measurement

Keywords:
navigation, pagerank, ranking, search, teleportation, web traffic, weighted host graph