nach oben

The Journal of Supercomputing

Erschienen in:

18.11.2020

Accelerating Louvain community detection algorithm on graphic processing unit

verfasst von: Maryam Mohammadi, Mahmood Fazlali, Mehdi Hosseinzadeh

Erschienen in: The Journal of Supercomputing | Ausgabe 6/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Louvain community detection algorithm is a hierarchal clustering method categorized in the NP-hard problem. Its execution time to find communities in large graphs is, therefore, a challenge. Parallelization is an effective solution for amortizing Louvain's execution time. In this paper, we propose an adaptive CUDA Louvain method (ACLM) algorithm that benefits from the graphic processing unit (GPU). ACLM uses the shared memory in GPU, as well as the optimal number of threads in the GPU blocks. These features minimize parallelization overhead and accelerate the calculation of modularity parameters. The proposed algorithm allocates threads to each block based on the number of required streaming multiprocessors (SMs) and warps on GPU. The implementation results show that ACLM can effectively accelerate the execution time by 77% compared to the competitive method in the large graph benchmarks.

Vorheriger Artikel Performance optimization in delay tolerant networks using backtracking algorithm for fully credits distribution to contrast selfish nodes

Nächster Artikel A cluster-tree-based energy-efficient routing protocol for wireless sensor networks with a mobile sink

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Guendouz M, Amine A, Hamou RM (2017) discrete modified fireworks algorithm for community detection in complex networks. Appl Intell 46:373–385. https://doi.org/10.1007/s10489-016-0840-9CrossRef

Fortunato S (2010) Community detection in graphs. Phys Rep 486:75–174. https://doi.org/10.1016/j.physrep.2009.11.002MathSciNetCrossRef

Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69:026113. https://doi.org/10.1103/PhysRevE.69.026113CrossRef

Clauset A, Newman MEJ, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70:066111. https://doi.org/10.1103/PhysRevE.70.066111CrossRef

Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, Wagner D (2008) On modularity clustering. IEEE Trans Knowl Data Eng 20:172–188. https://doi.org/10.1109/TKDE.2007.190689CrossRefMATH

Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech 10:P10008. https://doi.org/10.1088/1742-5468/2008/10/P10008CrossRefMATH

Moradi E, Fazlali M, Tabatabaee Malazi H (2015) Fast parallel community detection algorithm based on modularity. In: 2015 18th CSI international symposium on computer architecture and digital systems (CADS). IEEE. https://doi.org/10.1109/CADS.2015.7377794

Staudt CL, Meyerhenke H (2013) Engineering parallel algorithms for community detection in massive networks. In: Proceedings of the 42nd International Conference on Parallel Processing. https://doi.org/10.1109/ICPP.2013.27

Cheong CY, Huynh HP, Lo D, Goh RSM (2013) Hierarchical parallel algorithm for modularity-based community detection using GPUs. In: Proceedings of the 19th International Conference on Parallel Processing, Euro-Par'13. Springer, Berlin, pp 775–787. https://doi.org/10.1007/978-3-642-40047-6_77

10.

Lu H, Halappanavar M, Kalyanaraman A (2015) Parallel heuristics for scalable community detection. Parallel Comput 47:19–37. https://doi.org/10.1016/j.parco.2015.03.003MathSciNetCrossRef

11.

Fazlali M, Moradi E, Tabatabaee Malazi H (2017) Adaptive parallel Louvain community detection on a multicore platform. Microprocess Microsyst 54:26–34. https://doi.org/10.1016/j.micpro.2017.08.002CrossRef

12.

Zeng J, Yu H (2018) A scalable distributed Louvain algorithm for large-scale graph community detection. In: 2018 IEEE International Conference on Cluster Computing (CLUSTER). https://doi.org/10.1109/CLUSTER.2018.00044

13.

Forster R (2016) Louvain community detection with parallel heuristics on GPUs. In: IEEE 20th Jubilee International Conference on Intelligent Engineering Systems (INES), Budapest, Hungary, 30 June–2 July. https://doi.org/10.1109/INES.2016.7555126

14.

Erdos P, Renyi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17–61MathSciNetMATH

15.

Rezapoor Mirsaleh M, Meybodi MR (2016) A Michigan memetic algorithm for solving the community detection problem in complex network. Neurocomputing 214:535–545. https://doi.org/10.1016/j.neucom.2016.06.030CrossRef

