计算机工程与科学2025，Vol.47Issue(4)：621-633,13.DOI:10.3969/j.issn.1007-130X.2025.04.006
基于孤立集分区的并行Louvain社区发掘算法
An isolated sets based parallel Louvain algorithm for community detection
摘要
Abstract
To apply the popular Louvain algorithm used in community detection to large-scale graph networks,researchers have proposed a series of parallel Louvain algorithms.However,these parallel algorithms face two challenges:delay caused by information synchronization and the community label exchange problem.To address these challenges,this paper innovatively introduces the concept of isola-ted sets and partitions the graph network based on the characteristics of isolated sets.On this basis,a parallel Louvain algorithm based on isolated sets is proposed.This algorithm allows for parallel compu-tation and updating of vertex information without generating synchronization delays or requiring com-munity label exchanges.Furthermore,to address the limitation of the long tail effect in data processing inherent in the isolated sets parallel algorithm,an improved fusion algorithm based on hash tables is proposed,which further enhances computational efficiency.Experimental results show that the parallel algorithm and fusion algorithm based on isolated sets have good speedup ratios and higher modularity compared to traditional algorithms.关键词
并行计算/孤立集/图划分/Louvain算法/社区发掘Key words
parallel computing/isolate set/graph partition/Louvain algorithm/community detection分类
计算机与自动化引用本文复制引用
李世杰,刘阳,唐晋韬,郄航..基于孤立集分区的并行Louvain社区发掘算法[J].计算机工程与科学,2025,47(4):621-633,13.基金项目
量子信息研究所兼高性能计算国家重点实验室基金(202101-08) （202101-08）
