Hack 80. Play Six Degrees of Kevin Bacon

2017-11-03 09:05:03

In the Kevin Bacon game, you pick an actor and try to connect that actor to Kevin Bacon through movies that they both have been in.

The Kevin Bacon game is a fun way to explore network connection concepts. For example, if you were to choose fellow brat-packer Demi Moore the game would be easy. Both Kevin and Demi were in A Few Good Men (1992), so Demi's Kevin Bacon number is 1.

Had you chosen Steve McQueen, you would have to notice that Kevin Bacon worked with Dustin Hoffman in Sleepers (1996) and Dustin Hoffman costarred with McQueen in Papillon (1973). That gives Steve McQueen a Kevin Bacon number of 2.

Mathematicians play this game, but relative to Paul Erdös rather than Kevin Bacon. They calculate their Erdös numbers by following a chain of coauthored papers. The average number of coauthors is generally much smaller than the cast list of a movie, so the game is much harder for mathematicians.

To get started you need a database of movies, actors, and casting, such as the one at http://sqlzoo.net/h.htm#data. This example is based on a simplification of that data set.

The performsIn table contains (actor, movie) pairs. An entry in this table indicates that the actor was in the movie:

You can find the actors with a Kevin Bacon number of 1 by joining this table to itself:

You can make a VIEW based on this pattern that makes the next stage a little simpler. This VIEW connects all actors who have been in the same movie. The two actor columns are called actorIn and actorOut because you can think of this kind of view as a kind of function. You can also exclude the connection between each actor and him or herself:

CREATE VIEW actorToActor AS SELECT x.actor actorIn ,x.movie, y.actor actorOut FROM performsIn x JOIN performsIn y ON (x.movie=y.movie AND x.actor!=y.actor);

Running the Kevin Bacon 1 query using this view now gives the following results:

To get to Kevin Bacon 2 actors you can JOIN this view to itself. You tie up the output of one instance into the input of the other. The result is pretty big by this stage, so it is best to specify your target. In this example, the target is Alan Alda:

The six rows indicate that there are six different ways to connect Kevin Bacon to Alan Alda. The LEFT function has been used to truncate the actor and movie names.

All it takes is another join to connect Kevin Bacon to "Weird Al" Yankovic, who has a Kevin Bacon number of 3:

You can continue the number of links, but it gets more expensive at every level. The number of different paths grows exponentially. You very quickly get to the stage where the number of rows generated is greater than not just the number of actors in your database, but also the number of people on the planet.

The following query connects Kevin Bacon back to Kevin Bacon in four steps. It takes nearly five minutes and includes nearly 400,000 rows. There are fewer than 2,000 movies in the database.

mysql> SELECT COUNT(*) FROM( -> SELECT LEFT(w.movie,10) movie1 -> ,LEFT(w.actorOut,10) actor1 -> ,LEFT(z.movie,11) movie3 -> ,LEFT(z.actorOut,10) actor3 -> FROM actorToActor w JOIN actorToActor x ON w.actorOut=x.actorIn -> JOIN actorToActor y ON x.actorOut=y.actorIn -> JOIN actorToActor z ON y.actorOut=z.actorIn -> WHERE w.actorIn = 'Kevin Bacon' -> AND z.actorOut = 'Kevin Bacon' -> ) t; +----------+ | COUNT(*) | +----------+ | 400637 | +----------+ 1 row in set (4 min 43.02 sec)

There are limits on how far you can take this technique without using some shortcuts. Some large problems, such as calculating tag clouds or determining page rank calculations, require transitive links such as these to be calculated. As the numbers grow, you have to store intermediate results in tables so that you can effectively use indexes and remove duplicates.

Категории