Have you ever declined a party invitation from a good friend because of the chance you'd run into that colleague of theirs who you can't stand? Then you've had a taste of structural balance theory - a mathematical technique for assessing the the stability of social networks.

Sites like Facebook have popularised social graphs: each person is a node, and edges are drawn between friends. A slight generalisation -to 'signed' graphs - allows for both friendship (positive edges) and animosity (negative edges) to be represented in a single graph, and it's in this context that structural balance has been applied.

If we consider a triangle of three people - so each person is either a friend or enemy of each of the others - then there are four possible arrangements:

• (+++) If all three edges are positive, then we have three mutual friends: this is clearly stable.
• (+--) If there is only one positive edge, with the other two negative, then this is also stable - we have two friends who share a common enemy.
• (++-) If there is only one negative edge, however, then we have the unstable configuration discussed in the opening paragraph: of an individual with two friends who don't get along.
• (---) If all the edges are negative, then we have three mutual enemies. Since any two at least have their dislike of the third in common, and thus have an incentive to set aside their differences and team up against that individual, this may also be considered unstable.

A complete signed social graph is then balanced if every triangle is stable: in such a society, it must be the case that both the friend of your friend is your friend, and that the enemy of your enemy is your friend. A simple example is a population where everyone likes everyone else- clearly this is balanced. At the other extreme is a society polarised into two camps- where everyone is friends with the members of their camp, but an enemy of everyone in the other camp. (If we reinterpret positive/negative edges as political agreement/disagreement, then this models a two-party political system.)

Remarkably, it can be shown that these are the only ways to achieve structural balance:

Theorem A complete signed graph is balanced if and only if its nodes can be divided into two (possibly empty) sets so that every edge within a set is positive, and every edge between sets is negative.

If we relax the condition that the graph be complete, then we may generalise the notion of balance to this second characterisation, which leads us to

Theorem A signed graph is balanced if and only if the product of the signs in every cycle is positive.

for which it is necessary (but no longer sufficient) for every triangle to be stable.

It seems unreasonable to expect that this mathematical precision would carry over neatly to a situation as complex as human interaction, and that real-world social graphs would indeed be perfectly balanced. In fact, the motivating psychological argument shouldn't even lead to this conclusion: the claim is that unstable configurations introduce social tension, but this needn't tear the structure apart nor lead to instant reconciliations. Nonetheless, an examination1 of the 300,000 users in a massively multiplayer online game, dividing their actions into either friendly or hostile, showed that - compared to appropriately proportioned random assignments of edge signs - stable triangles were substantially over-represented, and the unstable ++- ones under-represented. The other unstable case (---), whilst less common than would be predicted by a random model, deviates less dramatically than the other cases: this lends weight to the weak model of structural balance, which interprets only (++-) configurations as unstable.

Structural balance has also been offered as a way to study the dynamics of international relations - an arena where one might reasonably expect every actor to have either a positive or negative opinion of the others. Here 'balance' needn't be a good thing, since world-wide friendship seems unlikely, and the alternative is the emergence of a pair of alliances each utterly opposed to the other, as demonstrated most recently by the cold war.

1Multirelational organization of large-scale social networks in an online world

Brought to you as part of Sam512's Nodingmeet In Winchester Without A Clever Title

Log in or register to write something here or to contact authors.