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 interactions
analysis. 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.
Full Text:
PDFReferences
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.10695
This work is licensed under a Creative Commons Attribution 3.0 License.