article

Decoding the structure of the WWW: A comparative analysis of Web crawls

Authors:

M. Ángeles Serrano,

Marián Boguñá,

Santo Fortunato,

Alessandro VespignaniAuthors Info & Claims

ACM Transactions on the Web (TWEB), Volume 1, Issue 2

Pages 10 - es

https://doi.org/10.1145/1255438.1255442

Published: 01 August 2007 Publication History

Abstract

The understanding of the immense and intricate topological structure of the World Wide Web (WWW) is a major scientific and technological challenge. This has been recently tackled by characterizing the properties of its representative graphs, in which vertices and directed edges are identified with Web pages and hyperlinks, respectively. Data gathered in large-scale crawls have been analyzed by several groups resulting in a general picture of the WWW that encompasses many of the complex properties typical of rapidly evolving networks. In this article, we report a detailed statistical analysis of the topological properties of four different WWW graphs obtained with different crawlers. We find that, despite the very large size of the samples, the statistical measures characterizing these graphs differ quantitatively, and in some cases qualitatively, depending on the domain analyzed and the crawl used for gathering the data. This spurs the issue of the presence of sampling biases and structural differences of Web crawls that might induce properties not representative of the actual global underlying graph. In short, the stability of the widely accepted statistical description of the Web is called into question. In order to provide a more accurate characterization of the Web graph, we study statistical measures beyond the degree distribution, such as degree-degree correlation functions or the statistics of reciprocal connections. The latter appears to enclose the relevant correlations of the WWW graph and carry most of the topological information of the Web. The analysis of this quantity is also of major interest in relation to the navigability and searchability of the Web.

References

[1]

Adamic, L. A. and Huberman, B. A. 2001. The Web's hidden order. Commun. ACM 44, 9, 55--60.

[2]

Albert, R., Jeong, H., and Barabási, A.-L. 1999. Diameter of the World-Wide Web. Nature 401, 6749, 130--131.

[3]

Arasu, A., Cho, J., Garcia-Molina, H., Paepcke, A., and Raghavan, S. 2001. Searching the Web. ACM Trans. Internet Tech. 1, 1, 2--43.

[4]

Bar-Yossef, Z., Berg, A., Chien, S., Fakcharoenphol, J., and Weitz, D. 2000. Approximating aggregate queries about web pages via random walks. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). 535--544.

[5]

Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 5439, 509--512.

[6]

Barabási, A.-L., Albert, R., and Jeong, H. 2000. Scale-free characteristics of random networks: The topology of the World-Wide Web. Physica A 281, 1-4, 69--77.

[7]

Barrat, A., Barthélemy, M., and Vespignani, A. 2004. Traffic-driven model of the World Wide Web graph, Stephano Leonardi, Ed. Algorithms and Models for the Web-Graph. Lecture Notes in Computer Science, vol. 3243. Springer, Berlin, Heidelburg, Germany, 56--67.

[8]

Boguñá, M. and Serrano, M. A. 2005. Generalized percolation in random directed networks. Phys. Rev. E 72, 1, 016106.

[9]

Boldi, P., Codenotti, B., Santini, M., and Vigna, S. 2004. Ubicrawler: A scalable fully distributed Web crawler. Softw. Pract. Exper. 34, 8, 711--726.

[10]

Boldi, P. and Vigna, S. 2004. The Webgraph framework i: Compression techniques. In WWW 2004 Conference Proceedings. ACM, New York, NY, 595--601.

[11]

Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, S., Tomkins, A., and Wiener, J. 2000. Graph structure in the Web. Comput. Netw. 33, 1-6, 309--320.

[12]

Cho, J. and Garcia-Molina, H. 2000. The evolution of the Web and implications for an incremental crawler. In Proceedings of the 26th International Conference on Very Large Databases (Cairo, Egypt). 200--209.

[13]

Cohen, R., Erez, K., ben Avraham, D., and Havlin, S. 2000. Resilience of the Internet to random breakdown. Phys. Rev. Lett. 85, 21, 4626.

[14]

Cothey, V. 2004. Web-crawling reliability. J. Amer. Soc. Inform. Sci. Techn. 55, 14, 1228--1238.

[15]

Dill, S., Kumar, R., McCurley, K., Rajagopalan, S., Sivakumar, D., and Tomkins, A. 2001. Self-similarity in the Web. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 69--78.

[16]

