Journal of Computer Science and Technology ›› 2023, Vol. 38 ›› Issue (2): 373-390.doi: 10.1007/s11390-023-1599-1

Special Issue: Computer Architecture and Systems; Artificial Intelligence and Pattern Recognition

• Computer Architecture and Systems • Previous Articles     Next Articles

Isolate Sets Based Parallel Louvain Method for Community Detection

Hang Qie (郄 航), Yong Dou* (窦 勇), Senior Member, CCF, Zhen Huang (黄 震), and Yun-Sheng Xiong (熊运生)   

  1. Science and Technology on Parallel and Distributed Laboratory, School of Computer National University of Defense Technology, Changsha 410073, China
  • Received:2021-05-20 Revised:2023-02-09 Accepted:2023-02-24 Online:2023-05-10 Published:2023-05-10
  • Contact: Yong Dou E-mail:yongdou@nudt.edu.cn
  • About author:Yong Dou is a professor and doctoral supervisor of the School of Computer at National University of Defense Technology, Changsha. He received his B.S. degree, M.E. degree and Ph.D. degree in computer science from National University of Defense Technology, Changsha, in 1989, 1992 and 1995 respectively. His research interests include design and implementation of the high performance accelerators and deep learning.
  • Supported by:
    This work is 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, and 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.

Key words: parallel computing; isolate sets; graph partition; Louvain method; community detection;

