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)

Abstract

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.

Documents

download article:

BibTeX

@inproceedings{edmonds-hoefler-lumsdaine-bc,
  author={Nicholas Edmonds and Torsten Hoefler and Andrew Lumsdaine},
  title={{A Space-Efficient Parallel Algorithm for Computing Betweenness Centrality in Distributed Memory}},
  year={2010},
  month={Dec.},
  pages={1 - 10},
  booktitle={International Conference on High Performance Computing},
  location={Goa, India},
  isbn={978-1-4244-8518-5 },
  source={http://www.unixer.de/~htor/publications/},
}


serving: 3.144.249.68:47189	© Torsten Hoefler