Библиографическое описание:About heuristic algorithm for Correlation Clustering problem solving : доклад, тезисы доклада / A. A. Soldatenko, D. V. Semenova, E. I. Ibragimova. - [S. l. : s. n.], 2023. - Текст : непосредственный // = Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2023) = Distributed computer and communication networks: control, computation, communications (DCCN-2023) : Материалы XXVI Международной научной конференции / Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2023) (2023 ; 25.09 - 29.09 ; Москва). - Москва. - P. 70-75. - This work is supported by the Krasnoyarsk Mathematical Center and financed by the Ministry of Science and Higher Education of the Russian Federation (Agreement No. 075-02-2023-936). - ISBN 9785914502697, DOI 10.25728/dccn.2023.010.
Аннотация:The Correlation Clustering (CC) problem is traditionally defined as a problem of partitioning a signed graph without specifying the number of clusters in advance. In this paper, CC problem is considered for undirected and unweighted signed graphs without multiple edges and loops, where error functional is linear combination of intercluster and intracluster errors. In this formulation, the CC problem is NP-complete. Exact algorithms for this problem are timeconsuming. Approximate algorithms for solving CC problem often lead to unsatisfactory results, and heuristic algorithms are often non-deterministic in the number of steps leading to a solution. We propose a new heuristic algorithm SGClustα for the CC problem solving. The main idea of this algorithm is in intracluster error minimizing and optimization of error functional according to the greedy strategy. It was proved that this algorithm takes polynomial time. Numerical experiments were carried out on randomly generated signed graphs.
