{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T12:00:51Z","timestamp":1790769651366,"version":"4.1.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"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":[[2021,10,31]]},"abstract":"<jats:p>\n            Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top-\n            <jats:italic>k<\/jats:italic>\n            degree-based quasi-cliques and make the following contributions: (1)\u00a0we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2)\u00a0We present a novel heuristic algorithm K\n            <jats:sc>ernel<\/jats:sc>\n            QC to enumerate the\n            <jats:italic>k<\/jats:italic>\n            largest quasi-cliques in a graph. Our method is based on identifying\n            <jats:italic>kernels<\/jats:italic>\n            of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3)\u00a0Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.\n          <\/jats:p>","DOI":"10.1145\/3446637","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T10:40:41Z","timestamp":1618483241000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Mining Largest Maximal Quasi-Cliques"],"prefix":"10.1145","volume":"15","author":[{"given":"Seyed-Vahid","family":"Sanei-Mehri","sequence":"first","affiliation":[{"name":"Iowa State University, Ames, Iowa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Apurba","family":"Das","sequence":"additional","affiliation":[{"name":"BITS Pilani, Hyderabad Campus, Hyderabad, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hooman","family":"Hashemi","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames, Iowa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanta","family":"Tirthapura","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames, Iowa"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646389.690506"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1973.9989826"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.09.004"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.032"},{"key":"e_1_2_1_9_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 ). Vladimir Batagelj and Matjaz Zaversnik. 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAIS.2009.39"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339726"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Learning and Intelligent Optimization. Springer, 41--55","author":"Brunato Mauro","year":"2007","unstructured":"Mauro Brunato , Holger H. Hoos , and Roberto Battiti . 2007 . On effectively finding maximal quasi-cliques in graphs . In Proceedings of the International Conference on Learning and Intelligent Optimization. Springer, 41--55 . Mauro Brunato, Holger H. Hoos, and Roberto Battiti. 2007. On effectively finding maximal quasi-cliques in graphs. In Proceedings of the International Conference on Learning and Intelligent Optimization. Springer, 41--55."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_19_1","volume-title":"Triangle listing in massive networks. ACM Transactions on Knowledge Discovery from Data 6, 4","author":"Chu Shumo","year":"2012","unstructured":"Shumo Chu and James Cheng . 2012. Triangle listing in massive networks. ACM Transactions on Knowledge Discovery from Data 6, 4 ( 2012 ), 17. Shumo Chu and James Cheng. 2012. Triangle listing in massive networks. ACM Transactions on Knowledge Discovery from Data 6, 4 (2012), 17."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","volume":"148","author":"Conte Alessio","year":"2016","unstructured":"Alessio Conte , Roberto Grossi , Andrea Marino , and Luca Versari . 2016 . Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) , Vol. 148 . 1--148. Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. 2016. Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916), Vol. 148. 1--148."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2018.00016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380936"},{"key":"e_1_2_1_26_1","volume-title":"Change-sensitive algorithms for maintaining maximal cliques in a dynamic graph. CoRR abs\/1601.06311","author":"Das Apurba","year":"2016","unstructured":"Apurba Das , Michael Svendsen , and Srikanta Tirthapura . 2016. Change-sensitive algorithms for maintaining maximal cliques in a dynamic graph. CoRR abs\/1601.06311 ( 2016 ). http:\/\/arxiv.org\/abs\/1601.06311 Apurba Das, Michael Svendsen, and Srikanta Tirthapura. 2016. Change-sensitive algorithms for maintaining maximal cliques in a dynamic graph. CoRR abs\/1601.06311 (2016). http:\/\/arxiv.org\/abs\/1601.06311"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004366"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.04.040"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1086\/229972"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_2_1_32_1","volume-title":"Johnson","author":"Garey Michael R.","year":"2002","unstructured":"Michael R. Garey and David S . Johnson . 2002 . Computers and Intractability. Vol. 29 . W.H. Freeman , New York. Michael R. Garey and David S. Johnson. 2002. Computers and Intractability. Vol. 29. W.H. Freeman, New York."},{"key":"e_1_2_1_33_1","volume-title":"Finding a Maximum Density Subgraph","author":"Goldberg Andrew V.","unstructured":"Andrew V. Goldberg . 1984. Finding a Maximum Density Subgraph . University of California Berkeley , CA. Andrew V. Goldberg. 1984. Finding a Maximum Density Subgraph. University of California Berkeley, CA."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.95"},{"key":"e_1_2_1_35_1","volume-title":"Scalable mining of maximal quasi-cliques: An algorithm-system codesign approach. arXiv preprint arXiv:2005.00081","author":"Guo Guimu","year":"2020","unstructured":"Guimu Guo , Da Yan , M. Tamer \u00d6zsu , and Zhe Jiang . 2020. Scalable mining of maximal quasi-cliques: An algorithm-system codesign approach. arXiv preprint arXiv:2005.00081 ( 2020 ). Guimu Guo, Da Yan, M. Tamer \u00d6zsu, and Zhe Jiang. 2020. Scalable mining of maximal quasi-cliques: An algorithm-system codesign approach. arXiv preprint arXiv:2005.00081 (2020)."},{"key":"e_1_2_1_36_1","volume-title":"A method for pinpoint clustering of web","author":"Haraguchi Makoto","unstructured":"Makoto Haraguchi and Yoshiaki Okubo . 2006. A method for pinpoint clustering of web pages with pseudo-clique search. In Federation Over the Web. Springer , 59--78. Makoto Haraguchi and Yoshiaki Okubo. 2006. A method for pinpoint clustering of web pages with pseudo-clique search. In Federation Over the Web. Springer, 59--78."},{"key":"e_1_2_1_37_1","volume-title":"Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data 2, 4","author":"Jiang Daxin","year":"2009","unstructured":"Daxin Jiang and Jian Pei . 2009. Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data 2, 4 ( 2009 ), 16. Daxin Jiang and Jian Pei. 2009. Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data 2, 4 (2009), 16."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.3390\/a9010021"},{"key":"e_1_2_1_41_1","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs Valdis E.","year":"2002","unstructured":"Valdis E. Krebs . 2002 . Mapping networks of terrorist cells . Connections 24 , 3 (2002), 43 -- 52 . Valdis E. Krebs. 2002. Mapping networks of terrorist cells. Connections 24, 3 (2002), 43--52.","journal-title":"Connections"},{"key":"e_1_2_1_42_1","volume-title":"Lakshmanan","author":"Lee Pei","year":"2016","unstructured":"Pei Lee and Laks V.S . Lakshmanan . 2016 . Query-driven maximum quasi-clique search. In Proceedings of the 2016 SIAM International Conference on Data Mining. SIAM , 522--530. Pei Lee and Laks V.S. Lakshmanan. 2016. Query-driven maximum quasi-clique search. In Proceedings of the 2016 SIAM International Conference on Data Mining. SIAM, 522--530."},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Guimei Liu Kelvin Sim and Jinyan Li. 2006. Efficient mining of large maximal bicliques. In Data Warehousing and Knowledge Discovery. 437--448.  Guimei Liu Kelvin Sim and Jinyan Li. 2006. Efficient mining of large maximal bicliques. In Data Warehousing and Knowledge Discovery. 437--448.","DOI":"10.1007\/11823728_42"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87481-2_3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2017.0037"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 112","author":"Marinelli Fabrizio","year":"2018","unstructured":"Fabrizio Marinelli , Andrea Pizzuti , and Fabrizio Rossi . 2018 . A star-based reformulation for the maximum quasi-clique problem . In Proceedings of the 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 112 . Fabrizio Marinelli, Andrea Pizzuti, and Fabrizio Rossi. 2018. A star-based reformulation for the maximum quasi-clique problem. In Proceedings of the 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 112."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00091-7"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.metabol.2014.10.030"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2016.2523997"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2527643"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Ha-Myung Park Francesco Silvestri Rasmus Pagh Chin-Wan Chung Sung-Hyon Myaeng and U. Kang. 2018. Enumerating trillion subgraphs on distributed systems. ACM Transactions on Knowledge Discovery from Data 12 6 (2018) 71.  Ha-Myung Park Francesco Silvestri Rasmus Pagh Chin-Wan Chung Sung-Hyon Myaeng and U. Kang. 2018. Enumerating trillion subgraphs on distributed systems. ACM Transactions on Knowledge Discovery from Data 12 6 (2018) 71.","DOI":"10.1145\/3237191"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21791"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.019"},{"key":"e_1_2_1_57_1","volume-title":"Handbook of Optimization in Complex Networks","author":"Pattillo Jeffrey","unstructured":"Jeffrey Pattillo , Nataly Youssef , and Sergiy Butenko . 2012. Clique relaxation models in social network analysis . In Handbook of Optimization in Complex Networks . Springer , 143--162. Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. 2012. Clique relaxation models in social network analysis. In Handbook of Optimization in Complex Networks. Springer, 143--162."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12637"},{"key":"e_1_2_1_61_1","volume-title":"Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data 11, 3","author":"Rozenshtein Polina","year":"2017","unstructured":"Polina Rozenshtein , Nikolaj Tatti , and Aristides Gionis . 2017. Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data 11, 3 ( 2017 ), 27. Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. 2017. Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data 11, 3 (2017), 27."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622352"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140443"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.111"},{"key":"e_1_2_1_66_1","volume-title":"Mirny","author":"Spirin Victor","year":"2003","unstructured":"Victor Spirin and Leonid A . Mirny . 2003 . Protein complexes and functional modules in molecular networks. 100, 21 (2003), 12123--12128. DOI:https:\/\/doi.org\/10.1073\/pnas.2032324100 10.1073\/pnas.2032324100 Victor Spirin and Leonid A. Mirny. 2003. Protein complexes and functional modules in molecular networks. 100, 21 (2003), 12123--12128. DOI:https:\/\/doi.org\/10.1073\/pnas.2032324100"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.08.011"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijms17060862"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_72_1","volume-title":"A novel approach to finding near-cliques: The triangle-densest subgraph problem. arXiv preprint arXiv:1405.1477","author":"Tsourakakis Charalampos E.","year":"2014","unstructured":"Charalampos E. Tsourakakis . 2014. A novel approach to finding near-cliques: The triangle-densest subgraph problem. arXiv preprint arXiv:1405.1477 ( 2014 ). Charalampos E. Tsourakakis. 2014. A novel approach to finding near-cliques: The triangle-densest subgraph problem. arXiv preprint arXiv:1405.1477 (2014)."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77120-3_36"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0051883"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-014-0782-2"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60796-8_45"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242530"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446637","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:31Z","timestamp":1750193251000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":77,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3446637"],"URL":"https:\/\/doi.org\/10.1145\/3446637","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}