Annals of Computer Science and Information Systems, Volume 11

DOI: http://dx.doi.org/10.15439/2017F166

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 403–406 (2017)

Full text

Abstract. Correlation clustering is a NP-hard problem, and for large graphs finding even just a good approximation of the optimal solution is a hard task. In previous articles we have suggested a contraction method and its divide and conquer variant. In this article we present several improvements of this method (preprocessing, quasi-parallelism, etc.) and prepare it for parallelism. Based on speed tests we show where it helps the concurrent execution, and where it pulls us back.

References

1. C. Zahn, Jr, “Approximating symmetric relations by equivalence relations,” Journal of the Society for Industrial & Applied Mathematics, vol. 12, no. 4, pp. 840–847, 1964. http://dx.doi.org/10.1137/0112071. [Online]. Available: http://dx.doi.org/10.1137/0112071
2. N. Bansal, A. Blum, and S. Chawla, “Correlation clustering,” Machine Learning, vol. 56, no. 1-3, pp. 89–113, 2004. doi: 10.1023/B:MACH.0000033116.57574.95. [Online]. Available: http://dx.doi.org/10.1023/B:MACH.0000033116.57574.95
3. L. Aszalós and M. Bakó, “Advanced search methods (in Hungarian),” http://www.tankonyvtar.hu/hu/tartalom/tamop412A/2011-0103 13 fejlett keresoalgoritmusok, 2012.
4. Z. Néda, R. Florian, M. Ravasz, A. Libál, and G. Györgyi, “Phase transition in an optimal clusterization model,” Physica A: Statistical Mechanics and its Applications, vol. 362, no. 2, pp. 357–368, 2006. http://dx.doi.org/10.1016/j.physa.2005.08.008. [Online]. Available: http://dx.doi.org/10.1016/j.physa.2005.08.008
5. L. Aszalós and T. Mihálydeák, “Correlation clustering by contraction, a more effective method,” in Recent Advances in Computational Optimization. Springer, 2016, vol. 655, pp. 81–95. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-40132-4 6
6. L. Aszalós and M. Bakó, “Correlation clustering: divide and conquer,” in Position Papers of the 2016 Federated Conference on Computer Science and Information Systems, ser. Annals of Computer Science and Information Systems, M. Ganzha, L. Maciaszek, and M. Paprzycki, Eds., vol. 9. PTI, 2016. http://dx.doi.org/10.15439/2016F168 pp. 73–78. [Online]. Available: http://dx.doi.org/10.15439/2016F168