In numerous contexts of our lives, specific dyadic interactions are characterized as “negative,” a term I use advisedly given its imprecise definition. To illustrate, consider one’s ego-centric networks, which are essentially the subgraphs formed by oneself and one’s immediate social connections. Within these networks, it is likely to identify relationships that are particularly favorable—these can be denoted with a ‘+’ sign on the corresponding edges. Conversely, relationships that are less favorable can be marked with a ‘-‘ sign. This sign convention aids in the binary classification of social connections into positive and negative categories. Typically, altering one’s perception of another person involves an additive process: the actions of acquaintances either enhance or diminish our respect and friendship towards them. For instance, a person towards whom one initially feels neutral might earn a positive ‘+’ label through a commendable act, or conversely, a negative ‘-‘ label through unfavorable actions.

The concepts underlying structural balance theory are highly intuitive. For instance, consider a hypothetical scenario involving a signed triangle among three entities referred to here as “peppers.” This triangle is described as unbalanced because the red pepper experiences anxiety about the potential unintended meeting of its two friends whenever it socializes with the blue pepper. In contrast, a triangle would be considered balanced if it contained either three positive signs (‘+’) or only one. There are four distinct signed configurations of triangles, which can be categorized based on the number of positive signs they contain—zero, one, two, or three. Let us denote each configuration as the i-th, where i represents the number of positive signs in the triangle.

0th Configuration: This represents an unstable scenario wherein there exists a strong propensity for the red and blue entities, herein described as “peppers,” to form an alliance against the green entity. For historical context, consider an analogy to World War II: envision the green pepper as Germany, with the blue and red peppers symbolizing England and Russia, respectively. These latter entities eventually formed a coalition to combat the adversarial forces led by Hitler.

1st configuration: Such a configuration is a stable one.

2nd configuration: Such a configuration is shown in the figure above and as we explained is unstable.

3rd configuration: In this configuration, all entities within the triangle maintain positive relationships with each other. This scenario could be referred to as the “harmonious” configuration, emphasizing a state of mutual peace and cooperation among all parties involved.

A fundamental principle observable from the previous discussion is that the product of the signs on any two edges of a triangle determines the sign of the third edge in a stable configuration. This principle is rooted in the intuitive concepts that “the enemy of my enemy is my friend,” “the friend of my friend is my friend,” “the friend of my enemy is my enemy,” and “the enemy of my friend is my enemy.” These relational dynamics are particularly evident in international relations, where alliances and enmities between nations often reflect these patterns.

Accordingly, one can define a labeling or edge coloring of a complete graph as balanced if every constituent triangle is balanced. In most real-world networks, it appears that there exists a significant number of such balanced triangles, alongside a larger subset of unbalanced triangles, which may contribute to what could be termed a ‘stable instability.’ This concept, though complex, can be analogously understood by examining the geopolitical landscape prior to the outbreak of the Second World War, where nations were aligning and defining their stances in relation to the emerging threat of the Nazis.

This theoretical framework lays the groundwork for further empirical investigation, such as a study examining the balance of international relations through graph-theoretic analysis. This approach not only provides a structured method to assess international dynamics but also contributes to our understanding of global stability through the lens of structural balance theory. An important graph theoretic result is the following theorem due to Harary.

Harary’s theorem: Assume the labeling of the complete graph is balanced. Then either all edges are positive or there exists a partition of the vertices into two groups such that every edge within and are positive and all edges across the cut are negative.

Select a vertex and assign along with all of its “positive” neighbors, denoted as , to the set . Simultaneously, place all the “negative” neighbors of , represented by , into the set . It is evident that the sets and are disjoint and together partition the vertex set of the complete graph.

[1] On the notion of balance in a signed graph, F. Harary[2] “Networks, Crowds and Markets“, Chapter 5,  D. Easley and  J.Kleinberg[3] Predicting Positive and Negative Links in Online Social Networks, Leskovec, Huttenlocker, Kleinberg

[4] Predicting positive and negative links with noisy queries: Theory & practice Tsourakakis, Mitzenmacher, Larsen, Blasiok, Lawson, Nakkiran, Nakos