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

来源：计算机工程与科学杂志2025年第4期北京时间：

作者：李世杰, 刘阳, 唐晋韬, 郄航

单位：1.国防科技大学计算机学院，湖南 长沙 410073；2.湖南涉外经济学院信息与机电工程学院，湖南 长沙 410205

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

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

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