Structural Balance

Imagine you have a completely labeled graph. Every node in the graph is aware of every other node, and each edge is defined as either positive or negative. Lots of research in social psychology and empirical evidence has shown that such graphs will tend towards a certain state, known as structural balance. Note that this type of modelling is best done in small networks likes a sports team, or with entire countries and diplomatic relations since those are cases where the graphs are actually complete with stated valences.

What is structural balance? It is the condition s.t that in every possible grouping of 3 nodes in the graph, there is either 1 or 3 positive edges. If there are 3 negative edges (0 positive edges),research demonstrates that one will flip positive. Because the enemy of my enemy is my friend. And if we only have 2 positive edges, something similar to the principle of triadic closure will dictate that the one negative edge will turn positive

Balance Theorem

There is an intuitive an easy to prove theorem that demonstrates that if a graph satisfies this structural balance property, then this equivalent to being able to separate all of the nodes into two sets, X & Y, s.t every node in X has positive relationships with each other, every node in Y has positive relationships with each other, and every node X has a negative relationship with Y (& vice versa).

This is easy to show by first starting with an arbitrary node "A" in your structurally balanced graph, and, W.L.O.G, assigning "A" and all of its friends into the Set X and all of "A"s enemeies into set Y. Taking the assumption of structural balance, we can take any 2 nodes (from set X, or Y) and add the third node "A".

The principle of structural balance applied to any arbitrary grouping of these nodes makes it then very easy to show that all nodes in X are friends, all nodes in Y are friends, and all edges between nodes in X and Y are negative.

Balance Theorem 2

Okay, but now suppose it is possible to have 3 negative edges when taking an arbitrary set of three nodes. The reason for allowing this is simply that empirical research has shown that the cognitive drive to change this state of affairs is less than the case of 2 positive edges. So suppose we allow these triangles to form. Does this lead to another version of the Balance Theorem? It turns out that when we allow for 3 negative edges, the Balance theorem generalizes to multiple sets X, Y, Z.. s.t al members are friends with each other within the set and enemies with everyone outside that set.

The way to prove it proceeds in the same way. Start with an arbitrary node A. Put all of its friends in our first set "X". For the proof to work, we need to show that all members in X are friends with each other and also that the are enemeies with every other member in the graph. We already know from the procedure in Balance Theorem 1 that the first case is true. To show that the second statement is true, consider a member outside of set X. Now take "A" and one of A's friends. A is already enemeis with that member Since A is friends with the other member, the other member must have a negative relationship with that member. So the set "X" satisfies this property and we can "remove" it from the graph. We can then iterate this procedure by treating the set "X" as a single node and creating subsequent new graphs. If structural balance holds, then we can create a multiple sets of Nodes s.t every member of each set is friends with each other and enemies with every member outside of it.

Showing Structural Balance in Arbitrary Graphs

Now consider an arbitrary graph where not everyone is aware of each other. This is a situation that obviously arises much more frequently. How can we define "structural balance" for such a graph? An easy definition would be simply that there exists a possible "filling in" of the edges such that structural balance becomes true. Another definition would be again to take the global view, and look at the balance theorem, which is that it is possible to divide the graph into two sets X & Y s.t members of X are friends with each other, members of Y are friends with each other, and members of X & Y are enemies - all to the extent that they know each other.

In fact these two characterizations are equivalent. I.e if one is true the other is true (to prove this we need to show the bidirectionality of this statement). But it is still hard to reason about. How can I easily show whether a graph does or does not satisfy structural balance?

Let's start with the global view. Suppose I start with some node A. I assign it to set "X". I then "walk" along the edges of A. if it's a positive edge I assign to the same set as the node before it. If it is negative, I switch. Structural balance will be violated if I end up with something like a dual labelling. For example, suppose I have a circular graph of 3 nodes. I start with A, and A has a negative relationship with B, so A is in set X and B is in set Y. B has a positive relationship with C so I put C in to Y. Now suppose C has a positive relationship with A. I would be forced to put A into set 'Y', but we've already placed A in set X

So this is a contradiction. In general, if we have an odd number of negative edges, in a cycle, this means that we have "flipped" the set membership when we go back to the original node, which leads to a contradiction. This violates the core corallary of structural balance which is that we can divide the network into these two different sets X & Y.

proof

So now we want to be able to prove that a signed graph is balaned if and only if it does not have a cycle with an odd number of negative edges. We do this by designing an algorithm that searches for the balaned division. If the only possible outcomes of such an algorithm are that it either achieves structural balance (we are able to divide the entire network into two sets X & Y s.t all members of X are friends and all members of Y are friends and all edges between X & Y are negative) or it finds a cycle with an odd number of negative edges, then the proof is complete

1. First find all of the positive edges. Create "blobs" of positive edges. These blobs can now just be called "supernodes". If there is a negative edge within the blob, we are done because there is a cycle with an odd number of negative edges. This also means that we have no structural balance. This is because we can create the node only by connecting positive edges. If there is a negative edge, then that negative edge must be within a triangle of nodes that do not satisfy structural balance (b/c for the node with the negative edge it's other two connectsions must be positve to be included in the supernode)
2. If we have satisfied this property, we can treat each supernode as its own node, and then work with this reduced graph (every node has a positive relationship with each other within each super node and negative relationships with everyone outside). Now we want to find a labelling "X" and "Y" for each super node. If we can do this succesfully we have structural balance because all the nodes can be assigned the same label as their parent node, and there will only be positive edges in X, positive edges in Y, and negative edges between them.
3. To find this type of labelling, we perform BFS from some arbitrary supernode. Since all the edges b/w supernodes are negative, we assign the opposite label to each "level" in the BFS. Note however that as a I perfrom BFS, when I make each subsequent step, I either enter into a new layer, or stay in the same layer (this happens if the neighbor of my neighbor is also my neighbor). This leads to a contradiction of what to label that particular node, which means such labelling of structual balance is impossible. It also means it creates a cycle with an odd number of negative edges (it will be a "trio" when looking at supernodes, but one can easily create arbitrary longer paths using various nodes within each of the supernodes).

Weaker Structural Balance

In this section we consider a version of structural balance that is more loose;for example at the local level it does not require that at the local level every triangle satisfies this property.