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.
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!