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 BaconThe Center of the Hollywood UniverseThe 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?
Efficient extensions of degree of separation
java;algorithms