2000 GraphStrctintheWeb

Jump to: navigation, search

Subject Headings:Graph structure; Diameter; Web measurement.


Cited By



The study of the Web as a graph is not only fascinating in its own right, but also yields valuable insight into Web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution. We report on experiments on local and global properties of the Web graph using two AltaVista crawls each with over 200 million pages and 1.5 billion links. Our study indicates that the macroscopic structure of the Web is considerably more intricate than suggested by earlier experiments on a smaller scale.


  • Adamic and Huberman (1) 99. L. Adamic and B. Huberman. The nature of markets on the World Wide Web, Xerox PARC Technical Report, 1999.
  • Adamic and Huberman (2) 99. L. Adamic and B. Huberman. Scaling behavior on the World Wide Web, Technical comment on Barabasi and Albert 99.
  • Aiello, Chung, and Lu 00. W. Aiello, F. Chung and L. Lu. A random graph model for massive graphs, ACM Symposium on the Theory and Computing 2000.
  • Albert, Jeong, and [[Barabasi 99 R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the World Wide Web, Nature 401:130-131, Sep 1999.
  • Barabasi and Albert 99. A. Barabasi and R. Albert. Emergence of scaling in random networks, Science, 286(509), 1999.
  • Barford et. al. 99. P. Barford, A. Bestavros, A. Bradley, and M. E. Crovella. Changes in Web client access patterns: Characteristics and caching implications, in World Wide Web, Special Issue on Characterization and Performance Evaluation, 2:15-28, 1999.
  • Bharat et. al. 98. K. Bharat, A. Broder, M. Henzinger, P. Kumar, and S. Venkatasubramanian. The connectivity server: fast access to linkage information on the web, Proceedings of 7th WWW, 1998.
  • Bharat and Henzinger 98. K. Bharat, and M. Henzinger. Improved algorithms for topic distillation in hyperlinked environments, Proceedings of 21st SIGIR, 1998.
  • Brin and Page 98. S. Brin, and L. Page. The anatomy of a large scale hypertextual web search engine, Proceedings of 7th WWW, 1998.
  • Butafogo and Schniederman 91. R. A. Butafogo and B. Schneiderman. Identifying aggregates in hypertext structures, Proceedings of 3rd ACM Conference on Hypertext, 1991.
  • Carriere and Kazman 97. J. Carriere, and R. Kazman. WebQuery: Searching and visualizing the Web through connectivity, Proceedings of 6th WWW, 1997.
  • „Chakrabarti et. al. (1) 98. S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, and S. Rajagopalan. Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of 7th WWW, 1998.
  • Chakrabarti et. al. (2) 98. S. Chakrabarti, B. Dom, D. Gibson, S. Ravi Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Experiments in topic distillation, Proceedings of ACM SIGIR workshop on Hypertext Information Retrieval on the Web, 1998.
  • Chakrabarti, Gibson, and McCurley 99. S. Chakrabarti, D. Gibson, and K. McCurley.Surfing the Web backwards, Proceedings of 8th WWW, 1999.
  • Cho and Garcia-Molina 2000 J. Cho, H. Garcia-Molina Synchronizing a database to Improve Freshness. To appear in 2000 ACM International Conference on Management of Data (SIGMOD), May 2000.
  • Faloutsos, Faloutsos, and Faloutsos 99. M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power law relationships of the internet topology, ACM SIGCOMM, 1999.
  • Glassman 94. S. Glassman. A caching relay for the world wide web, Proceedings of 1st WWW, 1994. Harary 75. F. Harary. Graph Theory, Addison Wesley, 1975.
  • Huberman et. al. 98. B. Huberman, P. Pirolli, J. Pitkow, and R. Lukose. Strong regularities in World Wide Web surfing, Science, 280:95-97, 1998.
  • Kleinberg 98. J. Kleinberg. Authoritative sources in a hyperlinked environment, Proceedings of 9th ACM-SIAM SODA, 1998.
  • Kumar et. al. (1) 99. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the Web for cyber communities, Proceedings of 8th WWW , Apr 1999.
  • Kumar et. al. (2) 99. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Extracting large scale knowledge bases from the Web, Proceedings of VLDB, Jul 1999.
  • Lukose and Huberman 98. R. M. Lukose and B. Huberman. Surfing as a real option, Proceedings of 1st International Conference on Information and Computation Economies, 1998.
  • Martindale and Konopka 96. C. Martindale and A K Konopka. Oligonucleotide frequencies in DNA follow a Yule distribution, Computer & Chemistry, 20(1):35-38, 1996.
  • Mendelzon, Mihaila, and Milo 97. A. Mendelzon, G. Mihaila, and T. Milo. Querying the World Wide Web, Journal of Digital Libraries 1(1), pp. 68-88, 1997.
  • Mendelzon and Wood 95. A. Mendelzon and P. Wood. Finding regular simple paths in graph databases, IAM J. Comp. 24(6):1235-1258, 1995.
  • Pareto 1897. V Pareto. Cours d'economie politique, Rouge, Lausanne et Paris, 1897. Pirolli, Pitkow, and Rao 96. P. Pirolli, J. Pitkow, and R. Rao. Silk from a sow's ear: Extracting usable structures from the Web, Proceedings of ACM SIGCHI, 1996.
  • Pitkow and Pirolli 97. J. Pitkow and P. Pirolli. Life, death, and lawfulness on the electronic frontier, Proceedings of ACM SIGCHI, 1997.
  • Simon 55. H.A. Simon. On a class of stew distribution functions, Biometrika, 42:425-440, 1955.

„* White and McCain 89. H.D. White and K.W. McCain, Bibliometrics, in: Ann. Rev. Info. Sci. and Technology, Elsevier, 1989, pp. 119-186.

„* Yule 44. G.U. Yule. Statistical Study of Literary Vocabulary, Cambridge University Press, 1944.

  • Zipf 49. G.K. Zipf. Human Behavior and the Principle of Least Effort, Addison-Wesley, 1949.,

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2000 GraphStrctintheWebAndrei Z. Broder
Ravi Kumar
Farzin Maghoul
Prabhakar Raghavan
Sridhar Rajagopalan
Raymie Stata
Janet Wienerc
Graph Structure in the WebComputer Networkshttp://www.sciencedirect.com/science/article/pii/S13891286000008392000