PCPlus 287: Calculate degrees of separation

In a week when I completed writing my 50th article for PC Plus, it’s kind of fitting to also republish a hoot of an article that I really enjoyed researching.

About Bacon numbers.

Yes, it’s got Computer Science and it’s got Bacon. What more could any geek want? OK, it’s Bacon as in actor and not tasty porcine food, but at least the editors tossed in a gratuitous shot of some bacon on a fork. Betcha a bunch of PC Plus readers at least read the first few paragraphs...

The Bacon number is the basis of a fun trivia game: someone names an actor and everyone then has to work out the shortest number of steps between Kevin Bacon and that actor (the Bacon number), where a “step” is counted to mean “appeared in the same movie”. So if I say Tom Hardy as the actor (he played Eames in Inception) what’s the smallest number of linked movies before you get to Kevin Bacon? (The Oracle of Bacon suggests a Bacon number of 2: Tom Hardy was in Star Trek: Nemesis with J. Patrick McCormak, who was in Hollow Man with... Kevin Bacon.)

Although a fun pub game, there’s some Computer Science behind it. Graph theory to be general; and shortest path algorithms to be precise. Once you have a network of links and nodes (edges and vertices in the Graph Theory vernacular), given two nodes, how do you find the shortest path between them by counting the links?

The article then goes on to Dijkstra’s algorithm which considers the same problem, but now each link has a “weight” or a “cost” associated with it. Now you need to try and find the path between two nodes with the least weight or cost. Such algorithms are at the heart of route planning systems in GPS units.

This article first appeared in issue 287, November 2009. It was also published online at techradar.com.

You can download the PDF here.

  Loading links to posts on similar topics...