KEVIN BACON AND GRAPH THEORY

Primus: Problems, Resources, and Issues in Mathematics Undergraduate Studies, Mar 2004 by Hopkins, Brian

ABSTRACT: The interconnected world of actors and movies is a familiar, rich example for graph theory. This paper gives the history of the "Kevin Bacon Game" and makes extensive use of a Web site to analyze the underlying graph. The main content is the classroom development of the weighted average to determine the best choice of "center" for the graph. The article concludes with additional student activities and some responses to the material.

KEYWORDS: Cinema, finite mathematics, graph theory, popular culture, six degrees of separation, weighted averages.

1 INTRODUCTION

Graph theory is the mathematics of connections. It has wide applications to large, interconnected systems: transportation networks, epidemiology, and the Internet, to name just a few. But we teach graph theory with pictures of a handful of dots and lines. There is one large system that is easy to work with, thanks to a Web site run by the University of Virginia, Department of Computer Science. The Oracle of Bacon at Virginia [6] uses the Internet Movie Database [3], which documents almost all of cinematic history. This is a good tool for illustrating complete subgraphs, connected components, and the distance between vertices. There is also a nice application of weighted averages. I have used this material in freshman finite mathematics classes and mathematics major courses that cover graph theory; students always respond enthusiastically.

2 SIX DEGREES

One notion of connection in popular culture is "six degrees of separation." This traces back to a 1967 article by Stanley Milgram, a social psychologist better known for experiments on obedience to authority. "The Small-World Problem" [5] reports an experiment where Milgram gave letters to residents of Omaha, Nebraska that were intended for a stockbroker in a Boston suburb. The letters could only be sent to someone the sender knew on a first-name basis, who would forward the letter, etc. Milgram collected the letters that made it to the stockbroker and tallied how many links there were. Surprisingly, the average was only 5.2. The popularized version of this concept claims that there are only six links between any two people on earth; sociologists continue to speculate on this notion [4]. Milgram also reports on patterns in the paths of the successfully delivered letters; over half came through the same three individuals in the Boston area. Malcolm Gladwell's "Six Degrees of Lois Weisberg" [2] is an entertaining article exploring these ideas and their ramifications in society.

There are several problems with six degrees of separation in the context of graph theory. Defining a graph requires specifying its vertices and edges. The vertices of the "six degrees graph" are people, but the edge criterion is vague: should your vertex be connected to the vertices of everyone you have met? your acquaintances? just your friends? Even if we settled what relationship merits an edge in the graph, we do not have access to a significant amount of data. No database lists all of my friends, for instance. Finally, even if there were such a database, it would be unwieldy: a graph with over 6 billion vertices is too big for current computational analysis.

3 CINEMA AND THE ORACLE

Fortunately, there is a well-defined system of connections documented in a database which is large enough to be interesting, but well within the range of current computational power. The Internet Movie Database (IMDb below) has information on roughly 620,000 movie actors from around the world and approximtely 280,000 films dating back to 1891. To make this a graph, make a vertex for each actor and use an edge to connect the vertices corresponding to two actors who were in the same film. For instance, Tom Cruise and Kevin Bacon were both in A Few Good Men, which we represent as in Figure 1.

There will be an edge corresponding to A Few Good Men between each pair of actors from that film, so the "cinema graph" will have many more than 280,000 edges. In other words, the subgraph of vertices for actors in A Few Good Men and all edges for that film make a complete graph. Many more graph theoretic aspects of the cinema graph are discussed in Duncan Watt's Small Worlds [9], which also considers the Western States Power Grid and the neural network of the Caenorhabditis elegans, a worm.

In January 1994, Craig Fass, Brian Turtle, and Mike Ginelli, students at Albright College, came up with a cinematic variant of six degrees of separation. The object of the "Kevin Bacon Game" is to link an actor to Kevin Bacon in as few films as possible. For example, Nicole Kidman has (to date) never been in a film with Kevin Bacon, but she was in Eyes Wide Shut with Tom Cruise, who we know is 1 away from Kevin Bacon. In the language of graph theory, the distance between Nicole Kidman and Kevin Bacon in the cinema graph is 2. The game, also known as "Six Degrees of Kevin Bacon," became popular among movie buffs [1].

If your knowledge of cinema is less than encyclopedic, then you can cheat in the Kevin Bacon Game with a very helpful interface for the IMDb. The Oracle of Bacon at Virginia [6] is hosted by Department of Computer Science at the University of Virginia. Enter the name of an actor, and it will quickly search the database to find that person's distance to Kevin Bacon, reporting back intermediaries and the associated films. Typing "Nicole Kidman" into the Oracle gives a length 2 connection different from above: she was in The Peacemaker with Steve Altes, who was in Hollow Man with Kevin Bacon. This illustrates the point that while distance is well-defined, there may be multiple paths of that minimal length between two vertices.