HyPC-Map: A Hybrid Parallel Community Detection Algorithm Using Information-Theoretic Approach

Community detection has become an important graph analysis kernel due to the tremendous growth of social networks and genomics discoveries. Even though there exist a large number of algorithms in the literature, studies show that community detection based on an information-theoretic approach (known as Infomap) delivers better quality solutions than others. Being inherently sequential, the Infomap algorithm does not scale well for large networks. In this work, we develop a hybrid parallel approach for community detection in graphs using Information Theory. We perform extensive benchmarking and analyze hardware parameters to identify and address performance bottlenecks. Additionally, we use cache-optimized data structures to improve cache locality. All of these optimizations lead to an efficient and scalable community detection algorithm, HyPC-Map, which demonstrates a 25-fold speedup (much higher than the state-of-the-art map-based techniques) without sacrificing the quality of the solution.

Automated summary

Community detection is crucial in graph analysis, and using an information-theoretic approach like Infomap can deliver better solutions. However, the inherently sequential nature of Infomap algorithm limits its scalability for large networks. This work introduces a hybrid parallel approach, HyPC-Map, which achieves a significant speedup of 25 times without sacrificing solution quality.