Recall the [six degrees of Kevin Bacon game][1]. You can even play the game at [The Oracle of Bacon][2], 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][3], 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!

  [1]: http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon
  [2]: https://oracleofbacon.org/how.php
  [3]: https://mathoverflow.net/questions/195046/papers-about-decentralized-search-and-cluster