Isolate Sets Based Parallel Louvain Method for Community Detection  

作　　者：郄航 窦勇 黄震 熊运生 Hang Qie;Yong Dou;Zhen Huang;Yun-Sheng Xiong(Science and Technology on Parallel and Distributed Laboratory,School of Computer National University of Defense Technology,Changsha 410073,China)

机构地区：[1]Science and Technology on Parallel and Distributed Laboratory,School of Computer National University of Defense Technology,Changsha 410073,China

出　　处：《Journal of Computer Science & Technology》2023年第2期373-390,共18页计算机科学技术学报（英文版）

基　　金：supported by the Key Program of National Natural Science Foundation of China under Grant No.61732018;the National Natural Science Foundation of China under Grant No.61902415;the Open Foundation of Science and Technology on Parallel and Distributed Laboratory(School of Computer,National University of Defense Technology)under Grant No.6142110190201.

摘　　要：Community detection is a vital task in many fields,such as social networks and financial analysis,to name a few.The Louvain method,the main workhorse of community detection,is a popular heuristic method.To apply it to large-scale graph networks,researchers have proposed several parallel Louvain methods(PLMs),which suffer from two challenges:the latency in the information synchronization,and the community swap.To tackle these two challenges,we propose an isolate sets based parallel Louvain method(IPLM)and a fusion IPLM with the hashtables based Louvain method(FIPLM),which are based on a novel graph partition algorithm.Our graph partition algorithm divides the graph network into subgraphs called isolate sets,in which the vertices are relatively decoupled from others.We first describe the concepts and properties of the isolate set.Second we propose an algorithm to divide the graph network into isolate sets,which enjoys the same computation complexity as the breadth-first search.Third,we propose IPLM,which can efficiently calculate and update vertices information in parallel without latency or community swap.Finally,we achieve further acceleration by FIPLM,which maintains a high quality of community detection with a faster speedup than IPLM.Our two methods are for shared-memory architecture,and we implement our methods on an 8-core PC;the experiments show that IPLM achieves a maximum speedup of 4.62x and outputs higher modularity(maximum 4.76%)than the serial Louvain method on 14 of 18 datasets.Moreover,FIPLM achieves a maximum speedup of 7.26x.

关 键 词：parallel computing isolate set graph partition Louvain method community detection 

分 类 号：O15[理学—数学]