{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:30:12Z","timestamp":1781217012423,"version":"3.54.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["419008"],"award-info":[{"award-number":["419008"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["2050483"],"award-info":[{"award-number":["2050483"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000947","name":"Australian Cancer Research Foundation","doi-asserted-by":"publisher","award":["M52020092"],"award-info":[{"award-number":["M52020092"]}],"id":[{"id":"10.13039\/501100000947","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n            <jats:italic>Maximal clique enumeration<\/jats:italic>\n            is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory space linear in the size of the input graph. This has become a serious concern in view of the massive volume of today's fast-growing networks. We propose a general framework for designing external-memory algorithms for maximal clique enumeration in large graphs. The general framework enables maximal clique enumeration to be processed recursively in small subgraphs of the input graph, thus allowing in-memory computation of maximal cliques without the costly random disk access. We prove that the set of cliques obtained by the recursive local computation is both correct (i.e., globally maximal) and complete. The subgraph to be processed each time is defined based on a set of\n            <jats:italic>base vertices<\/jats:italic>\n            that can be flexibly chosen to achieve different purposes. We discuss the selection of the base vertices to fully utilize the available memory in order to minimize I\/O cost in static graphs, and for update maintenance in dynamic graphs. We also apply our framework to design an external-memory algorithm for maximum clique computation in a large graph.\n          <\/jats:p>","DOI":"10.1145\/2043652.2043654","type":"journal-article","created":{"date-parts":[[2011,12,20]],"date-time":"2011-12-20T17:49:14Z","timestamp":1324403354000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":126,"title":["Finding maximal cliques in massive networks"],"prefix":"10.1145","volume":"36","author":[{"given":"James","family":"Cheng","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yiping","family":"Ke","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, New Territories, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ada Wai-Chee","family":"Fu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, New Territories, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, New Territories, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Linhong","family":"Zhu","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,12,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Conference on Research Trends in Science and Technology.","author":"Abu-Khzam F. N."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(79)90014-5"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the AAAI-04 Workshop on Agent Organizations: Theory and Practice.","author":"Berry N. M."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2004.02.004"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bomze I. M. Budinich M. Pardalos P. M. and Pelillo M. 1999. The maximum clique problem. In Handbook of Combinatorial Optimization. Kluwer Academic Publishers 1--74.  Bomze I. M. Budinich M. Pardalos P. M. and Pelillo M. 1999. The maximum clique problem. In Handbook of Combinatorial Optimization. Kluwer Academic Publishers 1--74.","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). 456--457","author":"Byskov J. M.","year":"2003"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.010"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00528-2_3"},{"key":"e_1_2_1_12_1","unstructured":"Dorogovtsev S. N. and Mendesand J. F. F. 2003. Evolution of Networks: From Biological Nets to the Internet and www. Oxford University Press.   Dorogovtsev S. N. and Mendesand J. F. F. 2003. Evolution of Networks: From Biological Nets to the Internet and www. Oxford University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Du N. Wu B. Xu L. Wang B. and Xin P. 2009. Parallel algorithm for enumerating maximal cliques in complex network. In Mining Complex Data 207--221.  Du N. Wu B. Xu L. Wang B. and Xin P. 2009. Parallel algorithm for enumerating maximal cliques in complex network. In Mining Complex Data 207--221.","DOI":"10.1007\/978-3-540-88067-7_12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Faust K. and Wasserman S. 1995. Social Network Analysis: Methods and Applications. Cambridge University Press.  Faust K. and Wasserman S. 1995. Social Network Analysis: Methods and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Data Mining (ICDM). 163--170","author":"Gouda K."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).","author":"Kilby P."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Knuth D. E. 1975. Estimating the efficiency of backtrack programs. Math. Comput. 29 129 121--136.  Knuth D. E. 1975. Estimating the efficiency of backtrack programs. Math. Comput. 29 129 121--136.","DOI":"10.2307\/2005469"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00286-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.12.1198"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Scandinavian Workshop on Algorithms Theory (SWAT). 260--272","author":"Makino K."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458288"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiolchem.2004.03.002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.01.003"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:COAP.0000008651.28952.b6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783712.1783736"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11811305_67"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn036"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2043652.2043654","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2043652.2043654","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:19Z","timestamp":1750240459000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2043652.2043654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2043652.2043654"],"URL":"https:\/\/doi.org\/10.1145\/2043652.2043654","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}