Parallel community detection algorithm using a data partitioning strategy with pairwise subdomain duplication

Diana Palsetia*, William Hendrix, Sunwoo Lee, Ankit Agrawal, Wei-Keng Liao, Alok Nidhi Choudhary

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Community detection is an important data clustering technique for studying graph structures. Many serial algorithms have been developed and well studied in the literature. As the problem size grows, the research attention has recently been turning to parallelizing the technique. However, the conventional parallelization strategies that divide the problem domain into non-overlapping subdomains do not scale with problem size and the number of processes. The main obstacle lies in the fact that the graph algorithms often exhibit a high degree of data dependency, which makes developing scalable parallel algorithms a great challenge. We present PMEP, a distributed-memory based parallel community detection algorithm that adopts an unconventional data partitioning strategy. PMEP divides a graph into subgraphs and assigns each pair of subgraphs to one process. This method duplicates a portion of computational workload among processes in exchange for a significantly reduced communication cost required in the later stages. After data partitioning, each process runs MEP on the assigned subgraph pair. MEP is a community detection algorithm based on the idea of maximizing equilibrium and purity. Our data partitioning method effectively simplifies the communication required for combining the local results into a global one and hence allows us to achieve better scalability over existing parallel algorithms without sacrificing the result quality. Our experimental results show a speedup of 126.95 on 190 MPI processes for using synthetic data sets and a speedup of 204.22 on 1225 processes for using a real-world data set.

Original languageEnglish (US)
Title of host publicationHigh Performance Computing - 31st International Conference, ISC High Performance 2016, Proceedings
EditorsJack Dongarra, Julian M. Kunkel, Pavan Balaji
PublisherSpringer Verlag
Pages98-115
Number of pages18
ISBN (Print)9783319413204
DOIs
StatePublished - Jan 1 2016
Event31st International Conference on High Performance Computing, ISC High Performance 2016 - Frankfurt, Germany
Duration: Jun 19 2016Jun 23 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9697
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other31st International Conference on High Performance Computing, ISC High Performance 2016
CountryGermany
CityFrankfurt
Period6/19/166/23/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parallel community detection algorithm using a data partitioning strategy with pairwise subdomain duplication'. Together they form a unique fingerprint.

  • Cite this

    Palsetia, D., Hendrix, W., Lee, S., Agrawal, A., Liao, W-K., & Choudhary, A. N. (2016). Parallel community detection algorithm using a data partitioning strategy with pairwise subdomain duplication. In J. Dongarra, J. M. Kunkel, & P. Balaji (Eds.), High Performance Computing - 31st International Conference, ISC High Performance 2016, Proceedings (pp. 98-115). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9697). Springer Verlag. https://doi.org/10.1007/978-3-319-41321-1_6