Great post. Would love to see more scientific analysis of private company internet data, especially given its abundance and proliferation. Props to Facebook for collaborating with outside academics. Johan Ugander (@jugander) at Cornell is top notch.

Lars Backstrom works at Facebook, so it's not exactly an "outside" collaboration.

Amazing results from an incredibly large and world-class data set. Great work @jugander!

What kind of heuristics would you use in a search like this?

For decentralized routing, Kleinberg has a wonderfully lucid paper in Science in 2000 that's one page long (something like "navigation in a small world"). Essentially, even though short paths may exist in a network, it's hard for any decentralized routing algorithm (like the one in Milgram's experiment) to find them.