THUẬT TOÁN GẦN ĐÚNG DỰA TRÊN PHƯƠNG THỨC KHỞI TẠO  LỜI GIẢI NHIỀU LẦN GIẢI BÀI TOÁN MINIMUM S-CLUB COVER

Phạm Đình Thành

doi:10.34238/tnu-jst.9280

THUẬT TOÁN GẦN ĐÚNG DỰA TRÊN PHƯƠNG THỨC KHỞI TẠO LỜI GIẢI NHIỀU LẦN GIẢI BÀI TOÁN MINIMUM S-CLUB COVER

Thông tin bài báo

Ngày nhận bài: 23/11/23 Ngày hoàn thiện: 27/12/23 Ngày đăng: 27/12/23

Các tác giả

Phạm Đình Thành , Trường Đại học Tây Bắc

Tóm tắt

Phủ đồ thị là một trong các chủ đề cơ bản trong nghiên cứu lý thuyết về khoa học máy tính. Đối với hướng nghiên cứu về phủ tập đỉnh của đồ thị, mô hình s-club được ứng dụng nhiều trong phân tích mạng xã hội, phân tích tương tác protein,... trong đó bài toán Minimum s-club cover nhận được sự quan tâm nghiên cứu trong thời gian gần đây. Mặc dù đã có thuật toán gần đúng để giải bài toán Minimum s-club cover, tuy nhiên, thuật toán này chỉ được áp dụng cho trường hợp s = 2 và do sử dụng chiến lược tham nên chất lượng lời giải của thuật toán phụ thuộc nhiều vào đồ thị đầu vào. Do đó, nghiên cứu này đề xuất thuật toán gần đúng dựa trên việc khởi tạo lời giải nhiều lần để giải bài toán Minimum s-club cover. Để nâng cao chất lượng lời giải tìm được, nghiên cứu còn đề xuất chiến lược tham lam để tìm club tốt nhất tại mỗi bước, cũng như phương pháp tạo lân cận và đánh giá lân cận của lời giải hiện tại. Hiệu quả của thuật toán đề xuất được chứng minh qua việc so sánh với thuật toán gần đúng được công bố trước đây trên hai tập dữ liệu khác nhau từ thư viện DIMACS. Kết quả thực nghiệm cho thấy, thuật toán đề xuất tìm được lời giải tốt hơn trên một phần ba bộ dữ liệu và tìm được lời giải bằng nhau trên hai phần ba bộ dữ liệu.

Từ khóa

Minimum s-club cover; Phương thức đa khởi tạo; Phủ đồ thị; Thuật toán tham lam; Lân cận

Toàn văn:

PDF

Tài liệu tham khảo

[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

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