16.

Newman MEJ (2006) Modularity and community structure in networks. Proc Natl Acad Sci 103:8577–8582. https://doi.org/10.1073/pnas.0601602103CrossRef

17.

Holmström E, Bock N, Brännlund J (2009) Modularity density of network community divisions. Physica D 238:1161–1167. https://doi.org/10.1016/j.physd.2009.03.015MathSciNetCrossRefMATH

18.

Zhao Y (2017) A survey on theoretical advances of community detection in networks. WIREs Comput Stat e1403:1–13. https://doi.org/10.1002/wics.1403CrossRef

19.

Khan BS, Niazi MA (2017) Network community detection: a review and visual survey. arXiv preprint: arXiv:1708.00977

20.

Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2017) Metrics for community analysis: a survey. ACM Comput Surv 50:1–37. https://doi.org/10.1145/3091106CrossRef

21.

Ghosh S, Halappanavar M, Tumeo A, Kalyanaraman A, Lu H, Chavarria-Miranda D, Khan A, Gebremedhin A (2018) Distributed louvain algorithm for graph community detection. In: 2018 IEEE international parallel and distributed processing symposium (IPDPS), pp 885–895. https://doi.org/10.1109/IPDPS.2018.00098

22.

Ozaki N, Tezuka H, Inaba M (2016) A simple acceleration method for the Louvain algorithm. Int J Comput Electr Eng 8:207–218. https://doi.org/10.17706/ijcee.2016.8.3.207-218CrossRef

23.

Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78:046110. https://doi.org/10.1103/PhysRevE.78.046110CrossRef

24.

Gutiérrez I, Gómez D, Castro J, Espínola R (2019) A new community detection algorithm based on fuzzy measures. In: International Conference on Intelligent and Fuzzy Systems, pp 133–140. https://doi.org/10.1007/978-3-030-23756-1_18

25.

Traag VA (2015) Faster unfolding of communities: speeding up the Louvain algorithm. Phys Rev E 92:032801. https://doi.org/10.1103/PhysRevE.92.032801CrossRef

26.

Carnivali GS, Vieira AB, Ziviani A, Esquef PAA (2020) CoVeC: coarse-grained vertex clustering for efficient community detection in sparse complex networks. Inf Sci. https://doi.org/10.1016/j.ins.2020.03.004MathSciNetCrossRef

27.

Bhowmick S, Srinivasan S (2013) A template for parallelizing the louvain method for modularity maximization. Dyn Complex Netw 2:111–124. https://doi.org/10.1007/978-1-4614-6729-8_6CrossRef

28.

Staudt CL, Meyerhenke H (2016) Engineering parallel algorithms for community detection in massive networks. Parallel Distrib Syst IEEE Trans 27:171–184. https://doi.org/10.1109/TPDS.2015.2390633CrossRef

29.

Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106. https://doi.org/10.1103/PhysRevE.76.036106CrossRef

30.

Shao J, Han Z, Yang Q, Zhou T (2015) Community detection based on distance dynamics. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, pp 1075–1084. http://dx.doi.org/https://doi.org/10.1145/2783258.2783301

31.

Naim Md, Manne F, Halappanavar M, Tumeo A (2017) Community detection on the GPU. In: 2017 IEEE international parallel and distributed processing symposium. https://doi.org/10.1109/IPDPS.2017.16

32.

Newman MEJ (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69:066133. https://doi.org/10.1103/PhysRevE.69.066133CrossRef

33.

Zhang L, Wahib M, Zhang H, Matsuoka S (2020) A study of single and multi-device synchronization methods in Nvidia GPUs. In: IEEE international parallel & distributed processing symposium 2020.

Titel: Accelerating Louvain community detection algorithm on graphic processing unit
verfasst von: Maryam Mohammadi
Mahmood Fazlali
Mehdi Hosseinzadeh
Publikationsdatum: 18.11.2020
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 6/2021
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-020-03510-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 6/2021

A new deep intuitionistic fuzzy time series forecasting method based on long short-term memory

Improving Clairvoyant: reduction algorithm resilient to imbalanced process arrival patterns

New set of adapted Gegenbauer–Chebyshev invariant moments for image recognition and classification

Multi-period traffic on elastic optical networks planning: alleviating the capacity crunch

Query processing optimization in broadcasting XML data in mobile communications

Error detection of arithmetic expressions