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α 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.
Download file
Counter downloads: 7
- Title Approach to analysis and construction of algorithms for solving one clustering problem on signed graphs
- Headline Approach to analysis and construction of algorithms for solving one clustering problem on signed graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 64
- Date:
- DOI 10.17223/20710410/64/9
Keywords
signed graph, correlation clustering, algorithm systematization, potential functionsAuthors
References
Il'ev V., Il'eva S., and Kononov A. Short survey on graph correlation clustering with minimization criteria // LNCS. 2016. V. 9869. P. 25-36.
Wahid D. F. and Hassini E. A literature review on correlation clustering: Cross-disciplinary taxonomy with bibliometric analysis // Oper. Res. Forum. 2022. V. 3. Article 47.
Ailon N., Charikar М., and Newm,an A. Aggregating inconsistent information: Ranking and clustering //j. ACM. 2008. V.55. Iss.5. Article 23. R 1 27.
Demaine E. D. and Immorlica N. Correlation clustering with partial information // LNCS. 2003. V.2764. P. 1 13.
Swamy C. Correlation clustering: Maximizing agreements via semidefinite programming // Proc. SODA'04. New Orleans, Louisiana, 2004. P. 526-527.
Bonizzoni P., Vedova D. G., Dondi R., and Jiang T. Correlation clustering and consensus clustering // LNCS. 2005. V.3827. R226 235.
Figueiredo R. and Moura G. Mixed integer programming formulations for clustering problems related to structural balance // Social Networks. 2013. No.35. P.639-651.
Queiroga E., Subramanian A., Figueiredo R., and Frota Yu,.Integer programming formulations and efficient local search for relaxed correlation clustering //j. Glob. Optim. 2021. No. 81. P.919-966.
Doreian P. and Mrvar A. Partitioning signed social networks // Soc.Networks. 2009. No. 31. P.1-11.
Graham R., L., Knuth D., E., and Patashnik O. Concrete Mathematics: A Foundation for Computer Science. 2nd ed. Massachusetts, USA: Addison-Weslev, 1994. 657 p.
Cartwright D. and Harary F. Structural balance: A generalization of Heider's theory // Psychol. Rev. 1956. V.63. No.5. P.227-293.
Doreian P. and Mrvar A. Structural Balance and Partitioning Signed Graphs, http://mrvar2.fdv.si/pajek/SignedNetworks/Bled94.pdf. 1996.
Bansal N., Blum A., and Chawla S. Correlation clustering // Machine Learning. 2004. No. 56. P.89-113.
Doreian P. and Mrvar A. A partitioning approach to structural balance // Soc.Networks. 1996. No. 18. P. 149-168.
Kormen T. H., Leiserson С. E., Rivest R. L., and Stein C.Introduction to Algorithms. 3rd ed. Cambridge: MIT Press, 2009. 1312 p.
Brusco M. J. and Doreian P. Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search // Soc.Networks. 2019. No.56. P.70-80.
Levorato M., Figueiredo R., Frota Yu,., and Drummond L. Evaluating balancing on social networks through the efficient solution of correlation clustering problems // EURO J.Comput. Optim. 2017. V. 5. P.467-498.
Ibragimova E., Semenova D., and Soldatenko A.Comparison of two heuristic algorithms for correlation clustering problem solving // 5th Intern. Conf. PCI. Baku, Azerbaijan, 2023. P. 1-4.
Soldatenko A., Semenova D., and Ibragimova E. On heuristic algorithm with greedy strategy for the correlation clustering problem solution // LNCS. 2024. V. 14123. P.462-477.
Солдатенко А. А., Семенова Д. В., Ибрагим,ова Э. И. Алгоритм с потенциальными функциями для задачи разбиения знаковых графов // Информационные технологии и математическое моделирование. Томск, 2023. С. 238-244.
Waxman В. М. Routing of multipoint connections // IEEE J. Selected Areas Commun. 1988. V.6. No. 9. P.1617-1622.
Approach to analysis and construction of algorithms for solving one clustering problem on signed graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/9
Download full-text version
Counter downloads: 143