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/ Any help/suggestions would be really appreciated. Metanil.