Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)4525210.22363/2658-4670-2025-33-2-130-143BMIMTXComputer ScienceИнформатика и вычислительная техникаResearch ArticleA technique of algorithms construction for solving a correlation clustering problemО методе построения алгоритмов для решения задачи корреляционной кластеризацииhttps://orcid.org/0000-0002-6852-228158766400800IbragimovaEllada I.ИбрагимоваЭ. И.

Assistant of Department of Higher and Applied Mathematics

EIbragimova@sfu-kras.ruhttps://orcid.org/0000-0002-8670-292149261191500O-3107-2019SemenovaDaria V.СеменоваД. В.

Candidate in Physics and Mathematics, Associate Professor of the Department of Higher and Applied Mathematics

DVSemenova@sfu-kras.ruhttps://orcid.org/0000-0001-6708-475357194285182O-8550-2019SoldatenkoAleksandr A.СолдатенкоА. А.

Candidate in Physics and Mathematics, Associate Professor of the Department of Higher and Applied Mathematics

ASoldatenko@sfu-kras.ruSiberian Federal UniversityСибирский федеральный университет15072025332VOL 33, NO2 (2025)ТОМ 33, №2 (2025)13014325072025Copyright ©; 2025, Ibragimova E.I., Semenova D.V., Soldatenko A.A.Copyright ©; 2025, Ибрагимова Э.И., Семенова Д.В., Солдатенко А.А.2025Ibragimova E.I., Semenova D.V., Soldatenko A.A.Ибрагимова Э.И., Семенова Д.В., Солдатенко А.А.https://creativecommons.org/licenses/by-nc/4.0https://journals.rudn.ru/miph/article/view/45252

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-алгоритм, построенный с помощью предлагаемой техники. Проведены вычислительные эксперименты на синтетических данных по сравнению модельного алгоритма с уже известными.

signed networkalgorithm systematizationnetwork structure based approachcorrelation clustering problemзнаковая сетьзадача корреляционной кластеризацииNS-алгоритмтехника построения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).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).Maatouk, A., Hajri, S. E., Assaad, M. & Sari, H. On optimal scheduling for joint spatial division and multiplexing approach in fdd massive mimo. IEEE Trans Signal Process 67, 1006-10213 (2018).Arinik, N., Figueiredo, R. & andLabatut, V. Multiple partitioning of multiplex signed networks: Application to European parliament votes. Social Networks 60, 83-102 (2020).Abdelnasser, A., Hossain, E. & Kim, D. I. Clustering and resource allocation for dense femtocells in a two-tier cellular OFDMA network. IEEE Trans Wireless Communications 13, 1628-1641 (2014).Hüffner, F., Betzler, N. & Niedermeier, R. Optimal Edge Deletions for Signed Graph Balancing in Experimental Algorithms (ed Demetrescu, C.) (Springer Berlin Heidelberg, Berlin, Heidelberg, 2007), 297-310.Figueiredo, R. & Frota, Y. An improved Branch-and-cut code for the maximum balanced subgraph of a signed graph 2013. ArXiv: abs/1312.4345.Figueiredo, R. & Frota, Y. The maximum balanced subgraph of a signed graph: Applications and solution approaches. European Journal of Operational Research 236 (2014).Tang, J., Chang, Y., Aggarwal, C. C. & Liu, H. A Survey of Signed Network Mining in Social Media. ACM Computing Surveys CSUR 49, 1-37 (2015).Il’ev, V., Il’eva, S. & Kononov, A. Short Survey on Graph Correlation Clustering with Minimization Criteria in Lecture Notes in Computer Science (Germany, Heidelberg, Springer-Verlag, 2016), 25-36.Wahid, D. F. & Hassini, E. A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis. Oper. Res. Forum 47 (2022).Queiroga, E., Subramanian, A., Figueiredo, R. & Frota, Y. T. Integer programming formulations and efficient local search for relaxed correlation clustering. Journal of Global Optimization 81, 919-966 (2021).Ailon, N., Charikar, M. & Newman, A. Aggregating inconsistent information: ranking and clustering in Symposium on the Theory of Computing (2005).Brusco, M. J. & Doreian, P. Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search. Social Networks 56, 70-80 (2019).Levorato, M., Figueiredo, R., Frota, Y. & Drummond, L. Evaluating balancing on social networks through the efficient solution of correlation clustering problems. EURO Journal on Computational Optimization 5, 467-498 (2017).Doreian, P. & Mrvar, A. Partitioning signed social networks. Soc. Networks 31, 1-11 (2009).Harary, F. Structural Balance: A Generalization of Heider’s Theory. Psychological Review 63, 227-293 (1956).Graham, R. L., Knuth, D. E. & Patashnik, O. Concrete Mathematics: A Foundation for Computer Science 2nd edn. 657 pp. (Addison-Wesley, Massachusetts, USA, 1994).Doreian, P. & Mrvar, A. A partitioning approach to structural balance. Social Networks 18, 149-168 (1996).Bansal, N., Blum, A. & Chawla, S. Correlation Clustering. Machine Learning 56, 89-113 (2002).Soldatenko, A. A., Semenova, D. V. & Ibragimova, E. I. An approach to analyzing and constructing algorithms for solving a one clustering problem on signed graphs. Applied discrete mathematics, 112-127 (2024).Ibragimova, E. I., D. V. Soldatenko, A. A. & Semenova. Comparison of Two Heuristic Algorithms for Correlation Clustering Problem Solving in 2023 5th International Conference on Problems of Cybernetics and Informatics (PCI) (IEEE, 2023), 1-4.Soldatenko, A., Semenova, D. & Ibragimova, E. On heuristic algorithm with greedy strategy for the Correlation Clustering problem solution in Lecture Notes in Computer Science (Germany, Heidelberg, Springer-Verlag, 2023), 462-477.Waxman, B. M. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications 6, 1617-1622 (1988).Ciotti, V., Bianconi, G., Capocci, A., Colaiori, F. & Panzarasa, P. Degree correlations in signed social networks. Physica A: Statistical Mechanics and its Applications, 25-39 (2015).Aniyan, A. & Naduvath, S. Induced signed graphs of some classes of graphs. Proceedings of the Jangjeon Mathematical Society 23, 283-291 (2020).Sudheer, N., George, A. C., Aniyan, A. & Naduvath, S. Some new results on colour-induced signed graphs. Acta Univ. Sapientiae Informatica 14, 338-353 (2022).