PERTANIKA JOURNAL OF SCIENCE AND TECHNOLOGY

 

e-ISSN 2231-8526
ISSN 0128-7680

Home / Regular Issue / JST Vol. 32 (3) Apr. 2024 / JST-4622-2023

 

Identifying Communities with Modularity Metric Using Louvain and Leiden Algorithms

Siti Haryanti Hairol Anuar, Zuraida Abal Abas, Norhazwani Md Yunos, Mohd Fariduddin Mukhtar, Tedy Setiadi and Abdul Samad Shibghatullah

Pertanika Journal of Science & Technology, Volume 32, Issue 3, April 2024

DOI: https://doi.org/10.47836/pjst.32.3.16

Keywords: Community detection, Leiden, Louvain, modularity, network structure

Published on: 24 April 2024

Over the past 20 years, there has been a significant increase in publication in complex network analysis research, especially in community detection. Many methods were proposed to identify community structure. Each community identification algorithm has strengths and weaknesses due to the complexity of information. Among them, the optimisation methods are widely focused on. This paper focuses on an empirical study of two community detection algorithms based on agglomerative techniques using modularity metric: Louvain and Leiden. In this regard, the Louvain algorithm has been shown to produce a bad connection in the community and disconnected when executed iteratively. Therefore, the Leiden algorithm is designed to successively resolve the weaknesses. Performance comparisons between the two and their concept were summarised in detail, as well as the step-by-step learning process of the state-of-the-art algorithms. This study is important and beneficial to the future study of interdisciplinary data sciences of network analysis. First, it demonstrates that the Leiden method outperformed the Louvain algorithm in terms of modularity metric and running time. Second, the paper displays the use of these two algorithms on synthetic and real networks. The experiment was successful as it identified better performance, and future work is required to confirm and validate these findings.

  • Anuar, S. H. H., Abas, Z. A., Yunos, N. M., Mohd Zaki, N. H., Hashim, N. A., Mokhtar, M. F., Asmai, S. A., Abidin, Z. Z., & Nizam, A. F. (2021). Comparison between Louvain and Leiden algorithm for network structure: A review. Journal of Physics: Conference Series, 2129(1), Article 012028. https://doi.org/10.1088/1742-6596/2129/1/012028

  • Blondel, V. D., Guillaume, J. L. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), 1–12. https://doi.org/10.1088/1742-5468/2008/10/P10008

  • Chatterjee, S., & Sanjeev, B. S. (2023). Community detection in Epstein-barr virus associated carcinomas and role of tyrosine kinase in etiological mechanisms for oncogenesis. Microbial Pathogenesis, 180, Article 106115. https://doi.org/10.1016/j.micpath.2023.106115

  • Cheng, J., Su, X., Yang, H., Li, L., Zhang, J., Zhao, S., & Chen, X. (2019). Neighbor similarity based agglomerative method for community detection in networks. Complexity, 2019, Article 8292485. https://doi.org/10.1155/2019/8292485

  • Chessa, A., D’Urso, P., De Giovanni, L., Vitale, V., & Gebbia, A. (2023). Complex networks for community detection of basketball players. Annals of Operations Research, 325(1), 363–389. https://doi.org/10.1007/s10479-022-04647-x

  • Chunaev, P. (2020). Community detection in node-attributed social networks: A survey. Computer Science Review, 37, Article 100286. https://doi.org/10.1016/j.cosrev.2020.100286

  • Ding, R., Fu, J., Du, Y., Du, L., Zhou, T., Zhang, Y., Shen, S., Zhu, Y., & Chen, S. (2022). Structural evolution and community detection of china rail transit route network. Sustainability, 14(19), Article 12342. https://doi.org/10.3390/su141912342

  • Evans, J. C., Lindholm, A. K., & König, B. (2022). Family dynamics reveal that female house mice preferentially breed in their maternal community. Behavioral Ecology, 33(1), 222–232. https://doi.org/10.1093/beheco/arab128

  • Gilad, G., & Sharan, R. (2023). From Leiden to Tel-Aviv University (TAU): Exploring clustering solutions via a genetic algorithm. PNAS Nexus, 2(6), Article pgad180. https://doi.org/10.1093/pnasnexus/pgad180

  • Han, Z., Mo, R., Yang, H., & Hao, L. (2018). Module partition for mechanical CAD assembly model based on multi-source correlation information and community detection. Journal of Advanced Mechanical Design, Systems, and Manufacturing, 12(1), Article JAMDSM0023. https://doi.org/10.1299/jamdsm.2018jamdsm0023

  • Irsyad, A., & Rakhmawati, N. A. (2019). Community detection in twitter based on tweets similarities in Indonesian using cosine similarity and Louvain Algorithms. Register: Jurnal Ilmiah Teknologi Sistem Informasi, 6(1), Article 22. https://doi.org/10.26594/register.v6i1.1595

  • Jin, D., Li, R., & Xu, J. (2020). Multiscale community detection in functional brain networks constructed using dynamic time warping. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 28(1), 52–61. https://doi.org/10.1109/TNSRE.2019.2948055

  • Kabir, K., Hassan, L., Rajabi, Z., Akhter, N., & Shehu, A. (2019). Graph-based community detection for decoy selection in template-free protein structure prediction. Molecules, 24(5), Article 854. https://doi.org/10.3390/molecules24050854

  • Karyotis, V., Tsitseklis, K., Sotiropoulos, K., & Papavassiliou, S. (2018). Big data clustering via community detection and hyperbolic network embedding in IoT applications. Sensors, 18(4), Article 1205. https://doi.org/10.3390/s18041205

  • Kramer, J., Boone, L., Clifford, T., Bruce, J., & Matta, J. (2020). Analysis of medical data using community detection on inferred networks. IEEE Journal of Biomedical and Health Informatics, 24(11), 3136–3143. https://doi.org/10.1109/JBHI.2020.3003827

  • Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: A comparative analysis. Physical Review E, 80(5), Article 056117. https://doi.org/10.1103/PhysRevE.80.056117

  • LaRock, T., Sakharov, T., Bhadra, S., & Eliassi-Rad, T. (2020). Understanding the limitations of network online learning. Applied Network Science, 5(1), Article 60. https://doi.org/10.1007/s41109-020-00296-w

  • Li, S., Zhao, C., Li, Q., Huang, J., Zhao, D., & Zhu, P. (2023). BotFinder: A novel framework for social bots detection in online social networks based on graph embedding and community detection. World Wide Web, 26(4), 1793–1809. https://doi.org/10.1007/s11280-022-01114-2

  • Needham, M., & Hodler, A. E. (2021). Graph algorithms Practical examples in Apache Spark and Neo4j. O’reilly. O’Reilly Media.

  • Nallusamy, K., & Easwarakumar, K. S. (2023). Classifying schizophrenic and controls from fMRI data using graph theoretic framework and community detection. Network Modeling Analysis in Health Informatics and Bioinformatics, 12(1), Article 19. https://doi.org/10.1007/s13721-023-00415-4

  • Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 69(2), Article 026113. https://doi.org/10.1103/PhysRevE.69.026113

  • Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582. https://doi.org/10.1073/pnas.0601602103

  • Nicolini, C., Bordier, C., & Bifone, A. (2017). Community detection in weighted brain connectivity networks beyond the resolution limit. NeuroImage, 146, 28–39. https://doi.org/10.1016/j.neuroimage.2016.11.026

  • Park, J. H., & Kwon, H. Y. (2022). Cyberattack detection model using community detection and text analysis on social media. ICT Express, 8(4), 499–506. https://doi.org/10.1016/j.icte.2021.12.003

  • Peeples, M. A., & J. Bischoff, R. (2023). Archaeological networks, community detection, and critical scales of interaction in the U.S. Southwest/Mexican Northwest. Journal of Anthropological Archaeology, 70, Article 101511. https://doi.org/10.1016/j.jaa.2023.101511

  • Rahiminejad, S., Maurya, M. R., & Subramaniam, S. (2019). Topological and functional comparison of community detection algorithms in biological networks. BMC Bioinformatics, 20(1), 1-25. https://doi.org/10.1186/s12859-019-2746-0

  • Singhal, A., Cao, S., Churas, C., Pratt, D., Fortunato, S., Zheng, F., & Ideker, T. (2020). Multiscale community detection in Cytoscape. PLOS Computational Biology, 16(10), Article e1008239. https://doi.org/10.1371/journal.pcbi.1008239

  • Torene, S., Follmann, A., Teague, T., Chang, P., & Howald, B. (2022). Automated hashtag hierarchy generation using community detection and the Shannon Diversity Index, with applications to Twitter and Parler. International Journal of Semantic Computing, 16(04), 473–496. https://doi.org/10.1142/S1793351X22500052

  • Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: Guaranteeing well-connected communities. Scientific Reports, 9(1), Article 5233. https://doi.org/10.1038/s41598-019-41695-z

  • Ullah, A., Wang, B., Sheng, J. F., Long, J., Khan, N., & Ejaz, M. (2022). A novel relevance-based information interaction model for community detection in complex networks. Expert Systems with Applications, 196, Article 116607. https://doi.org/10.1016/j.eswa.2022.116607

  • Wang, C., & Wang, F. (2022). GIS-automated delineation of hospital service areas in Florida: From Dartmouth method to network community detection methods. Annals of GIS, 28(2), 93–109. https://doi.org/10.1080/19475683.2022.2026470

  • Wang, J., Zhou, C., Rong, J., Liu, S., & Wang, Y. (2022). Community-detection-based spatial range identification for assessing bilateral jobs-housing balance: The case of Beijing. Sustainable Cities and Society, 87, Article 104179. https://doi.org/10.1016/j.scs.2022.104179

  • Xie, L., Cui, J., Qin, Y., & Qiu, L. (2022). Analysis of deformation characteristics of reverse slope under the influence of reservoir water based on community detection. Environmental Earth Sciences, 81(4), Article 110. https://doi.org/10.1007/s12665-022-10252-9

  • Yuan, Q., & Liu, B. (2021). Community detection via an efficient nonconvex optimization approach based on modularity. Computational Statistics and Data Analysis, 157, Article 107163. https://doi.org/10.1016/j.csda.2020.107163

  • Zu, J., Hu, G., Yan, J., & Tang, S. (2021). A community detection based approach for service function chain online placement in data center network. Computer Communications, 169, 168–178. https://doi.org/10.1016/j.comcom.2021.01.014