{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T19:47:54Z","timestamp":1781812074571,"version":"3.54.5"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education, Singapore","doi-asserted-by":"crossref","award":["MOE-T2EP20221-0013,MOE-T2EP20220-0011"],"award-info":[{"award-number":["MOE-T2EP20221-0013,MOE-T2EP20220-0011"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>k-clique listing is a vital graph mining operator with diverse applications in various networks. The state-of-the-art algorithms all adopt a branch-and-bound (BB) framework with a vertex-oriented branching strategy (called VBBkC), which forms a sub-branch by expanding a partial k-clique with a vertex. These algorithms have the time complexity of O(k \u00b7 m \u00b7 (\u03b4\/2)k-2 ), where m is the number of edges in the graph and \u03b4 is the degeneracy of the graph. In this paper, we propose a BB framework with a new edge-oriented branching (called EBBkC), which forms a sub-branch by expanding a partial k-clique with two vertices that connect each other (which correspond to an edge ). We explore various edge orderings for EBBkC such that it achieves a time complexity of O( m \u00b7 \u03b4 + k \u00b7 m \u00b7 (\u03c4\/2)k-2 ), where \u03c4 is an integer related to the maximum truss number of the graph and we have \u03c4 &lt; \u03b4. The time complexity of EBBkC is better than that of VBBkC algorithms for k&gt;3 since both O(m \u00b7 \u03b4) and O(k \u00b7 m \u00b7 (\u03c4\/2)k-2 ) are bounded by O(k \u00b7 m \u00b7 (\u03b4\/2)k-2 ). Furthermore, we develop specialized algorithms for sub-branches on dense graphs so that we can early-terminate them and apply the specialized algorithms. We conduct extensive experiments on 19 real graphs, and the results show that our newly developed EBBkC based algorithms with the early termination technique consistently and largely outperform the state-of-the-art (VBBkC based) algorithms.<\/jats:p>","DOI":"10.1145\/3639262","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":16,"title":["Efficient k-Clique Listing: An Edge-Oriented Branching Strategy"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6650-2850","authenticated-orcid":false,"given":"Kaixin","family":"Wang","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1153-2902","authenticated-orcid":false,"given":"Kaiqiang","family":"Yu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Real Graphs. http:\/\/lcs.ios.ac.cn\/~caisw\/Resource\/realworld%20graphs.tar.gz."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl039"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_2_2_4_1","volume-title":"arXiv preprint cs\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003)."},{"key":"e_1_2_2_5_1","volume-title":"Higher-order organization of complex networks. Science 353, 6295","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163--166."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00602-z"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401971"},{"key":"e_1_2_2_10_1","series-title":"SIAM Journal on computing 14, 1","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210--223."},{"key":"e_1_2_2_11_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008)."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_2_14_1","volume-title":"A combinatorial problem in geometry. Compositio mathematica 2","author":"Erd\u00f6s Paul","year":"1935","unstructured":"Paul Erd\u00f6s and George Szekeres. 1935. A combinatorial problem in geometry. Compositio mathematica 2 (1935), 463--470."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.229"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612697"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2008.0010"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.7763\/IJMLC.2012.V2.207"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2021.115915"},{"key":"e_1_2_2_22_1","volume-title":"Reducibility among combinatorial problems","author":"Karp Richard M","unstructured":"Richard M Karp. 2010. Reducibility among combinatorial problems. Springer."},{"key":"e_1_2_2_23_1","volume-title":"Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1--3","author":"Latapy Matthieu","year":"2008","unstructured":"Matthieu Latapy. 2008. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1--3 (2008), 458--473."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137660"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.016"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.1"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"e_1_2_2_30_1","volume-title":"Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043","author":"Palla Gergely","year":"2005","unstructured":"Gergely Palla, Imre Der\u00e9nyi, Ill\u00e9s Farkas, and Tam\u00e1s Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043 (2005), 814--818."},{"key":"e_1_2_2_31_1","volume-title":"Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043","author":"Palla Gergely","year":"2005","unstructured":"Gergely Palla, Imre Der\u00e9nyi, Ill\u00e9s Farkas, and Tam\u00e1s Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043 (2005), 814--818."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2014.986778"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1244408.1244417"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.01.003"},{"key":"e_1_2_2_37_1","first-page":"25","article-title":"Implementation issues of clique enumeration algorithm. Special issue: Theoretical computer science and discrete mathematics","volume":"9","author":"Takeaki UNO","year":"2012","unstructured":"UNO Takeaki. 2012. Implementation issues of clique enumeration algorithm. Special issue: Theoretical computer science and discrete mathematics, Progress in Informatics 9 (2012), 25--30.","journal-title":"Progress in Informatics"},{"key":"e_1_2_2_38_1","volume-title":"The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1","author":"Tomita Etsuji","year":"2006","unstructured":"Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1 (2006), 28--42."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_2_42_1","unstructured":"Kaixin Wang Kaiqiang Yu and Cheng Long. 2023. Efficient k-Clique Listing: An Edge-Oriented Branching Strategy (Technical Report). https:\/\/github.com\/wangkaixin219\/EBBkC\/blob\/main\/EBBkC_TR.pdf."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.104867"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157802"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00192"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58325-4_182"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639262","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:11:58Z","timestamp":1755789118000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639262"],"URL":"https:\/\/doi.org\/10.1145\/3639262","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}