{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T23:24:23Z","timestamp":1777937063516,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF Graduate Research Fellowship","award":["1122374"],"award-info":[{"award-number":["1122374"]}]},{"name":"DOE Early Career Award","award":["DE-SC0018947"],"award-info":[{"award-number":["DE-SC0018947"]}]},{"name":"NSF CAREER Award","award":["CCF-1845763"],"award-info":[{"award-number":["CCF-1845763"]}]},{"name":"Google Faculty Research Award, Google Research Scholar Award, CSAIL CAP Initiative, DARPA SDH Award","award":["HR0011-18-3-0007"],"award-info":[{"award-number":["HR0011-18-3-0007"]}]},{"name":"Applications Driving Architectures (ADA) Research Center, a JUMP Center co-sponsored by SRC and DARPA"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Counting the frequency of subgraphs in large networks is a classic research question that reveals the underlying substructures of these networks for important applications. However, subgraph counting is a challenging problem, even for subgraph sizes as small as five, due to the combinatorial explosion in the number of possible occurrences. This article focuses on the five-cycle, which is an important special case of five-vertex subgraph counting and one of the most difficult to count efficiently.<\/jats:p>\n          <jats:p>We design two new parallel five-cycle counting algorithms and prove that they are work efficient and achieve polylogarithmic span. Both algorithms are based on computing low out-degree orientations, which enables the efficient computation of directed two-paths and three-paths, and the algorithms differ in the ways in which they use this orientation to eliminate double-counting. Additionally, we present new parallel algorithms for obtaining unbiased estimates of five-cycle counts using graph sparsification. We develop fast multicore implementations of the algorithms and propose a work scheduling optimization to improve their performance. Our experiments on a variety of real-world graphs using a 36-core machine with two-way hyper-threading show that our best exact parallel algorithm achieves 10\u201346\u00d7 self-relative speedup, outperforms our serial benchmarks by 10\u201332\u00d7, and outperforms the previous state-of-the-art serial algorithm by up to 818\u00d7. Our best approximate algorithm, for a reasonable probability parameter, achieves up to 20\u00d7 self-relative speedup and is able to approximate five-cycle counts 9\u2013189\u00d7 faster than our best exact algorithm, with between 0.52% and 11.77% error.<\/jats:p>","DOI":"10.1145\/3556541","type":"journal-article","created":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T12:33:21Z","timestamp":1660653201000},"page":"1-23","source":"Crossref","is-referenced-by-count":3,"title":["Parallel Five-cycle Counting Algorithms"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4485-5492","authenticated-orcid":false,"given":"Jessica","family":"Shi","sequence":"first","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1951-1372","authenticated-orcid":false,"given":"Louisa Ruixue","family":"Huang","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6163-6625","authenticated-orcid":false,"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0965-5"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/892318"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_7_2","first-page":"38:1\u201338:20","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference","author":"Bera Suman K.","year":"2020","unstructured":"Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. 2020. Linear time subgraph counting, graph degeneracy, and the chasm at size six. In Proceedings of the Innovations in Theoretical Computer Science Conference, Vol. 151. 38:1\u201338:20."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554819"},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Besta Maciej","year":"2020","unstructured":"Maciej Besta, Armon Carigiet, Kacper Janda, Zur Vonarburg-Shmaria, Lukas Gianinazzi, and Torsten Hoefler. 2020. High-performance parallel graph coloring with strong guarantees on work, depth, and quality. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Article 99."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1086\/421787"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210414"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3398682.3399168"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783413"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883082"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.026107"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2010.03.004"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185438"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_56"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt717"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1086\/224954"},{"key":"e_1_3_2_27_2","first-page":"2:1\u20132:18","volume-title":"Proceedings of the International Symposium on Experimental Algorithms (SEA\u201921)","volume":"190","author":"Huang Louisa Ruixue","year":"2021","unstructured":"Louisa Ruixue Huang, Jessica Shi, and Julian Shun. 2021. Parallel five-cycle counting algorithms. In Proceedings of the International Symposium on Experimental Algorithms (SEA\u201921), Vol. 190. 2:1\u20132:18."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/133889"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39890-5_25"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-010-0405-3"},{"key":"e_1_3_2_31_2","unstructured":"Jure Leskovec and Andrej Krevl. 2019. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1561\/106.00000003"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297929"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_3_2_43_2","article-title":"Algorithmic aspects of triangle-based network analysis","author":"Schank T.","year":"2007","unstructured":"T. Schank. 2007. Algorithmic aspects of triangle-based network analysis. Ph.D. Dissertation. Universitat Karlsruhe (2007).","journal-title":"Ph.D. Dissertation. Universitat Karlsruhe"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976830.13"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.2"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl038"},{"key":"e_1_3_2_50_2","volume-title":"Efficient and Scalable Listing of Four-Vertex Subgraphs","author":"Xia Xiangzhou","year":"2016","unstructured":"Xiangzhou Xia. 2016. Efficient and Scalable Listing of Four-Vertex Subgraphs. Master\u2019s thesis. Texas A&M University."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00100"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556541","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3556541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:32Z","timestamp":1750186832000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":50,"alternative-id":["10.1145\/3556541"],"URL":"https:\/\/doi.org\/10.1145\/3556541","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,21]]}}}