Transcription
Andrew Beveridge and Jie ShanThe international hit HBOseries Game of Thrones,adapted from George R. R.Martin’s epic fantasy novelseries A Song of Ice andFire, features interweaving plotlinesand scores of characters. With somany people to keep track of in thissprawling saga, it can be a challengeto fully understand the dynamicsbetween them.To demystify this saga, we turn tonetwork science, a new and evolvingbranch of applied graph theorythat brings together traditions frommany disciplines, including sociology,economics, physics, computer science,and mathematics. It has been appliedbroadly across the sciences, the social sciences, thehumanities, and in industrial settings.In this article we perform a network analysis ofGame of Thrones to make sense of the intricatecharacter relationships and their bearing on the futureplot (but we promise: no spoilers!).First, a quick introduction toGame of Thrones: Westeros andEssos, separated by the NarrowSea, are homes of several noblehouses (figure 1). The narrativestarts at a time of peace, with allthe houses unified under the rule ofKing Robert Baratheon, who holdsthe Iron Throne. Early on, KingRobert dies in a hunting accident,and the young, cruel Prince Joffreyascends the throne, backed by hismother’s house, Lannister. However,the prince’s legitimacy, and even hisidentity, are seriously questionedacross the kingdom. As a result, warbreaks out, with multiple claimantsHelen Sloan/HBOto the Iron Throne.Driven by cause or circumstance, characters fromthe many noble families launch into arduous andintertwined journeys. Among these houses are thehonorable Stark family (Eddard, Catelyn, Robb,Sansa, Arya, Bran, and Jon Snow), the pompousLannisters (Tywin, Jaime, Cersei, Tyrion, and Joffrey),the slighted Baratheons (led by Robert’s brotherStannis) and the exiled Daenerys, the last of the oncepowerful House Targaryen.The Social NetworkFigure 1. The Game of Thrones world: Westeros,the Narrow Sea, and Essos (from left to right). Sigilsrepresent the locations of the noble houses at thebeginning of the saga.18 April 2016 : : Math Horizons : : www.maa.org/mathhorizonsOur first task is to turn the Game of Thrones worldinto a social network. Our network, shown in figure 2,has sets of vertices V and edges E. The 107 verticesrepresent the characters, including ladies and lords,guards and mercenaries, councilmen and consorts,villagers and savages. The vertices are joined by353 integer-weighted edges, in which higher weightscorrespond to stronger relationships between thosecharacters.We generated the edges using A Storm of Swords,the third book in the series. We opted for this volumebecause the main narrative has matured, with thecharacters scattered geographically and enmeshed in
ltonLysaRobert orahBarristanRobertDaenerysCerseiTywinKraznys ysPycelleDoranMerynMyrcella Podrick BronnOberynCommunity DetectionThe network layout and colors in figure 2 clearlyidentify seven communities: the Lannisters and King’sLanding, Robb’s army, Bran and friends, Arya andMaceAmoryIlynEllariatheir own social circles. We parsed the ebook, incrementing the edge weight between two characters whentheir names (or nicknames) appeared within 15 wordsof one another. Afterward, we performed some manualvalidation and cleaning. Note that an edge betweentwo characters doesn’t necessarily mean that they arefriends—it simply means that they interact, speak ofone another, or are mentioned together.The complex structure of our network reflects theinterweaving plotlines of the story. Notably, we observe two characteristics found in many real-worldnetworks. First, the network contains multiple densersubnetworks, held together by a sparser global web ofedges. Second, it is organized around a subset of highlyinfluential people, both locally and globally. We nowdescribe how to quantify these observations using theanalytical tools of network sJoffreyMargaeryIllyrioSandorJon JonRickonJeyneLotharManceFigure 2. The social networkgenerated from A Storm ofChatayaSwords. The color of a vertexindicates its community. Thesize of a vertex corresponds toits PageRank value, and the sizeof its label corresponds to itsEHWZHHQQHVV FHQWUDOLW\ Q HGJH·V thickness represents its weight.companions, Jon Snow and the far North, Stannis’sforces, and Daerenys and the exotic people of Essos.Remarkably, these communities were identified fromonly the network structure, as we explain below.We want to divide the network into coherent communities, meaning that there are many edges within communities and few edges between communities. We detectour network communities by using a global metric calleddenote the weight of the edgemodularity. Letbetween vertices i and j, wherewhen there isno edge. Letdenote the weighted degreeof vertex i. Intuitively, the modularity Q compares ourgiven network to a network with the same weighteddegrees, but in which all edges are rewired at random.This random network should be community-free, so itmakes a good baseline for comparison.Suppose that vertices i and j belong to the same community C. We would expect that wij is at least as largeas the number of edges between them in our randomlyrewired network. A touch of combinatorial probabilityshows that the expected number of such random edgeswhere m is the total number of edges iniswww.maa.org/mathhorizons : : Math Horizons : : April 2016 19
24036Degree0214550Weighted BranCatelyn1,275BetweennessFigure 3. Centrality measures for the network. Larger values correspond to greater importance, except for closenesscentrality, where smaller values are better. Numbers in the bars give the rankings of these characters.the network. Summing over all vertices in a communityC, we haveMeanwhile, if C is not actually a community, thenthis quantity may be negative. The modularity Q of avertex partition C1, ,Cl of the network iswhere we have normalized this quantity so thatOur goal is to partition the vertices into communitiesso as to maximize Q. Finding this partition is computationally difficult, so we use a fast approximationalgorithm called the Louvain method.Crucially, the algorithm determines the numberof communities; it is not an input. In our case, wediscover the seven communities in figure 2. The King’sLanding community accounts for 37 percent of thenetwork. When we perform community detection onthis major subnetwork, we obtain four communities.A high resolution version of figure 2 and the networkof subcommunities of King’s Landing can be found atmaa.org/math-horizons-supplements.20 April 2016 : : Math Horizons : : www.maa.org/mathhorizonsCentrality MeasuresNetwork science can also identify important vertices. Aperson can play a central role in multiple ways. For example, she could be well connected, be centrally located,or be uniquely positioned to help disperse information orinfluence others. Figure 3 displays the importance of 14prominent characters, according to six centrality measures, which we explain below.Degree centrality is the number of edges incident withthe given vertex. Weighted degree centrality is definedsimilarly by summing the weights of the incident edges.In our network, degree centrality measures the numberof connections to other characters, while weighted degreecentrality measures the number of interactions.Eigenvector centrality is weighted degree centralitywith a feedback loop: A vertex gets a boost for beingconnected to important vertices. The importance xi ofvertex i is the weighted sum of the importance of itsneighboring vertices:for eachSolving the resulting linear system gives the eigenvector centrality. (This name comes from linear algebra:We actually find an eigenvector for eigenvalueofthe matrix W with entries wij.)Let’s compare the weighted degree and eigenvector centralities for our network. The late King Robertreceives a huge boost: He has only 18 connections,
but half of them are to other prominent players! Mostleading characters also benefit from the feedback loop,being directly involved in the political intrigue andsweeping military turmoil that grips the realm. Theexceptions are isolated from the main action: Bran(presumed dead and on the run), Jon Snow (marginalized in the far North), and Daenerys (exiled across theNarrow Sea).PageRank is another variation on this theme. Thismeasure was the founding idea behind Brin and Page’sGoogle search engine. Each vertex has an inherentimportancealong with an importance acquiredfrom its neighbors. Unlike eigenvector centrality, avertex does not get full credit for the total importanceof its neighbors. Instead, that neighbor’s importance isdivided equally among its direct connections. In otherwords, a vertex of very high degree passes along only asmall fraction of its importance to each neighbor.The PageRank yi of vertex i is given bywhereis the number of (j,k)-shortest paths andis the number of these (j,k)-shortest paths thatgo through vertex i. A vertex that appears on manyshort paths is a broker of information in the network:Efficient communication between different parts ofthe network will frequently pass through such a vertex.Such connectors have the potential to be highly influential by inserting themselves into the dealings of otherparties.Betweenness centrality gives a distinctive rankingof the characters. This is the only measure in whichTyrion does not come out on top: He places third,behind Jon Snow (thanks to his ties to both HouseStark and the remote denizens of the North) andRobert Baratheon (the only person directly connectedto all four noble houses of the leading characters).Meanwhile, Daenarys rises to fourth place (her bestshowing) because of the hub-and-spoke nature of theeclectic Essos community.There is no single “right” centrality measure for anetwork. Each measure gives complementary informa-whereandResearchers typicallyuseto find an effective balance betweeninherent importance and the neighborhood boost.PageRank does not penalize our three far-flungcharacters and actually has the opposite effect onDaenerys. In fact, the PageRank ordering is nearlyidentical to the degree centrality ordering, exceptDaenerys jumps from 12th place to fifth place. SoPageRank correctly identifies the charismatic Daenerysas one of the most important players, even though shehas relatively few connections.This brings us to two centrality measures whosedefinitions take a more global view of the network. Thecloseness centrality of a vertex is the average distancefrom the vertex to all other vertices. (Unlike the othercentrality measures, lower values correspond to greaterimportance.) The closeness values for our list of maincharacters is quite compressed, except for the farawayDaenarys. However, Tyrion and Sansa have a slightedge over everyone else.The final centrality measure is the most subtle. Thebetweenness centrality of a vertex measures how frequently that vertex lies on short paths between otherpairs of vertices. Mathematically, the betweenness zi ofvertex i isJon Snow is uniquely positioned inthe network, with connections tohighborn lords, the Night’s Watchmilitia, and the savage wildlingsbeyond the Wall.tion, and taking them in concert can be quite revealing. In our network, three characters stand out consistently: Tyrion, Jon, and Sansa. Acting as the Handof the King, Tyrion is thrust into the center of thepolitical machinations of the capitol city. Our analysissuggests that he is the true protagonist of the book.Meanwhile, Jon Snow is uniquely positioned inthe network, with connections to highborn lords, theNight’s Watch militia, and the savage wildlings beyondthe Wall. The real surprise may be the prominenceof Sansa Stark, a de facto captive in King’s Landing.However, other players are aware of her value as aStark heir and they repeatedly use her as a pawn intheir plays for power. If she can develop her cunning,then she can capitalize on her network importance todramatic effect.Meanwhile, Robert and Daenarys stand out byoverperforming in certain centrality measures. Theywww.maa.org/mathhorizons : : Math Horizons : : April 2016 21
Directions to Be Read,Then IgnoredGary Gordon and Rebecca GordonIn writing worksheets, homework assignments, quizzes, and exams, we (theauthors) often take afew liberties with thestandard “Do all ofthese problems to thebest of your ability”instructions at the topof the paper. Here are a fewof the ones we’ve used, often in reference to the topic ofthe day, but also referring to current events, pop culture,and students in the class—and always just plain silly.» Like snowflakes, no two of these problems areexactly the same. Also like snowflakes, they will meltif you touch them. Solve all of these problems withouttouching anything.» There is an invisible dog in the room. It will barkuncontrollably if you make a mistake. Good luck!» One of these problems was not approved for humanconsumption. If you eat that one by mistake, the antidote is to eat the next problem. (Note: This tells yousomething about which problem might be toxic.)» You walk into a doctor’s office and say, “I need anprovide a clear counterpoint to one another and returnour attention to the Iron Throne itself. Robert’s memory unifies the crumbling network of the recent past,while Daenarys will surely upend the current networkwhen she returns to Westeros in pursuit of the throne.A Networked LifeWe have visited the realms of Westeros and Essos totour the basic tools of network science. We performedan empirical analysis of our network, finding communities and identifying influential people. Our networkanalysis confirmed some expectations and providednew insights into this richly imagined saga. We haveconsidered a fanciful application of network science togive an enticing taste of its capabilities. More seriousapplications abound, and network science promises tobe invaluable in understanding our modern networkedlife. QFurther Reading[1] A.-L. Barabási, Network Science. ml.22 April 2016 : : Math Horizons : : www.maa.org/mathhorizonsinjection.” He says, “” Comment.» Why does calculus keep getting harder?Come to think of it, why does everythingkeep getting harder? Classes, friendships, life—seriously, it’s everything!These are some intense philosophical questions that won’t beanswered on this test.Good luck trying toconcentrate now!» As we sit here inthis classroom, a largecomet is speeding towardthe earth. Scientists expectit to hit this building in exactly onehour. Plan your test-taking strategy accordingly.» This is the beginning of a long, pointless exercise—like college. Enjoy!» You have only 50 minutes for this one—don’t wastetime reading the directions. QGary and Rebecca Gordon are a father-daughter mathteam. Gary teaches at Lafayette College and is theMath Horizons problems editor. Rebecca teaches mathematics at Newark Academy. The family is publishinga book on the card game SET, called The Joy of SET.Email: gordong@lafayette.eduEmail: orizons.23.4.22[2] D. Easley, J. Kleinberg. Networks, Crowds andMarkets. Cambridge University Press, Cambridge,2010.[3] S. Fortunato. Community detection in graphs.Physics Reports 486 nos. 3–5 (2010) 75–174.[4] M. Newman, Networks: An Introduction. OxfordUniversity Press, Oxford, 2010.Andrew Beveridge is an associate professor of mathematics at Macalester College. He plays bass guitar in aband called Math Emergency and owns the world’s onlyvelvet Erdős painting.Email: abeverid@macalester.eduJie Shan graduated from Macalester College in 2014with majors in computer science, applied math andstats, and economics.When away from computersand numbers, he is a board game enthusiast, wannabecomic artist, and recreational soccer player.Email: orizons.23.4.18
Figure 1. The Game of Thrones world: Westeros, the Narrow Sea, and Essos (from left to right). Sigils represent the locations of the noble houses at the beginning of the saga. First, a quick introduction to Game of Thrones: Westeros and Essos, separated by the Narrow Sea, ar
