{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T19:10:49Z","timestamp":1772910649758,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0705359IIS-0808661"],"award-info":[{"award-number":["IIS-0705359IIS-0808661"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["2\/7\/3960"],"award-info":[{"award-number":["2\/7\/3960"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory, Office of Science","doi-asserted-by":"publisher","award":["DE-AC52-07NA27344"],"award-info":[{"award-number":["DE-AC52-07NA27344"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>Given large, multimillion-node graphs (e.g., Facebook, Web-crawls, etc.), how do they evolve over time? How are they connected? What are the central nodes and the outliers? In this article we define the Radius plot of a graph and show how it can answer these questions. However, computing the Radius plot is prohibitively expensive for graphs reaching the planetary scale.<\/jats:p>\n          <jats:p>\n            There are two major contributions in this article: (a) We propose HADI (HAdoop DIameter and radii estimator), a carefully designed and fine-tuned algorithm to compute the radii and the diameter of massive graphs, that runs on the top of the\n            <jats:sc>Hadoop<\/jats:sc>\n            \/\n            <jats:sc>MapReduce<\/jats:sc>\n            system, with excellent scale-up on the number of available machines (b) We run HADI on several real world datasets including YahooWeb (6B edges, 1\/8 of a Terabyte), one of the largest public graphs ever analyzed.\n          <\/jats:p>\n          <jats:p>Thanks to HADI, we report fascinating patterns on large networks, like the surprisingly small effective diameter, the multimodal\/bimodal shape of the Radius plot, and its palindrome motion over time.<\/jats:p>","DOI":"10.1145\/1921632.1921634","type":"journal-article","created":{"date-parts":[[2011,3,3]],"date-time":"2011-03-03T08:44:26Z","timestamp":1299141866000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":91,"title":["HADI"],"prefix":"10.1145","volume":"5","author":[{"given":"U.","family":"Kang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana Paula","family":"Appel","sequence":"additional","affiliation":[{"name":"Universidade de S\u00e3o Paulo at S\u00e3o Carlos"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jure","family":"Leskovec","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Conference on Very Large Databases.","author":"Aggarwal C. C.","unstructured":"Aggarwal , C. C. , Xie , Y. , and Yu , P. S . 2009. Gconnect: A connectivity index for massive disk-resident graphs . In Proceedings of the International Conference on Very Large Databases. Aggarwal, C. C., Xie, Y., and Yu, P. S. 2009. Gconnect: A connectivity index for massive disk-resident graphs. In Proceedings of the International Conference on Very Large Databases."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.04.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Very Large Databases.","author":"Chaiken R.","unstructured":"Chaiken , R. , Jenkins , B. , Larson , P.-A. , Ramsey , B. , Shakib , D. , Weaver , S. , and Zhou , J . 2008. Scope: easy and efficient parallel processing of massive data sets . In Proceedings of the International Conference on Very Large Databases. Chaiken, R., Jenkins, B., Larson, P.-A., Ramsey, B., Shakib, D., Weaver, S., and Zhou, J. 2008. Scope: easy and efficient parallel processing of massive data sets. In Proceedings of the International Conference on Very Large Databases."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014064"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335230"},{"key":"e_1_2_1_11_1","unstructured":"Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. The MIT Press. Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms . The MIT Press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557140"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956764"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1115"},{"key":"e_1_2_1_15_1","unstructured":"Erd\u0151s P. and R\u00e9nyi A. 1959. On random graphs. Publicationes Mathematicae. Erd\u0151s P. and R\u00e9nyi A. 1959. On random graphs. Publicationes Mathematicae ."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Symposium on High-Performance Computer Architecture.","author":"Ferrez J.-A.","unstructured":"Ferrez , J.-A. , Fukuda , K. , and Liebling , T . 1998. Parallel computation of the diameter of a graph . In Proceedings of the International Symposium on High-Performance Computer Architecture. Ferrez, J.-A., Fukuda, K., and Liebling, T. 1998. Parallel computation of the diameter of a graph. In Proceedings of the International Symposium on High-Performance Computer Architecture."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Conference on Very Large Databases.","author":"Garofalakis M. N.","unstructured":"Garofalakis , M. N. and Gibbon , P. B . 2001. Approximate query processing: Taming the terabytes . In Proceedings of the International Conference on Very Large Databases. Garofalakis, M. N. and Gibbon, P. B. 2001. Approximate query processing: Taming the terabytes. In Proceedings of the International Conference on Very Large Databases."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402000"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2nd Workshop on Large-Scale Data Mining: Theory and Applications.","author":"Kang U.","unstructured":"Kang , U. , Chau , D. , and Faloutsos , C . 2010a. Inference of beliefs on billion-scale graphs . In Proceedings of the 2nd Workshop on Large-Scale Data Mining: Theory and Applications. Kang, U., Chau, D., and Faloutsos, C. 2010a. Inference of beliefs on billion-scale graphs. In Proceedings of the 2nd Workshop on Large-Scale Data Mining: Theory and Applications."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of SIAM International Conference on Data Mining.","author":"Kang U.","unstructured":"Kang , U. , Tsourakakis , C. , Appel , A. P. , Faloutsos , C. , and Leskovec , J . 2010b. Radius plots for mining tera-byte scale graphs: Algorithms, patterns, and observations . In Proceedings of SIAM International Conference on Data Mining. Kang, U., Tsourakakis, C., Appel, A. P., Faloutsos, C., and Leskovec, J. 2010b. Radius plots for mining tera-byte scale graphs: Algorithms, patterns, and observations. In Proceedings of SIAM International Conference on Data Mining."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0305-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598334138"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining.","author":"Ke Y.","unstructured":"Ke , Y. , Cheng , J. , and Yu , J. X . 2009. Top-k correlative graph mining . In Proceedings of the SIAM International Conference on Data Mining. Ke, Y., Cheng, J., and Yu, J. X. 2009. Top-k correlative graph mining. In Proceedings of the SIAM International Conference on Data Mining."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.89"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121445.3121464"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1516232"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02939544"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401955"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Newman. M. 2005. A measure of betweenness centrality based on random walks. Social Netw. Newman. M. 2005. A measure of betweenness centrality based on random walks. Social Netw .","DOI":"10.1016\/j.socnet.2004.11.009"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775059"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.142"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559865"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Pike R. Dorward S. Griesemer R. and Quinlan S. 2005. Interpreting the data: Parallel analysis with sawzall. Scien. Program. J. Pike R. Dorward S. Griesemer R. and Quinlan S. 2005. Interpreting the data: Parallel analysis with sawzall. Scien. Program. J .","DOI":"10.1155\/2005\/962135"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557101"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676702"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_41_1","volume-title":"Mach: Fast randomized tensor decompositions. CoRR abs\/0909.4969.","author":"Tsourakakis C. E.","year":"2009","unstructured":"Tsourakakis , C. E. 2009 . Mach: Fast randomized tensor decompositions. CoRR abs\/0909.4969. Tsourakakis, C. E. 2009. Mach: Fast randomized tensor decompositions. CoRR abs\/0909.4969."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_43_1","unstructured":"Tsourakakis C. E. Kolountzakis M. N. and Miller G. L. 2009b. Approximate triangle counting. CoRR abs\/0904.3761. Tsourakakis C. E. Kolountzakis M. N. and Miller G. L. 2009b. Approximate triangle counting. CoRR abs\/0904.3761."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014088"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the IEEE International Conference on Data Mining.","author":"Yan X.","unstructured":"Yan , X. and Han , J . 2002. gspan: Graph-based substructure pattern mining . In Proceedings of the IEEE International Conference on Data Mining. Yan, X. and Han, J. 2002. gspan: Graph-based substructure pattern mining. In Proceedings of the IEEE International Conference on Data Mining."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557125"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921632.1921634","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921632.1921634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921632.1921634"}},"subtitle":["Mining Radii of Large Graphs"],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1145\/1921632.1921634"],"URL":"https:\/\/doi.org\/10.1145\/1921632.1921634","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2]]},"assertion":[{"value":"2010-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}