Тип публикации: статья из журнала
Год издания: 2024
Идентификатор DOI: 10.17223/20710410/64/9
Ключевые слова: Signed graph, Correlation Clustering, algorithm systematization, potential functions, знаковый граф, корреляционная кластеризация, систематизация алгоритмов, потенциальные функции
Аннотация: Рассматривается NP-трудная оптимизационная задача корреляционной кластеризации для неориентированных и невзвешенных знаковых графов без кратных рёбер и петель, где функционал ошибки представляет собой линейную комбинацию межкластерной и внутрикластерной ошибок. Предложен системный подход построения и анализа алгоритмов, основанных на структуре графа, для решения этой задачи. Подход представлен в виде общей схемы, состоящей из шести взаимосвязанных блоков, отражающих основные этапы решения задачи корреляционной кластеризации. С использованием данной схемы проанализированы шесть существующих алгоритмов. Согласно общей схеме построен новый алгоритм CarVeR, который является модификацией алгоритма SGClustα с помощью потенциальных функций. Топология общей схемы открывает возможности для анализа и доказательства вычислительной сложности алгоритмов, что продемонстрировано в теореме о вычислительной сложности алгоритма CarVeR. Представлены вычислительные эксперименты на синтетических данных для сравнения пяти алгоритмов. Результаты экспериментов показали конкурентную способность алгоритма CarVeR как по времени выполнения, так и по минимизации значения функционала ошибки. We consider the NP-hard correlation clustering problem for undirected and unweighted signed graphs without multiple edges and loops, where the error functional is a linear combination of intercluster and intracluster errors. In this paper, we propose a systematic approach for constructing and analyzing graph structure based algorithms to solve this problem. The approach is presented in the form of a general scheme consisting of six interrelated blocks reflecting the main stages of solving the correlation clustering problem. Six existing algorithms have been analyzed using this scheme. According to the general scheme, a new algorithm CarVeR has been constructed, which is a modification of the SGClustα algorithm using potential functions. The topology of the general scheme opens up the possibility of analyzing and proving the computational complexity of the algorithms, which is demonstrated in the computational complexity theorem of the CarVeR algorithm. This paper presents computational experiments on synthetic data to compare five algorithms. The experimental results show the competitive ability of the CarVeR algorithm both in terms of execution time and minimization of the value of the error functional.
Журнал: Прикладная дискретная математика
Выпуск журнала: №64
Номера страниц: 112-127
ISSN журнала: 20710410
Место издания: Томск
Издатель: Национальный исследовательский Томский государственный университет