Winter Has Come. The Endgame of Thrones.
A Three-Eyed Raven’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 tell. 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 is “who are the most important characters?”, “who might die next?”, or “who will win the game and claim the Iron Throne?”. 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 have to see things in a different way, much like how the three-eyed raven sees certain things, so with that new perspective we may find some kind of order hidden within all the chaos. To help shed more light into this, we borrow tools from math and science, specifically 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 (computer networks). Network science provides 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 a network, a node represents an entity/actor and an edge between two nodes represents some form of interaction or relationship between them.
In the series Game of Thrones, 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 scene co-appearances. Here, we only analyzed the interactions from all the episodes that were extracted from their scripts.
We compiled all the interactions from Seasons 1 to 7 and ended up with a network of 387 nodes and 3,341 edges. After mapping them all out, the network below was produced. The size of the names and circles represent the number of interactions they had. The colors represent the communities detected after looking at the strength and number of interactions between sets of characters. We can see that over the past seven seasons, five large communities emerged which are led by Tyrion (red), Deanerys (yellow), Jon (brown), Arya (blue), and Theon (green).
Who are the Protagonists?
In the complex world of Game of Thrones, one of the big question is “Who are the most important characters?”. With network science, we can use centrality measures to determine a node’s influence, importance or how central it is in the network. For this analysis, we focused on only five of the common ones for now:
- 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. Note that each centrality measure compute for the importance of a node but in different ways. You normally interpret the resulting values as “the higher, the better”.
Who has the most interactions?
Degree Centrality is the simplest among the five measures. It is counts the number of unique connections that a node has with other nodes. So if a node has relatively 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 it is positioned 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. 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 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, back in first place for this centrality is Tyrion Lannister again, followed by Daenerys Targaryen, then Jon Snow. They are the three characters that took more advantage of their connections than the rest of the network.
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, 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 more with Jon Snow, Daenerys and her dragons in battle.
Brandon Stark, despite being closer to the humans, 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–7 is Tyrion Lannister, topping almost every centrality measure. He’s been through a lot. 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. However, the centrality analysis do not always capture other important characters such as the Night King and Brandon Stark who could actually play very important 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 but complex. We’ll need more than a network for that. However, that’s not where the plot is headed right now. Instead of that, let’s attempt to answer the other question of “Who might die this season?”.
Looking at all the measures from the last section, there seem to be no clear predictive features that tell us who might live or die. But perhaps a machine learning algorithm would be able to make sense out of them.
Recently in the AI research community, a new class of ML algorithms for networks, called Graph Neural Networks (i.e. Neural Networks for Graphs/Networks. Yup, ikr.), have been introduced. Just like how we can use deep neural networks (deep learning) to learn better representations for words and images, the same can now be done for networks.
Traditionally, you could only learn from graphs by transforming them into a list of features per node (like in CSV format), but you end up losing the information of the graph’s structure in the process. But with the recent approach, you can feed in the graph to the algorithms and they would be able to leverage its structure information. Moreover, you can also make the training data much richer by including features for the nodes and edges.
Alright, back to the GoT network!
To predict who might live or die in GoT, we used the same interaction network earlier along with the nodes’ computed features such as centrality measures and other network measures (e.g. eccentricity, clustering coefficient, number of triangles) that I will not further discuss for brevity. Additionally, in any supervised learning task, the algorithm needs the ground truth label for each node (whether the character lived or died) to guide its training.
Like centrality measures, there are also many existing graph ML algorithms, but for now we just picked one (due to time constraints). We selected one of the top performing node classification algorithms called Graph Attention Networks (GATs).
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 we only had a network that is considerably small. The data was not enough to train the network in the first place.
However, we’re not so keen to achieve state-of-the-art performance on the GoT network anyway. For this project, we just want 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 — and we don’t know that yet.
Looking at the results, here are the characters that the model predicts will die, starting with Bronn who had the most interactions and down to Denys Mallister with the least interactions.
A few of the interesting predictions we see are Bronn, Eddison, and also the Night King. So the good news is the Night King could die, but the bad news is Bronn and Eddison might also go down during the season. Now that the season has started, let us see if these predictions will hold out.
Or maybe the Season 8 writers have different things planned for the characters. As a man would say, Valar Morghulis.
If you thought this was interesting, stay tuned for more!
But for now, you could check out this cool and comprehensive resource by Network of Thrones. You’ll find all the network analyses that were made per season and all seasons. They were one of my inspirations for coming up with my own analysis and predictions. The dataset that we actually used for this project also came from them. So, kudos to their team!