Betweenness Centrality Revisited on Four Processors

The betweenness centrality measure has been widely adopted in various graph analytics applications, such as community detection and brain network analysis. Due to the high intensity of BC computation and rapid data growth, there have been a number of studies on parallel BC computation, either on CPUs or GPUs. However, there has not been a comprehensive comparative study on the BC algorithm on different processors. In this paper, we revisit shared-memory parallel BC computation on four kinds of processors, including multi-core CPUs, many-core GPUs, and two generations of Intel MIC processors. We find that, with suitable parallelization strategies and data-oriented optimizations, commodity multi-core CPUs are the fastest, followed by the second generation MIC. These two processors are faster than the state-of-the-art GPU implementations across all kinds of graphs. In comparison, the GPU outperforms the first generation MIC only on small-diameter graphs and is the slowest on the other kinds of graphs.