Analysis of the Malatya Centrality-Based Clique Method on DIMACS Benchmarks and Random Graphs

Year 2024, Volume: 5 Issue: 2, 63 - 69, 30.12.2024

Furkan Öztemiz , Selman Yakut

https://doi.org/10.46572/naturengs.1591530

Abstract

The Maximum Clique Problem (MCP) is an NP-complete problem that aims to find the largest clique (complete subgraph) within a given graph. This problem has widespread applications in fields such as social network analysis, bioinformatics, chemical information systems, and communication networks. Although various solution methods have been proposed in the literature, an effective method that provides a general solution across different graph types is not yet available. In this study, we demonstrate that our previously proposed maximum clique method provides an effective solution for MCP on DIMACS benchmark graphs and random graphs generated using different models such as Erdos-Renyi, Forest Fire, Watts-Strogatz, and Regular Random models. The proposed method begins by computing the complement of the original graph. In the complement graph, the maximum independent set is determined using the Malatya Independent Set Algorithm, an efficient algorithm well-recognized in the literature. The maximum independent set identified in the complement graph is then used to determine the subgraph corresponding to the maximum clique in the original graph. The effectiveness of the proposed method was validated through tests on widely recognized DIMACS benchmark graphs. Additionally, to evaluate its performance and robustness on unpredictable graphs, tests were conducted on random graphs of varying complexities generated using Erdos-Renyi, Forest Fire, Watts-Strogatz, and Regular Random models. The results of these tests demonstrated that the method produced optimal or near-optimal MCP solutions for both DIMACS and random graphs. The successful outcomes further highlight the efficiency of the proposed method and its potential applicability in MCP-related domains.

Keywords

Maximum clique, Maximum clique problem, Independent sets, Malatya centrality, Malatya independent set algorithm

References

