New Local Search Strategy for the Minimum s-Club Cover Problem
Abstract
The Minimum s-Club Cover problem presents significant challenges in social networks and group interactionsanalysis. Several studies have employed hybrid approaches to solve this problem, notably combining local search techniques with multifactorial evolutionary algorithms. To enhance the computational efficiency of such hybrid methodologies, this study proposes a novel local search method designed specifically for integration with a multifactorial evolutionary framework. The proposed local search algorithm is based on a combination of greedy and exhaustive strategies. The greedy strategy is applied when selecting clubs, while the exhaustive strategy is used when determining the appropriate clubs for vertex relocation. Unlike existing local search methods that operate at the vertex level, the proposed algorithm focuses on manipulating clubs directly. The effectiveness of the proposed approach is evaluated using benchmark datasets from the DIMACS library. Experimental results demonstrate that the algorithm achieves competitive performance, validating its potential in solving the Minimum s-Club Cover problem.References
Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: 10th dimacs implementation challengegraph
partitioning and graph clustering (2011)
Binh, H.T.T., Thang, T.B., Thai, N.D., Thanh, P.D.: A bi-level encoding scheme for the clustered
shortest-path tree problem in multifactorial optimization. Engineering Applications of Artificial
Intelligence 100, 104187 (2021)
Binh, H.T.T., Thangy, T.B., Long, N.B., Hoang, N.V., Thanh, P.D.: Multifactorial evolutionary
algorithm for inter-domain path computation under domain uniqueness constraint. In: 2020 IEEE
Congress on Evolutionary Computation (CEC). pp. 1–8. IEEE (2020)
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 138(1), 21–28 (2002)
Cavique, L., Mendes, A.B., Santos, J.M.: An algorithm to discover the k-clique cover in networks.
In: Progress in Artificial Intelligence: 14th Portuguese Conference on Artificial Intelligence,
EPIA 2009, Aveiro, Portugal, October 12-15, 2009. Proceedings 14. pp. 363–373. Springer
(2009)
Cerioli, M.R., Faria, L., Ferreira, T.O., Martinhon, C.A., Protti, F., Reed, B.: Partition into
cliques for cubic graphs: Planar case, complexity and approximation. Discrete Applied Mathematics
(12), 2270–2278 (2008)
Chakraborty, D., Chandran, L.S., Padinhatteeri, S., Pillai, R.R.: Algorithms and complexity of
s-club cluster vertex deletion. In: International Workshop on Combinatorial Algorithms. pp. 152–
Springer (2021)
Chaouche, A., Boulif, M.: Solving the unsupervised graph partitioning problem with genetic algorithms: Classical and new encoding representations. Computers & Industrial Engineering 137, 106025 (Nov
, https://linkinghub.elsevier.com/retrieve/pii/S036083521930484X
Dinh, T.P., Thanh, B.H.T., Ba, T.T., Binh, L.N.: Multifactorial evolutionary algorithm for solving
clustered tree problems: competition among cayley codes: Case studies on the clustered shortestpath
tree problem and the minimum inter-cluster routing cost clustered tree problem. Memetic Computing 12(3), 185–217 (2020)
Dondi, R., Lafond, M.: On the tractability of covering a graph with 2-clubs. Algorithmica 85(4),
–1028 (2023)
Dondi, R., Mauri, G., Sikora, F., Italo, Z.: Covering a graph with clubs. Journal of Graph Algorithms
and Applications 23(2) (2019)
Dondi, R., Mauri, G., Sikora, F., Italo, Z.: Covering a graph with clubs. Journal of Graph Algorithms
and Applications 23(2) (2019)
Dondi, R., Mauri, G., Zoppis, I.: On the tractability of finding disjoint clubs in a network. Theoretical
Computer Science 777, 243–251 (2019)
Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs. Graphs and Combinatorics
(3), 399–411 (2011)
Feng, L., Huang, Y., Zhou, L., Zhong, J., Gupta, A., Tang, K., Tan, K.C.: Explicit evolutionary
multitasking for combinatorial optimization: A case study on capacitated vehicle routing problem.
IEEE transactions on cybernetics 51(6), 3143–3156 (2020)
Fortunato, S.: Community detection in graphs. Physics reports 486(3-5), 75–174 (2010)
Gupta, A., Ong, Y.S., Feng, L.: Multifactorial evolution: toward evolutionary multitasking.
IEEE Transactions on Evolutionary Computation 20(3), 343–357 (2015)
Gupta, A., Zhou, L., Ong, Y.S., Chen, Z., Hou, Y.: Half a dozen real-world applications of evolutionary
multitasking, and more. IEEE Computational Intelligence Magazine 17(2), 49–66 (2022)
Huynh Thi Thanh, B., Pham Dinh, T.: Two levels approach based on multifactorial optimization
to solve the clustered shortest path tree problem. Evolutionary Intelligence 15(1), 185–213 (2022)
Johnson, D.S., Trick, M.A.: Cliques, coloring, and satisfiability: second DIMACS implementation
challenge, October 11-13, 1993, vol. 26. American Mathematical Soc. (1996)
Laan, S., Marx, M., Mokken, R.J.: Close communities in social networks: boroughs and 2-
clubs. Social Network Analysis and Mining 6, 1–16 (2016)
Lu, Z., Zhou, Y., Hao, J.K.: A hybrid evolutionary algorithm for the clique partitioning problem.
IEEE Transactions on Cybernetics 52(9), 9391–9403 (2021), publisher: IEEE
Maggi, L., Leguay, J., Cohen, J., Medagliani, P.: Domain clustering for inter-domain path computation
speed-up. Networks 71(3), 252–270 (2018)
Mokken, R.J., Heemskerk, E.M., Laan, S.: Close communication and 2-clubs in corporate networks:
Europe 2010. Social Network Analysis and Mining 6, 1–19 (2016)
Mokken, R.J., et al.: Cliques, clubs and clans. Quality & Quantity 13(2), 161–173 (1979)
Pasupuleti, S.: Detection of protein complexes in protein interaction networks using n-clubs.
In: Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics: 6th European
Conference, EvoBIO 2008, Naples, Italy, March 26-28, 2008. Proceedings 6. pp. 153–164.
Springer (2008)
Thang, T.B., Long, N.B., Hoang, N.V., Binh, H.T.T.: Adaptive knowledge transfer in multifactorial
evolutionary algorithm for the clustered minimum routing cost problem. Applied Soft Computing 105, 107253 (2021)
Thanh, P.D., Anh, D.T.: A hybrid multifactorial evolutionary algorithm for the minimum s-club
cover problem. In: International Symposium on Information and Communication Technology. pp.
–242. Springer (2024)
Thanh, P.D., Long, N.B., Vinh, L.S., Binh, H.T.T.: Evolutionary multitasking algorithm
based on a dynamic solution encoding strategy for the minimum s-club cover problem. Evolutionary
Intelligence 18(1), 15 (2025)
Wen, Y.W., Ting, C.K.: Parting ways and reallocating resources in evolutionary multitasking. In:
IEEE Congress on Evolutionary Computation (CEC). pp. 2404–2411. IEEE (2017)
DOI:
https://doi.org/10.31449/inf.v49i3.10695Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
