@inproceedings{3ae4334eaa1a4e0c86784db591886749,
title = "Parallel community detection algorithm using a data partitioning strategy with pairwise subdomain duplication",
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.",
author = "Diana Palsetia and William Hendrix and Sunwoo Lee and Ankit Agrawal and Liao, {Wei Keng} and Alok Choudhary",
note = "Funding Information: This work is supported in part by the following grants: NSF awards CCF-1029166, IIS-1343639, CCF-1409601; DOE awards DE-SC0007456, DE-SC0014330; AFOSR award FA9550-12-1-0458; NIST award 70NANB14H012; DARPA award N66001-15-C-4036. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 31st International Conference on High Performance Computing, ISC High Performance 2016 ; Conference date: 19-06-2016 Through 23-06-2016",
year = "2016",
doi = "10.1007/978-3-319-41321-1_6",
language = "English (US)",
isbn = "9783319413204",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "98--115",
editor = "Jack Dongarra and Kunkel, {Julian M.} and Pavan Balaji",
booktitle = "High Performance Computing - 31st International Conference, ISC High Performance 2016, Proceedings",
}