5
$\begingroup$

Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search.

I interpret the punchline as saying that if I start with a random actor I can "usually" get to Kevin Bacon with six steps. So perhaps there's a probability distribution over all starting actors and the expected number of steps to Kevin Bacon is less than six. EDIT: I just found in Section 2.3 of Kleinberg and Easley's book that the average Bacon number is 2.9 and the max known to the authors (other than $\infty$) is 8.

Does anyone know the variance of this probability distribution?

I would be satisfied with either a theoretical answer or a data-driven answer. The former might look like a reference to a paper where someone proposed a graph that acts like IMDB and has studied the search problem on it. This is related to a question my student recently asked, and it seems the type of graph which most closely represents IMDB might be an intersection graph.

The latter type of answer might come from a query to the IMDB database. Their data is publicly available and I'm waiting for a confirmation from them that it can be used for academic purposes. The Oracle of Bacon website links to the FTPs where you can get the IMDB data. My student and I can do this analysis, but I wanted to post a question here first to see if someone else had already done it.

We need the variance for a step in our current research project. Thanks!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This is one classic paper on the search problem: cs.cornell.edu/home/kleinber/swn.pdf ... and in general it's a good entry point into the literature. $\endgroup$
    – Martin M. W.
    Commented Feb 2, 2015 at 2:03
  • $\begingroup$ Hi Martin. Thanks for the pointer. That was actually the article we began with in December (along with his Complex Networks paper). We're now reading his book with Easley but it's a lot of material. One way to phrase our general project is to recast this work into the language of intersection graphs, to better mimic IMDB data (where nodes are sets of actors). One question we've been trying to figure out is if anyone has generalized Kleinberg's model so that it allows undirected weak ties (chapter 20 of the book). Do you happen to know the answer? $\endgroup$
    – David White
    Commented Feb 2, 2015 at 2:28

0

Reset to default

You must log in to answer this question.