{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T03:53:31Z","timestamp":1761796411737,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:00:00Z","timestamp":1761609600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2109988","OAC-2402560","CCF-2453324"],"award-info":[{"award-number":["CCF-2109988","OAC-2402560","CCF-2453324"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Counting and listing triangles in graphs is a fundamental task in network analysis, supporting applications such as community detection, clustering coefficient computation, k-truss decomposition, and triangle centrality. We introduce the cover-edge set, a novel concept that eliminates unnecessary edges during triangle enumeration, thereby improving efficiency. This compact cover-edge set is rapidly constructed using a breadth-first search (BFS) strategy. Using this concept, we develop both sequential and parallel triangle-counting algorithms and conduct comprehensive comparisons with state-of-the-art methods. We also design a benchmarking framework to evaluate our sequential and parallel algorithms in a systematic and reproducible manner. Extensive experiments on the latest Intel Xeon 8480+ processor reveal clear performance differences among algorithms, demonstrate the benefits of various optimization strategies, and show how graph characteristics, such as diameter and degree distribution, affect algorithm performance. Our source code is available on GitHub.<\/jats:p>","DOI":"10.3390\/a18110685","type":"journal-article","created":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T05:48:46Z","timestamp":1761716926000},"page":"685","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cover Edge-Based Novel Triangle Counting"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7380-5876","authenticated-orcid":false,"given":"David A.","family":"Bader","sequence":"first","affiliation":[{"name":"Department of Data Science, New Jersey Institute of Technology (NJIT), Newark, NJ 07102, USA"}]},{"given":"Fuhuan","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Data Science, New Jersey Institute of Technology (NJIT), Newark, NJ 07102, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8435-1611","authenticated-orcid":false,"given":"Zhihui","family":"Du","sequence":"additional","affiliation":[{"name":"Department of Data Science, New Jersey Institute of Technology (NJIT), Newark, NJ 07102, USA"}]},{"given":"Palina","family":"Pauliuchenka","sequence":"additional","affiliation":[{"name":"Department of Data Science, New Jersey Institute of Technology (NJIT), Newark, NJ 07102, USA"}]},{"given":"Oliver Alvarado","family":"Rodriguez","sequence":"additional","affiliation":[{"name":"Department of Data Science, New Jersey Institute of Technology (NJIT), Newark, NJ 07102, USA"}]},{"given":"Anant","family":"Gupta","sequence":"additional","affiliation":[{"name":"Computer Science & Data Science, Rutgers University, New Brunswick, NJ 08901, USA"}]},{"given":"Sai Sri Vastav","family":"Minnal","sequence":"additional","affiliation":[{"name":"Computer Science, University of Pennsylvania, Philadelphia, PA 19104, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2162-7286","authenticated-orcid":false,"given":"Valmik","family":"Nahata","sequence":"additional","affiliation":[{"name":"Machine Learning and Neural Computation, University of California, San Diego, CA 92093, USA"}]},{"given":"Anya","family":"Ganeshan","sequence":"additional","affiliation":[{"name":"Operations Research & Computer Science, Columbia University, New York, NY 10027, USA"}]},{"given":"Ahmet Cemal","family":"Gundogdu","sequence":"additional","affiliation":[{"name":"Computer Science & Entrepreneurship, Santa Clara University, Santa Clara, CA 95053, USA"}]},{"given":"Jason","family":"Lew","sequence":"additional","affiliation":[{"name":"Department of Data Science, New Jersey Institute of Technology (NJIT), Newark, NJ 07102, USA"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_2","first-page":"1","article-title":"Trusses: Cohesive subgraphs for social network analysis","volume":"16","author":"Cohen","year":"2008","journal-title":"Natl. Secur. Agency Tech. Rep."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/3685677","article-title":"Triangle Centrality","volume":"18","author":"Burkhardt","year":"2024","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_4","unstructured":"Graph 500 Steering Committee (2025, September 10). The Graph500 Benchmark. Available online: https:\/\/graph500.org\/."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Samsi, S., Gadepally, V., Hurley, M., Jones, M., Kao, E., Mohindra, S., Monticciolo, P., Reuther, A., Smith, S., and Song, W. (2018, January 25\u201327). GraphChallenge.org: Raising the Bar on Graph Analytic Performance. Proceedings of the 2018 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547527"},{"key":"ref_6","unstructured":"Harrod, W. (2022, May 24). Advanced Graphical Intelligence Logical Computing Environment (AGILE), Available online: https:\/\/www.iarpa.gov\/images\/PropsersDayPDFs\/AGILE\/AGILE_Proposers_Day_sm.pdf."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0207033","article-title":"Finding a minimum circuit in a graph","volume":"7","author":"Itai","year":"1978","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1016\/j.tcs.2008.07.017","article-title":"Main-memory triangle computations for very large (sparse (power-law)) graphs","volume":"407","author":"Latapy","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/MCSE.2009.120","article-title":"Graph twiddling in a MapReduce world","volume":"11","author":"Cohen","year":"2009","journal-title":"Comput. Sci. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Pearce, R. (2017, January 12\u201314). Triangle counting for scale-free graphs at scale in distributed memory. Proceedings of the IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA USA.","DOI":"10.1109\/HPEC.2017.8091051"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ghosh, S., and Halappanavar, M. (2020, January 22\u201324). TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure. Proceedings of the IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC43674.2020.9286167"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF02523189","article-title":"Finding and counting given length cycles","volume":"17","author":"Alon","year":"1997","journal-title":"Algorithmica"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Alman, J., and Williams, V.V. (2021, January 10\u201313). A refined laser method and faster matrix multiplication. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Virtual.","DOI":"10.1137\/1.9781611976465.32"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Xu, Y., Xu, Z., and Zhou, R. (2024, January 7\u201310). New bounds for matrix multiplication: From alpha to omega. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, Virginia.","DOI":"10.1137\/1.9781611977912.134"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An algorithm for subgraph isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM (JACM)"},{"key":"ref_16","first-page":"5","article-title":"Fast Parallel Algorithms for Counting and Listing Triangles in Big Graphs","volume":"14","author":"Arifuzzaman","year":"2019","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Makkar, D., Bader, D.A., and Green, O. (2017, January 18\u201321). Exact and Parallel Triangle Counting in Dynamic Graphs. Proceedings of the 24th IEEE International Conference on High Performance Computing, HiPC 2017, Jaipur, India.","DOI":"10.1109\/HiPC.2017.00011"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Mailthody, V.S., Date, K., Qureshi, Z., Pearson, C., Nagi, R., Xiong, J., and Hwu, W.m. (2018, January 25\u201327). Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. Proceedings of the 2018 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547517"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0214017","article-title":"Arboricity and Subgraph Listing Algorithms","volume":"14","author":"Chiba","year":"1985","journal-title":"SIAM J. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Davis, T.A. (2018, January 25\u201327). Graph algorithms via SuiteSparse: GraphBLAS: Triangle counting and K-truss. Proceedings of the 2018 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547538"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Mowlaei, S. (2017, January 12\u201314). Triangle counting via vectorized set intersection. Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2017.8091053"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Schank, T., and Wagner, D. (2005, January 10\u201313). Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study. Proceedings of the 4th International Conference on Experimental and Efficient Algorithms, Santorini Island, Greece. WEA\u201905.","DOI":"10.1007\/11427186_54"},{"key":"ref_23","unstructured":"Schank, T. (2007). Algorithmic Aspects of Triangle-Based Network Analysis. [Ph.D Thesis, Karlsruhe Institute of Technology]."},{"key":"ref_24","unstructured":"Ortmann, M., and Brandes, U. (2014, January 5). Triangle Listing Algorithms: Back from the Diversion. Proceedings of the Meeting on Algorithm Engineering & Expermiments, Portland, OR, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Low, T.M., Rao, V.N., Lee, M., Popovici, D., Franchetti, F., and McMillan, S. (2017, January 12\u201314). First look: Linear algebra-based triangle counting without matrix multiplication. Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2017.8091046"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Shun, J., and Tangwongsan, K. (2015, January 13\u201317). Multicore triangle computations without tuning. Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, Seoul, Republi of Korea.","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Parimalarangan, S., Slota, G.M., and Madduri, K. (June, January 29). Fast parallel graph triad census and triangle counting on shared-memory platforms. Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Orlando, FL, USA.","DOI":"10.1109\/IPDPSW.2017.144"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Hu, Y., Liu, H., and Huang, H.H. (2018, January 11\u201318). TriCore: Parallel triangle counting on GPUs. Proceedings of the SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, Dallas, TX, USA.","DOI":"10.1109\/SC.2018.00017"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Hu, L., Zou, L., and Liu, Y. (2021, January 20\u201325). Accelerating triangle counting on GPU. Proceedings of the 2021 International Conference on Management of Data, Xi\u2019an, China.","DOI":"10.1145\/3448016.3452815"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Zeng, L., Yang, K., Cai, H., Zhou, J., Zhao, R., and Chen, X. (2022, January 19\u201323). HTC: Hybrid vertex-parallel and edge-parallel Triangle Counting. Proceedings of the IEEE High Performance Extreme Computing Conference (HPEC), Virtual.","DOI":"10.1109\/HPEC55821.2022.9926383"},{"key":"ref_31","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2022). Introduction to Algorithms, MIT Press. [4th ed.]."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Li, F., Ganeshan, A., Gundogdu, A., Lew, J., Rodriguez, O.A., and Du, Z. (2023, January 25\u201329). Triangle Counting Through Cover-Edges. Proceedings of the 2023 IEEE High Performance Extreme Computing Conference (HPEC), Boston, MA, USA.","DOI":"10.1109\/HPEC58863.2023.10363465"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bader, D.A. (2023, January 25\u201329). Fast Triangle Counting. Proceedings of the 2023 IEEE High Performance Extreme Computing Conference (HPEC), Boston, MA, USA.","DOI":"10.1109\/HPEC58863.2023.10363539"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., and Faloutsos, C. (2004, January 22\u201324). R-MAT: A recursive model for graph mining. Proceedings of the 2004 SIAM International Conference on Data Mining, Lake Buena Vista, FL, USA.","DOI":"10.1137\/1.9781611972740.43"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/11\/685\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T03:48:34Z","timestamp":1761796114000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/11\/685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,28]]},"references-count":34,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2025,11]]}},"alternative-id":["a18110685"],"URL":"https:\/\/doi.org\/10.3390\/a18110685","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,10,28]]}}}