{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T18:17:55Z","timestamp":1761675475539},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2007,2]]},"abstract":"<jats:p>In this article we present an experimental study of the properties of webgraphs. We study a large crawl from 2001 of 200M pages and about 1.4 billion edges, made available by the WebBase project at Stanford, as well as several synthetic ones generated according to various models proposed recently. We investigate several topological properties of such graphs, including the number of bipartite cores and strongly connected components, the distribution of degrees and PageRank values and some correlations; we present a comparison study of the models against these measures.Our findings are that (i) the WebBase sample differs slightly from the (older) samples studied in the literature, and (ii) despite the fact that these models do not catch all of its properties, they do exhibit some peculiar behaviors not found, for example, in the models from classical random graph theory.Moreover we developed a software library able to generate and measure massive graphs in secondary memory; this library is publicy available under the GPL licence. We discuss its implementation and some computational issues related to secondary memory graph algorithms.<\/jats:p>","DOI":"10.1145\/1189740.1189744","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"4","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["The Web as a graph"],"prefix":"10.1145","volume":"7","author":[{"given":"Debora","family":"Donato","sequence":"first","affiliation":[{"name":"University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[{"name":"University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Millozzi","sequence":"additional","affiliation":[{"name":"University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Abello J. Pardalos P. M. and Resende M. G. C. 2002. Handbook of massive data sets. Kluwer Academic Publishers.   Abello J. Pardalos P. M. and Resende M. G. C. 2002. Handbook of massive data sets. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-0005-6"},{"key":"e_1_2_1_2_1","unstructured":"Adler M. and Mitzenmacher M. 2001. Towards compressing web graphs. in the Proceedings of the Data Compression Conference (DCC'01)   Adler M. and Mitzenmacher M. 2001. Towards compressing web graphs. in the Proceedings of the Data Compression Conference (DCC'01)"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129080"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_5_1","volume-title":"Ubicrawler: A scalable fully distributed web crawler.","author":"Boldi P.","year":"2002","unstructured":"Boldi , P. , Codenotti , B. , Santini , M. , and Vigna , S . 2002 . Ubicrawler: A scalable fully distributed web crawler. Boldi, P., Codenotti, B., Santini, M., and Vigna, S. 2002. Ubicrawler: A scalable fully distributed web crawler."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 9th WWW conference.","author":"Broder A.","unstructured":"Broder , A. , Kumar , R. , Maghoul , F. , Raghavan , P. , Rajagopalan , S. , Stata , S. , Tomkins , A. , and Wiener , J . 2000. Graph structure in the web . In Proceedings of the 9th WWW conference. Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, S., Tomkins, A., and Wiener, J. 2000. Graph structure in the web. In Proceedings of the 9th WWW conference."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511464"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149121.1149124"},{"key":"e_1_2_1_11_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms 6th ed. MIT Press and McGraw-Hill Book Company.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms 6th ed. MIT Press and McGraw-Hill Book Company."},{"key":"e_1_2_1_12_1","unstructured":"cyvellance. www.cyvellance.com. Cyvellance.  cyvellance. www.cyvellance.com. Cyvellance."},{"key":"e_1_2_1_13_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"Diestel , R. 1997. Graph Theory . Springer , New York . Diestel, R. 1997. Graph Theory. Springer, New York."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 27th VLDB Conference.","author":"Dill S.","unstructured":"Dill , S. , Kumar , R. , McCurley , K. , Rajagopalan , S. , Sivakumar , D. , and Tomkins , A . 2001. Self-similarity in the web . In Proceedings of the 27th VLDB Conference. Dill, S., Kumar, R., McCurley, K., Rajagopalan, S., Sivakumar, D., and Tomkins, A. 2001. Self-similarity in the web. In Proceedings of the 27th VLDB Conference."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00056-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2004.73"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. D13, COSIN European Research Project","author":"Donato D.","year":"2004","unstructured":"Donato , D. , Laura , L. , Leonardi , S. , and Millozzi , S . 2004 c. A software library for generating and measuring massive Webgraphs . Tech. Rep. D13, COSIN European Research Project . http:\/\/www.dis.uniroma1.it\/~cosin\/html_pages\/COSIN-Tools.htm. Donato, D., Laura, L., Leonardi, S., and Millozzi, S. 2004c. A software library for generating and measuring massive Webgraphs. Tech. Rep. D13, COSIN European Research Project. http:\/\/www.dis.uniroma1.it\/~cosin\/html_pages\/COSIN-Tools.htm."},{"key":"e_1_2_1_18_1","unstructured":"Erd\u00f6s P. and R\u00e9nyi A. 1960. On the evoluation of random graphs Publ. Math. Inst. Hung. Acad. Sci 5.  Erd\u00f6s P. and R\u00e9nyi A. 1960. On the evoluation of random graphs Publ. Math. Inst. Hung. Acad. Sci 5."},{"key":"e_1_2_1_19_1","volume-title":"Tech. Rep. 038, Yahoo&excl","author":"Gleich D.","year":"2004","unstructured":"Gleich , D. , Zuchov , L. , and Berkhin , P . 2004 . Fast Parallel PageRank: A Linear System Approach. Tech. Rep. 038, Yahoo&excl ; Research . Gleich, D., Zuchov, L., and Berkhin, P. 2004. Fast Parallel PageRank: A Linear System Approach. Tech. Rep. 038, Yahoo&excl; Research."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062745.1062789"},{"key":"e_1_2_1_21_1","volume-title":"Graph Theory","author":"Harary F.","unstructured":"Harary , F. 1969. Graph Theory . Addison-Wesley , Reading, MA . Harary, F. 1969. Graph Theory. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_22_1","volume-title":"Efficient computation of PageRank. Tech. rep","author":"Haveliwala T. H.","unstructured":"Haveliwala , T. H. 1999. Efficient computation of PageRank. Tech. rep ., Stanford University . Haveliwala, T. H. 1999. Efficient computation of PageRank. Tech. rep., Stanford University."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Combinatorics and Computing. 1--18","author":"Kleinberg J.","unstructured":"Kleinberg , J. , Kumar , R. , Raghavan , P. , Rajagopalan , S. , and Tomkins , A . 1999. The Web as a graph: measurements, models and methods . In Proceedings of the International Conference on Combinatorics and Computing. 1--18 . Kleinberg, J., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. The Web as a graph: measurements, models and methods. In Proceedings of the International Conference on Combinatorics and Computing. 1--18."},{"key":"e_1_2_1_25_1","volume-title":"Seminumerical Algorithms","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1997. Seminumerical Algorithms , Third ed. The Art of Computer Programming, vol. 2 . Addison-Wesley , Reading, Massachusetts. Knuth, D. E. 1997. Seminumerical Algorithms, Third ed. The Art of Computer Programming, vol. 2. Addison-Wesley, Reading, Massachusetts."},{"key":"e_1_2_1_26_1","volume-title":"Second Workshop on Algorithms and Models for the Web-Graph (WAW2003)","author":"Kraft R.","unstructured":"Kraft , R. , Hastor , E. , and Stata , R . 2003. Timelinks: Exploring the link structure of the evolving Web . In Second Workshop on Algorithms and Models for the Web-Graph (WAW2003) . Kraft, R., Hastor, E., and Stata, R. 2003. Timelinks: Exploring the link structure of the evolving Web. In Second Workshop on Algorithms and Models for the Web-Graph (WAW2003)."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 41st FOCS. 57--65","author":"Kumar R.","unstructured":"Kumar , R. , Raghavan , P. , Rajagopalan , S. , Sivakumar , D. , Tomkins , A. , and Upfal , E . 2000. Stochastic models for the Web graph . In Proceedings of the 41st FOCS. 57--65 . Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E. 2000. Stochastic models for the Web graph. In Proceedings of the 41st FOCS. 57--65."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 8th WWW Conference. 403--416","author":"Kumar R.","unstructured":"Kumar , R. , Raghavan , P. , Rajagopalan , S. , and Tomkins , A . 1999. Trawling the Web for emerging cyber communities . In Proceedings of the 8th WWW Conference. 403--416 . Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. Trawling the Web for emerging cyber communities. In Proceedings of the 8th WWW Conference. 403--416."},{"key":"e_1_2_1_29_1","volume-title":"On-line proceedings of the 2nd International Workshop on Web Dynamics.","author":"Laura L.","year":"2002","unstructured":"Laura , L. , Leonardi , S. , Caldarelli , G. , and De Los Rios , P. 2002 . A multi-layer model for the Webgraph . In On-line proceedings of the 2nd International Workshop on Web Dynamics. Laura, L., Leonardi, S., Caldarelli, G., and De Los Rios, P. 2002. A multi-layer model for the Webgraph. In On-line proceedings of the 2nd International Workshop on Web Dynamics."},{"key":"e_1_2_1_30_1","first-page":"2","article-title":"A brief history of generative models for power law and lognormal distributions","volume":"1","author":"Mitzenmacher M.","year":"2003","unstructured":"Mitzenmacher , M. 2003 . A brief history of generative models for power law and lognormal distributions . Internet Math. 1 , 2 . Mitzenmacher, M. 2003. A brief history of generative models for power law and lognormal distributions. Internet Math. 1, 2.","journal-title":"Internet Math."},{"key":"e_1_2_1_31_1","first-page":"330","article-title":"Using PageRank to characterize Web structure. In Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON), Springer-Verlag","volume":"2387","author":"Pandurangan G.","year":"2002","unstructured":"Pandurangan , G. , Raghavan , P. , and Upfal , E. 2002 . Using PageRank to characterize Web structure. In Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON), Springer-Verlag , Ed. LNCS 2387. 330 -- 339 . Pandurangan, G., Raghavan, P., and Upfal, E. 2002. Using PageRank to characterize Web structure. In Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON), Springer-Verlag, Ed. LNCS 2387. 330--339.","journal-title":"Ed. LNCS"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032085699"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564917"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_35_1","first-page":"2","article-title":"Algorithms for parallel memory i: Two-level memories","volume":"12","author":"Vitter J.","year":"1994","unstructured":"Vitter , J. and Shriver , E. 1994 a. Algorithms for parallel memory i: Two-level memories . Algorithmica 12 , 2 - 3 , 107--114. Vitter, J. and Shriver, E. 1994a. Algorithms for parallel memory i: Two-level memories. Algorithmica 12, 2-3, 107--114.","journal-title":"Algorithmica"},{"key":"e_1_2_1_36_1","first-page":"2","article-title":"Algorithms for parallel memory ii: Hierarchical multilevel memories","volume":"12","author":"Vitter J.","year":"1994","unstructured":"Vitter , J. and Shriver , E. 1994 b. Algorithms for parallel memory ii: Hierarchical multilevel memories . Algorithmica 12 , 2 - 3 , 148--169. Vitter, J. and Shriver, E. 1994b. Algorithms for parallel memory ii: Hierarchical multilevel memories. Algorithmica 12, 2-3, 148--169.","journal-title":"Algorithmica"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"e_1_2_1_38_1","unstructured":"webbase. The Stanford Webbase project. http:\/\/www-diglib.stanford.edu\/~testbed\/doc2\/WebBase\/.  webbase. The Stanford Webbase project. http:\/\/www-diglib.stanford.edu\/~testbed\/doc2\/WebBase\/."},{"key":"e_1_2_1_39_1","unstructured":"Witten I. H. Moffat A. and Bell T. C. 1999. Managing Gigabytes (2nd ed.): Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers Inc.   Witten I. H. Moffat A. and Bell T. C. 1999. Managing Gigabytes (2nd ed.): Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers Inc."}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189740.1189744","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T18:29:51Z","timestamp":1672252191000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189740.1189744"}},"subtitle":["How far we are"],"short-title":[],"issued":{"date-parts":[[2007,2]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,2]]}},"alternative-id":["10.1145\/1189740.1189744"],"URL":"https:\/\/doi.org\/10.1145\/1189740.1189744","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"value":"1533-5399","type":"print"},{"value":"1557-6051","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2]]},"assertion":[{"value":"2007-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}