Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 9

Position Papers of the 2016 Federated Conference on Computer Science and Information Systems

Correlation clustering: divide and conquer

,

DOI: http://dx.doi.org/10.15439/2016F168

Citation: Position Papers of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 9, pages 73–78 ()

Full text

Abstract. The correlation clustering is an NP-hard problem, hence its solving methods do not scale well. The contraction method and its improvement enable us to construct a divide and conquer algorithm, which could help us to clustering bigger sets. In this article we present the contraction method and compare the effectiveness of this new new and our old methods.

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. [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. [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://morse.inf.unideb.hu/aszalos/diak/fka, 2012.
  4. S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo, “Higher-order correlation clustering for image segmentation,” in Advances in Neural Information Processing Systems, 2011, pp. 1530–1538.
  5. A. Bhattacharya and R. K. De, “Divisive correlation clustering algorithm (dcca) for grouping of genes: detecting varying patterns in expression profiles,” bioinformatics, vol. 24, no. 11, pp. 1359–1366, 2008. [Online]. Available: dx.doi.org/10.1093/bioinformatics/btn133
  6. B. Yang, W. K. Cheung, and J. Liu, “Community mining from signed social networks,” Knowledge and Data Engineering, IEEE Transactions on, vol. 19, no. 10, pp. 1333–1348, 2007.
  7. T. DuBois, J. Golbeck, J. Kleint, and A. Srinivasan, “Improving recommendation accuracy by clustering social networks with trust,” Recommender Systems & the Social Web, vol. 532, pp. 1–8, 2009. [Online]. Available: http://dx.doi.org/10.1145/2661829.2662085
  8. Z. Chen, S. Yang, L. Li, and Z. Xie, “A clustering approximation mechanism based on data spatial correlation in wireless sensor networks,” in Wireless Telecommunications Symposium (WTS), 2010. IEEE, 2010, pp. 1–7. [Online]. Available: http://dx.doi.org/10.1109/WTS.2010.5479626
  9. 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. [Online]. Available: http://dx.doi.org/10.1016/j.physa.2005.08.008
  10. L. Aszalós and T. Mihálydeák, “Rough clustering generated by correlation clustering,” in Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Springer Berlin Heidelberg, 2013, pp. 315–324. [Online]. Available: http://dx.doi.org/10.1109/TKDE.2007.1061
  11. L. Aszalós and T. Mihálydeák, “Rough classification based on correlation clustering,” in Rough Sets and Knowledge Technology. Springer, 2014, pp. 399–410. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-11740-9_37
  12. L. Aszalós and T. Mihálydeák, “Correlation clustering by contraction,” in Computer Science and Information Systems (FedCSIS), 2015 Federated Conference on. IEEE, 2015, pp. 425–434.
  13. L. Aszalós and T. Mihálydeák, “Correlation clustering by contraction, a more effective method,” to appear in Studies in Computational Intelligence.
  14. S. Alstrup, M. Thorup, I. L. Gørtz, T. Rauhe, and U. Zwick, “Union-find with constant time deletions,” ACM Transactions on Algorithms (TALG), vol. 11, no. 1, p. 6, 2014.