David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



Generalizing k-Betweenness Centrality Using Short Paths and a Parallel Multithreaded Implementation

We present a new parallel algorithm that extends and generalizes the traditional graph analysis metric of betweenness centrality to include additional non-shortest paths according to an input parameter k. Betweenness centrality is a useful kernel for analyzing the importance of vertices or edges in a graph and has found uses in social networks, biological networks, and power grids, among others. k-betweenness centrality captures the additional information provided by paths whose length is within k units of the shortest path length. These additional paths provide robustness that is not captured in traditional betweenness centrality computations, and they may become important shortest paths if key edges are missing in the data. We implement our parallel algorithm using lock-free methods on a massively multithreaded Cray XMT. We apply this implementation to a real-world data set of pages on the World Wide Web and show the importance of the additional data incorporated by our algorithm.

Publication History

Versions of this paper appeared as:
  1. K. Jiang, D. Ediger, and D.A. Bader, ``Generalizing k-Betweenness Centrality Using Short Paths and a Parallel Multithreaded Implementation,'' The 38th International Conference on Parallel Processing (ICPP 2009), Vienna, Austria, pages 542-549, September 22-25, 2009.

Download this report in Adobe PDF


Last updated: June 26, 2010


Computational Biology

Parallel Computing