How can we design graph algorithms that scale efficiently in large scale parallel computations? This is and active area of research with many applications.  

See http://www-static.cc.gatech.edu/~bader/.