关键词: 并行计算, 孤立集, 图划分, Louvain算法, 社区发掘

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 isolated 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 computation and updating of vertex information without generating synchronization delays or requiring community 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.

Key words: parallel computing, isolate set, graph partition, Louvain algorithm, community detection