{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T22:37:49Z","timestamp":1789684669812,"version":"4.0.1"},"reference-count":66,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Graphs and networks are used to model interactions in a variety of contexts. There is a growing need to quickly assess the characteristics of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle-based and give a measure of the connectedness of mutual friends. This is often summarized in terms of clustering coefficients, which measure the likelihood that two neighbors of a node are themselves connected. Computing these measures exactly for large-scale networks is prohibitively expensive in both memory and time. However, a recent wedge-sampling algorithm has proved successful in efficiently and accurately estimating clustering coefficients. In this paper, we describe how to implement this approach in MapReduce to deal with massive graphs. We show results on publicly available networks, the largest of which is 132M nodes and 4.7B edges, as well as artificially generated networks (using the Graph500 benchmark), the largest of which has 240M nodes and 8.5B edges. We can estimate the clustering coefficient by degree bin (e.g., we use exponential binning) and the number of triangles per bin, as well as the global clustering coefficient and total number of triangles, in an average of 0.33 seconds per million edges plus overhead (approximately 225 seconds total for our configuration). The technique can also be used to study triangle statistics such as the ratio of the highest and lowest degree, and we highlight differences between social and nonsocial networks. To the best of our knowledge, these are the largest triangle-based graph computations published to date.<\/jats:p>","DOI":"10.1137\/13090729x","type":"journal-article","created":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T10:30:52Z","timestamp":1414665052000},"page":"S48-S77","source":"Crossref","is-referenced-by-count":68,"title":["Counting Triangles in Massive Graphs with MapReduce"],"prefix":"10.1137","volume":"36","author":[{"given":"Tamara G.","family":"Kolda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Todd","family":"Plantenga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christine","family":"Task","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"atypb1","unstructured":"Hadoop\n                      , Apache Software Foundation, http:\/\/hadoop.apache.org\/ (2012)."},{"key":"atypb2","first-page":"1450","volume-title":"Proceedings of High Performance Computing, Networking, Storage and Analysis (SCC)","author":"Arifuzzaman S.","year":"2012"},{"key":"atypb3","volume-title":"Technical report 12-042, Network Dynamics and Simulation Science Laboratory","author":"Arifuzzaman S. M.","year":"2012"},{"key":"atypb4","volume-title":"Proceedings of KDD-LDMTA'10","author":"Avron H.","year":"2010"},{"key":"atypb5","first-page":"623","volume-title":"Proceedings of SODA'02","author":"Bar-Yossef Z.","year":"2002"},{"key":"atypb6","first-page":"1","volume-title":"Proceedings of IPDPS 2009: IEEE International Symposium on Parallel and Distributed Processing","author":"Barrett B. W.","year":"2009"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398503"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066117"},{"key":"atypb21","first-page":"17","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation","author":"Gonzalez J.","year":"2012"},{"key":"atypb22","first-page":"10","volume-title":"Proceedings of CASON '09: International Conference on Computational Aspects of Social Networks","author":"Guo W.","year":"2009"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.2307\/2282952"},{"key":"atypb24","volume-title":"Social Science Research Network","author":"Huang Z.","year":"2010"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"atypb26","unstructured":"M. Jha, C. Seshadhri, and A. Pinar, http:\/\/arxiv.org\/abs\/1310.7665\n                      When a Graph is Not So Simple: Counting Triangles in Multigraph Streams\n                      , arXiv:1310.7665, 2013."},{"key":"atypb27","first-page":"710","volume-title":"COCOON'05: Computing and Combinatorics, L. Wang, ed., Lecture Notes in Comput. Sci. 3595","author":"Jowhari H.","year":"2005"},{"key":"atypb28","first-page":"229","volume-title":"Proceedings of ICDM '09. Ninth IEEE International Conference on Data Mining","author":"Kang U.","year":"2009"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"atypb32","first-page":"85","volume-title":"Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '11","author":"Lattanzi S.","year":"2011"},{"key":"atypb33","first-page":"985","volume":"11","author":"Leskovec J.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb34","volume-title":"Throw Away Everything That's Not a Nail! arXiv:1209.2191","author":"Lin J.","year":"2012"},{"key":"atypb35","unstructured":"J. Lin and C. Dyer,\n                      Data-Intensive Text Processing with MapReduce\n                      , http:\/\/lintool.github.com\/MapReduceAlgorithms\/ed1n.htmlhttp:\/\/lintool.github. com\/MapReduceAlgorithms\/ed1n.html (2012)."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/1830252.1830263"},{"key":"atypb37","unstructured":"Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein, http:\/\/arxiv.org\/abs\/1006.4990\n                      GraphLab: A New Framework for Parallel Machine Learning\n                      , arXiv:1006.4990, 2010."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.021544898"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.036122"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.037103"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"atypb45","volume-title":"Proceedings of IPDPS","author":"Pearce R.","year":"2013"},{"key":"atypb46","volume-title":"MapReduce R-MAT graph generator","author":"Plantenga T.","year":"2012"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.10.005"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772778"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00108"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"atypb52","first-page":"587","volume-title":"ICDM 2011: Proceedings of the 2011 IEEE International Conference on Data Mining","author":"Seshadhri C.","year":"2011"},{"key":"atypb53","volume-title":"Proceedings of the 2012 SIAM International Conference on Data Mining","author":"Seshadhri C."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"atypb55","first-page":"781","volume-title":"CIKM13: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, ACM","author":"Tangwongsan K.","year":"2013"},{"key":"atypb56","first-page":"66","volume-title":"Proceedings of ASONAM '09. International Conference on Advances in Social Network Analysis and Mining","author":"Tsourakakis C.","year":"2009"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00245"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"atypb60","unstructured":"J. Ugander, B. Karrer, L. Backstrom, and C. Marlow, http:\/\/arxiv.org\/abs\/1111.4503\n                      The Anatomy of the Facebook Social Graph\n                      , arXiv:1111.4503v1, 2011."},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"atypb63","first-page":"43","volume-title":"ICNC'11: 2011 7th International Conference on Natural Computation","volume":"1","author":"Wu B.","year":"2011"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24082-9_83"},{"key":"atypb65","volume-title":"Hadoop JobInfo tool","author":"Yoshimura A.","year":"2012"},{"key":"atypb66","first-page":"390","volume-title":"IPDPS'12: Proceedings of the IEEE 26th International Parallel Distributed Processing Symposium","author":"Zhao Z.","year":"2012"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/13090729X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:44:32Z","timestamp":1787327072000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/13090729X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":66,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/13090729X"],"URL":"https:\/\/doi.org\/10.1137\/13090729x","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}