There are all kinds of strategies that can be used to speed this up.
Let's say that we're trying to find a short path between someone in the US and someone in China. Start by trying to find a link that allows you to hop the Pacific ocean as quickly as possible. Try to find an American friend of the Chinese guy, or vice versa. When you've got it to two people in the same country, then start picking the nodes that allow you to hop the greatest distance.
You could come up with a group of highly-connected people to start with - the people who have lots of connections in various countries, economic classes, interests, etc. Create a graph of these people and pre-compute all the shortest paths between them. Then when you're going through all the combinations, you just need to get to brute-force your way to this central graph.
Of course this won't get you the shortest path between each pair of people, but it'll probably get you pretty close. Close enough to say if an average of "six degrees" is reasonable.