Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 20

Communication Papers of the 2019 Federated Conference on Computer Science and Information Systems

Correlation Clustering: Let All The Flowers Bloom!

,

DOI: http://dx.doi.org/10.15439/2019F93

Citation: Communication Papers of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 20, pages 21–28 ()

Full text

Abstract. 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.

References

  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