This paper presents a study of graph partitioning schemes for parallel graph community detection on distributed memory machines. We investigate the relationship between graph structure and parallel clustering effectiveness, and develop a heuristic partitioning algorithm suitable for modularity-based algorithms. We demonstrate the accuracy and scalability of our approach using several real-world large graph datasets compared with state-of-the-art parallel algorithms on the Cray XK7 supercomputer at Oak Ridge National Laboratory. Given the ubiquitous graph model, we expect this high-performance solution will help lead to new insights in numerous fields.
Zeng, J., and H. Yu, 2016: A study of graph partitioning schemes for parallel graph community detection. Parallel Computing, 58, 131–139, doi:10.1016/j.parco.2016.05.008This material is based upon work supported by the National Science Foundation under Grant No. 1541043. Opinions, findings, conclusions or recommendations expressed are those of the authors and do not reflect the views of the NSF.