{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:19:46Z","timestamp":1762323586164,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>\n            <jats:italic>Triangle listing<\/jats:italic>\n            is one of the fundamental algorithmic problems whose solution has numerous applications especially in the analysis of complex networks, such as the computation of clustering coefficients, transitivity, triangular connectivity, trusses, etc. Existing algorithms for triangle listing are mainly in-memory algorithms, whose performance cannot scale with the massive volume of today's fast growing networks. When the input graph cannot fit in main memory, triangle listing requires random disk accesses that can incur prohibitively huge I\/O cost. Some streaming, semistreaming, and sampling algorithms have been proposed but these are approximation algorithms. We propose an I\/O-efficient algorithm for triangle listing. Our algorithm is exact and avoids random disk access. Our results show that our algorithm is scalable and outperforms the state-of-the-art in-memory and local triangle estimation algorithms.\n          <\/jats:p>","DOI":"10.1145\/2382577.2382581","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":72,"title":["Triangle listing in massive networks"],"prefix":"10.1145","volume":"6","author":[{"given":"Shumo","family":"Chu","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"James","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2012,12,18]]},"reference":[{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS'06)","author":"Abou-Rjeili A.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/48529.48535"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1006\/jcss.1997.1545"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.5555\/647904.739463"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1007912.1007931"},{"volume-title":"Proceedings of the ACM\/SIAM Annual Symposium on Discrete Algorithms (SODA'02)","author":"Bar-Yossef Z.","key":"e_1_2_1_6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/S0378-8733(01)00035-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1016\/j.disc.2005.09.051"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1401890.1401898"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1839490.1839494"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1341531.1341547"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/1142351.1142388"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1109\/ICDE.2011.5767911"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1807167.1807217"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/2043652.2043654"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/2020408.2020513"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/MCSE.2009.120"},{"volume-title":"Proceedings of the ACM SIGMOD-SIGACT-SIGART Annual Symposium on Discrete Algorithms (SODA'04)","author":"Coppersmith D.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1073\/pnas.032093399"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/978-3-642-03367-4_25"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/316188.316229"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/795666.796597"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/335305.335370"},{"volume-title":"Proceedings of the IEEE Design Automation Conference.","author":"Fiduccia C. M.","key":"e_1_2_1_24_1"},{"unstructured":"Fritzke B. 1993. A self-organizing network for unsupervised learning. Tech. rep. TR-03-026 42.  Fritzke B. 1993. A self-organizing network for unsupervised learning. Tech. rep. TR-03-026 42.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1086\/225469"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/800105.803390"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1137\/0207033"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1137\/S0036144598334138"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1016\/j.tcs.2008.07.017"},{"doi-asserted-by":"crossref","unstructured":"Milo R. Shen-Orr S. Itzkovitz S. Kashtan N. Chklovskii D. and Alon U. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 824--827.  Milo R. Shen-Orr S. Itzkovitz S. Kashtan N. Chklovskii D. and Alon U. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 824--827.","key":"e_1_2_1_32_1","DOI":"10.1126\/science.298.5594.824"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1137\/S003614450342480"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1073\/pnas.012582999"},{"unstructured":"Schank T. 2007. Algorithmic aspects of triangle-based network analysis. Ph.D. dissertation Universit\u00e4t Karlsruhe Fakult\u00e4t f\u00fcr Informatik.  Schank T. 2007. Algorithmic aspects of triangle-based network analysis. Ph.D. dissertation Universit\u00e4t Karlsruhe Fakult\u00e4t f\u00fcr Informatik.","key":"e_1_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/11427186_54"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/1963405.1963491"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/274363.274365"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/1557019.1557111"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.14778\/1921071.1921073"},{"doi-asserted-by":"crossref","unstructured":"Wasserman S. and Faust K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.  Wasserman S. and Faust K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.","key":"e_1_2_1_41_1","DOI":"10.1017\/CBO9780511815478"},{"doi-asserted-by":"crossref","unstructured":"Watts D. J. and Strogatz S. H. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 440--442.  Watts D. J. and Strogatz S. H. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 440--442.","key":"e_1_2_1_42_1","DOI":"10.1038\/30918"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382577.2382581","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2382577.2382581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:38Z","timestamp":1750239278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382577.2382581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2382577.2382581"],"URL":"https:\/\/doi.org\/10.1145\/2382577.2382581","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}