Home
Publications
conferences
presentations
techreports
theses
all years
2010
2009
2008
2007
2006
2005
2004
Professional
Research
Teaching
BLOG
Me(e)t me?
Miscellaneous
CV
Events
|
Publications of Torsten Hoefler
Copyright Notice:
The documents distributed by this server have been provided by the
contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all
rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the explicit
permission of the copyright holder.
N. Edmonds, T. Hoefler and A. Lumsdaine:
| | | A Space-Efficient Parallel Algorithm for Computing Betweenness Centrality in Distributed Memory
(Dec. 2010, Accepted at the 2010 International Conference on High Performance Computing (HiPC'10) )
AbstractBetweenness 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 | | | BibTeX | @inproceedings{edmonds-hoefler-lumsdaine-bc,
author={N. Edmonds and T. Hoefler and A. Lumsdaine},
title={{A Space-Efficient Parallel Algorithm for Computing Betweenness Centrality in Distributed Memory}},
year={2010},
month={Dec.},
note={Accepted at the 2010 International Conference on High Performance Computing (HiPC'10)},
source={http://www.unixer.de/~htor/publications/},
} |
|
|
