1

I'm trying to play around with the 6 degrees of separation problem, specifically the Kevin Bacon game to find alternative ways of playing the game. I want to eventually port it over to MapReduce, but for now, I'm concentrating on plain old Java to get a solid understanding of the problem.

Basically I have a working program which can calculate the shortest path and the degrees of separation between any two actors, which I've implemented using breadth first search on the IMDB database. It can also calculate the average center of a given actor (a weighted distribution) as per these two links.

The Six Degrees of Kevin Bacon

The Center of the Hollywood Universe

The second link shows the top 1000 'centers' in Hollywood which I implemented by literally iterating over every actor, applying BFS and then sorting by the centers, but as you can imagine with a database the size of IMDB, this is sloooowwww!

This leads me to my problem as I want to try other things like adjusting the center of each actor depending on which films they were in and how many actors were in that movie. Even better would be give the actor a better center if they starred in movies actors with 'good' centers, e.g. those in the top 1000 list mentioned above. In my head, the latter would require a pass over each actor to get their center and then another pass to adjust the center based on the co-stars in each movie. I could probably bring Dijkstra into play here using the centers as weights but it's still going to be slow right?

Does anyone have any alternative approaches or should I give up from here on and start on MapReduce?

Improve this question
2
  • 1
    It seems to me that this problem more or less reduces to this problem. So for the IMDB case and doing this in a very strict fashion, I believe the answer is to go parallel. But, depending on your definition of center, I think you may find other types of computation to be a good approximation at a much lower cost. For example, I think you might find looking at the unique number of actors out to say 3 links deep to be an interesting metric. I'm sure graph theory may provide some interesting options here.
    – J Trana
    Jun 25, 2015 at 0:42
  • @J Trana, thanks for the suggestion. I'm now trying to solve it using a randomised algorithm which will hopefully give me a good enough approximation of the top 1000. It'll be interesting to run a comparison of the two methods.
    – Metaman
    Jul 14, 2015 at 9:03

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.