Abstract
Structural balance theory is an important theory in signed graphs. We consider the optimization problems: given a signed graph, the maximum number of edges that needed to be kept to make it balanced is called K(G). We firstly prove the computation of K(G) is NP-hard. Next we design four approximation algorithms to compute K(G).
This research is supported part by National Natural Science Foundation of China under Grant No.11901605, and by the disciplinary funding of Central University of Finance and Economics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Antal, T., Krapivsky, P.L., Redner, S.: Social balance on networks: the dynamics of friendship and enmity. Phys. D 224(1–2), 130–136 (2006)
Cartwright, D., Harary, F.: Structural balance: a generalization of Heider’s theory. Psychol. Rev. 63(5), 277 (1956)
Davis, J.A.: Structural balance, mechanical solidarity, and interpersonal relations. Am. J. Sociol. 68(4), 444–462 (1963)
Easley, D., Kleinberg, J., et al.: Networks, Crowds, and Markets, vol. 8. Cambridge University Press, Cambridge (2010)
Fritz, H., et al.: The Psychology of Interpersonal Relations. Wiley, New York (1958)
Guha, R., Kumar, R., Raghavan, P., Tomkins, A.: Propagation of trust and distrust, pp. 403–412 (2004)
Harary, F., et al.: On the notion of balance of a signed graph. Michigan Math. J. 2(2), 143–146 (1953)
Håstad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798–859 (2001)
Heider, F.: Attitudes and cognitive organization. J. Psychol. 21(1), 107–112 (1946)
Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319–357 (2007)
König, D.: Akademische verlagsgesellschaft (1936)
Kunegis, J., Lommatzsch, A., Bauckhage, C.: The slashdot zoo: mining a social network with negative edges, pp. 741–750 (2009)
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media, pp. 1361–1370 (2010)
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks, pp. 695–704 (2008)
Marvel, S.A., Strogatz, S.H., Kleinberg, J.M.: Energy landscape of social balance. Phys. Rev. Lett. 103(19), 198701 (2009)
Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074–2097 (2000)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2013)
Zaslavsky, T.: A mathematical bibliography of signed and gain graphs and allied areas. Electron. J. Comb. DS8-Dec (2012)
Acknowledge
The authors are indebted to Professor Xujin Chen, Professor Xiaodong Hu and three anonymous referees for their invaluable suggestions and comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Diao, Z., Tang, Z. (2020). Approximation Algorithms for Balancing Signed Graphs. In: Zhang, Z., Li, W., Du, DZ. (eds) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science(), vol 12290. Springer, Cham. https://doi.org/10.1007/978-3-030-57602-8_36
Download citation
DOI: https://doi.org/10.1007/978-3-030-57602-8_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57601-1
Online ISBN: 978-3-030-57602-8
eBook Packages: Computer ScienceComputer Science (R0)