A physicist loose among the liberal arts

Category: graphs

Some Networks are Simple

In which the Idiosopher gets to do Inklings stuff on the clock.

logo of the winter simulation conferenceLast summer, the blog started following Sørina Higgins’s suggestion about network analysis to see how interactions between the Inklings in real life turned into stylistic evolution in their literary styles. I haven’t mentioned it since, due to a lack of discoveries that are interesting (even to me).

This week was the 2017 Winter Simulation Conference, a world-wide hootenanny of computer-simulation experts. With all my responsibilities discharged, I got to spend the last half-day attending talks on anything that sounded interesting.  Here’s a good one from Wai Kin (Victor) Chan of Tsinghua University:

This paper studies social influence (i.e., adoption of belief) using agent-based simulation and regression models. Each agent is modeled by a linear regression model. Agents interact with neighbors by exchanging social beliefs. It is observed that if individual belief is linear in neighbors’ beliefs, system-level belief and aggregated neighbors’ beliefs can also be described by a linear regression model. Analysis is conducted on a simplified 2-node network to provide insight into the interactions and results of general models. Least squares estimates are developed. Explicit expressions are obtained to explain relationship between initial belief and current belief.

Social networks are complicated. People go in and out, they talk more or less, they form cliques, etc. If you want to measure things about them, you usually have to build a computer model with a clock and a bunch of “agents” in it. An agent is (in this case) a person with ideas (represented by a number), and as time advances, the agents pick up ideas from each other. Then you inspect the agents after a the simulation has been calculated and find out what ideas each agent has absorbed.

What Prof. Chan has discovered is that, as long as each person in a social network only picks up an idea from three others (which is comparable to the situation for the Inklings), all the complicated stuff drops out – the results of the full-powered simulation always look like a straight-line influence!  This paper is his attempt to prove that’s actually true.  If he’s right, then the spread of some ideas through a literary group will show a very simple pattern, and a literary scholar will be able to do lots of Digital Humanities research with just a spreadsheet. (Hi, Sparrow!)

An anecdote: another thing I did last summer was serve on a jury.  We had to decide on a prison sentence.  At the beginning, we went around the table and got everybody’s first impression. There was quite a bit of difference among us.  After four hours of discussion, which got pretty acrimonious at times, we agreed on a number that was within 5% of the average of everybody’s initial opinion.  That’s what a social-influence model would predict, if Prof. Chan is correct.

If the idea you’re studying can be cast as how strongly an opinion is held, on a scale from 0 to 1, then a linear regression is all you need to solve it.  That’s what I suggested Theosophy might look like, in the post from last July.  Division of territory, such as giving up Arthurian legends to one colleague, space travel to another, and focusing your own attention on time-travel, isn’t describable this way.

Prof. Chan started off his talk by saying the topic was just his own interest, not funded by any organization, and it wasn’t finished yet and he didn’t know what it meant, and the talk was still interesting.  My new scholarship goal is to be able to do that.

Irrelevant note: today is Idiosophy’s second bloggiversary.


What the One Ring Does

If you believe Peter Jackson, the Ring doesn’t do much of anything. It’s just a MacGuffin. With the Ring, someone who’s a hundred feet tall can knock down dozens of soldiers with one sweep of a thirty-foot mace, but I’m pretty sure I could do that without a Ring. (It’s all in the wrists.) The Ring blurs your vision and fills your ears with voices, which seems counterproductive when you’re trying to rule an evil empire. It enables you to see Ringwraiths, but who would want to?

The cost of Ringlessness

So what does the Ring actually do? We can try to figure that out by looking for things that only happened because Sauron didn’t have it. Here are a few:

The Nazgûl aren’t very effective, without their Lord

When the Black Riders split up they can scare people, but they can’t accomplish much useful. Granted, there is power working against them in the Shire, but it would have to be stronger than the military of Gondor to neutralize the Nazgûl to that extent, and I don’t think it is. Besides, the Riders seem kind of disorganized. The One Ring may be the only channel of control that works on all nine of their rings.

Saruman attacked Rohan too soon

Time to take another swipe at Peter Jackson. Saruman in his movie is a willing slave of Sauron, which makes his attack on Rohan ridiculous. If he’d held off a week,  until about March 8, the Rohirrim would have still been pinned down in Helm’s Deep as the gates of Minas Tirith were shattered. War over.

In the book, this makes perfect sense. Saruman thinks he’s an independent agent, pursuing his own ends. I can’t find any evidence that he knows Sauron’s timetable for the attack on Gondor. Sauron can’t give him a direct order without revealing his dominance, which would provoke some kind of resistance. Considering the distance and Saruman’s considerable power, resistance could have done quite a bit of damage to Sauron’s plans. All this is because Sauron doesn’t have his Ring. With the Ring, Saruman’s own ring would have bound him to Sauron’s will, with no need to keep up a pretense, and the synchronized attacks on Gondor and Rohan would have been devastating.

The fight among the orcs in the Tower of Cirith Ungol

Sam called it “lucky” that Shagrat’s and Gorbag’s forces wiped each other out, so we should keep an eye out for the hand of Providence. And everything worked out so neatly that it must have been there, but in this case it’s hardly needed. The natural centrifugal instincts of Orcs aren’t held in check by the Ring (even though it’s just a few feet away). A bit of “binding” would have kept the lines of command clear, and made sure that either Shagrat or Gorbag would have known to shut up and obey.

The chaotic orders Shagrat gets from Lugbúrz

