Skip to main content
Article
Hierarchical Parallel Algorithm for Modularity-Based Community Detection Using GPUs
Euro-Par 2013 Parallel Processing: 19th International Conference, Aachen, Germany, August 26-30, 2013. Proceedings
  • Chun Yew CHEONG, Institute of High Performance Computing, A*STAR, Singapore
  • Huynh Phung HUYNH, Institute of High Performance Computing, A*STAR, Singapore
  • David LO, Singapore Management University
  • Rick Siow Mong GOH, Institute of High Performance Computing, A*STAR, Singapore
Publication Type
Conference Proceeding Article
Publication Date
8-2013
Abstract

This paper describes the design of a hierarchical parallel algorithm for accelerating community detection which involves partitioning a network into communities of densely connected nodes. The algorithm is based on the Louvain method developed at the Université Catholique de Louvain, which uses modularity to measure community quality and has been successfully applied on many different types of networks. The proposed hierarchical parallel algorithm targets three levels of parallelism in the Louvain method and it has been implemented on single-GPU and multi-GPU architectures. Benchmarking results on several large web-based networks and popular social networks show that on top of offering speedups of up to 5x, the single-GPU version is able to find better quality communities. On average, the multi-GPU version provides an additional 2x speedup over the single-GPU version but with a 3% degradation in community quality.

Keywords
  • Community detection,
  • parallel algorithm,
  • GPU,
  • social networks
ISBN
9783642400476
Identifier
10.1007/978-3-642-40047-6_77
Publisher
Springer Verlag
City or Country
Aachen, Germany
Additional URL
http://dx.doi.org/10.1007/978-3-642-40047-6_77
Citation Information
Chun Yew CHEONG, Huynh Phung HUYNH, David LO and Rick Siow Mong GOH. "Hierarchical Parallel Algorithm for Modularity-Based Community Detection Using GPUs" Euro-Par 2013 Parallel Processing: 19th International Conference, Aachen, Germany, August 26-30, 2013. Proceedings Vol. 8097 (2013) p. 775 - 787
Available at: http://works.bepress.com/david_lo/145/