Write a narrative network analysis paper describing the game “The six degrees of Kevin Bacon”. In the game, you are person “0” so create a listing of all the movies you have seen “starring” Kevin Bacon. Second, create a listing of all the movies in which Kevin Bacon starred or was seen by someone else (spouse = person “1’ or a friend = person “2”) has seen. Third, create a listing of all the movies starring Kevin Bacon a person #1 spouses or friend of #2’s friend has seen. Next using only using narrative text describes how everything is related or connected.
“The Six Degrees of Kevin Bacon game is actually a problem in graph theory. Every actor is assigned to a vertex, and an edge is added between two actors if they have appeared together in a movie. Then, the problem of connecting a given actor to Kevin Bacon in the fewest number of steps becomes a traditional graph theory problem – finding the shortest path between two vertices. There are many shortest path algorithms that could be applied to this problem. For example, Dijkstra’s algorithm, which solves the positive-weighted shortest-path problem, could be used. After running Dijkstra’s algorithm, we would have the path with the lowest cost (i.e. the shortest path) between a given source vertex (the vertex corresponding to Kevin Bacon for our application) and all other vertices. However, using Dijkstra’s algorithm in this context is excessive. Dijkstra’s algorithm is best suited for situations where each edge has an associated non-negative length/weight and the goal is to find the path that minimizes the total length. For the Six Degrees of Kevin Bacon game, we are only concerned with finding the shortest path in terms of the number of connecting movies (edges) used, so each edge can be thought of as having weight 1. Thus, we would like to use the breadth-first search algorithm, which will solve the problem and be more time-efficient than Dijkstra’s algorithm.
The breadth-first search (BFS) algorithm operates by processing vertices in layers: Those closest to the source vertex are evaluated first, and those most distant are evaluated last. The algorithm uses a “roving eyeball” approach, where the eyeball moves from vertex to vertex, starting at the source (Kevin Bacon). Associated with each vertex is a number, which is the cost of getting from the source vertex to vertex. In our application, the cost after running the BFS algorithm is the Bacon number of the actor associated with the vertex. It is the source vertex, we initialize the costs with and for all. The algorithm proceeds as follows, with the eyeball starting at the source vertex:
- If is the vertex that the eyeball is currently on, then, for all that is adjacent to, we set if.
- Move the eyeball to another vertex (which has not already been visited by the eyeball) such that . If that is not possible, we move to a that satisfies. If that is not possible, we are done.
The algorithm uses a queue data structure to store intermediate results as the eyeball moves around the graph. When a vertex has its distance lowered (which can only happen once), it is placed in the queue so that the eyeball can visit it in the future. The source vertex is placed in the queue when its distance is initialized to zero.
In the BFS algorithm, there is nothing special about the vertex associated with Kevin Bacon, other than the fact that it is designated as the source vertex and so is where the eyeball starts. We could have just as easily started with a different actor, which would give us a new “center” of the Hollywood universe. But can we do better than Kevin Bacon? According to the Oracle of Bacon, the answer is yes! By comparing the average personality numbers (e.g. for Kevin Bacon we would use the weighted average of all “Bacon Numbers” while for Sean Connery we would use the weighted average of all “Connery Numbers”), actors can be ranked. As of April 28, 2013, Kevin Bacon is the 370th best center, where actors are compared based on their average number.”