Approach to analysis and construction of algorithms for solving one clustering problem on signed graphs

A. A. Soldatenko ; D. V. Semenova ; E. I. Ibragimova

Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 112-127

Résumé

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$_{\alpha}$ 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.

Détail

Keywords: signed graph, correlation clustering, algorithm systematization, potential functions.