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.

Bibliographie

[1] Il'ev V., Il'eva S., and Kononov A., “Short survey on graph correlation clustering with minimization criteria”, LNCS, 9869, 2016, 25–36 | MR | Zbl

[2] Wahid D. F. and Hassini E., “A literature review on correlation clustering: Cross-disciplinary taxonomy with bibliometric analysis”, Oper. Res. Forum, 3 (2022), 47 | DOI | MR | Zbl

[3] Ailon N., Charikar M., and Newman A., “Aggregating inconsistent information: Ranking and clustering”, J. ACM, 55:5 (2008), 23, 1–27 | DOI | MR

[4] Demaine E. D. and Immorlica N., “Correlation clustering with partial information”, LNCS, 2764, 2003, 1–13 | MR | Zbl

[5] Swamy C., “Correlation clustering: Maximizing agreements via semidefinite programming”, Proc. SODA'04 (New Orleans, Louisiana), 2004, 526–527 | MR | Zbl

[6] Bonizzoni P., Vedova D. G., Dondi R., and Jiang T., “Correlation clustering and consensus clustering”, LNCS, 3827, 2005, 226–235 | MR | Zbl

[7] Figueiredo R. and Moura G., “Mixed integer programming formulations for clustering problems related to structural balance”, Social Networks, 2013, no. 35, 639–651 | DOI

[8] 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, 919–966 | DOI | MR | Zbl

[9] Doreian P. and Mrvar A., “Partitioning signed social networks”, Soc. Networks, 2009, no. 31, 1–11 | DOI

[10] Graham R., L., Knuth D., E., and Patashnik O., Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, Massachusetts, USA, 1994, 657 pp. | MR | Zbl

[11] Cartwright D. and Harary F., “Structural balance: A generalization of Heider's theory”, Psychol. Rev., 63:5 (1956), 227–293 | DOI

[12] Doreian P. and Mrvar A., Structural Balance and Partitioning Signed Graphs, 1996 http://mrvar2.fdv.si/pajek/SignedNetworks/Bled94.pdf

[13] Bansal N., Blum A., and Chawla S., “Correlation clustering”, Machine Learning, 2004, no. 56, 89–113 | DOI | MR | Zbl

[14] Doreian P. and Mrvar A., “A partitioning approach to structural balance”, Soc. Networks, 1996, no. 18, 149–168 | DOI

[15] Kormen T. H., Leiserson C. E., Rivest R. L., and Stein C., Introduction to Algorithms, 3rd ed., MIT Press, Cambridge, 2009, 1312 pp. | MR

[16] Brusco M. J. and Doreian P., “Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search”, Soc. Networks, 2019, no. 56, 70–80 | DOI

[17] 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., 5 (2017), 467–498 | DOI | MR | Zbl

[18] Ibragimova E., Semenova D., and Soldatenko A., “Comparison of two heuristic algorithms for correlation clustering problem solving”, 5th Intern. Conf. PCI (Baku, Azerbaijan), 2023, 1–4

[19] Soldatenko A., Semenova D., and Ibragimova E., “On heuristic algorithm with greedy strategy for the correlation clustering problem solution”, LNCS, 14123, 2024, 462–477

[20] Soldatenko A. A., Semenova D. V., Ibragimova E. I., “Algorithm with potential functions for the problem of partitioning signed graphs”, Informatsionnye Tekhnologii i Matematicheskoe Modelirovanie, Tomsk, 2023, 238–244 (in Russian)

[21] Waxman B. M., “Routing of multipoint connections”, IEEE J. Selected Areas Commun., 6:9 (1988), 1617–1622 | DOI