This blog post introduces a notion of Structural Balance for non-complete networks and applies it to a graph representing the relationships between parties bound up Middle Eastern conflict.  I made and used the following Python program in the analysis of the graph.  Feel free to modify and use it for your own purposes (but note that you’ll need NetworkX if you want to run it.)
***

The early sections of Chapter 5 of Networks, Crowds and Markets introduced us to a basic notion of Structural Balance for signed graphs which represent positive and negative relationships between nodes.  In those sections, Easley and Kleinberg point out that the notion of Structural Balance is relevant to the study of international relations (p. 113); but it is clear that many fruitful applications of this notion will require that we extend its definition.  More specifically, we dealt with a notion of Structural Balance which was uncompromising in two important ways:

• The basic notion can only be applied to complete graphs, in which there are edges connecting every pair of nodes.  It is entirely plausible, however, that we will encounter situations in which some of the parties represented by nodes in a graph are either unaware of one another’s existence or have neutral relationships—and we would still like to have a notion of Structural Balance which applies in these cases.
• A graph G can only count as balanced if every set of three nodes in G satisfies the Structural Balance Property; thus, even a huge graph with an extremely low percentage of unbalanced triangles would count as unbalanced.  It would be useful, however, to have a more flexible definition of Structural Balance which we can use to characterize approximately balanced graphs.

Section 5.5 of our textbook discusses both of these ways of generalizing the basic definition of Structural Balance.  In this blog post, we will cover the first of these generalizations and work with a definition of balance for social networks which are not necessarily complete.  We will then use it in the analysis of this graph (by Egyptian blogger The Big Pharaoh) from Max Fisher’s blog post at The Washington Post:

The graph documents positive and negative relationships between parties involved in the conflict.  (For our purposes, we will ignore the “has no clue” edges.)  According to Fisher, the graph suggests that there is continual conflict in the region due to an instability which itself arose from the complexity of the situation:

“There are rivals who share mutual enemies, allies who back opposite sides of the same conflict, conflicting interests and very strange bedfellows. There are two categories of countries: the ones that meddle (the United States, Iran, Saudi Arabia, Qatar, Turkey and Israel) and the ones that are meddled with (Egypt, Syria, Lebanon and the Palestinian territories). Each of the former is pushing for a different outcome in each of the latter, falling in and out of cooperation and competition. And that long-running interference is an important part of why conflict persists.”

If Fisher is right, we have reason to think the graph will not be structurally balanced according to the new definition.  Let’s see whether this is, in fact, the case.

Structural Balance in Arbitrary Networks

In section 5.5A of the textbook, Easley and Kleinberg introduce a definition of Structural Balance which can be applied to arbitrary signed graphs: that is, graphs in which any two nodes are either joined by a negative edge, a positive edge, or no edge at all.  (Note that the authors take negative, positive, and non-existant edges to indicate enmity, friendship, and mutual ignorance respectively; in our analysis of the graph, however, we will take the lack of an edge between two parties to indicate their neutrality.)

E&K begin by redefining Structural Balance in two different yet equivalent ways.  The first definition focuses on a local property; it states that a non-complete network is balanced just in case it is possible to produce only balanced triangles by “filling in” all of the missing edges.  The second definition focuses on a global property; it requires that the graph divide into exactly two mutually opposed sets of friends, X and Y, such that there are only positive or neutral relationships with in each group, and that all X-Y relationships are either negative or neutral.  Yet neither of these definitions are very satisfying from a conceptual point of view, since neither provides us with a straightforward way of checking whether an arbitrary network is balanced.  This leads us to the following characterization of balanced graphs, which picks out exactly those graphs which were considered balanced according to the previous definitions (cf. p. 123-127 for proofs):

A signed graph is balanced if and only if it contains no cycle with an odd number of negative edges.

Cycles with an odd number of negative edges make a graph unbalanced for the following intuitive reason.  Recall that a balanced graph divides into two mutually opposed groups of friends X and Y. Now consider a case in which you pick a node a in a cycle and place it in the set X.  We can then start “walking” along the cycle starting with a, putting nodes on the cycle in their appropriate sets, given the polarity of the edges.  What’s crucial is that every time we crossed a negative edge, we have to change the set into which we are putting the nodes.  Thus, if there is an odd number of negative edges in the cycle, when we get back to a, it will have to be placed in Y instead of X—so it is not possible to divide a graph with such a cycle into two mutually opposed groups of friends.  Interestingly enough, any structurally unbalanced graph will contain a cycle with an odd number of negative edges: again, for proof of this, see p. 123-127 of the text.

Analyzing the “terrifying chart”

The Big Pharaoh’s graph has to be modified in two of ways before we can begin our analysis.  Firstly, note that the original graph is directed, whereas Structural Balance is a property of undirected graphs.  This will not prove to be problem, since we can expect that:

• If a party a is supported by a party b, then a probably has a positive relationship with b.
• If a party a is hated by a party b, then a is very likely to have a negative relationship with b.

Consequently, we will drop the directions of the edges; we will also (as mentioned earlier) eliminate the “has no clue” edges.  Otherwise, we leave the graph as it is.

Given that the graph contains 15 nodes and 40 edges, it helps to use the the following Python program to get the data we need.  The program first establishes whether the graph is balanced according to the new definition.  It counts the total number of cycles in the graph and the number of these cycles which are “bad” or “unbalanced” (i.e., cycles with an odd number of negative edges.)  Upon request, it also presents specific counterexamples to Structural Balance in the graph if these exist.  Finally, the program calculates what we call the volatility scores of each of the nodes and finds the most “volatile” node.  (A node’s score increases as the number of unbalanced cycles in which it appears outweighs the number of balanced cycles, indicating that a large number of its relationships may be unstable.)

Running the program gives something like the following:

We see here that more than half of the 83,586 cycles in the graph are unbalanced.  On this run, the program produced one counterexample to Structural Balance: a cycle containing 7 negative edges.  And while a number of parties had scores in the 4K range (including Assad, Sisi, and Syria Rebels), the party with the highest volatility score was USA with a score of 4607.

Our graph is teeming with counterexamples to the new definition of Structural Balance.  This strongly suggests that many of the relationships captured by the graph are under a significant amount of stress; and this, in turn, could explain why parties constantly readjust their positions with respect to one another, thereby prolonging the conflict.  Furthermore, given that the US has the highest volatility score, we have some grounds for thinking its relationships may be some of the least stable in the network.