• Y. Wang, S. Cai, J. Chen, and M. Yin, “SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem,” Artif. Intell., vol. 280, p. 103230, 2020, doi: 10.1016/j.artint.2019.103230.
• M. J. Brusco, D. Steinley, and A. L. Watts, “A maximal-clique-based set-covering approach to overlapping community detection,” Optim. Lett., no. 0123456789, 2023, doi: 10.1007/s11590-023-02054-0.
• D. Kumlander, “Some Practical Algorithms to Solve The Maximum Clique Problem,” 2005.
• Z. Yu, X. Wang, and J. Zhao, “A local dense decision-making method for solving the maximum clique problem in large-scale undirected graphs,” Comput. Electr. Eng., vol. 102, no. April, p. 108220, 2022, doi: 10.1016/j.compeleceng.2022.108220.
• S. Yakut and F. Öztemiz, “A New Maximum Clique Method,” in International Informatics Congress, 2024, pp. 200–208.
• H. Jiang, K. Bai, H. J. Liu, C. M. Li, F. Manyà, and Z. H. Fu, “Parallel Bounded Search for the Maximum Clique Problem,” J. Comput. Sci. Technol., vol. 38, no. 5, pp. 1187–1202, 2023, doi: 10.1007/s11390-022-1803-8.
• B. Peng, L. Wu, Y. Wang, and Q. Wu, “Solving maximum quasi-clique problem by a hybrid artificial bee colony approach,” Inf. Sci. (Ny)., vol. 578, pp. 214–235, 2021, doi: 10.1016/j.ins.2021.06.094.
• B. Pattabiraman, M. M. A. Patwary, A. H. Gebremedhin, W. K. Liao, and A. Choudhary, “Fast algorithms for the maximum clique problem on massive sparse graphs,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 8305 LNCS, no. 00, pp. 156–169, 2013, doi: 10.1007/978-3-319-03536-9_13.
• A. Douik, H. Dahrouj, T. Y. Al-Naffouri, and M. S. Alouini, “A Tutorial on Clique Problems in Communications and Signal Processing,” Proc. IEEE, vol. 108, no. 4, pp. 583–608, 2020, doi: 10.1109/JPROC.2020.2977595.
• M. T. Belachew and N. Gillis, “Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation,” J. Optim. Theory Appl., vol. 173, no. 1, pp. 279–296, 2017, doi: 10.1007/s10957-016-1043-6.
• M. Zhou, Q. Zeng, and P. Guo, “SMC-BRB: an algorithm for the maximum clique problem over large and sparse graphs with the upper bound via s+ -index,” J. Supercomput., vol. 79, no. 7, pp. 8026–8047, 2023, doi: 10.1007/s11227-022-04982-7.
• E. Pelofske, G. Hahn, and H. N. Djidjev, “Solving larger maximum clique problems using parallel quantum annealing,” Quantum Inf. Process., vol. 22, no. 5, pp. 1–22, 2023, doi: 10.1007/s11128-023-03962-x.
• M. Hasan, M. R. Islam, and A. G. Mugdha, “Solving maximum clique problem using chemical reaction optimization,” Opsearch, vol. 60, no. 3, pp. 1230–1266, 2023, doi: 10.1007/s12597-023-00654-z.
• M. Seda, “The Maximum Clique Problem and Integer Programming Models, Their Modifications, Complexity and Implementation,” Symmetry (Basel)., pp. 1–19, 2023.
• P. San Segundo, F. Furini, D. Álvarez, and P. M. Pardalos, “CliSAT: A new exact algorithm for hard maximum clique problems,” Eur. J. Oper. Res., vol. 307, no. 3, pp. 1008–1025, 2023, doi: 10.1016/j.ejor.2022.10.028.
• K. Reba, M. Guid, K. Rozman, D. Janežič, and J. Konc, “Exact maximum clique algorithm for different graph types using machine learning,” Mathematics, vol. 10, no. 1, 2022, doi: 10.3390/math10010097.
• F. Marinelli, A. Pizzuti, and F. Rossi, “LP-based dual bounds for the maximum quasi-clique problem,” Discret. Appl. Math., vol. 296, pp. 118–140, 2021, doi: 10.1016/j.dam.2020.02.003.
• J. Abello, P. Pardalos, and M. Resende, “On maximum clique problems in very large graphs,” AT&T Labs Res. Tech. Rep., no. November 1998, pp. 119–130, 1999, doi: 10.1090/dimacs/050/06.
• Z. Ertem, E. Lykhovyd, Y. Wang, and S. Butenko, “The maximum independent union of cliques problem: complexity and exact approaches,” J. Glob. Optim., vol. 76, no. 3, pp. 545–562, 2020, doi: 10.1007/s10898-018-0694-2.
• L. Chang, “Efficient maximum clique computation and enumeration over large sparse graphs,” VLDB J., vol. 29, no. 5, pp. 999–1022, 2020, doi: 10.1007/s00778-020-00602-z.
• D. H. Smith, R. Montemanni, and S. Perkins, “The use of an exact algorithm within a tabu search maximum clique algorithm,” Algorithms, vol. 13, no. 10, pp. 1–12, 2020, doi: 10.3390/A13100253.
• Y. Jin, B. Xiong, K. He, Y. Zhou, and Y. Zhou, “On fast enumeration of maximal cliques in large graphs,” Expert Syst. Appl., vol. 187, no. September 2021, p. 115915, 2022, doi: 10.1016/j.eswa.2021.115915.
• S. Horvát et al., “IGraph/M: graph theory and network analysis for Mathematica,” J. Open Source Softw., vol. 8, no. 81, p. 4899, 2023, doi: 10.21105/joss.04899.
• S. A. Mojallal and P. Hansen, “On the difference of energies of a graph and its complement graph,” Linear Algebra Appl., vol. 595, pp. 1–12, 2020, doi: 10.1016/j.laa.2020.02.026.
• S. Yakut, F. Öztemiz, and A. Karcı, “A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm,” Comput. Sci., vol. 55, no. 35, pp. 1–100, Jan. 2023, doi: 10.53070/bbd.1224520.
• N. Bousquet, A. Lagoutte, and S. Thomassé, “Clique versus independent set,” Eur. J. Comb., vol. 40, no. February, pp. 73–92, 2014, doi: 10.1016/j.ejc.2014.02.003.
• M. Xiao, S. Huang, Y. Zhou, and B. Ding, “Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set,” in In Proceedings of the Web Conference 2021 (WWW ’21). Association for Computing Machinery, 2021, pp. 3930–3940. [Online]. Available: https://doi.org/10.1145/3442381.3450130
• P. M. Pardalos and J. Xue, “The maximum clique problem,” J. Glob. Optim., vol. 4, no. 3, pp. 301–328, 1994, doi: 10.1007/BF01098364.
• F. Öztemiz and S. Yakut, “An Effective Method for Determining Node Dominance Values: Malatya Centrality Algorithm,” 32nd IEEE Conf. Signal Process. Commun. Appl. SIU 2024 - Proc., pp. 1–4, 2024, doi: 10.1109/SIU61531.2024.10601155.
• S. Yakut, F. Öztemiz, and A. Karci, “A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm,” J. Supercomput., vol. 79, no. 17, pp. 19746–19769, 2023, doi: 10.1007/s11227-023-05397-8.