期刊
出版社
IEEE
DOI: 10.1109/HPEC49654.2021.9622866
关键词
Community Detection; Parallel Algorithms; Information-Theory; Map Equation; MDL; Graphs
类别
资金
- US Department of Energy/Berkeley Lab/University of California Subcontract Award [7551418, DE-AC02-05CH11231]
- Louisiana Board of Regents RCS [LEQSF(201720)-RDA-25]
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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据