Scalable Flow-Based Community Detection for Large-Scale Network Analysis

Abstract—Community-detection is a powerful approach to un-cover important structures in large networks. Since networks of-ten describe flow of some entity, flow-based community-detection methods are particularly interesting. One such algorithm is called Infomap, which optimizes the objective function known as the map equation. While Infomap is known to be an effective algo-rithm, its serial implementation cannot take advantage of multi-core processing in modern computers. In this paper, we propose a novel parallel generalization of Infomap called RelaxMap. This al-gorithm relaxes concurrency assumptions to avoid lock overhead, achieving 70 % parallel efficiency in shared-memory multicore experiments while exhibiting similar convergence properties and finding similar community structures as the serial algorithm. We evaluate our approach on a variety of real graph datasets as well as synthetic graphs produced by a popular graph generator used for benchmarking community detection algorithms. We describe the algorithm, the experiments, and some emerging research directions in high-performance community detection on massive graphs. I