×

Contraction methods for correlation clustering: the order is important. (English) Zbl 1420.68165

Fidanova, Stefka (ed.), Recent advances in computational optimization. Results of the workshop on computational optimization WCO 2017, Prague, Czech Republic, September 3–6, 2017. Cham: Springer. Stud. Comput. Intell. 795, 1-13 (2019).
Summary: 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 examine the effect of executing the steps of the contraction method in a different order.
For the entire collection see [Zbl 1419.90003].

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aszalós, L., Bakó, M.: Advanced search methods (in Hungarian). http://www.tankonyvtar.hu/hu/tartalom/tamop412A/2011-0103_13_fejlett_keresoalgoritmusok (2012) · Zbl 1420.68165
[2] Aszalós, L., Bakó, M.: Correlation clustering: divide and conquer. In: Ganzha, M., Maciaszek, L., Paprzycki, M. (eds.) Position Papers of the 2016 Federated Conference on Computer Science and Information Systems, Annals of Computer Science and Information Systems, vol. 9, pp. 73-78. PTI (2016). https://doi.org/10.15439/2016F168 · doi:10.15439/2016F168
[3] Aszalós, L., Mihálydeák, T.: Rough clustering generated by correlation clustering. In: Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, pp. 315-324. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1109/TKDE.2007.1061 · Zbl 1323.68425 · doi:10.1109/TKDE.2007.1061
[4] Aszalós, L., Mihálydeák, T.: Rough classification based on correlation clustering. In: Rough Sets and Knowledge Technology, pp. 399-410. Springer (2014). https://doi.org/10.1007/978-3-319-11740-9_37 · Zbl 1323.68425 · doi:10.1007/978-3-319-11740-9_37
[5] Aszalós, L., Mihálydeák, T.: Correlation clustering by contraction, a more effective method. In: Recent Advances in Computational Optimization, vol. 655, pp. 81-95. Springer (2016). https://doi.org/10.1007/978-3-319-40132-4_6 · doi:10.1007/978-3-319-40132-4_6
[6] Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1-3), 89-113 (2004). https://doi.org/10.1023/B:MACH.0000033116.57574.95 · Zbl 1089.68085 · doi:10.1023/B:MACH.0000033116.57574.95
[7] Bhattacharya, A., De, R.K.: Divisive correlation clustering algorithm (dcca) for grouping of genes: detecting varying patterns in expression profiles. Bioinformatics 24(11), 1359-1366 (2008). https://doi.org/10.1093/bioinformatics/btn133 · doi:10.1093/bioinformatics/btn133
[8] Chen, Z., Yang, S., Li, L., Xie, Z.: A clustering approximation mechanism based on data spatial correlation in wireless sensor networks. In: Wireless Telecommunications Symposium (WTS), 2010, pp. 1-7. IEEE (2010). https://doi.org/10.1109/WTS.2010.5479626 · doi:10.1109/WTS.2010.5479626
[9] DuBois, T., Golbeck, J., Kleint, J., Srinivasan, A.: Improving recommendation accuracy by clustering social networks with trust. Recommender Systems & the Social Web 532, 1-8 (2009). https://doi.org/10.1145/2661829.2662085 · doi:10.1145/2661829.2662085
[10] Kim, S., Nowozin, S., Kohli, P., Yoo, C.D.: Higher-order correlation clustering for image segmentation. In: Advances in Neural Information Processing Systems, pp. 1530-1538 (2011). DOI 10.1.1.229.4144
[11] Néda, Z., Florian, R., Ravasz, M., Libál, A., Györgyi, G.: Phase transition in an optimal clusterization model. Physica A: Stat. Mech. Appl. 362(2), 357-368 (2006). https://doi.org/10.1016/j.physa.2005.08.008 · doi:10.1016/j.physa.2005.08.008
[12] Yang, B., Cheung, W.K., Liu, J.: Community mining from signed social networks. Knowl. Data Eng. IEEE Trans. 19(10), 1333-1348 (2007) · doi:10.1109/TKDE.2007.1061
[13] Zahn Jr, C.: Approximating symmetric relations by equivalence relations. J. Soc. Ind. Appl. Math. 12(4), 840-847 (1964) · Zbl 0129.16003 · doi:10.1137/0112071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.