Discamus continentiam augere, luxuriam coercere
Home -> Publications
edited volumes
  Full CV [pdf]


  Past Events

Publications of Torsten Hoefler
Nicholas Edmonds, Torsten Hoefler and Andrew Lumsdaine:

 A Space-Efficient Parallel Algorithm for Computing Betweenness Centrality in Distributed Memory

(In International Conference on High Performance Computing, presented in Goa, India, pages 1 - 10, ISBN: 978-1-4244-8518-5 , Dec. 2010)


Betweenness centrality is a measure based on shortest paths that attempts to quantify the relative importance of nodes in a network. As computation of betweenness centrality becomes increasingly important in areas such as social network analysis, networks of interest are becoming too large to fit in the memory of a single processing unit, making parallel execution a necessity. Parallelization over the vertex set of the standard algorithm, with a final reduction of the centrality for each vertex, is straightforward but requires \Omega(|V|^2) storage. In this paper we present a new parallelizable algorithm with low spatial complexity that is based on the best known sequential algorithm. Our algorithm requires O(|V| + |E|) storage and enables efficient parallel execution. Our algorithm is especially well suited to distributed memory processing because it can be implemented using coarse-grained parallelism. The presented time bounds for parallel execution of our algorithm on CRCW PRAM and on distributed memory systems both show good asymptotic performance. Experimental results with a distributed memory computer show the practical applicability of our algorithm.


download article:


  author={Nicholas Edmonds and Torsten Hoefler and Andrew Lumsdaine},
  title={{A Space-Efficient Parallel Algorithm for Computing Betweenness Centrality in Distributed Memory}},
  pages={1 - 10},
  booktitle={International Conference on High Performance Computing},
  location={Goa, India},
  isbn={978-1-4244-8518-5 },

serving:© Torsten Hoefler