Donato, D., Laura, L., Leonardi, S., and Millozzi, S. 2004. Large scale properties of the Webgraph. Eur. Phys. J. B 38, 2, 239--243.

[17]

Donato, D., Leonardi, S., Millozzi, S., and Tsaparas, P. 2005. Mining the inner structure of the Web graph. In Proceedings of the Eighth International Workshop on the Web and Databases (WebDB). 145--150.

[18]

Dorogovtsev, S. N. and Mendes, J. F. F. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford, U. K.

[19]

Eckmann, J. P. and Moses, E. 2002. Curvature of co-links uncovers hidden thematic layers in the World Wide Web. Procc. Natl. Acad. Sci. 99, 9, 5825--5829.

[20]

Fortunato, S., Boguñá, M., Flammini, A., and Menczer, F. 2006. Approximating pagerank from in-degree. In cs.IR/0511016, presented at the Fourth Workshop on Algorithms and Models for the Web-Graph, Nov. 30 -- Dec. 1, Banff, Alta., (Canada).

[21]

Garlaschelli, D. and Loffredo, M. I. 2004. Patterns of link reciprocity in directed networks. Phys. Rev. Lett. 93, 26, 268701.

[22]

Gulli, A. and Signorini, A. 2005. The indexable Web is more than 11.5 billion pages. In WWW 2005 Conference Proceedings (Chiba, Japan). ACM Press, New York, NY, 902--903.

[23]

Henzinger, M. R., Heydon, A., Mitzenmacher, M., and Najork, M. 2000. On near-uniform URL sampling. In WWW 2000 Conference Proceedings (Amsterdam, The Netherlands). ACM Press, New York, NY, 295--308.

[24]

Hirai, J., Raghavan, S., Paepcke, A., and Garcia-Molina, H. 2000. Webbase: A repository of Web pages. In WWW 2000 Conference Proceedings (Amsterdam, The Netherlands). ACM Press, New York, NY, 277--293.

[25]

Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E. 2000. Stochastic models for the Web graph. In Proceedings of the 41th IEEE Symposium on Foundations of Computer Science (FOCS). 57--65.

[26]

Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. Trawling emerging cyber-communities automatically. In WWW 1999 Conference Proceedings (Toronto, Ont., Canada). ACM Press, New York, NY, 3--4.

[27]

Lawrence, S. and Giles, C. L. 1998. Searching the world wide web. Science 280, 5360, 98--100.

[28]

Lawrence, S. and Giles, C. L. 1999. Accessibility of information on the Web. Nature 400, 6740, 107--109.

[29]

Mahadevan, P., Krioukov, D., Fall, K., and Vahdat, A. 2006. Systematic topology analysis and generation using degree correlations. In Proceedings of SIGCOMM06 (Pisa, Italy). ACM Press, New York, NY.

[30]

Mossa, S., Barthélemy, M., Stanley, H. E., and Amaral, L. A. N. 2002. Truncation of power law behavior in scale-free network models due to information filtering. Phys. Rev. Lett. 88, 13, 138701.

[31]

Newman, M. E. J. 2002. Assortative mixing in networks. Phys. Rev. Lett. 89, 20, 208701.

[32]

Pastor-Satorras, R., Vázquez, A., and Vespignani, A. 2001. Dynamical and correlation properties of the Internet. Phys. Rev. Lett. 87, 25, 258701.

[33]

Pastor-Satorras, R. and Vespignani, A. 2001. Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86, 14, 3200--3203.

[34]

Pastor-Satorras, R. and Vespignani, A. 2004. Evolution and Structure of the Internet. A Statistical Physics Approach. Cambridge University Press, Cambridge, U. K.

[35]

Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., and Giles, C. L. 2002. Winners don't take all: Characterizing the competition for links on the web. Proc. Natl. Acad. Sci. 99, 8, 5207--5211.

[36]

Rusmevichientong, P., Pennock, D. M., Lawrence, S., and Giles, C. L. 2001. Methods for sampling pages uniformly from the World Wide Web. In Proceedings of the AAAI Fall Symposium on Using Uncertainty Within Computation. 121--128.

Cited By

Perekhodko E(2024)Local 2-connected bow-tie structure of the Web and of social networksApplied Network Science10.1007/s41109-024-00638-y9:1Online publication date: 9-Jul-2024
https://doi.org/10.1007/s41109-024-00638-y
Chowdhary SAndres EManna ABlagojević LDi Gaetano LIñiguez G(2023)Temporal patterns of reciprocity in communication networksEPJ Data Science10.1140/epjds/s13688-023-00382-w12:1Online publication date: 10-Mar-2023
https://doi.org/10.1140/epjds/s13688-023-00382-w
Ristoski P(2023)Web MiningMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_20(447-467)Online publication date: 26-Feb-2023
https://doi.org/10.1007/978-3-031-24628-9_20
Show More Cited By

