Balance and Frustration in Signed Networks

Abstract

The frustration index is a key measure for analysing signed networks, which has been underused due to its computational complexity. We use an exact optimisation-based method to analyse frustration as a global structural property of signed networks coming from diverse application areas. In the classic friend-enemy interpretation of balance theory, a by-product of computing the frustration index is the partitioning of nodes into two internally solidary but mutually hostile groups. The main purpose of this paper is to present general methodology for answering questions related to partial balance in signed networks, and apply it to a range of representative examples that are now analysable because of advances in computational methods. We provide exact numerical results on social and biological signed networks, networks of formal alliances and antagonisms between countries, and financial portfolio networks. Molecular graphs of carbon and Ising models are also considered. The purpose served by exploring several problems in this paper is to propose a single general methodology for studying signed networks and to demonstrate its relevance to applications. We point out several mistakes in the signed networks literature caused by inaccurate computation, implementation errors or inappropriate measures.

Accepted version, 28 pages, 13 figures, and 5 tables

References in corpus (3)

• Social Balance on Networks: The Dynamics of Friendship and Enmity
• On network bipartivity
• Measuring Partial Balance in Signed Networks

Cited by in corpus (16)

• Detecting coalitions by optimally partitioning signed networks of political collaboration
• Testing structural balance theories in heterogeneous signed networks
• Polarization and multiscale structural balance in signed networks
• Identifying hidden coalitions in the US House of Representatives by optimally partitioning signed networks based on generalized balance
• The structure of gene-gene networks beyond pairwise interactions
• Second to first order phase transition; coevolutionary versus structural balance
• Frustration-critical signed graphs
• Signed graphs in data sciences via communicability geometry
• Assessing frustration in real-world signed networks: a statistical theory of balance
• Strange Attractors in Complex Networks
• Patterns of link reciprocity in directed, signed networks
• Community detection in bipartite signed networks is highly dependent on parameter choice
• Efficient Enumeration of the Optimal Solutions to the Correlation Clustering problem
• Quantum-Assisted Correlation Clustering
• Shaping Magnetic Order by Local Frustration for Itinerant Fermions on a Graph
• Negative Ties Highlight Hidden Extremes in Social Media Polarization