Библиографическое описание: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. - 2025. - Т. 33, № 2. - P. 130-143. - This work is supported by the Krasnoyarsk Mathematical Center and financed by the Ministry of Science and Higher Education of the Russian Federation (Agreement No. 075-02-2024-1429). - ISSN 2658-4670. - ISSN 2658-7149, DOI 10.22363/2658-4670-2025-33-2-130-143.
Аннотация: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.
Развивается техника построения алгоритмов, основанных на структуре сети (NS-алгоритмы), для решения задачи корреляционной кластеризации (CCP) для знаковых сетей. Моделью знаковой сети выступает неориентированный и невзвешенный простой знаковых графов. Эта задача рассматривается в оптимизационной форме с функционалом ошибки в виде линейной комбинации межкластерной и внутрикластерной ошибок. Известно, что в данной постановке задача является NP-трудной. Техника построения NS-алгоритмов основана на системном подходе, представленном в виде общей схемы. Схема состоит из шести взаимосвязанных блоков, каждый из которых отражает основные этапы решения CCP. Основная идея техники заключается в комбинировании модулей, представляющих каждый блок схемы. Предложенный подход реализован в виде программного комплекса. В работе представлен модельный NS-алгоритм, построенный с помощью предлагаемой техники. Проведены вычислительные эксперименты на синтетических данных по сравнению модельного алгоритма с уже известными.
