This article originally appeared in The Skeptic, Volume 26, Issue 2, 2013
In 1623, John Donne pondered, “No man is an island entire of itself; every man is a piece of the continent, a part of the main.” We are only realised and complete within the social fabric that unifies us. He concluded with an equally famous reflection on a funeral bell: “any man’s death diminishes me, because I am involved in mankind, and therefore never send to know for whom the bell tolls; it tolls for thee.” Donne recognised that a consequence of cohesion is the propagation of the local to the global. However, he leaves a huge and mysterious gap between the reach of people’s daily lives and the vastness of his meditation. Centuries would pass before we could begin to map out even a fraction of Donne’s continent of connected humanity with some insight and clarity.
Mathematician Leonard Euler introduced the rudiments of a mathematical theory of interconnection in 1736, albeit at a much smaller scale. Locals in Königsburg (now Kaliningrad, Russia) had an unresolved curiosity: Was it possible to take a round-trip stroll that visited both banks of the Pregel River and its two islands while crossing each of the city’s seven bridges exactly once? Euler proved this stroll’s impossibility by liberating the connections from their geographic context. All that mattered was the pattern of the four places connected by seven links.
Euler’s solution marked the birth of the study of networks. A network is a collection of objects (called vertices) along with the links between them (called edges). Another two hundred years would elapse before the study of large and complex networks would emerge from the confluence of disciplines that study connection, behavior and structure.
Twentieth century interest in natural networks germinated in the social sciences before expanding to other disciplines. The field of network science has coalesced over the last two decades, catalysed by increased computational power and collaborative methodologies. Researchers have finally been able to construct, explore and analyse diverse relational systems of massive scale, including scientific, economic, social and technological networks. Unexpectedly, they discovered remarkable similarities among the resulting network architectures. Subsequent focus on these common features identified some universal laws guiding networked behavior. To illustrate this coming together of ideas, let’s sample some motifs of networked life.
Donne’s continent of humanity was on the minds of researchers in the late 1960’s and early 1970’s as they investigated how local interconnection creates surprising large-scale properties. Psychologist Stanley Milgram explored the “small-world” hypothesis that people are connected by short (and navigable) chains of acquaintances. This idea is now known colloquially as “six degrees of separation.” Sociologist Michael Granovetter investigated the “strength of weak ties,” how looser connections between communities play a crucial role in the global percolation of influence and information. Economist Thomas Schelling formulated another network effect. He observed that dynamic processes on networks are prone to a tipping-point phenomenon, characterised by an accumulation of a critical mass followed by explosive propagation. “Going viral” seems commonplace now, but Schelling’s insight came long before posts and tweets were sparking global cascades.
This brings us to the mathematical patterns of the networks themselves. In natural large-scale networks, not all vertices are created equal. These networks contain a subset of hubs having far more connections than average. These vertices are crucial to the efficiency of the network, just as hub cities are essential for airline travel. The hubs are actually a feature of a broader pattern in the network: the number of vertices with a given number of connections obeys a natural rule of decay, called a power law. In 1999, physicists Albert-Lászlo Barabási and Réka Albert introduced a simple network formation model that adheres to this power law. Their work shows that self-reinforcing popularity is a universal ingredient to the growth process of successful real-world networks. As networks expand, “the rich get richer’, meaning that newly added vertices are more likely to attach to existing vertices of high degree.
In addition to high connection count, there are other ways in which vertices hold key positions within the network. Researchers use a variety of centrality measures to quantify various local and global properties. Some measures capture how well-positioned vertices are as connectors between disparate parts of the network. Others capture the vitality of the network in the face of vertex deletions. One of the most successful centrality measures is Google’s PageRank, introduced by Sergei Brin and Larry Page in 1998. Their importance measure uses a feedback loop that incorporates both local features and global structure to determine the most influential vertices.
To demonstrate the power of the network analysis, let’s turn to a fictional human continent: the Seven Kingdoms of Westeros. George R. R. Martin’s A Song of Ice and Fire series stands among the most richly imagined fantasy sagas of our time. The books are populated by hundreds of characters enmeshed in a complex web of alliances, loyalties, histories and conflicts. Unusually, the series does not have a clear protagonist. Instead, the narrative perspective is shared across many prominent characters, emphasizing three competing royal houses: the forthright Starks, the unscrupulous Lannisters and the exiled Targaryens.
Here’s how we turned this complex story into an interaction network. After compiling an exhaustive list of characters and their nicknames, we generated a network for the first volume, A Game of Thrones, by linking two characters each time they appeared within fifteen words of one another. Each link corresponds to an interaction (either direct or indirect) between these characters. The resulting network is shown below (and you can find further analysis here). It contains 187 vertices and 684 weighted edges, accounting for 7,366 interactions. This system exhibits the hallmarks of large networks: a confederated small-world structure of strong and weak ties, loosely organized around a collection of hubs.
Network science techniques draw out the hidden patterns in this complex relational data. Community detection discovers six main communities in A Game of Thrones. A suite of centrality measures highlights the different ways in which characters play essential roles. Prominence in this interaction network corresponds to narrative importance. PageRank’s feedback loop is particularly effective in this regard: encounters between prominent characters accelerate narrative development. PageRank rightly identifies Ned Stark as the clear protagonist of the first book.
Certainly, a reader doesn’t need mathematical analysis to draw similar conclusions about communities and characters. But that is actually quite remarkable! This streamlined model of interconnection encodes the salient features of Martin’s intricately plotted story. A subsequent mathematical analysis of the network decodes this information, revealing structure and rankings that align with the reader’s own conclusions. In short, we have succeeded in making a mathematical model that captures narrative development in A Game of Thrones.
Moreover, this quantitative vantage draws our eye to some subtler observations. This first volume clearly favors the Starks, but PageRank places Tyrion Lannister in second place, presaging the narrative expansion coming in the subsequent books. Meanwhile, the network penalises Jon and especially Daenerys for their remote separation from the main action. Their time is yet to come, with long, heroic journeys ahead before they become central to the game of thrones. On the other hand, it might be surprising that the cartoonish Robert nearly ties Catelyn for third place, but a second look confirms that most of that book’s action and intrigue revolves around him. In these cases, the network perspective inspires deeper reflection on these characters, and on the broader narrative itself.
Like Donne’s continent of humanity, complex systems arise from a fabric of objects. Our Westrosi example introduces the network analysis process: create a useful network model, analyse its structure, and then contextualise and interpret by reincorporating the original source. Network science provides a new toolkit for guiding and illuminating disciplinary investigation.
This approach is so broadly applicable precisely because network science emerged from the intersection of so many fields. That is remarkably appropriate for the study of interconnection.
References
- A. L. Barabasi. Network Science. Cambridge University Press, 2016.
- A.-L. Barabasi and R. Albert. The emergence of scaling in random networks. Science, 286:509-512, 1999.
- S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30:107-117, 1998.
- D. Easley and J. Kleinberg. Networks, Crowds and Markets. Cambridge University Press, 2010.
- S. Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75-174, 2010.
- M. Granovetter. The strength of weak ties. American Journal of Sociology, 78:1360-1380, 1973.
- S. Milgram. The small-world problem. Psychology Today, 2:60-67, 1967.
- M. Newman. Networks: An Introduction. Oxford University Press, 2010.
- T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
- J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry, 32(4):425-443, 1969.
Andrew Beveridge is an Associate Professor in the Mathematics, Statistics and Computer Science Department at Macalester College in St Paul, Minnesota.
