A physicist loose among the liberal arts

Category: graphs

Signed Graphs and Interesting Stories

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:
three-node signed graphsHere’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.

Graphing the Inklings

Sørina Higgins’s lecture at Mythmoot IV gave us a hint about where she’s going intellectually in the near future. She wants to apply network theory to create “meta-fictional narratives” about the interactions among the Inklings and how it affected their writing, and invited us to do the same.

The coolest figure from “Graph Theory as a Mathematical Model in Social Science”

This seemed like a good time to blow the dust off my command of graph theory. You can figure out lots of cool things from networks, if you know about graphs.   Frank Harary, writing from a period contemporary with The Lord of the Rings until well into this century, pushed the use of mathematical graph theory into the social sciences.  Here’s a short version.  Here’s what I think is his clearest explication of what can be done with graphs in the social sciences (which is what we are doing, now).

For instance, graphs are used a lot in management theory.  The fastest performing network structures were those in which the distance of all nodes from some central person (the “integrator”) was the shortest, say Borgatti, Stephen P., et al. “Network analysis in the social sciences.” science323.5916 (2009): 892-895. Now, if you’re looking for a paradigm of a stable, efficiently operating organization, the Inklings are not an obvious place to start.  I’m pretty sure that C.S. Lewis would turn out to be the integrator, but then what?  Here’s a chart from Borgatti et al. that might clarify the relevance:

Following Sørina’s Ansatz, we might begin with the box on the left to determine our set of writers (nodes). Next, we’d assign a numerical quantity to each node, probably derived from a lexomic analysis.  Then, we’d build links from the two boxes on the right, Interactions and Flows, based on accounts of how the writers interacted, to see how some attribute of the nodes changes over time.

The easiest thing to see would be something like the spread of Theosophy or Anthroposophy. Weird philosophies come with an idiosyncratic jargon that should be trivial to find in the writers’ texts. The mathematical tools we’d need to identify the influence of some *osophy have already been developed to model the spread of infectious disease.

Slightly more difficult would be to track down an agreement between the writers to split things up.  There was the famous wager between Tolkien and C.S. Lewis about writing a time-travel and a space-travel story, respectively.  We’d look for some lexemes they shared equally, which then split up mitotically into space on Lewis’s side and time on Tolkien’s. But a difficulty presents itself. It might be possible to find lexemes in Tolkien that correlate well with space travel, but I can’t think of them.  We’d have to find them via statistical correlations, which tend to make the final result less credible.  A better choice might be King Arthur.  In an old lecture on Youtube, Sørina mentions that Tolkien may have given up work on Arthurian legends because Charles Williams was doing so much in that area. It should be easy to find convincing Arthurian terms whose frequency evolves over time.

Caveat:  Sørina drops a hint that she’s dealing with a large network, which the Inklings are not.  We’ll have to wait and see.


Powered by WordPress & Theme by Anders Norén