Email this article APROXIMATION ALGORITHM BASED ON MULTI-START METHOD TO SOLVE THE MINIMUM S-CLUB COVER
About this article
Received: 23/11/23 Revised: 27/12/23 Published: 27/12/23Authors
Pham Dinh Thanh
, Tay Bac University
Abstract
s-club model is widely used in social network analysis, protein interaction analysis, etc., where the Minimum s-club cover problem has recently received attention. Although there is an approximate algorithm to solve the Minimum s-club cover problem, this algorithm can only be applied to the case s = 2. In addition, the previous algorithm uses a greedy strategy, so the quality of the obtained solution is not good and depends on the input graph. Therefore, this study proposes an approximate algorithm based on multi-start method to solve the Minimum s-club cover problem. To improve the quality of the received solutions, this study also proposes a greedy strategy to find the best club at each step, as well as a method for creating and evaluating neighbors of the current solution. The effectiveness of the proposed algorithm is demonstrated through comparison with a previously published approximation algorithm on two different data sets from the DIMACS library. Experimental results show that the proposed algorithm finds better solutions in one-third of the tested cases, and the two algorithms are equal in two-thirds of the tested cases.
Keywords
Full Text:
PDF (Tiếng Việt)References
[1] R. J. Mokken, “Cliques, clubs and clans,” Qual. Quant., vol. 13, no. 2, pp. 161–173, 1979.
[2] S. Fortunato, “Community detection in graphs,” Phys. Rep., vol. 486, no. 3–5, pp. 75–174, 2010.
[3] S. Pasupuleti, “Detection of protein complexes in protein interaction networks using n-clubs,” presented at the European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, Springer, 2008, pp. 153–164.
[4] L. Cavique, A. B. Mendes, and J. M. Santos, “An algorithm to discover the k-clique cover in networks,” presented at the Progress in Artificial Intelligence: 14th Portuguese Conference on Artificial Intelligence, EPIA 2009, Aveiro, Portugal, October 12-15, 2009. Proceedings 14, Springer, 2009, pp. 363–373.
[5] D. Chakraborty, L. S. Chandran, S. Padinhatteeri, and R. R. Pillai, “Algorithms and complexity of s-club cluster vertex deletion,” presented at the International Workshop on Combinatorial Algorithms, Springer, 2021, pp. 152–164.
[6] A. Figiel, A.-S. Himmel, A. Nichterlein, and R. Niedermeier, “On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering.,” presented at the CIAC, 2021, pp. 216–230.
[7] H. Liu, P. Zhang, and D. Zhu, “On editing graphs into 2-club clusters,” presented at the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management: Joint International Conference, FAW-AAIM 2012, Beijing, China, May 14-16, 2012. Proceedings, Springer, 2012, pp. 235–246.
[8] J.-M. Bourjolly, G. Laporte, and G. Pesant, “An exact algorithm for the maximum k-club problem in an undirected graph,” Eur. J. Oper. Res., vol. 138, no. 1, pp. 21–28, 2002.
[9] Y. Asahiro, E. Miyano, K. Samizo, and H. Shimizu, “Optimal approximation algorithms for maximum distance-bounded subgraph problems,” Algorithmica, vol. 80, no. 6, pp. 1834–1856, 2018.
[10] R. Dondi, G. Mauri, and I. Zoppis, “On the tractability of finding disjoint clubs in a network,” Theor. Comput. Sci., vol. 777, pp. 243–251, 2019.
[11] P. Zou, H. Li, W. Wang, C. Xin, and B. Zhu, “Finding disjoint dense clubs in a social network,” Theor. Comput. Sci., vol. 734, pp. 15–23, 2018.
[12] R. Dondi, G. Mauri, F. Sikora, and Z. Italo, “Covering a graph with clubs,” J. Graph Algorithms Appl., vol. 23, no. 2, pp. 271–292, 2019.
[13] M. Gendreau and J.-Y. Potvin, Handbook of metaheuristics, vol. 2. Springer, 2010.
[14] R. Martí, J. A. Lozano, A. Mendiburu, and L. Hernando, “Multi-start methods,” in Handbook of heuristics, Springer, 2018, pp. 155–175.
[15] R. Martí, M. G. Resende, and C. C. Ribeiro, “Multi-start methods for combinatorial optimization,” Eur. J. Oper. Res., vol. 226, no. 1, pp. 1–8, 2013.
[16] D. S. Johnson and M. A. Trick, Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, vol. 26. American Mathematical Soc., 1996.
[17] D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Graph partitioning and graph clustering, vol. 588. American Mathematical Society Providence, RI, 2013.
DOI: https://doi.org/10.34238/tnu-jst.9280
Refbacks
- There are currently no refbacks.