Correlation clustering: Let all the flowers bloom!

• Autorzy: Aszalós László , Bakó Mária

Identyfikatory

DOI

10.15439/2019F93

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

Correlation clustering is a NP-hard problem, and for large signed graphs finding even just a good approximation of the optimal solution is a hard task. In this article we examine the effect of ranking of the nodes and process them in order of ranks. We present that based on the rate of positive edges in the graph we should use different optimization methods. We show that all the building blocks of our methods are needed under certain circumstances.

Słowa kluczowe

EN

NP-hard problem; graph; cluster analysis

PL

problem NP-trudny; wykres; graf; analiza skupień

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 20
• Strony: 21--28
• Opis fizyczny: Bibliogr. 14 poz., wykr., tab.

Twórcy

autor

Aszalós László

• Faculty of Informatics at University of Debrecen, 26 Kassai út H4028 Debrecen, Hungary

autor

Bakó Mária

• Faculty of Informatics at University of Debrecen, 26 Kassai út H4028 Debrecen, Hungary

Bibliografia

• 1. Agarwal, G., Kempe, D.: Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B 66(3), 409–418 (2008)
• 2. Aszalós, L., Bakó, M.: Advanced search methods (in Hungarian). http://www.tankonyvtar.hu/hu/tartalom/tamop412A/2011-0103 13 fejlett keresoalgoritmusok (2012)
• 3. Aszalós, L., Bakó, M.: Contraction methods for correlation clustering: The order is important. In: Recent Advances in Computational Optimization, pp. 1–13. Springer (2019)
• 4. Aszalós, L., Nagy, D.: Iterative set approximations based on tolerance relation. In: International Joint Conference on Rough Sets, pp. 76–88. Springer (2019)
• 5. Bakó, M., Aszalós, L.: Combinatorial optimization methods for correlation clustering. In: D. Dumitrescu, R.I. Lung, L. Cremene (eds.) Coping with complexity, pp. 2–12. Casa Cartii de Stiinta, Cluj-Napoca (2011)
• 6. Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Machine Learning 56(1-3), 89–113 (2004). DOI 10.1023/B:MACH.0000033116. 57574.95. URL http://dx.doi.org/10.1023/B:MACH.0000033116.57574. 95
• 7. Berend, D., Tassa, T.: Improved bounds on bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics 30(2), 185–205 (2010)
• 8. Bonchi, F., Gionis, A., Gullo, F., Tsourakakis, C.E., Ukkonen, A.: Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data (TKDD) 9(4), 34 (2015)
• 9. Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N.: Correlation clustering in general weighted graphs. Theoretical Computer Science 361(2-3), 172–187 (2006)
• 10. Emanuel, D., Fiat, A.: Correlation clustering–minimizing disagreements on arbitrary weighted graphs. In: European Symposium on Algorithms, pp. 208–220. Springer (2003)
• 11. Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 1167–1176. Society for Industrial and Applied Mathematics (2006)
• 12. Néda, Z., Florian, R., Ravasz, M., Libál, A., Györgyi, G.: Phase transition in an optimal clusterization model. Physica A: Statistical Mechanics and its Applications 362(2), 357–368 (2006). DOI 10.1016/j.physa.2005.08.008. URL http://dx.doi.org/10.1016/j.physa.2005.08.008
• 13. Shi, J., Malik, J.: Normalized cuts and image segmentation. Departmental Papers (CIS) p. 107 (2000)
• 14. Zahn Jr, C.: Approximating symmetric relations by equivalence relations. Journal of the Society for Industrial & Applied Mathematics 12(4), 840–847 (1964). DOI 10.1137/0112071. URL http://dx.doi.org/10.1137/0112071

Uwagi

1. Track 1: Artificial Intelligence and Applications

2. Technical Session: 12th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).