Balance Theory

Some social configurations are stable and others are not. A triangle of three mutual friends holds; a triangle in which two friends both dislike a third does not, and tends to resolve itself one way or the other. Balance theory formalises that intuition as a property of signed graphs, where edges carry a positive or negative sign rather than merely existing.

This seminar paper, written for a module on graph-algorithmic methods for analysing social networks, works through the theory from its origins to its practical consequences.

Signed graphs

A signed graph is a simple undirected graph whose edges carry a binary weighting: either a positive relation or a negative one. The actors become nodes, their relations become edges, and the configuration can be written as a matrix. For a graph on three nodes where node 1 dislikes node 2 and likes node 3:

$$M = \begin{pmatrix} 0 & -1 & 1 \\ -1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

with entries defined as

$$M_{ij} = \begin{cases} +1, & \text{if } i \text{ and } j \text{ like each other} \\ 0, & \text{indifference} \\ -1, & \text{if } i \text{ and } j \text{ dislike each other} \end{cases}$$

That middle case is worth pausing on, because Heider does not allow for it. His model assumes the actors in a triad are always mutually aware of one another, so the situation where no relation exists at all falls outside it entirely. The generalisation below is essentially an attempt to recover that missing case.

A complete graph, which is what Heider’s condition requires, has

$$\Delta_{n-1} = \binom{n}{2} = \frac{n(n-1)}{2}$$

edges, and the number of sign permutations available to it is

$$2^{\binom{n}{2}} = 2^{\frac{n(n-1)}{2}}$$

For the triad that gives three edges and eight permutations:

$$\Delta_{3-1} = \binom{3}{2} = 3, \qquad 2^{\binom{3}{2}} = 2^{3} = 8$$

The exponent is where the trouble starts. Adding actors grows the permutation count quadratically in the exponent, and the resulting runtime problem sits in the NP-complete class. Analysing one triad by hand takes a moment. Analysing a real network does not scale at all without simplification, and the remainder of the paper is about what those simplifications cost.

The P-O-X model and its eight permutations

Heider’s model is a relationship system of three elements. P is the person from whose perspective the situation is analysed, O is a second party, and X is an object towards which both hold an attitude. The triangle they form is the triad, and the situation is always read from P’s point of view.

A triad is in equilibrium when all three relations are positive, or when two are negative and one positive. It is in disequilibrium when exactly one relation is negative. Counting negatives is therefore enough to tell the two apart: none or two of them means balance, one means imbalance. That leaves a fourth case, the triad in which all three relations are negative, which Heider declines to decide either way and which counts as ambiguous.

Unbalanced systems are experienced as disharmonious and full of tension. That tension generates instability across the whole network, which in turn produces a tendency to change into a balanced one, in the simplest case by changing the relations themselves. Every version of balance theory shares this principle of a tendency towards equilibrium.

The four balanced permutations are the ones that have passed into ordinary speech:

• All three relations positive: the friend of my friend is my friend.
• P and O positive, both negative towards X: the enemy of my friend is my enemy.
• P negative towards both O and X, O positive towards X: the friend of my enemy is my enemy.
• P positive towards X, both negative towards O: the enemy of my enemy is my friend.

The structural balance property

Determining balance across a whole network is a far harder task than inside a triad, and the structural balance property is the first of two simplifications the paper examines. Cartwright and Harary stated it in their graph-theoretically decisive article of 1956:

An s-graph is balanced if and only if its points can be separated into two mutually exclusive subsets such that each positive line joins two points of the same subset and each negative line joins points from different subsets.

Harary had put it more plainly three years earlier, in the Michigan Mathematical Journal:

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 each pair of people in X likes each other, each pair of people in Y likes each other and everyone in X is the enemy of everyone in Y.

Two possibilities follow, and only two. Either balance through uniformly positive edges, or balance through a partition into exactly two subsets holding uniformly opposed attitudes towards one another.

Applied to a network sharing a single attitude object A, the theorem is expressed through two subsets of the signed graph:

$$X \subset G(V, E), \quad Y \subset G(V, E), \quad X \cap Y = \emptyset$$

The disjointness condition carries the whole content. A node cannot be a mutual friend inside both camps at once, and it is that exclusion which allows the balance of an arbitrarily large network to be decided by finding a partition rather than by enumerating its triads.

Generalisation

For all the simplification it buys, the structural balance property remains a restrictive solution, defined only for complete graphs. It cannot answer the question Heider categorically excluded: what happens when a person holds no relation at all to another person or to an attitude object, whether through having no knowledge of them or through plain indifference.

The answer is to relax the property, summarising similar groups within the graph into clusters. The procedure runs in two repeated steps.

First, clusters are formed by merging nodes joined to one another by positive edges. Second, where a negative edge runs from two separate clusters to a single node outside both, those clusters are connected through that node; the node itself then drops out and the connecting edge becomes negative. Iterating reduces a dense signed graph to a small graph of clusters standing in signed relations to one another, which can be read directly.

What this buys and what it costs are the same thing. The limits of these methods lie above all in the accuracy of the evaluation, because generalising the result is exactly what makes it tractable.

Where the idea comes from

The question of how interpersonal relations hang together considerably predates Heider formalising it in the 1950s. The metaphorical readings of balanced triads go back at least to the fourth century BC, where the Indian philosopher Kautilya set out the relation in the Arthashastra:

The king who is situated anywhere immediately on the circumference of the conqueror’s territory is termed the enemy.

The king who is likewise situated close to the enemy, but separated from the conqueror only by the enemy, is termed the friend (of the conqueror).

In recent history the clearest instance is Churchill’s positioning towards Nazi Germany and the Soviet Union. He accepted a positive relation with the Soviet Union, a power the Allies were otherwise hostile to, in order to make Germany a shared enemy. Read as a triad, that is the fourth balanced permutation being engineered deliberately.

Applications

Political relations form signed networks directly, with politicians or states as nodes and a political issue as the attitude object, the system combining attraction and repulsion. Alliance formation, war and coalition building are the concrete cases, and they render particularly well as a matrix: the paper uses a relationship map of the United States and the states of the Middle East as it stood in 2014.

Online product rating sites give the same structure a very different setting. Customers become the nodes and the products or services become the attitude object, with positive and negative ratings supplying the signs. Epinions and Amazon are the examples named.

Conclusion

Heider’s work stands as the basis for a good deal of foundational graph theory, and what makes it notable is the multidisciplinary route it took, connecting approaches from psychology’s pre-information-technology era to modern analysis tools in computer science.

The qualification is the one the mathematics forced from the start. Under a time-complexity reading, many graph problems of this kind are NP-hard, which makes solving them completely impossible for large networks. What the structural balance property and the generalisation achieve is precisely a conversion: they turn NP-hard problems into problems solvable in polynomial time, and the price is paid in the accuracy of what comes out.

The theory applies anywhere at least three actors interact while holding relations both to one another and to a shared attitude object.

@techreport{golombeck2017balancetheorie,
  author      = {Golombeck, Marius},
  title       = {{Balancetheorie}},
  institution = {University of Applied Sciences and Arts Dortmund},
  address     = {Dortmund, Germany},
  year        = {2017},
  month       = aug,
  language    = {german},
  doi         = {10.13140/RG.2.2.29573.60644},
  url         = {https://www.researchgate.net/publication/330162670}
}