Comparison of Two Heuristic Algorithms for Correlation Clustering Problem Solving
Ellada Ibragimova, Daria V. Semenova, Aleksandr A. Soldatenko · 2023
This paper compares two heuristic algorithms for solving the correlation clustering problem (CCP). CCP is solved for undirected and unweighted simple signed graphs, where error functional is combination of intercluster and intracluster errors, which is NP-complete. A detailed description of the strategy of our algorithm SGClusta is given. The main focus is on comparing the well-known iterated local search (ILS) algorithm and SGClusta on model data. The results of computational experiments demonstrate that these algorithms are comparable in terms of the error value, however, SGClusta is significantly faster.