基于孤立集分区的并行Louvain社区发掘算法  

An isolated sets based parallel Louvain algorithm for community detection

作　　者：李世杰 刘阳 唐晋韬[1] 郄航 LI Shijie;LIU Yang;TANG Jintao;QIE Hang(College of Computer Science and Technology,National University of Defense Technology,Changsha 410073;School of Information and Mechanical&Electrical Engineering,Hunan International Economics University,Changsha 410205,China)

机构地区：[1]国防科技大学计算机学院,湖南长沙410073 [2]湖南涉外经济学院信息与机电工程学院,湖南长沙410205

出　　处：《计算机工程与科学》2025年第4期621-633,共13页Computer Engineering & Science

基　　金：量子信息研究所兼高性能计算国家重点实验室基金(202101-08)。

摘　　要：为了将社区发掘应用中流行的Louvain算法应用于大规模图网络,研究人员提出了一系列并行Louvain算法,但这些并行算法均面临着2个挑战:信息同步产生的延迟和社区标签交换问题。为此创新性地引入了“孤立集”的概念,根据孤立集特性对图网络进行分区,并在此基础上提出了基于孤立集的并行Louvain算法。该算法可并行计算和更新顶点信息,不再产生同步延迟或社区标签交换。而后针对孤立集并行算法存在数据长尾效应的局限性,提出了基于哈希表的改进融合算法,进一步提升了计算效能。实验结果表明,孤立集并行算法和融合算法相比传统算法具有良好的加速比和更高的模块度。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.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]