A technique of algorithms construction for solving a correlation clustering problem - Ellada I. Ibragimova; Daria V. Semenova; Aleksandr A. Soldatenko (Discrete and Continuous Models and Applied Computational Science)
We propose a construction method for network structure based algorithms (NS-algorithms), aimed at solving the correlation clustering problem (CCP) specifically for signed networks. Our model assumes an undirected, unweighted simple signed graph. This problem is considered in optimization form with the error functional as a linear combination of inter-cluster and intra-cluster errors. It is known that this formulation of the problem is NP-hard. The technique of NS-algorithms constructing is grounded on the system approach presented in the form of a general scheme. The proposed scheme comprises six interconnected blocks, each corresponding to a stage in addressing the CCP solution. The main idea of the technique is to combine modules representing each block of the scheme. The proposed approach has been realized as a software package. The paper presents a model NS-algorithm constructed using the proposed technique. To evaluate its performance, computational experiments utilizing synthetic datasets are conducted, comparing the new algorithm against existing methods.