What makes a graph algorithm a good candidate for concurrency?
Two words: associative and commutative

In other words, the operations that the algorithm does need to be independent of how you order or group your data...this minimizes the need for cross-talk in the algorithm and leads to more efficiency.