Look at this mess:

“Any trespasser found by the guard is to be held at the tower. Prisoner is to be stripped. Full description of every article, garment, weapon, letter, ring, or trinket is to be sent to Lugbúrz at once, and to Lugbúrz only. And the prisoner is to be kept safe and intact, under pain of death for every member of the guard, until He sends or comes Himself.”

VI, i.

Shagrat’s reporting path upwards goes through the bureaucracy of Barad-dûr, but the path back down does not. This is a recipe for disaster: the middle-managers aren’t kept apprised of the actions at the top, so who knows what they’ll screw up, even if they’re following orders to the letter.

Let’s put these together into an Orc Chart. This graphic shows a disaster waiting to happen. Shagrat has three directions from which orders can arrive; that’s the obvious point of failure of this organization.  (JRRT’s military experience shows up again.) The Nazgûl don’t have any lines between their boxes. If I were Lord of the Nazgûl, I’d have designated two deputies, with three wraiths reporting to each one. Put one team at each Bree-gate, and LotR ends in Chapter 11. The green boxes are characters called “lieutenant”. Not very similar roles. The Ring can be thought of as a set of command and control channels among the characters that clear up that disorderly network.

organization chart of forces of Mordor

Organization of Morgul & Cirith Ungol Divisions

Looking for the Ring in our world

From the 1950s through the 1970s, people who were looking for real-world analogues of the Ring usually thought of the atomic bomb. I was never comfortable with that because of one salient feature of the Ring: when it’s destroyed, Sauron will fall. This was a very puzzling thing to a teen-aged first-time reader. What kind of tool or weapon reduces its user to nothingness when it’s taken away? Stephen Winter wrote an essay recently about Sauron’s project, which gets at that important point.

Stephen reminds us that Sauron can not create. He calls Sauron a “false maker” (which seems to be a deliberate counterpoint to the word “sub-creator”). Previously in the history of Middle-Earth, Sauron had worked via the psychology of individuals. He was effective at sowing discord, but it didn’t help him build an empire of evil because it generally led to the destruction of the place he was working in. He needed something more tangible for his attempt to conquer and hold the world. But what tangible thing is available to a false maker? Sauron found the loophole: organizing is not creating. Matter can be rearranged almost indefinitely without overstepping any bounds. In particular, people and things can be arranged into a hierarchy.

A hierarchy is a tremendous tool for multiplying the force of a leader. In the mid-twentieth century, it reached a peak of implementation in Nazi Germany, Stalin’s Soviet Union, and Mao’s China. In fact, the word “totalitarian” could be defined as a state that allows no interactions among its citizens outside the hierarchy. There’s a pattern here. I am reminded of the comment by a (probably apocryphal) German officer in World War 2: “The reason the Americans do so well in war is that war is chaos, and Americans practice chaos every day.” The forces of the West in Middle Earth are the same way. If there’s any clear path of authority across the races, it’s hard to see. This came up in the comments at Middle-Earth Reflections, a while back. Leadership among Elves and post-Numenoreans is a matter of personal relationships between a commander and the troops. (Éowyn: “They go only because they would not be parted from thee — because they love thee.” V, ii) It’s not a hierarchy, or any kind of structure you can draw on a PowerPoint chart.

To make a hierarchy work, though, the boss has to pay a price. He has to delegate both authority or responsibility. Or, in Ring-terms, “let a great part of his former power pass into it.” (I, ii). The hierarchy can be turned against the boss, or if it’s destroyed the boss finds himself sitting at a desk, with a dead telephone, commanding nothing. Powerless.


Organization was missing in the First Age, so it’s what Sauron added when he set up on his own. Hierarchy is the key, a thing Morgoth never had. Théoden King of Rohan had more levels of structure in a 6,000-man (ok, 5998-man) detachment than you can find mentioned in the entire Silmarillion. For us in the Information Age, the closest thing to the Ring is not a weapon, it’s a hierarchical org chart.

Won’t you be my neighbor?

I’m playing with graphs again. Here’s a picture of my net-neighborhood out to two steps, i.e., the sites on my blogroll and the sites on their blogrolls.

graph of blog links

Web Neighborhood

The funniest thing about this graph is that, despite the fact that it was designed to be my neighborhood, Idiosophy isn’t in the center.  Olga’s Middle Earth Reflections is. (Fair enough; her blog has more than a thousand followers.) Science teaches humility, along with everything else.

Nobody else is interested in economics, so Grasping Reality is ‘way over in the corner. The rest of the network is easier to read if I cut that one link.

Zooming in on the non-economic network

J.R.R. Tolkien brings together some diverse parts of the world. There are priests and theologians along the south, language-inventors up in the northwest corner, medievalists in the northeast, and a little knot of modernists on the east side.  Nobody who knows Tolkien’s curriculum vitae would be surprised to see that list (except perhaps for the economists and the physicist), but if there’s anything else in life that connects these communities, it doesn’t come immediately to mind.

Technical note

Drawing these graphs took ten minutes.  The tools you can download freely from the Web are amazing.  This was made by the “igraph” package in R.  To make these plots, I used an algorithm that simulates a simplified physical system to place the nodes. It puts an electric charge on the nodes, so they want to be separated and legible. Then it pretends the links are rubber bands, so inter-linked nodes are pulled tighter together.  I learned how to do this from an excellent tutorial by Katherine Ognyanova. (Who must be one of us; she posted the etymology of her name on her blog. I wonder if she’s related to the Vedic fire-god Agni.)

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