Physical Sciences and Mathematics Commons^™

Hierarchical Parallel Algorithm For Modularity-Based Community Detection Using Gpus, Chun Yew Cheong, Huynh Phung Huynh, David Lo, Rick Siow Mong Goh

David LO

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 …