Structural Balance

Prerequisites

Introduction to Graphs
Strong and Weak Ties
Weighted Graphs

Outcomes

Understand the structural balance property for sets of three nodes
Understand the structural balance theorem for a graph
Recognize structural balance in a weighted graph

References

Easley and Kleinberg chapter 5 (especially section 5.1-5-3)

Introduction¶

We now shift our discussion to the notion of whether or not a network is balanced
For this discussion we will use undirected, signed graphs
- +1 (also called +): the nodes are friends
- -1 (also called -): the nodes are enemies
We won’t consider strength of ties right now
We will limit discussion to complete graphs (cliques), where every pair of distinct nodes is connected by a + or - edge
There are no missing or zero-weight edges in this model

Balance in Triangles¶

To start thinking about balance, consider the possible configurations of + and - edges in a triangle
There are 4 options, shown in Figure 1

Four triangles labeled a through d. AB, AC, BC signs are +++, ++−, +−−, and −−− respectively. Cases a and c are balanced; b and d are not. — Figure 1:The four triangle types have 3, 2, 1, and 0 positive edges. Redrawn from Easley and Kleinberg (2010), *Networks, Crowds, and Markets*, Figure 5.1.

In (a) all people are friends -- this is happy and balanced
In (c) A-B are friends with a common enemy C -- nobody has reason to change alliances => balanced
In (b) A is friends with B and C, but they are enemies -- B and C may try to flip A against other => not balanced
In (d) all are enemies -- two parties have incentive to team up against common enemy => not balanced

Balance In Graphs¶

This definition of balance in triangles can be extended to graphs
A complete graph G satisfies the Structural Balance Property if for every set of three nodes, exactly one or three of the edges is labeled +

Implications: Balance Theorem¶

One implication of the Structural Balance Property is the Balance Theorem

If a labeled complete graph is balanced, then either all pairs of nodes are friends, or else the nodes can be divided into two groups, X and Y , such that every pair of nodes in X like each other, every pair of nodes in Y like each other, and everyone in X is the enemy of everyone in Y .

Notice the strength of the statement: either all + or two mutually exclusive groups of friends that are all enemies with other group

We can see both possibilities in Figure 2.

Two complete four-node graphs: all positive edges, or positive edges within each of two groups and negative edges across groups. — Figure 2:A balanced complete graph has either all positive edges or two groups with positive edges within each group and negative edges between them.

Question: could we have three mutually hostile groups and keep every triangle balanced?

Proving Balance Theorem¶

We will provide some intuition for how to prove the Balance Theorem, which will help us understand why it is true
Consider a complete Graph G
Two alternative cases:
1. Everyone is friends: satisfies theorem by definition
2. At least one pair of nodes are enemies: need to prove
For case 2, we must be able to split G into $X$ and $Y$ where the following hold
1. Every node in $X$ is friends with every other node in $X$
2. Every node in $Y$ is friends with every other node in $Y$
3. Every node in $X$ is enemies with every node in $Y$

Proof by construction¶

Start with a complete, balanced graph $G$
We will prove the balance theorem by constructing sets $X$ and $Y$ and verifying that their members satisfy the 3 properties outlined above
To start, pick any node $A \in G$
Put $A$ and all its friends in $X$ . Put all its enemies in $Y$
Because $G$ is complete and every edge is labeled + or -, these sets contain all nodes

We know two signs in each triangle in Figure 3. What must the third sign be?

Three triangles anchored at A. Two positive signs force a positive third sign; two negative signs force a positive third sign; mixed signs force a negative third sign. — Figure 3:Balance forces the amber edge in each triangle. The first two cases give positive edges within X and within Y; the third gives negative edges between X and Y.

Condition 1: $\forall B, C \in X,\ B \ne C \quad B \leftrightarrow C = +$ ¶

If one of the nodes is $A$ , the edge is positive by the definition of $X$
Otherwise, let distinct nodes $B, C \in X$ be different from $A$
We know $A \leftrightarrow B = +$ and $A \leftrightarrow C = +$
Because graph is balanced, this triangle must have 1 or 3 +
There are already 2, so it must be that $B \leftrightarrow C = +$
B, C were arbitrary, so this part is proven

Condition 2: $\forall D, E \in Y,\ D \ne E \quad D \leftrightarrow E = +$ ¶

Let distinct nodes $D, E \in Y$
We know $A \leftrightarrow D = -$ and $A \leftrightarrow E = -$
Because graph is balanced, this triangle must have 1 or 3 +
There are no positive edges and only one edge left, so it must be that $D \leftrightarrow E = +$
D, E were arbitrary, so this part is proven

Condition 3: $\forall B \in X$ and $E \in Y \quad B \leftrightarrow E = -$ ¶

If $B=A$ , the edge to $E$ is negative by the definition of $Y$
Otherwise, let $B \in X$ and $E \in Y$
We know $A \leftrightarrow E = -$ and $A \leftrightarrow B = +$
Because the graph is balanced, this triangle must have 1 or 3 positive edges
There is one positive edge and only one edge left, so $B \leftrightarrow E = -$
B and E were arbitrary, so this part is proven

Summary¶

We’ve just proven that for any complete, balanced graph $G$ ; we can partition $G$ into sets $X$ and $Y$ that satisfy the group structure of all friends or two groups of friends
This has interesting implications for fields like social interactions, international relations, and online behavior

Application: International Relations¶

Consider the European alliances represented in Figure 4, from 1872 to 1907

Six European alliance schematics from 1872–81 through 1907. Solid blue edges mean friendship; dashed amber edges mean enmity. Missing edges remain absent. The final complete graph has friendly groups Great Britain–France–Russia and Austria-Hungary–Germany–Italy, with negative edges between groups. — Figure 4:European alliances, 1872–1907. Redrawn from Easley and Kleinberg (2010), *Networks, Crowds, and Markets*, Figure 5.5; their underlying source is Antal, Krapivsky, and Redner (2006), *Social balance on networks: The dynamics of friendship and enmity* (bibliography entry 20). Country positions, edge signs, and missing edges follow the source figure.

The first five panels are incomplete: a missing edge means the relationship is not shown, not that it is negative
The balance theorem above applies to complete signed graphs. The final panel meets that assumption and shows two internally friendly groups
These snapshots illustrate the model; they do not establish why alliances changed or why war occurred

Question: in the 1907 panel, which countries form each of the two groups?