Index Terms

Decoding the structure of the WWW: A comparative analysis of Web crawls
1. Information systems
  1. Information systems applications
2. Mathematics of computing
  1. Probability and statistics

Recommendations

Browser Feature Usage on the Modern Web
IMC '16: Proceedings of the 2016 Internet Measurement Conference

Modern web browsers are incredibly complex, with millions of lines of code and over one thousand JavaScript functions and properties available to website authors. This work investigates how these browser features are used on the modern, open web. We ...
Coarse-grained classification of web sites by their structural properties
WIDM '06: Proceedings of the 8th annual ACM international workshop on Web information and data management

In this paper, we identify and analyze structural properties which reflect the functionality of a Web site. These structural properties consider the size, the organization, the composition of URLs, and the link structure of Web sites. Opposed to ...
Classifying web sites
WWW '07: Proceedings of the 16th international conference on World Wide Web

In this paper, we present a novel method for the classification of Web sites. This method exploits both structure and content of Web sites in order to discern their functionality. It allows for distinguishing between eight of the most relevant ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on the Web

ACM Transactions on the Web Volume 1, Issue 2

August 2007

105 pages

ISSN:1559-1131

EISSN:1559-114X

DOI:10.1145/1255438

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2007

Published in TWEB Volume 1, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
1,509
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Perekhodko E(2024)Local 2-connected bow-tie structure of the Web and of social networksApplied Network Science10.1007/s41109-024-00638-y9:1Online publication date: 9-Jul-2024
https://doi.org/10.1007/s41109-024-00638-y
Chowdhary SAndres EManna ABlagojević LDi Gaetano LIñiguez G(2023)Temporal patterns of reciprocity in communication networksEPJ Data Science10.1140/epjds/s13688-023-00382-w12:1Online publication date: 10-Mar-2023
https://doi.org/10.1140/epjds/s13688-023-00382-w
Ristoski P(2023)Web MiningMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_20(447-467)Online publication date: 26-Feb-2023
https://doi.org/10.1007/978-3-031-24628-9_20
Jamaldini MHosseinzadeh BShojaee A(2022)Effects of Web-Based Management on Organizational Time Management among the Managers of Islamic Azad University of HormozganJournal of Management and Development Process10.52547/jmdp.35.3.19735:3(197-219)Online publication date: 1-Dec-2022
https://doi.org/10.52547/jmdp.35.3.197
Alharbi AFaizan MAlosaimi WAlyami HAgrawal AKumar RKhan R(2021)Exploring the Topological Properties of the Tor Dark WebIEEE Access10.1109/ACCESS.2021.30555329(21746-21758)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3055532
O’Keeffe KGriffith VXu YSanti PRatti C(2021)The Darkweb: A Social Network AnomalyUnifying Themes in Complex Systems X10.1007/978-3-030-67318-5_22(335-347)Online publication date: 15-Jun-2021
https://doi.org/10.1007/978-3-030-67318-5_22
Bernaschi MCelestini AGuarino SLombardi FMastrostefano E(2019)Spiders like Onions: on the Network of Tor Hidden ServicesThe World Wide Web Conference10.1145/3308558.3313687(105-115)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313687
Leming MSu LChattopadhyay SSuckling J(2019)Normative pathways in the functional connectomeNeuroImage10.1016/j.neuroimage.2018.09.028184(317-334)Online publication date: Jan-2019
https://doi.org/10.1016/j.neuroimage.2018.09.028
Díaz MÁlvarez VSeijo F(2018)The Evolution of the (Hidden) Web and Its Hidden DataThe Dark Web10.4018/978-1-5225-3163-0.ch006(84-113)Online publication date: 2018
https://doi.org/10.4018/978-1-5225-3163-0.ch006
Xie YChang SZhang ZZhang MYang L(2018)Efficient sampling of complex network with modified random walk strategiesPhysica A: Statistical Mechanics and its Applications10.1016/j.physa.2017.09.032492(57-64)Online publication date: Feb-2018
https://doi.org/10.1016/j.physa.2017.09.032
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents