{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T01:05:21Z","timestamp":1777597521697,"version":"3.51.4"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T00:00:00Z","timestamp":1733961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T00:00:00Z","timestamp":1733961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s11704-024-40238-8","type":"journal-article","created":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T01:42:55Z","timestamp":1733967775000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improving local search algorithms for clique relaxation problems via group driven initialization"],"prefix":"10.1007","volume":"19","author":[{"given":"Rui","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiyuan","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,12]]},"reference":[{"key":"40238_CR1","first-page":"106","volume-title":"Proceedings of the 9th International Symposium on Experimental Algorithms","author":"N Malod-Dognin","year":"2010","unstructured":"Malod-Dognin N, Andonov R, Yanev N. Maximum cliques in protein structure comparison. In: Proceedings of the 9th International Symposium on Experimental Algorithms. 2010, 106\u2013117"},{"key":"40238_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-23247-3_6","volume-title":"Handbook of Memetic Algorithms","author":"J K Hao","year":"2012","unstructured":"Hao J K. Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P, eds. Handbook of Memetic Algorithms. Berlin: Springer, 2012, 73\u201394"},{"issue":"2","key":"40238_CR3","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/TCSS.2018.2831694","volume":"5","author":"N Alduaiji","year":"2018","unstructured":"Alduaiji N, Datta A, Li J. Influence propagation model for clique-based community detection in social networks. IEEE Transactions on Computational Social Systems, 2018, 5(2): 563\u2013575","journal-title":"IEEE Transactions on Computational Social Systems"},{"issue":"1","key":"40238_CR4","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/s00357-019-9310-5","volume":"37","author":"G Ouyang","year":"2020","unstructured":"Ouyang G, Dey D K, Zhang P. Clique-based method for social network clustering. Journal of Classification, 2020, 37(1): 254\u2013274","journal-title":"Journal of Classification"},{"issue":"3","key":"40238_CR5","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/s10878-012-9473-z","volume":"26","author":"S Shahinpour","year":"2013","unstructured":"Shahinpour S, Butenko S. Algorithms for the maximum k-club problem in graphs. Journal of Combinatorial Optimization, 2013, 26(3): 520\u2013554","journal-title":"Journal of Combinatorial Optimization"},{"key":"40238_CR6","first-page":"5613","volume-title":"Proceedings of the 32nd International Joint Conference on Artificial Intelligence","author":"H Jiang","year":"2023","unstructured":"Jiang H, Xu F, Zheng Z, Wang B, Zhou W. A refined upper bound and inprocessing for the maximum k-plex problem. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 2023, 5613\u20135621"},{"key":"40238_CR7","first-page":"12258","volume-title":"Proceedings of the 35th AAAI Conference on Artificial Intelligence","author":"J Chen","year":"2021","unstructured":"Chen J, Cai S, Pan S, Wang Y, Lin Q, Zhao M, Yin M. NuQClq: An effective local search algorithm for maximum quasi-clique problem. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 12258\u201312266"},{"key":"40238_CR8","first-page":"10174","volume-title":"Proceedings of the 36th AAAI Conference on Artificial Intelligence","author":"J Gao","year":"2022","unstructured":"Gao J, Xu Z, Li R, Yin M. An exact algorithm with new upper bounds for the maximum k-defective clique problem in massive sparse graphs. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 10174\u201310183"},{"key":"40238_CR9","series-title":"Dissertation","volume-title":"Graph theoretic generalizations of clique: optimization and extensions","author":"B Balasundaram","year":"2007","unstructured":"Balasundaram B. Graph theoretic generalizations of clique: optimization and extensions. Texas A&M University, Dissertation, 2007"},{"key":"40238_CR10","first-page":"137","volume-title":"Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"D Kempe","year":"2003","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 137\u2013146"},{"issue":"1","key":"40238_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/310641.310644","volume":"6","author":"L Terveen","year":"1999","unstructured":"Terveen L, Hill W, Amento B. Constructing, organizing, and visualizing collections of topically related web resources. ACM Transactions on Computer-Human Interaction, 1999, 6(1): 67\u201394","journal-title":"ACM Transactions on Computer-Human Interaction"},{"issue":"7","key":"40238_CR12","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1093\/bioinformatics\/btl014","volume":"22","author":"H Yu","year":"2006","unstructured":"Yu H, Paccanaro A, Trifonov V, Gerstein M. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 2006, 22(7): 823\u2013829","journal-title":"Bioinformatics"},{"key":"40238_CR13","volume-title":"Nature Precedings","author":"S Bandyopadhyay","year":"2012","unstructured":"Bandyopadhyay S, Bhattacharyya M. Mining the largest quasi-clique in human protein interactome. Nature Precedings, 2012"},{"key":"40238_CR14","first-page":"253","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing","author":"M Yannakakis","year":"1978","unstructured":"Yannakakis M. Node- and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing. 1978, 253\u2013264"},{"issue":"1","key":"40238_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0377-2217(01)00133-3","volume":"138","author":"J M Bourjolly","year":"2002","unstructured":"Bourjolly J M, Laporte G, Pesant G. An exact algorithm for the maximum k-club problem in an undirected graph. European Journal of Operational Research, 2002, 138(1): 21\u201328","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"40238_CR16","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram B, Butenko S, Hicks I V. Clique relaxations in social network analysis: the maximum k-plex problem. Operations Research, 2011, 59(1): 133\u2013142","journal-title":"Operations Research"},{"issue":"1\u20132","key":"40238_CR17","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.dam.2012.07.019","volume":"161","author":"J Pattillo","year":"2013","unstructured":"Pattillo J, Veremyev A, Butenko S, Boginski V. On the maximum quasi-clique problem. Discrete Applied Mathematics, 2013, 161(1\u20132): 244\u2013257","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"40238_CR18","doi-asserted-by":"publisher","first-page":"143601","DOI":"10.1007\/s11704-019-7235-0","volume":"14","author":"Y Peng","year":"2020","unstructured":"Peng Y, Xu Y, Zhao H, Zhou Z, Han H. Most similar maximal clique query on large graphs. Frontiers of Computer Science, 2020, 14(3): 143601","journal-title":"Frontiers of Computer Science"},{"key":"40238_CR19","first-page":"5648","volume-title":"Proceedings of the 32nd International Joint Conference on Artificial Intelligence","author":"Z Wang","year":"2023","unstructured":"Wang Z, Zhou Y, Luo C, Xiao M. A fast maximum k-plex algorithm parameterized by the degeneracy gap. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 2023, 5648\u20135656"},{"issue":"3","key":"40238_CR20","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1287\/ijoc.2019.0922","volume":"32","author":"Z Miao","year":"2020","unstructured":"Miao Z, Balasundaram B. An ellipsoidal bounding scheme for the quasi-clique number of a graph. INFORMS Journal on Computing, 2020, 32(3): 763\u2013778","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"40238_CR21","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1287\/ijoo.2021.0068","volume":"4","author":"N Daemi","year":"2022","unstructured":"Daemi N, Borrero J S, Balasundaram B. Interdicting low-diameter cohesive subgroups in large-scale social networks. INFORMS Journal on Optimization, 2022, 4(3): 304\u2013325","journal-title":"INFORMS Journal on Optimization"},{"key":"40238_CR22","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.cor.2014.07.006","volume":"52","author":"M T Almeida","year":"2014","unstructured":"Almeida M T, Carvalho F D. Two-phase heuristics for the k-club problem. Computers & Operations Research, 2014, 52: 94\u2013104","journal-title":"Computers & Operations Research"},{"issue":"8","key":"40238_CR23","doi-asserted-by":"publisher","first-page":"1947","DOI":"10.1007\/s11590-015-0971-7","volume":"12","author":"E Moradi","year":"2018","unstructured":"Moradi E, Balasundaram B. Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optimization Letters, 2018, 12(8): 1947\u20131957","journal-title":"Optimization Letters"},{"key":"40238_CR24","first-page":"10146","volume-title":"Proceedings of the 36th AAAI Conference on Artificial Intelligence","author":"J Chen","year":"2022","unstructured":"Chen J, Wang Y, Cai S, Yin M, Zhou Y, Wu J. NukCP: an improved local search algorithm for maximum k-club problem. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 10146\u201310155"},{"key":"40238_CR25","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cor.2017.05.005","volume":"86","author":"Y Zhou","year":"2017","unstructured":"Zhou Y, Hao J K. Frequency-driven tabu search for the maximum s-plex problem. Computers & Operations Research, 2017, 86: 65\u201378","journal-title":"Computers & Operations Research"},{"key":"40238_CR26","first-page":"2343","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence","author":"P Chen","year":"2020","unstructured":"Chen P, Wan H, Cai S, Li J, Chen H. Local search with dynamic-threshold configuration checking and incremental neighborhood updating for maximum k-plex problem. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 2343\u20132350"},{"issue":"3","key":"40238_CR27","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10732-020-09459-5","volume":"27","author":"W Pullan","year":"2021","unstructured":"Pullan W. Local search for the maximum k-plex problem. Journal of Heuristics, 2021, 27(3): 303\u2013324","journal-title":"Journal of Heuristics"},{"key":"40238_CR28","doi-asserted-by":"publisher","first-page":"109758","DOI":"10.1016\/j.asoc.2022.109758","volume":"131","author":"Y Jin","year":"2022","unstructured":"Jin Y, Drake J H, He K, Benlic U. Reinforcement learning based coarse-to-fine search for the maximum k-plex problem. Applied Soft Computing, 2022, 131: 109758","journal-title":"Applied Soft Computing"},{"key":"40238_CR29","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/j.cie.2019.04.040","volume":"132","author":"Y Djeddi","year":"2019","unstructured":"Djeddi Y, Haddadene H A, Belacel N. An extension of adaptive multistart tabu search for the maximum quasi-clique problem. Computers & Industrial Engineering, 2019, 132: 280\u2013292","journal-title":"Computers & Industrial Engineering"},{"issue":"1","key":"40238_CR30","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.ejor.2020.03.019","volume":"286","author":"Q Zhou","year":"2020","unstructured":"Zhou Q, Benlic U, Wu Q. An opposition-based memetic algorithm for the maximum quasi-clique problem. European Journal of Operational Research, 2020, 286(1): 63\u201383","journal-title":"European Journal of Operational Research"},{"key":"40238_CR31","doi-asserted-by":"publisher","first-page":"S741","DOI":"10.1051\/ro\/2020003","volume":"55","author":"B Q Pinto","year":"2021","unstructured":"Pinto B Q, Ribeiro C C, Riveaux J A, Rosseti I. A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy. RAIRO-Operations Research, 2021, 55: S741\u2013S763","journal-title":"RAIRO-Operations Research"},{"issue":"6","key":"40238_CR32","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1016\/j.physa.2011.12.004","volume":"391","author":"A Lipowski","year":"2012","unstructured":"Lipowski A, Lipowska D. Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and Its Applications, 2012, 391(6): 2193\u20132196","journal-title":"Physica A: Statistical Mechanics and Its Applications"},{"issue":"3","key":"40238_CR33","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu Q, Hao J K. A review on algorithms for maximum clique problems. European Journal of Operational Research, 2015, 242(3): 693\u2013709","journal-title":"European Journal of Operational Research"},{"key":"40238_CR34","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1613\/jair.5443","volume":"59","author":"S Cai","year":"2017","unstructured":"Cai S, Lin J, Luo C. Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess. Journal of Artificial Intelligence Research, 2017, 59: 463\u2013494","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"40238_CR35","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"M E J Newman","year":"2004","unstructured":"Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113","journal-title":"Physical Review E"},{"issue":"10","key":"40238_CR36","doi-asserted-by":"publisher","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"V D Blondel","year":"2008","unstructured":"Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008","journal-title":"Journal of Statistical Mechanics: Theory and Experiment"},{"key":"40238_CR37","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","volume":"3","author":"M L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez M, Dubois-Lacoste J, C\u00e1ceres L P, Birattari M, St\u00fctzle T. The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives, 2016, 3: 43\u201358","journal-title":"Operations Research Perspectives"},{"key":"40238_CR38","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026","volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11\u201313, 1993","author":"D S Johnson","year":"1996","unstructured":"Johnson D S, Trick M A. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11\u201313, 1993. Boston: American Mathematical Society, 1996"},{"issue":"8\u20139","key":"40238_CR39","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K Xu","year":"2007","unstructured":"Xu K, Boussemart F, Hemery F, Lecoutre C. Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 2007, 171(8\u20139): 514\u2013534","journal-title":"Artificial Intelligence"},{"issue":"1","key":"40238_CR40","first-page":"1","volume":"38","author":"T A Davis","year":"2011","unstructured":"Davis T A, Hu Y. The university of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 2011, 38(1): 1","journal-title":"ACM Transactions on Mathematical Software"},{"key":"40238_CR41","first-page":"4292","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence","author":"R A Rossi","year":"2015","unstructured":"Rossi R A, Ahmed N K. The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 4292\u20134293"},{"key":"40238_CR42","doi-asserted-by":"publisher","first-page":"103230","DOI":"10.1016\/j.artint.2019.103230","volume":"280","author":"Y Wang","year":"2020","unstructured":"Wang Y, Cai S, Chen J, Yin M. SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem. Artificial Intelligence, 2020, 280: 103230","journal-title":"Artificial Intelligence"},{"issue":"2","key":"40238_CR43","doi-asserted-by":"publisher","first-page":"182326","DOI":"10.1007\/s11704-023-3018-8","volume":"18","author":"L Jiang","year":"2024","unstructured":"Jiang L, Ouyang D, Zhang Q, Zhang L. DeciLS-PBO: an effective local search method for pseudo-Boolean optimization. Frontiers of Computer Science, 2024, 18(2): 182326","journal-title":"Frontiers of Computer Science"},{"issue":"4","key":"40238_CR44","doi-asserted-by":"publisher","first-page":"174326","DOI":"10.1007\/s11704-022-2023-7","volume":"17","author":"S Pan","year":"2023","unstructured":"Pan S, Ma Y, Wang Y, Zhou Z, Ji J, Yin M, Hu S. An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem. Frontiers of Computer Science, 2023, 17(4): 174326","journal-title":"Frontiers of Computer Science"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40238-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-024-40238-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40238-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T03:40:41Z","timestamp":1733974841000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-024-40238-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,12]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["40238"],"URL":"https:\/\/doi.org\/10.1007\/s11704-024-40238-8","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,12]]},"assertion":[{"value":"8 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"<b>Competing interests<\/b> The authors declare that they have no competing interests or financial conflicts to disclose.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics"}}],"article-number":"196403"}}