Yikes, I had to stop when the author mentioned MapReduce for computing shortest distance. That's one of the problems for which MapReduce approach is extraordinarily bad.

Sadly.... I'm noticing that folks that have done one MapReduce job are convinced it is the way to go for all jobs. It is scary just how fad based development can be.

To be fair, abstracting that fact away, the rest of the post is still an interesting thought experiment.

A better approach at the scale being discussed in the article would be to...?

What does 'scale' mean :) ? Solving graph problems are best done in-memory with a big machine (RAM!), otherwise you are an order of magnitude slower (at least) if you try to distribute. But if you really have no choice I would have a look if some of the graph databases has a good distributed model. My gut feeling tells me that even a bad approach there is faster than spark ...

I guess Titan DB would fit the bill: http://thinkaurelius.github.io/titan/

Facebook has blogged about scaling Apache Giraph to insane number of Vertices/Edges.

I don't think you have a choice, you'll have to use MapReduce if the data is too big to fit into memory. I believe that's what Facebook and Google do:

https://www.facebook.com/notes/facebook-engineering/scaling-...

http://googleresearch.blogspot.com/2009/06/large-scale-graph...

Your 2nd link describes Pregel, Google's distributed graph database specifically built for these kinds of tasks.

They were using Map Reduce prior to that, but it was a cascading mess.

If you have a hammer everything looks like a ...

unicorn?