I am pretty new to both boost and parallel boost.

I am using Brandes Centrality algorithm, but the performance really doesn't meet my expectation.

If I used Java, which is only using 1 CPU core would complete it in around 30 hrs. 

The parallel version which use 8 CPU cores tooks 17 hours!!

I don't know why there is just around 13 hours gain if i use 8 cores against 1, unless there are lots and lots of communication between each cores.

I am using just 1 machine (not a cluster), right now.

Graph size is Node 80K, edges 120K

I am reading edges from files. I used distributed compressed_sparse_row to represent graph. 

Right now, it seems like all the cpu cores are reading files on its own, I am assuming each CPU core will takes its graph part automatically (distributed algorithm do it ?).

Note: I downloaded the parallel version from: http://osl.iu.edu/research/pbgl/software/