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

Previous Articles Next Articles

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

CLC Number:

05C85
68W25

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.

TrendMD

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal [J]. Journal of the Operations Research Society of China, 2021, 9(4): 883-892.
[2]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.