Community Detection Based on the LO-WT Algorithm
Received: 16 February 2025 | Revised: 18 April 2025, 19 May 2025, and 15 June 2025 | Accepted: 3 July 2025 | Online: 6 October 2025
Corresponding author: Zainab Falah Hasan
Abstract
Community detection is an important and difficult task in network analysis. This study proposes the Louvain algorithm combined with the Walk-Trap algorithm (LO-WT), leveraging structural and path-based similarities to enhance the detection accuracy. The structural similarity between nodes is a sensitive issue and essential for community identification. First, computing the similarity between the nodes is applied to determine the weights assigned to the edges connecting them. On the other hand, this information is used to guide the walking process in the Walk-Trap algorithm to obtain the trajectories for each node. Then, the similarity is calculated based on the Jaccard similarity among the trajectories. This builds a similarity matrix, which is then used to create a new graph as a weighted network based on a certain threshold depending on the network's complexity. The weights represent the degree of similarity between the nodes. The Louvain algorithm can then be effectively applied to the new graph to identify the communities by maximizing the modularity rather than using agglomerative clustering in the Walk-Trap algorithm. This approach leverages the efficiency of the algorithm to uncover the meaningful community structures within the data. Four real and synthetic networks are used to validate the results, and the algorithm is evaluated against several algorithms, including baseline and state-of-the-art methods. Critical parameters, such as the structure-based similarity threshold (0.1–0.3) and trajectory length (2–4) are carefully adjusted to optimize the performance. The results show that LO-WT significantly outperforms recent related methods and traditional algorithms. Specifically, it outperforms the Louvain algorithm in terms of Normalized Mutual Information (NMI) and is competitive regarding modularity. Additionally, it surpasses related work by achieving higher performance across all four real-world networks: Karate (0.41), Dolphin (0.52), Football (0.60), and Facebook (0.83). Furthermore, LO-WT can exhibit high conductivity and density, demonstrating its robust performance. Overall, the LO-WT algorithm demonstrates its effectiveness for accurate community detection.
Keywords:
Louvain algorithm, Walk-Trap algorithm, Jaccard similarity, random walksDownloads
References
Y. Chang, H. Ma, L. Chang, and Z. Li, "Community detection with attributed random walk via seed replacement," Frontiers of Computer Science, vol. 16, no. 5, Jan. 2022, Art. no. 165324.
F. Belloum, L. Houichi, and M. Kherouf, "The Performance of Spectral Clustering Algorithms on Water Distribution Networks: Further Evidence," Engineering, Technology & Applied Science Research, vol. 12, no. 4, pp. 9056–9062, Aug. 2022.
Murniyati, A. B. Mutiara, S. Wirawan, T. Yusnitasari, and D. Anggraini, "Expanding Louvain Algorithm for Clustering Relationship Formation," International Journal of Advanced Computer Science and Applications (IJACSA), vol. 14, no. 1, pp. 701–708, 31 2023.
B. Yao, J. Zhu, P. Ma, K. Gao, and X. Ren, "A Constrained Louvain Algorithm with a Novel Modularity," Applied Sciences, vol. 13, no. 6, Mar. 2023, Art. no. 40445.
J. Zhang, J. Fei, X. Song, and J. Feng, "An Improved Louvain Algorithm for Community Detection," Mathematical Problems in Engineering, vol. 2021, no. 1, Nov. 2021, Art. no. 1485592.
P. Pons and M. Latapy, "Computing Communities in Large Networks Using Random Walks," in Computer and Information Sciences - ISCIS 2005: 20th International Symposium, Istanbul, Turkey, 2005, pp. 284–293.
M. Rosvall, D. Axelsson, and C. T. Bergstrom, "The map equation," The European Physical Journal Special Topics, vol. 178, no. 1, pp. 13–23, Nov. 2009.
A. Kosmatopoulos, K. Loumponias, D. Chatzakou, T. Tsikrika, S. Vrochidis, and I. Kompatsiaris, "Random-Walk Graph Embeddings and the Influence of Edge Weighting Strategies in Community Detection Tasks," in Proceedings of the 2021 Workshop on Open Challenges in Online Social Networks, Virtual Event, Ireland, 2021, pp. 9–13.
E. A. Abbas and H. N. Nawaf, "Improving Louvain Algorithm by Leveraging Cliques for Community Detection," in 2020 International Conference on Computer Science and Software Engineering, Duhok, Iraq, 2020, pp. 244–248.
M. Milano, P. Cinaglia, P. H. Guzzi, and M. Cannataro, "A novel local alignment algorithm for Multilayer networks," Informatics in Medicine Unlocked, vol. 44, Jan. 2024, Art. no. 101425.
A. Aldabobi, A. Sharieh, and R. Jabri, "An Improved Louvain Algorithm based on Node Importance for Community Detection," Journal of Theoretical and Applied Information Technology, vol. 100, no. 23, pp. 7055–7063, Dec. 2022.
A. Ballal, W. B. Kion-Crosby, and A. V. Morozov, "Network community detection and clustering with random walks," Physical Review Research, vol. 4, no. 4, Nov. 2022, Art. no. 043117.
Y. Xu, T. Ren, and S. Sun, "Community Detection Based on Node Influence and Similarity of Nodes," Mathematics, vol. 10, no. 6, Mar. 2022, Art. no. 970.
R. Bhattacharya, N. K. Nagwani, and S. Tripathi, "A community detection model using node embedding approach and graph convolutional network with clustering technique," Decision Analytics Journal, vol. 9, Dec. 2023, Art. no. 100362.
R. George, K. Shujaee, M. Kerwat, Z. Felfli, D. Gelenbe, and K. Ukuwu, "A Comparative Evaluation of Community Detection Algorithms in Social Networks," Procedia Computer Science, vol. 171, pp. 1157–1165, Jan. 2020.
D. D. Hieu and P. T. Ha Duong, "Detecting communities in large networks using the extended Walktrap algorithm," in 2022 RIVF International Conference on Computing and Communication Technologies, Ho Chi Minh City, Vietnam, 2022, pp. 100–105.
W. W. Zachary, "An Information Flow Model for Conflict and Fission in Small Groups," Journal of Anthropological Research, vol. 33, no. 4, pp. 452–473, Dec. 1977.
D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations," Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396–405, Sept. 2003.
M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical Review E, vol. 69, no. 2, Feb. 2004, Art. no. 026113.
J. McAuley and J. Leskovec, "Learning to discover social circles in ego networks," in Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1, Red Hook, NY, USA, 2012, pp. 539–547.
M. Ning, J. Gong, and Z. Zhou, "A Novel Label Propagation Method for Community Detection Based on Game Theory," International Journal of Advanced Computer Science and Applications (IJACSA), vol. 14, no. 5, pp. 924–938, May 2023.
A. Kanavos, Y. Voutos, F. Grivokostopoulou, and P. Mylonas, "Evaluating Methods for Efficient Community Detection in Social Networks," Information, vol. 13, no. 5, May 2022, Art. no. 209.
K. R. Žalik and M. Žalik, "Density-Based Entropy Centrality for Community Detection in Complex Networks," Entropy, vol. 25, no. 8, Aug. 2023, Art. no. 1196.
J. Yao and B. Liu, "Community-Detection Method of Complex Network Based on Node Influence Analysis," Symmetry, vol. 16, no. 6, June 2024, Art. no. 754.
A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, "Finding Statistically Significant Communities in Networks," Plos One, vol. 6, no. 4, Apr. 2011, Art. no. e18961.
M. E. J. Newman, "Fast algorithm for detecting community structure in networks," Physical Review E, vol. 69, no. 6, June 2004, Art. no. 066133.
Downloads
How to Cite
License
Copyright (c) 2025 Zainab Falah Hasan, Huda Naji Nawaf
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
