Of all the types of graphs, signed graphs are probably the most interesting for looking at interactions among groups of people. Definition: a signed graph is a collection of nodes and links between them, just like a regular graph, but each link is flagged with a positive or negative sign. When we’re using the graph to describe a social network, those might be “loves” and “hates”, “admires” and “sneers at”, or any other dichotomy that comes to mind.
Some graphs have closed paths in them. Mathematicians call a closed path a “cycle”. If you go around a cycle and encounter an even number of negative signs, it’s a balanced cycle. A graph that contains only balanced cycles is a balanced graph. These are the simplest cycles:
Here’s where things get interesting: signed graphs apparently figure into human sociology. If a network of relationships forms a balanced graph, it’s a stable structure. Relationships that fall into unbalanced graphs aren’t stable, and lead to drama. (That last word can be taken either literally, or in the euphemistic sense that people give it these days.) I don’t think anybody knows why such a simple mathematical condition seems to be true; that’s just the kind of thing mathematics does every now and then. Some brilliant psychologist will figure it out someday.
In the unbalanced graph “a”, I colored the vertices pink and blue because my wife watches soap operas, and nearly as I can tell, there’s a cycle like that at the heart of every one of them. It never ends well, because it’s unbalanced. The balanced graph “b”, by contrast, is “you and me against the world”, which is a stable configuration. The all-negative graph “c” can go one of two ways. If the vertices represent people, two of them just go away and the network disintegrates. If the vertices represent countries, or something else that’s forced into interaction because it can’t quit the game, the network changes when two of the nodes look for an advantage by conspiring against the third. The fourth possibility, “d”, is that all the links are positive. It is balanced and kind of boring in its dramatic implications.
There’s a perfect example of three-party instability in Book IV of LotR among Frodo, Sam, and Gollum. From the time they meet up, it’s graph “a”: Sam loves Frodo, Sméagol loves Frodo, Sam doesn’t like Sméagol. Type “a” is unstable, so something’s got to give. The crisis comes in Chapter 8, when Sméagol (possibly) tries to turn the graph into a stable all-positive triangle, but Sam intrudes, the opportunity is lost, and Gollum plots with Shelob to turn the graph into type “b”.
Of course, three-person networks are easy to understand without graph theory. The real advantage of mathematics is that it becomes possible to handle any size network. There’s a theorem about graph balance that applies in general: Any balanced graph can be re-drawn in a simple form. (Can I say “isomorphic”? Sure I can. Y’all are tough enough.) All balanced graphs are isomorphic to a graph that’s split into two parts, where there are only positive links within each part, and all the links between the parts are negative. That’s called the Cartwright-Harary Theorem. Prof. Harary says that the theorem is unexpected and counter-intuitive, which I am half in agreement. The positive interpretation is easy to accept: if the world consists of two parties, and every member of a party agrees with each other, and every member of each party disagrees with all members of the other party, the situation is stable. (Then Romeo meets Juliet, and the stability is history.) The counter-intuitive part is that this is the only way for a graph to be stable. That’s it – the one way you can build a stable social system is for everybody on your side to agree and to hate the other side, and contrariwise on the other side. In practice, I suppose you could allow disagreement on issues that were irrelevant to the structure, and thereby outside the graph model. But on any important issue, perfect party unity and perfect hatred of the other side is your only chance.
Interesting stories, whether they’re fictional or meta-fictional, don’t have balanced graphs. One of the most intriguing things I scribbled down during Sørina’s lecture was that we might be able to define a new subset of graphs under the rubric of “interestingly-unbalanced”.
Illiterate Coda
Maintaining stable structures without fomenting partisan warfare is critically important in a society as complex as ours. But math is math. So how do we handle the dilemma of the Cartwright-Harary Theorem? We go around the horns. Almost every organization chart you’ll ever see has the same basic structure: No cycles, so the theorem doesn’t apply. That type of graph is called a tree. It’s useful in all sorts of contexts, but until now it had never occurred to me that it means that management never has to choose between polarization and instability.
Leave a Reply