By Amdahl's law, that idealisation assumes that your program is totally parallelisable. Very few real world applications actually are. Out of interest, was yours? (Or at least very close to it?)
Yes, our algorithm performed an O(N^2) loop over the graph vertices so B for us was very close to 1.
OK, but I think you mean B was close to zero then?
Fair enough.
If this is the Moyes algorithm which does graph clustering I think you have to ask yourself a couple of things:
1. can a parallel algorithm that optimizes each node individually get the same result as a serial algorithm that optimizes them sequentially (this is not at all obvious, and for some graph clustering algorithms the answer is "no")
2. is a O(n^3) total work algorithm really that much better than one of the multiple existing subquadratic graph clustering algorithms out there.