[1] Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3/4/5): 75–174. DOI: 10.1016/j.physrep.2009.11.002.
[2] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 066111. DOI: 10.1103/PhysRevE.70.066111.
[3] Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics, 2008, 2008: P10008. DOI: 10.1088/1742-5468/2008/10/P10008.
[4] Lu H, Halappanavar M, Kalyanaraman A. Parallel heuristics for scalable community detection. Parallel Computing, 2015, 47: 19–37. DOI: 10.1016/j.parco.2015.03.003.
[5] Que X Y, Checconi F, Petrini F, Gunnels J A. Scalable community detection with the Louvain algorithm. In Proc. the 29th IEEE International Parallel and Distributed Processing Symposium, May 2015, pp.28–37. DOI: 10.1109/IPDPS.2015.59.
[6] Staudt C L, Meyerhenke H. Engineering parallel algorithms for community detection in massive networks. IEEE Trans. Parallel and Distributed Systems, 2016, 27(1): 171–184. DOI: 10.1109/TPDS.2015.2390633.
[7] Forster R. Louvain community detection with parallel heuristics on GPUs. In Proc. the 20th IEEE Jubilee International Conference on Intelligent Engineering Systems, Jun. 30–Jul. 2, 2016, pp.227–232. DOI: 10.1109/INES.2016.7555126.
[8] Naim M, Manne F, Halappanavar M, Tumeo A. Community detection on the GPU. In Proc. the 2017 IEEE International Parallel and Distributed Processing Symposium, May 29–Jun. 2, 2017, pp.625–634. DOI: 10.1109/IPDPS.2017.16.
[9] Zeng J P, Yu H F. A scalable distributed Louvain algorithm for large-scale graph community detection. In Proc. the 2018 IEEE International Conference on Cluster Computing, Sept. 2018, pp.268–278. DOI: 10.1109/CLUSTER.2018.00044.
[10] Ghosh S, Halappanavar M, Tumeo A, Kalyanaraman A, Lu H, Chavarrià-Miranda D, Khan A, Gebremedhin A. Distributed Louvain algorithm for graph community detection. In Proc. the 2018 IEEE International Parallel and Distributed Processing Symposium, May 2018, pp.885–895. DOI: 10.1109/IPDPS.2018.00098.
[11] Zeng J P, Yu H F. Parallel modularity-based community detection on large-scale graphs. In Proc. the 2015 IEEE International Conference on Cluster Computing, Sept. 2015. DOI: 10.1109/CLUSTER.2015.11.
[12] Duckworth W, Zito M. Large 2-independent sets of regular graphs. Electronic Notes in Theoretical Computer Science, 2003, 78: 223–235. DOI: 10.1016/S1571-0661(04)81015-6.
[13] Blidia M, Chellali M, Favaron O, Meddah N. Maximal k-independent sets in graphs. Discussiones Mathematicae Graph Theory, 2008, 28(1): 151–163. DOI: 10.7151/dmgt.1398.
[14] Wang D W, Cui W Q, Qin B. CK-modes clustering algorithm based on node cohesion in labeled property graph. Journal of Computer Science and Technology, 2019, 34(5): 1152–1166. DOI: 10.1007/s11390-019-1966-0.
[15] Yang W, Shen G W, Wang W, Gong L Y, Yu M, Dong G Z. Anomaly detection in microblogging via co-clustering. Journal of Computer Science and Technology, 2015, 30(5): 1097–1108. DOI: 10.1007/s11390-015-1585-3.
[16] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(4): 1118–1123. DOI: 10.1073/pnas.0706851105.
[17] Rosvall M, Axelsson D, Bergstrom C T. The map equation. The European Physical Journal Special Topics, 2009, 178(1): 13–23. DOI: 10.1140/epjst/e2010-01179-1.
[18] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970, 49(2): 291–307. DOI: 10.1002/j.1538-7305.1970.tb01770.x.
[19] MacQueen J. Some methods for classification and analysis of multivariate observations. In Proc. the 5th Berkeley Symposium on Mathematical Statistics and Probability, Le Cam L M, Neyman J (eds.), Statistical Laboratory of the University of California, 1967, pp.407.
[20] Barnes E R. An algorithm for partitioning the nodes of a graph. SIAM Journal on Algebraic Discrete Methods, 1982, 3(4): 541–550. DOI: 10.1137/0603056.
[21] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821–7826. DOI: 10.1073/pnas.122653799.
[22] Flake G W, Lawrence S, Lee Giles C. Efficient identification of Web communities. In Proc. the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2000, pp.150–160. DOI: 10.1145/347090.347121.
[23] Flake G W, Lawrence S, Giles C L, Coetzee F M. Self-organization and identification of Web communities. Computer, 2002, 35(3): 66–70. DOI: 10.1109/2.989932.
[24] Airoldi E M, Blei D M, Fienberg S E, Xing E P. Mixed membership stochastic blockmodels. The Journal of Machine Learning Research, 2008, 9: 1981–2014. DOI: 10.5555/1390681.1442798.
[25] Mehta N, Carin L, Rai P. Stochastic blockmodels meet graph neural networks. arXiv: 1905.05738, 2019. https://arxiv.org/abs/1905.05738, May 2019.
[26] Gopalan P K, Blei D M. Efficient discovery of overlapping communities in massive networks. Proceedings of the National Academy of Sciences of the United States of America, 2013, 110(36): 14534–14539. DOI: 10.1073/pnas.1221839110.
[27] Cheong C Y, Huynh H P, Lo D, Goh R S M. Hierarchical parallel algorithm for modularity-based community detection using GPUs. In Proc. the 19th European Conference on Parallel Processing, Aug. 2013, pp.775–787. DOI: 10.1007/978-3-642-40047-6_77.
[28] Fazlali M, Moradi E, Malazi H T. Adaptive parallel Louvain community detection on a multicore platform. Microprocessors and Microsystems, 2017, 54: 26–34. DOI: 10.1016/j.micpro.2017.08.002.
[29] Wickramaarachchi C, Frincu M, Small P, Prasanna V K. Fast parallel algorithm for unfolding of communities in large graphs. In Proc. the 2014 IEEE High Performance Extreme Computing Conference, Sept. 2014. DOI: 10.1109/HPEC.2014.7040973.
[30] Kunegis J. KONECT: The Koblenz network collection. In Proc. the 22nd International Conference on World Wide Web, May 2013, pp.1343–1350. DOI: 10.1145/2487788.2488173.
[31] Boldi P, Rosa M, Santini M, Vigna S. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proc. the 20th International Conference on World Wide Web, Mar. 2011, pp.587–596. DOI: 10.1145/1963405.1963488.
[1] Dong-Fang Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng, Jing-Ya Zhou, Zhao Liu. Optimal Path Embedding in the Exchanged Crossed Cube [J]. , 2017, 32(3): 618-629.
[2] Peng Qu, Jin Yan, You-Hui Zhang, Guang R. Gao. Parallel Turing Machine, a Proposal [J]. , 2017, 32(2): 269-285.
[3] Xiao-Hu Yan, Fa-Zhi He, Yi-Lin Chen. A Novel Hardware/Software Partitioning Method Based on Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization [J]. , 2017, 32(2): 340-355.
[4] Jack B. Dennis. Principles to Support Modular Software Construction [J]. , 2017, 32(1): 3-10.
[5] Huai-Yu Wan, Zhi-Wei Wang You-Fang Lin, Xu-Guang Jia, Yuan-Wei Zhou. Discovering Family Groups in Passenger Social Networks [J]. , 2015, 30(5): 1141-1153.
[6] Rong Chen, Jia-Xin Shi, Hai-Bo Chen, Bin-Yu Zang. Bipartite-Oriented Distributed Graph Partitioning for Big Learning [J]. , 2015, 30(1): 20-29.
[7] Yu-Xin Ma, Jia-Yi Xu, Di-Chao Peng, Ting Zhang, Cheng-Zhe Jin, Hua-Min Qu, Wei Chen, and Qun-Sheng Peng . A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks [J]. , 2013, 28(5): 797-809.
[8] Ying-Jun Wu(吴英骏), Han Huang(黄翰), Member, CCF, ACM, IEEE, Zhi-Feng Hao(郝志峰), and Feng Chen(陈丰). Local Community Detection Using Link Similarity [J]. , 2012, 27(6): 1261-1268.
[9] Mao-Guo Gong (公茂果), Senior Member, CCF, Member, ACM, IEEE, Ling-Jun Zhang (张岭军), Jing-Jing Ma (马晶晶), and Li-Cheng Jiao (焦李成), Senior Member, CCF, IEEE. Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm [J]. , 2012, 27(3): 455-467.
[10] Zhi-Hao Wu (武志昊), You-Fang Lin (林友芳), Steve Gregory, Huai-Yu Wan (万怀宇), Student Member, CCF, and Sheng-Feng Tian (田盛丰). Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks [J]. , 2012, 27(3): 468-479.
[11] Huai-Yu Wan (万怀宇), Student Member, CCF, You-Fang Lin (林友芳), Zhi-Hao Wu (武志昊), and Hou-Kuan Huang (黄厚宽), Senior Member, CCF. Discovering Typed Communities in Mobile Social Networks [J]. , 2012, 27(3): 480-491.
[12] Xue Wang (王雪), Xuan Zhou (周烜), and Shan Wang; (王珊), Senior Member, CCF, Member, ACM. Summarizing Large-Scale Database Schema Using Community Detection [J]. , 2012, 27(3): 515-526.
[13] Xin Liu (刘欣) and Tsuyoshi Murata, Member, ACM, IEEE. Detecting Communities in K-Partite K-Uniform (Hyper)Networks [J]. , 2011, 26(5): 778-791.
[14] Chuan Shi (石川), Member, CCF, IEEE, Zhen-Yu Yan (闫震宇), Member, IEEE, Xin Pan (潘欣), Ya-Nan Cai (蔡亚男), and Bin Wu (吴斌), Member, CCF. A Posteriori Approach for Community Detection [J]. , 2011, 26(5): 792-805.
[15] Dong-Rui Fan, Member, CCF, IEEE, Nan Yuan, Jun-Chao Zhang, Member, CCF, ACM, Yong-Bin Zhou, Wei Lin, Feng-Long Song, Xiao-Chun Ye, He Huang, Lei Yu, Guo-Ping Long, Hao Zhang, and Lei Liu. Godson-T: An Efficient Many-Core Architecture for Parallel Program Executions [J]. , 2009, 24(6): 1061-1073.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Li Wei;. A Structural Operational Semantics for an Edison Like Language(2)[J]. , 1986, 1(2): 42 -53 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[5] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[6] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[7] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[8] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[9] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[10] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved