Parallel Louvain Community Detection Algorithm Based on Dynamic Thread Assignment on Graphic Processing Unit

Mohammadi, M.; Fazlali, M.; Hosseinzadeh, M.

doi:10.22061/jecei.2021.7771.432

تعداد نشریات	13
تعداد شماره‌ها	237
تعداد مقالات	2,400
تعداد مشاهده مقاله	3,852,999
تعداد دریافت فایل اصل مقاله	2,796,977

	Parallel Louvain Community Detection Algorithm Based on Dynamic Thread Assignment on Graphic Processing Unit
Journal of Electrical and Computer Engineering Innovations (JECEI)
مقاله 7، دوره 10، شماره 1، فروردین 2022، صفحه 75-88 اصل مقاله (1.37 M)
نوع مقاله: Original Research Paper
شناسه دیجیتال (DOI): 10.22061/jecei.2021.7771.432
نویسندگان
M. Mohammadi¹؛ M. Fazlali^* ²؛ M. Hosseinzadeh³
¹Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
²Department of Computer and Data Sciences, Faculty of Mathematical Sciences, Shahid Beheshti University, Tehran, Iran
³Mental Health Research Center, Psychosocial Health Research Institute, Iran University of Medical Sciences, Tehran, Iran
تاریخ دریافت: 18 بهمن 1399، تاریخ بازنگری: 23 فروردین 1400، تاریخ پذیرش: 27 خرداد 1400
چکیده
Background and Objectives: Louvain is a time-consuming community detection algorithm especially in large-scale networks. Using Graphic Processing Unit (GPU) in order to calculate modularity sigma, which is a major processing section in Louvain algorithm, can reduce algorithm execution time and make it practical for large-scale networks. Methods: The proposed algorithm Dynamic CUDA Louvain Method (DCLM) blocks hardware threads dynamically on cores inside GPU. By considering the properties of GPU, this algorithm allocates the maximal number of processing cores to each Stream Multi-Processor (SM) as number of threads in a block. If the number of nodes in the graph is smaller than all physical cores on GPU, number of threads per block Is equal to the ratio number of graph nodes over the number of SMs. Results: The implementation results demonstrated that the proposed algorithm is able to decrease the run time by 15% in comparison with the best past method in the large-scale graph. Conclusion: We have introduced DCLM algorithm based on GPU that accelerates Louvain community detection algorithm. Dynamic allocation of threads to each block has a significant effect on the reduction of algorithm execution time. However, incrementing the number of threads per block alone does not result to acceleration the speed of calculations.
کلیدواژه‌ها
Louvain Algorithm؛ Community Detection؛ Modularity؛ Hardware Thread

مراجع
[1] M. Guendouz, A. Amine, R. M. Hamou, "Discrete modified fireworks algorithm for community detection in complex networks," Appl. Intell., 46: 373–385, 2017. [2] D. Sudhakaran, S. Renjith, "Survey of community detection algorithms to identify the best community in real-time networks," Int. J. Sci. Eng. Appl. Sci., (IJSEAS), 2: 529-533, 2016. [3] S. Fortunato, "Community detection in graphs," Phys. Rep., 486: 75-174, 2010. [4] M.E.J. Newman, M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E, 69: 026113, 2004. [5] A. Clauset, M.E.J. Newman, C. Moore, "Finding community structure in very large networks," Phys. Rev. E, 70: 066111, 2004. [6] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, D. Wagner, "On modularity clustering," IEEE Trans. Knowl. Data Eng., 20: 172-188, 2008. [7] M. Faysal, S. Arifuzzaman, "Distributed community detection in large networks using an information-theoretic approach," in Proc. 2019 IEEE International Conference on Big Data (Big Data): 4773-4782, 2019. [8] Q. Ni, J. Guo, W. Wu, C. Huang, "Continuous inuence-based community partition for social networks," arXiv:2002.08554v1 [cs.SI] 20 Feb 2020, 2020. [9] V.D. Blondel, J.L. Guillaume, R. Lambiotte, E. Lefebvre, "Fast unfolding of communities in large networks," J. Stat. Mech., 10: P10008, 2008. [10] E. Moradi, M. Fazlali, H. Tabatabaee Malazi, "Fast parallel community detection algorithm based on modularity," in proc. 2015 18th CSI International Symposium on Computer Architecture and Digital Systems (CADS), IEEE, 2015. [11] C.L. Staudt, H. Meyerhenke, "Engineering parallel algorithms for community detection in massive networks," in proc. 42nd International Conference on Parallel Processing, 2013. [12] C.Y. Cheong, H.P. Huynh, D. Lo, R.S.M. Goh, "Hierarchical parallel algorithm for modularity-based community detection using GPUs," in proc. 19th International Conference on Parallel Processing, Euro-Par’13: 775–787, 2013. [13] H. Lu, M. Halappanavar, A. Kalyanaraman, "Parallel heuristics for scalable community detection," Parallel Comput., 47: 9–37, 2015. [14] M. Fazlali, E. Moradi, H. Tabatabaee Malazi, "Adaptive parallel Louvain community detection on a multicore platform," Microprocess. Microsyst., 54: 26–34, 2017. [15] J. Zeng, H. Yu, "A scalable distributed louvain algorithm for large-scale graph community detection," in proc. 2018 IEEE International Conference on Cluster Computing (CLUSTER), 2018. [16] R. Forster, "Louvain community detection with parallel heuristics on GPUs," presented at the IEEE 20th Jubilee International Conference on Intelligent Engineering Systems (INES), Budapest, Hungary, 2016. [17] L. Zhang, M. Wahib, H. Zhang, S. Matsuoka, "A study of single and multi-device ynchronization methods in nvidia GPUs," in proc. IEEE International Parallel & Distributed Processing Symposium 2020. [18] Y. Wang, M. Guo, Y. Zhao, J. Jiang, "GPUs‑RRTMG_LW: high-efficient and scalable computing for a longwave radiative transfer model on multiple GPUs," J. Supercomput. 77: 4698–4717, 2020. [19] M.E.J. Newman, "Modularity and community structure in networks," in proc. Natl. Acad. Sci, 103: 8577–8582, 2006. [20] D. LaSalle, G. Karypis, "Multi-threaded modularity based graph clustering using the multilevel paradigm," J. Parallel Distrib. Comput., 76: 66-80, 2015. [21] Y. Guo, Z. Huang, Y. Kong, Q. Wang, "Modularity and mutual information in networks: two sides of the same coin," arXiv preprint arXiv:2103.02542, 2021. [22] C.L. Staudt, H. Meyerhenke, "Engineering parallel algorithms for community detection in massive networks," IEEE Trans. Parallel Distrib. Syst., 27: 171–184, 2016. [23] U.N. Raghavan, R. Albert, S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Phys. Rev. E, 76: 036106, 2007. [24] G.S. Carnivali, A.B. Vieira, A. Ziviani, P.A.A. Esquef, "CoVeC: Coarse-Grained vertex clustering for efficient community detection in sparse complex networks," Inf. Sci., 522: 180-192, 2020. [25] X. Que, F. Checconi, F. Petrini, J. Gunnels, "Scalable community detection with louvain algorithm," in proc. 2015 IEEE 29th International Parallel and Distributed Processing Symposium, 2015. [26] J. Zeng, H. Yu, "Effectively unified optimization for large-scale graph community detection," in proc. 2019 IEEE International Conference on Big Data (Big Data): 475-482, 2019. [27] W. Fang, X. Wang, L. Liu, Z. Wu, S. Tang, Z. Zheng, "Community detection through vector-label propagation algorithms," arXiv preprint arXiv:2011.08342, 2020. [28] R.P. Sarmento, "Density-based community detection/optimization" arXiv preprint arXiv: 1904.12593, 2019. [29] J. Huang, T. Zhang, W. Yu, J. Zhu, E. Cai, "Community detection based on modularized deep nonnegative matrix factorization," Int. J. Pattern Recognit Artif Intell., 35(2): 21590061-215900617, 2020. [30] S. Souravlas, A. Sifaleras, S. Katsavounis, "Hybrid CPU-GPU community detection in weighted networks," IEEE Access, 8: 57527 – 57551, 2020. [31] J. Shao, Z. Han, Q. Yang, T. Zhou, "Community detection based on distance dynamics," in proc. 21th ACM SIGKDD international conference on knowledge discovery and data mining. New York: ACM: 1075-1084, 2015. [32] J. Zhu, X. Ren, P. Ma, K. Gao, "Community detection on complex networks based on a new centrality indicator and a new modularity function," arXiv preprint arXiv:2003.13609, 2020. [33] I. Gutiérrez, D. Gómez, J. Castro, R. Espínola, "A new community detection algorithm based on fuzzy measures," in Proc. International Conference on Intelligent and Fuzzy Systems: 133-140, 2019. [34] P. Miasnikof, A.Y. Shestopaloff, A.J. Bonner, "A density-based statistical analysis of graph clustering algorithm performance," J. Complex Networks, 8(3): 1-33, 2020. [35] D. Jin, B. Zhang, Y. Song, D. He, Z. Feng, S. Chen, W. Li, K. Musial, "ModMRF: A modularity-based Markov Random Field method for community detection," Neurocomputing, 405: 218-228, 2020. [36] G. Konstantinos, M. Christos, P. Georgios, "A distributed hybrid community detection methodology for social networks," Algorithms, 12(8): 175, 2019. [37] J.O. Palacio-Niño, F. Berzal "On the use of local structural properties for improving the efficiency of hierarchical community detection methods," arXiv preprint arXiv:2009.06798, 2020. [38] A. Mahabadi, M. Hosseini, "SLPA-based parallel overlapping community detection approach in large complex social networks," Multimed. Tool. Appl., 80: 6567–6598, 2021. [39] M.d. Naim, F. Manne, M. Halappanavar, A. Tumeo, "Community detection on the GPU," in proc. 2017 IEEE International Parallel and Distributed Processing Symposium, 2017. [40] M. Mohammadi, M. Fazlali, M. Hosseinzadeh, "Accelerating Louvain community detection algorithm on graphic processing unit," J. Supercomput., 77: 6056–6077, 2021. [41] M.E.J. Newman, "Fast algorithm for detecting community structure in networks," Phys. Rev. E, 69: 066133, 2004.
آمار تعداد مشاهده مقاله: 995 تعداد دریافت فایل اصل مقاله: 996

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

آمار

Parallel Louvain Community Detection Algorithm Based on Dynamic Thread Assignment on Graphic Processing Unit