The graph 500 benchmark was developed to help people benchmark machines and programming environments for graph algorithms which tend to be different from numerical algorithms. There is a reference implementation in octave available. It should be a good example problem.
http://www.graph500.org/specifications http://www.graph500.org/referencecode
