Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах

Рассматривается NP-трудная оптимизационная задача корреляционной кластеризации для неориентированных и невзвешенных знаковых графов без кратных рёбер и петель, где функционал ошибки представляет собой линейную комбинацию межкластерной и внутрикластерной ошибок. Предложен системный подход построения и анализа алгоритмов, основанных на структуре графа, для решения этой задачи. Подход представлен в виде общей схемы, состоящей из шести взаимосвязанных блоков, отражающих основные этапы решения задачи корреляционной кластеризации. С использованием данной схемы проанализированы шесть существующих алгоритмов. Согласно общей схеме построен новый алгоритм CarVeR, который является модификацией алгоритма SGClust$_{\alpha}$ с помощью потенциальных функций. Топология общей схемы открывает возможности для анализа и доказательства вычислительной сложности алгоритмов, что продемонстрировано в теореме о вычислительной сложности алгоритма CarVeR. Представлены вычислительные эксперименты на синтетических данных для сравнения пяти алгоритмов. Результаты экспериментов показали конкурентную способность алгоритма CarVeR как по времени выполнения, так и по минимизации значения функционала ошибки.