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

  • سال انتشار: 1401
  • محل انتشار: مجله نوآوری های مهندسی برق و کامپیوتر، دوره: 10، شماره: 1
  • کد COI اختصاصی: JR_JECEI-10-1_007
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 301
دانلود فایل این مقاله

نویسندگان

M. Mohammadi

Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

M. Fazlali

Department of Computer and Data Sciences, Faculty of Mathematical Sciences, Shahid Beheshti University, Tehran, Iran

M. Hosseinzadeh

Mental Health Research Center, Psychosocial Health Research Institute, Iran University of Medical Sciences, Tehran, Iran

چکیده

kground 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 ۱۵% 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

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.