The Network of Thrones

Is Jon Snow really dead? Will Tyrion Lannister continue his uneasy alliance with Daenerys Targaryen and survive his sister Cersei’s wrath? Will Sansa Stark escape from the sadistic Ramsay Bolton and take her place as Queen of the North?

These questions, on the surface, have nothing to do with mathematics. However, according to a recent study applying the theory of networks to the Game of Thrones, Jon, Tyrion, and Sansa are the provably central characters in the saga.

For those of you living in a cave, Game of Thrones (GOT, for short) is one of the most popular shows on television, based on the hugely popular novels by George R.R. Martin. GOT is a fantasy yarn set in the lands of Westeros and Essos. The story contains the usual array of dueling kings and queens, dragons, and magic. Unlike Lord of the Rings, however, the story is thoroughly adult with sex and violence in spades. Main characters die. A lot. There is large ensemble cast emanating from the main royal families contesting the Iron Throne.

The lead author of the short paper Network of Thrones is a co-author of mine, Andrew Beveridge of Macalester College. Andrew is a graph theorist, with a background in both theoretical and applied mathematics.

In today’s blog, I am going to give a tour of the paper, its implications, and some discussion about why the work matters. The full citation of the paper is:

A. Beveridge,  J. Shan, Network of Thrones, Math Horizons Magazine, 23  (2016) 18-22.

See also the Network of Throne website containing data sets, articles about their study, and more. There is also Twitter hashtag: #NetworkOfThrones

GOT data

We can view the characters in GOT as nodes in a network, with edges between them if they share social ties. This is an example of a social network, albeit a fictional one.  Social networks have been studied for decades, with a renewed interest in them lately owing to the dominance of on-line social networks like Facebook and Twitter.

What is the GOT social network data set? It consists of 107 characters from the third book of the series A Storm of Swords (chosen since the characters and their relationships had matured by then). The authors used algorithms to mine the electronic version of the book, looking for connections between the characters. If their names appeared within 15 words of each other, then they placed an edge between them. This is the common data mining technique using word frequency: the more often the co-appearance of two names, the weightier the edge linking them.

Here is the network they discovered (a figure from the paper):

This a relatively small example of social network. Network scientists (like myself) often study very big networks like Facebook and Twitter, hoping to mine their global and local properties. Such networks have hundreds of millions of nodes. I’ve written earlier blogs which talk about such real-world, complex networks. In 2008, I wrote a book about one the earliest studied complex networks: the web graph.

Notice that the network above is broken into communities, focused on key actors such as Robb, John, Tyrion, etc. The authors used various algorithms to detect these communities and enumerate them. They use the concept of modularity, which compares the network to a random one, where you would expect no community structure. The modularity gives a graph partition, which results in the colored clumps you see above in the figure.

By the way, community detection is a major open problem in network science. We have good heuristics for the problem, but no universally accepted methodology or even definition for what comprises a community. Most of the approaches I know use techniques from spectral graph theory. Roughly, communities should be subgraphs where the more edges inside then going outside. The figure above recalls the famous Zachary Karate Club graph, which arose in one of the first papers on community detection.

Once communities were detected, Beveridge and Shan measured the importance of individuals in each GOT community by several methods. An obvious approach is to look at degrees; the degree of a node is the number of edges joined to it. If nodes are connected to many others, then they are likely important. But degree is not always the best measure of centrality.

You can be important by being connected to an important person. Suppose Barack Obama followed me on Twitter. That would be only one new follower (which would bump up my degree by one), but I would likely become quite popular on Twitter as Obama is such a powerful individual in the social network. Others would see that important connection, and also follow me.

A clever approach to bypass the issues with degree centrality is to use PageRank, which is an algorithm developed by Sergey Brin and Larry Page of Google fame. PageRank allows Google to rank webpages and speed up web search.

The underlying mathematics of PageRank has to do with random walks on networks, akin to how random surfers propagate through a network. Precisely, PageRank is an example of a discrete ergodic Markov Chain. Random surfers follow links, but occasionally teleport to random vertices. The PageRank of a node is the probability it is visited by a random surfer with teleportation. PageRank is now widely recognized as a way of detecting central nodes in a network, and even has applications in systems biology.

What the mathematics tells us

Beveridge and Shan uncovered some interesting findings. Using just their mathematical analysis, the main conclusions are that Tyrion, Jon, and Sansa are key actors in the social network. Tyrion comes as no surprise to fans of the show or books, nor Jon. But Sansa is an interesting emerging character. Her nickname is Little Bird, which emphasizes her role so far as a pawn in the schemes of others. I think we are going to see Sansa emerge as a powerful player in the coming seasons. At least, I hope she will, if they don’t kill her off, which the show likes to do often with its main characters!

Another interesting conclusion derived solely from the mathematics is that Daenerys Targerion is influential, but only locally. Any fan of GOT knows that, but it is fascinating to see how that arises objectively in the data analysis. She hasn’t interacted much with the other players in the Westeros network. This too is going to change, I think. One of my favorite scenes in the series is when she meets Tyrion. Her famous quote about breaking the wheel gave me chills!

Season 6 of Game of Thrones returns to HBO on April 24.

Fiction meets Big Data

The study of Beveridge and Shan is a nice reminder of the role mathematics has to play in popular culture.  Using well-known tools from networks, the authors reach surprising conclusions about a TV show and literary work. Call it the new field of the big data of fiction.

The cool thing is that you can replicate the study with any fictional social network from your favorite book or series. The more characters the better, so works like the Lord of the Rings would make good candidates for this kind of analysis. I found one such paper, published this April by some Brazilian physicists, studying characters from the Lord of the Rings, The Hobbit, and the Silmarillion.

From these and other studies, we are reminded once again of the importance of numeracy. We frequent sites Rotten Tomatoes and Box Office Mojo when checking the critical or financial success of movies. Network science and big data can show us much more than box office returns or simple averages of critic scores: they can reveal patterns and nuances in the story that we wouldn’t ordinarily notice. They also provide alternatives supporting (of course, not replacing) traditional literary analysis.

Mathematics through its use in big data is already used in many decision-making domains like finance and health care. Maybe the next application of mathematics is to entertainment in the form of the analysis of characters in literature, TV, and movies.

Wouldn’t that be something?

Anthony Bonato