Approximation Algorithms on k-Correlation Clustering

doi:10.1007/s40305-022-00418-4

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 911-924.doi: 10.1007/s40305-022-00418-4

收稿日期:2021-07-13 修回日期:2022-02-25 出版日期:2023-12-30 发布日期:2023-12-26
通讯作者: Zhuo Diao, Zhong-Zheng Tang E-mail:diaozhuo@amss.ac.cn;tangzhongzheng@amss.ac.cn

Approximation Algorithms on k-Correlation Clustering

Zhong-Zheng Tang¹, Zhuo Diao²

1. School of Science, Beijing University of Posts and Telecommunications, Beijing, 100876, China;
2. School of Statistics and Mathematics, Central University of Finance and Economics, Beijing, 100081, China

Received:2021-07-13 Revised:2022-02-25 Online:2023-12-30 Published:2023-12-26
Contact: Zhuo Diao, Zhong-Zheng Tang E-mail:diaozhuo@amss.ac.cn;tangzhongzheng@amss.ac.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 11901605 and 12101069), the disciplinary funding of Central University of Finance and Economics (CUFE), the Emerging Interdisciplinary Project of CUFE, the Fundamental Research Funds for the Central Universities and Innovation Foundation of BUPT for Youth (No. 500421358).

摘要/Abstract

Abstract: In this paper, we consider the k-correlation clustering problem. Given an edge-weighted graph G(V, E) where the edges are labeled either “+” (similar) or “-” (different) with nonnegative weights, we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of “+” edges within clusters and “-” edges between clusters. This problem is NP-hard. We design an approximation algorithm with the approximation ratio max $\left\{a, \frac{(2-k) a+k-1}{k}\right\}$, where a is the weighted proportion of “+” edges in all edges. As a varies from 0 to 1, the approximation ratio varies from $\frac{k-1}{k}$ to 1 and the minimum value is 1/2.

Key words: k-Correlation clusters, Approximation algorithms, Choosing the better of two solutions

中图分类号:

05C85
68W25

. [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.

Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering[J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.

参考文献

[1] Heider, F.: Attitudes and cognitive organization. J. Psychol. Interdiscip. Appl. 21(1), 107-112 (1946)
[2] Cartwright, D., Harary, F.: Structural balance: a generalization of Heiders theory. Psychol. Rev. 63(5), 277-293 (1956)
[3] Abell, P., Ludwig, M.: Structural balance: a dynamic perspective. J. Math. Sociol. 33(2), 129-155 (2009)
[4] Doreian, P., Mrvar, A.: A partitioning approach to structural balance. Soc. Netw. 18(2), 149-168 (1996)
[5] Doreian, P., Mrvar, A.: Partitioning signed social networks. Soc. Netw. 31(1), 1-11 (2009)
[6] Inohara, T., Takahashi, S., Nakano, B.: On conditions for a meeting not to reach a deadlock. Appl. Math. Comput. 90(1), 1-9 (1998)
[7] Bo, Y., Cheung, W.K., Liu, J.: Community mining from signed social networks. IEEE Trans. Knowl. Data Eng. 19(10), 1333-1348 (2007)
[8] Facchetti, G., Giovanni, L., Altafini, C.: Computing global structural balance in large-scale signed social networks. Proc. Natl. Acad. Sci. 108(52), 20953-20958 (2011)
[9] Srinivasan, A.: Local balancing influences global structure in social networks. Proc. Natl. Acad. Sci. USA 108(5), 1751-1752 (2011)
[10] Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1/3), 89-113 (2004)
[11] Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360-383 (2003)
[12] Erik, D., Nicole, I.: Correlation clustering with partial information. In: Proceeding of the 6th International Workshop on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, pp. 1-13 (2003)
[13] Emanuel, D., Fiat, A.: Correlation clustering-minimizing disagreements on arbitrary weighted graphs. In: Proceeding of the 11th Annual European Symposium on Algorithms, pp. 208-220 (2003)
[14] Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 526-527 (2004)
[15] Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. Theory Comput. 2, 249-266 (2006)
[16] Andersson, G., Engebretsen, L., Hastad, J.: A new way of using semidefinite programming with applications to linear equations mod p. J. Algorithms 39(2), 162-204 (2001)
[17] Brusco, M., Steinley, D.: K-balance partitioning: an exact method with applications to generalized structural balance and other psychological contexts. Psychol. Methods 15(2), 145-57 (2010)
[18] Figueiredo, R., Moura, G.: Mixed integer programming formulations for clustering problems related to structural balance. Soc. Netw. 35(4), 639-651 (2013)
[19] Lcia, D., Rosa, F., Yuri, F., Mrio, L.: Efficient solution of the correlation clustering problem: An application to structural balance. In: Proceeding of OTM Confederated International Conferences “On the Move to Meaningful Internet Systems”, pp. 674-683 (2013)
[20] Mario, L., Lucia, D., Yuri, F., Rosa, F.: An ils algorithm to evaluate structural balance in signed social networks. In: Proceeding of the 30th Annual ACM Symposium, pp. 1117-1122 (2015)
[21] Levorato, M., Figueiredo, R., Frota, Y., Drummond, L.: Evaluating balancing on social networks through the efficient solution of correlation clustering problems. EURO J. Comput. Optim. 5(4), 467-498 (2017)
[22] Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N.: Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2), 172-187 (2006)
[23] Facchetti, G., Lacono, G., Altafini, C.: Computing global structural balance in large-scale signed social networks. Proc. Natl. Acad. Sci. 108(52), 20953-20958 (2011)
[24] Ma, L., Gong, M., Haifeng, D., Shen, B., Jiao, L.: A memetic algorithm for computing and transforming structural balance in signed networks. Knowl. Based Syst. 85(9), 196-209 (2015)
[25] Ma, L., Gong, M., Yan, J., Yuan, F., Haifeng, D.: A decomposition-based multi-objective optimization for simultaneous balance computation and transformation in signed networks. Inf. Sci. Int. J. 378, 144-160 (2017)
[26] Pouya, E., Abtahi, S.E., Jalili, M.: Mesoscopic analysis of online social networks: the role of negative ties. Phys. Rev. E 90(4), 042817 (2014)
[27] Esmailian, P., Jalili, M.: Community detection in signed networks: the role of negative ties in different scales. Sci. Rep. 5, 14339 (2015)
[28] Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79-100 (1988)

Approximation Algorithms on k-Correlation Clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价