Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2023); Москва; Москва
Год издания: 2023
Идентификатор DOI: 10.25728/dccn.2023.010
Ключевые слова: Correlation Clustering, Signed graph, Heuristic Greedy algorithm, structural balance, graph partition
Аннотация: 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 inteПоказать полностьюrcluster 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.
Номера страниц: 70-75
Место издания: Москва