{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T14:59:03Z","timestamp":1784905143126,"version":"3.55.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks.<\/jats:p>\n          <jats:p>\n            In this paper, we devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approach\n            <jats:italic>RMC<\/jats:italic>\n            , for the randomized maximum clique problem, employs a binary search while maintaining a lower bound\n            <jats:italic>\n              &lt;u&gt;\u03c9\n              <jats:sub>c<\/jats:sub>\n              &lt;\/u&gt;\n            <\/jats:italic>\n            and an upper bound [EQUATION] of\n            <jats:italic>\u03c9<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ). In each iteration,\n            <jats:italic>RMC<\/jats:italic>\n            attempts to find a\n            <jats:italic>\n              \u03c9\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            -clique where [EQUATION]. As finding\n            <jats:italic>\n              \u03c9\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            in each iteration is NP-complete, we extract a seed set\n            <jats:italic>S<\/jats:italic>\n            such that the problem of finding a\n            <jats:italic>\n              \u03c9\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            -clique in\n            <jats:italic>G<\/jats:italic>\n            is equivalent to finding a\n            <jats:italic>\n              \u03c9\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            -clique in\n            <jats:italic>S<\/jats:italic>\n            with probability guarantees (\u22651\u2212\n            <jats:italic>\n              n\n              <jats:sup>\u2212c<\/jats:sup>\n            <\/jats:italic>\n            ). We propose a novel iterative algorithm to determine the maximum clique by searching a\n            <jats:italic>k<\/jats:italic>\n            -clique in\n            <jats:italic>S<\/jats:italic>\n            starting from\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>\n              &lt;u&gt;\u03c9\n              <jats:sub>c<\/jats:sub>\n              &lt;\/u&gt;\n            <\/jats:italic>\n            +1 until\n            <jats:italic>S<\/jats:italic>\n            becomes [EQUATION], when more iterations benefit marginally. As confirmed by the experiments, our approach is much more efficient and robust than previous solutions and can always find the exact maximum clique.\n          <\/jats:p>","DOI":"10.14778\/3137628.3137660","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1538-1549","source":"Crossref","is-referenced-by-count":53,"title":["Finding the maximum clique in massive graphs"],"prefix":"10.14778","volume":"10","author":[{"given":"Can","family":"Lu","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hao","family":"Wei","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yikai","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"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.1145\/2505515.2505751"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"A.-L. Barab\u00e1si and R. Albert. Emergence of scaling in random networks. Science 286(5439) 1999.  A.-L. Barab\u00e1si and R. Albert. Emergence of scaling in random networks. Science 286(5439) 1999.","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_5_1","unstructured":"V. Batagelj and M. Zaversnik. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 2003.  V. Batagelj and M. Zaversnik. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 2003."},{"key":"e_1_2_1_6_1","volume-title":"Prof. of AAAI-04 Workshop on Agent Organizations: Theory and Practice","author":"Berry N.","year":"2004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339724"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_12_1","first-page":"6","article-title":"On random graphs i","author":"Erd\u00f6s P.","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740816"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185341"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"T. A. Feo and M. G. Resende. Greedy randomized adaptive search procedures. Journal of global optimization 6 1995.  T. A. Feo and M. G. Resende. Greedy randomized adaptive search procedures. Journal of global optimization 6 1995.","DOI":"10.1007\/BF01096763"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90072-U"},{"key":"e_1_2_1_18_1","volume-title":"Proc. of VLDB","author":"Gibson D.","year":"2005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"F. Glover and M. Laguna. Tabu Search. 2013.  F. Glover and M. Laguna. Tabu Search. 2013.","DOI":"10.1007\/978-1-4419-7997-1_17"},{"key":"e_1_2_1_20_1","volume-title":"Proc. of FOCS","author":"Ha\u00e5stad J.","year":"1996"},{"key":"e_1_2_1_21_1","first-page":"3","article-title":"Large cliques elude the metropolis process","author":"Jerrum M.","year":"1992","journal-title":"Random Structures & Algorithms"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_23_1","volume-title":"Complexity of computer computations.","author":"Karp R. M.","year":"1972"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00286-3"},{"key":"e_1_2_1_25_1","unstructured":"J. Konc and D. Janezic. An improved branch and bound algorithm for the maximum clique problem. proteins 4(5) 2007.  J. Konc and D. Janezic. An improved branch and bound algorithm for the maximum clique problem. proteins 4(5) 2007."},{"key":"e_1_2_1_26_1","volume-title":"Found. Control Eng.","author":"Kopf R.","year":"1987"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_29_1","unstructured":"J. Leskovec and R. Sosi\u010d. SNAP: A general purpose network analysis and graph mining library in C++. http:\/\/snap.stanford.edu\/snap 2014.  J. Leskovec and R. Sosi\u010d. SNAP: A general purpose network analysis and graph mining library in C++. http:\/\/snap.stanford.edu\/snap 2014."},{"key":"e_1_2_1_30_1","volume-title":"Proc. of ACSW","author":"Leung K.","year":"2005"},{"key":"e_1_2_1_31_1","first-page":"14","article-title":"A method of matrix analysis of group structure","author":"Luce R. D.","year":"1949","journal-title":"Psychometrika"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"e_1_2_1_34_1","volume-title":"Helsinki University of Technology Helsinki","author":"Niskanen S.","year":"2003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0224-z"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03536-9_13"},{"key":"e_1_2_1_38_1","first-page":"5","article-title":"Exact algorithms for maximum clique: A computational study","author":"Prosser P.","year":"2012","journal-title":"Algorithms"},{"key":"e_1_2_1_39_1","first-page":"25","article-title":"Dynamic local search for the maximum clique problem","author":"Pullan W.","year":"2006","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2577283"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"S. B. Seidman. Network structure and minimum degree. Social networks 5 1983.  S. B. Seidman. Network structure and minimum degree. Social networks 5 1983.","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_42_1","first-page":"6","article-title":"Finding a maximum independent set","author":"Tarjan R. E.","year":"1977","journal-title":"SIAM Journal on Computing"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-006-9039-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_18"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487689"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature 393(6684) 1998.  D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature 393(6684) 1998.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_49_1","first-page":"101","article-title":"Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction","author":"Yeger-Lotem E.","year":"2004","journal-title":"PNAS"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113300"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150506"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"X. Zheng T. Liu Z. Yang and J. Wang. Large cliques in arabidopsis gene coexpression network and motif discovery. Journal of plant physiology 168 2011.  X. Zheng T. Liu Z. Yang and J. Wang. Large cliques in arabidopsis gene coexpression network and motif discovery. Journal of plant physiology 168 2011.","DOI":"10.1016\/j.jplph.2010.09.010"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:59:12Z","timestamp":1672221552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137660"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":52,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137660"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137660","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}