Improving local search algorithms for clique relaxation problems via group driven initialization

Abstract

Clique relaxation problems are important extension versions of the maximum clique problem with extensive real-world applications. Although lots of studies focus on designing local search algorithms for solving these problems, almost all state-of-the-art local search algorithms adopt a common general initialization method. This paper develops a general group driven initialization method for clique relaxation problems. The proposed method uses two kinds of ways to divide vertices into some subgroups by using the useful information of the search procedure and the structure information of a given instance and then constructs a good initial solution by considering the generated group information. We apply the proposed initialization method to two clique relaxation problems. Experimental results demonstrate that the proposed initialization method clearly improves the performance of state-of-the-art algorithms for the clique relaxation problems.

Graphical abstract

Keywords

combinatorial optimization / clique relaxation problems / group driven initialization / local search / group information

Rui Sun received the BS and MS degrees from the Software College, Jilin University, China in 2019 and 2022, respectively. His current research interests include local search, combinatorial optimization, propositional satisfiability problems

Yiyuan Wang is an associate professor at School of Computer Science and Information Technology, Northeast Normal University, China. He received his PhD degree from Jilin University, China. His research interests include heuristic search, local search, algorithmic design, combinatorial optimization

Minghao Yin is a professor at School of Computer Science and Information Technology, Northeast Normal University, China. He received his PhD degree in Computer Software and Theory from Jilin University, China. His research interests include heuristic search, data mining, and combinatorial optimization

References

[1] 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−117

[2] Hao J K. Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P, eds. Handbook of Memetic Algorithms. Berlin: Springer, 2012, 73−94

[3] 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–575

[4] Ouyang G, Dey D K, Zhang P . Clique-based method for social network clustering. Journal of Classification, 2020, 37( 1): 254–274

[5] Shahinpour S, Butenko S . Algorithms for the maximum k-club problem in graphs. Journal of Combinatorial Optimization, 2013, 26( 3): 520–554

[6] 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−5621

[7] 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−12266

[8] 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−10183

[9] Balasundaram B. Graph theoretic generalizations of clique: optimization and extensions. Texas A&M University, Dissertation, 2007

[10] Kempe D, Kleinberg J, Tardos É. 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−146

[11] 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–94

[12] Yu H, Paccanaro A, Trifonov V, Gerstein M . Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 2006, 22( 7): 823–829

[13] Bandyopadhyay S, Bhattacharyya M . Mining the largest quasi-clique in human protein interactome. Nature Precedings, 2012,

[14] Yannakakis M. Node-and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing. 1978, 253−264

[15] 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–28

[16] Balasundaram B, Butenko S, Hicks I V . Clique relaxations in social network analysis: the maximum k-plex problem. Operations Research, 2011, 59( 1): 133–142

[17] Pattillo J, Veremyev A, Butenko S, Boginski V . On the maximum quasi-clique problem. Discrete Applied Mathematics, 2013, 161( 1−2): 244–257

[18] 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

[19] 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−5656

[20] Miao Z, Balasundaram B . An ellipsoidal bounding scheme for the quasi-clique number of a graph. INFORMS Journal on Computing, 2020, 32( 3): 763–778

[21] 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–325

[22] Almeida M T, Carvalho F D . Two-phase heuristics for the k-club problem. Computers & Operations Research, 2014, 52: 94–104

[23] Moradi E, Balasundaram B . Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optimization Letters, 2018, 12( 8): 1947–1957

[24] 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−10155

[25] Zhou Y, Hao J K . Frequency-driven tabu search for the maximum s-plex problem. Computers & Operations Research, 2017, 86: 65–78

[26] 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−2350

[27] Pullan W . Local search for the maximum k-plex problem. Journal of Heuristics, 2021, 27( 3): 303–324

[28] 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

[29] Djeddi Y, Haddadene H A, Belacel N . An extension of adaptive multi-start tabu search for the maximum quasi-clique problem. Computers & Industrial Engineering, 2019, 132: 280–292

[30] 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–83

[31] 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–S763

[32] Lipowski A, Lipowska D . Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and Its Applications, 2012, 391( 6): 2193–2196

[33] Wu Q, Hao J K . A review on algorithms for maximum clique problems. European Journal of Operational Research, 2015, 242( 3): 693–709

[34] 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–494

[35] Newman M E J, Girvan M . Finding and evaluating community structure in networks. Physical Review E, 2004, 69( 2): 026113

[36] 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

[37] López-Ibáñez M, Dubois-Lacoste J, Cáceres L P, Birattari M, Stützle T . The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives, 2016, 3: 43–58

[38] Johnson D S, Trick M A. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11−13, 1993. Boston: American Mathematical Society, 1996

[39] Xu K, Boussemart F, Hemery F, Lecoutre C . Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 2007, 171( 8-9): 514–534

[40] Davis T A, Hu Y . The university of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 2011, 38( 1): 1

[41] 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−4293

[42] 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

[43] 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

[44] 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

Acknowledgement

This work was supported by the National Natural Science Foundation of China (Grant Nos. 61806050, 61976050), CCF Huawei Hu Yanglin Foundation Theoretical Computer Science Project (CCF-HuaweiLK2023001), the Fundamental Research Funds for the Central Universities (2412022ZD015, 2412023YQ003), and Jilin Science and Technology Department (YDZJ202201ZYTS412, 20240602005RC).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2025 Higher Education Press