Winter Has Come. The Endgame of Thrones.
A Science Man’s Perspective
With the final season of Game of Thrones already underway, a man may be faced with much uncertainty or many questions. If only a man had the foresight of the three-eyed raven, he would be able to resolve them. Although a man does not have that kind of ability, what he does have are the tools of science.
The Three-Eyed Raven warns you, “Spoilers ahead!”.
…for those who haven’t watched seasons 1 to 7 yet.
A natural question that one might start to wonder about the final season is “who are the most important characters?” or “who might die next?”. One is free to make a guess but amidst all of the chaos that have transpired over the past seven seasons, it has become ever so difficult to become certain about anyone — or anything. After all, no one can escape the wrath of George R. R. Martin.
But maybe it isn’t actually that hard to answer such questions. Maybe we just need to see things in a different way, much like how the three-eyed raven sees certain things, so we could uncover some kind of hidden pattern within all the chaos. To attempt those questions, we borrow tools from math and science, specifically from network science and machine learning.
A Network of Interactions
Network science, or the “science of networks”, provides a framework to help us understand real-life systems that surround us, or simply the interconnected world that we all now live in. They may come in the form of social networks (such as Facebook & Twitter), technological networks (the WWW), biological networks (the human brain & protein interactome) and physical networks (power grids & computer networks). Network science offers us a common set of tools and techniques to better understand the structure of any network and the kind of dynamics that they may lead to.
In the Game of Thrones series, one can actually build a network that arises from the interactions between all the characters. They all interact together in one form or another, such as through dialog exchanges and appearing in scenes together. Here, we analyzed all the character interactions extracted from all the episode scripts.
In our network, a node represents an actor and an edge between two nodes represents some form of interaction between them.
We compiled all the interactions from Seasons 1 to 7 and ended up with a network of 387 nodes and 3,341 edges (visualized below). The size of the names and circles scale with the number of interactions they had. The colors represent the communities detected using a community detection algorithm called Louvain. They are based on the number and strength of interactions (edges) between all pairs of characters. We can see that over the past seven seasons, five large communities emerged which are led by Tyrion Lannister (red), Daenerys (yellow), Jon Snow (brown), Arya Stark (blue), and Theon Greyjoy (green).
Who are the protagonists?
In the complex world of GoT, one of the big questions from earlier is “who are the most important characters?”. With network science, we can easily answer this using centrality measures. They are used to determine a node’s influence, importance or how central it is to the network. For our analysis, we focused on five common measures. Each one may reveal a different answer to the same ‘protagonist’ question.
- Degree Centrality
- Closeness Centrality
- Betweenness Centrality
- Eigenvector Centrality
- PageRank Centrality
We computed all five measures for every node in the network and zoomed in on the top 10 characters sorted in descending order of their scores. Normally, you would interpret the ranking values as “the higher, the better”.
Who has the most interactions?
To answer this question, we can look at the simplest measures Degree Centrality and Weighted Degree Centrality. It counts the number of unique connections that a node has with other nodes. So if a node has many connections, then that node is considered to be very influential or important. And for all the seven seasons, it is the people’s favorite, Tyrion Lannister, that had the most connections to other characters in the network. The character in second place is Cersei Lannister, followed by Jon Snow in third place. However, this changes when we consider the strength or weight of their connections. Tyrion still is on top which means he interacts a lot with a lot of the other characters, showing his large influence. One notable change would be Daenerys’ rise which is testament to the depth of relationship she has with the limited number of characters she interacts with.
How close is everyone else to each other?
Closeness Centrality indicates how close a node is to the rest of the nodes in the network and also reflects how central its positioning is in the network. A high score means a node has short average distance to the rest of the nodes in the network, which makes that node easily reachable by the other nodes. Nodes with low values when visualized would be those that are at the periphery of the network. If we ignore the anomaly of the small sub-network formed by Black Jack, Mully and Kegs (minor characters), the character that is the most reachable is Tyrion Lannister. Second place goes to Jon Snow, followed by Cersei Lannister in third place.
Who does information pass through the most?
Given all the shortest paths between all the nodes, the Betweenness Centrality counts how many shortest paths are passing through a node. The more times a node is selected as part of a shortest path, the more important it becomes. With this measure, we can then tell how well a node is strategically positioned in the network. The node on the top of this ranking is Tyrion Lannister again, imposing his control over the flow of information. Second place goes to Jon Snow, then third place for Cersei Lannister.
Who interacts most with the main characters?
Eigenvector Centrality is similar to Degree Centrality but takes into account the weights of the connections a node has to other nodes that are also important. In other words, if a node has more connections to other important nodes, the more that node also becomes important. Surprisingly, Cersei Lannister made it to the top, although she is followed very closely by Tyrion Lannister and Sansa Stark. Cersei’s sudden rise simply means she made more important connections over all the seasons.
PageRank Centrality also counts connections to important nodes, but a node only gets a portion of the its neighbor’s importance. The rest of the importance is shared to the other nodes connected to that important neighbor. For a node to get a bigger chunk of the pie, it would have to interact more with that neighbor. So, in first place for this centrality is Tyrion Lannister again, followed by Daenerys Targaryen, then Jon Snow. This means that they are the three characters that took more advantage of their connections than the rest of the network.
Additional Notes
It would also be interesting to look at the some characters that do not appear in any of the top 10 such as the Night King and Brandon Stark but may perhaps play a key role in the new season.
You might think that the Night King would place somewhere at the bottom for all 5 measures due to his limited appearances, but he actually sits somewhere between 50th-100th (out of 387 characters). He would probably place much higher later on in the final season as he would potentially interact with more characters such as Jon Snow and Daenerys.
Brandon Stark, despite being closer to the living human characters than the white walkers, places way much lower in all of the rankings (around 120th-251st). That’s even way lower than the Night King. This is understandable since Brandon does not need to interact with a lot of people, but he still remains important by playing the role of a spectator as the current Three-Eyed Raven.
Overall, the most important character of seasons 1 to 7 is Tyrion Lannister, topping almost every centrality measure. This is expected as he has made a lot of interactions with many characters, some that are also key ones. Despite his supporting character image, his wit has definitely helped him overcome challenges and stay alive. Next to Tyrion are Jon Snow, Cersei Lannister, and Daenerys Targaryen. They have emerged as big characters, fighting for their right to the Iron Throne. Centrality analysis, however, do not always capture other important characters such as the Night King and Brandon Stark who may likely play pivotal roles in the final season.
The Machine Learning Bit
Predicting who lives and who dies…
Trying to predict who might claim the Iron Throne in the end is non-trivial and complex. We’ll need more than a network for that. However, that’s not where the plot is headed as of now. Instead of that, we attempt to answer the last question of “who might die next?” with the help of machine learning.
Looking at the network and its measures, there seem to be no clear predictive features that tell us who might live or, more importantly, who might die. But perhaps a machine learning algorithm would be able to make sense out of them.
Recently in the AI research community, Graph Neural Networks (or neural networks for graph data), have been gaining popularity. Just like how we can use deep neural networks (or deep learning) to learn better representations for words and images, the same can also be done for graphs or networks.
Traditionally, models could only learn from graphs by transforming them into a matrix of features per node (like your familiar CSV or table format), but you end up losing the information of the graph’s network structure in the process. But with the new approach, you can now feed in a raw graph to the algorithms and they would leverage the information from its network structure. Moreover, you can also include features for the nodes (like the centrality measures) and edges to make your dataset much richer.
Alright, back to the GoT network!
So, to predict who might live or die next in GoT, we used the same interaction network from earlier along with the nodes’ computed features such as centrality measures and additional network properties (e.g. eccentricity, clustering coefficient, number of triangles) that I will not further discuss for brevity. Also, as in any supervised learning task, the algorithm needs the ground truth label for each node to guide its training. In this case, we indicate whether or not the character died in the previous seasons.
Like network centrality measures, there are also many existing learning algorithms for graph neural networks, but for now we just picked one to experiment on (due to time constraints). We selected one of the top performing node classification algorithms called Graph Attention Networks (GATs).
Specifically, we trained a 2-layer GAT model and eventually arrived at a test accuracy of around ~60%. We hoped that the algorithm would perform somehow better as they can leverage the topology or structure of the network, along with the features of its nodes. However, that did not seem to be the case probably because the network data we had was considerably small. However, we’re not so keen to achieve state-of-the-art performance on the GoT network. For this fun side project, we just wanted a model to predict what may happen to all of the characters who are still alive in the network, i.e. whether they may or may not survive in the new season.
So here are our model’s death predictions that we simply sorted by the total number of connections each character has.
A few of the interesting predictions we see are Bronn, Eddison, and also the Night King. So the good news is that the Night King could die, but the bad news is some people’s favorites, Bronn and Eddison, might also go down during the final season. So, let us how well these predictions will hold out until the end. Maybe the writers have different things planned for the fans. Or perhaps, George Martin would just say, “Valar Morghulis”.
If you thought this was interesting, stay tuned for more!
You could also check out this cool and comprehensive resource by Network of Thrones. You’ll find all the network analyses that were made for each individual season and all of the previous seasons combined. They inspired me to come up with my own analyses and predictions. The dataset we used actually came from them as well. So, kudos to their team!
