Increasing Community Detection Accuracy in Social Networks using Improved Label Diffusion Approach

Subject Areas : New technologies in distributed systems and algorithmic computing

Nafiseh Afkhami ¹ , Nazbanou Farzaneh Bahalgardi ² , Hassan Shakeri ^{3 *}

1 - Department of Computer Engineering, Imam Reza International University, Mashhad, Iran
2 - Department of Computer Engineering, Imam Reza International University, Mashhad, Iran
3 - Department of Computer Engineering, Mashhad Branch, Islamic Azad University, Mashhad, Iran

Received: 2024-11-21 Accepted : 2025-06-01 Published : 2025-06-07

Keywords: Community detection, Social network modeling, Label propagation algorithm, Clustering,

Abstract :

Detecting communities in large networks is an important challenge in social network analysis, and providing an algorithm with optimal accuracy and efficiency for extracting communities is very important. There are different approaches to identify communities in social networks, including methods based on classical clustering, algorithms based on criteria of similarity in features, methods based on finding subgraphs with a lot of internal communication, as well as a label propagation approach. In the label propagation approach, first, the most important vertices of the network are determined based on a series of importance and centrality criteria, and different community labels are assigned to them. Then the label of each of these vertices is propagated to the neighboring vertices and around them. The aim of this research is to improve a community detection algorithm called LBLD. This algorithm first determines five percent of the most important network vertices based on a similarity criterion. Then, with a balanced approach, communities are developed both from the center and from the borders, and finally a phase of integration is implemented so that small communities are combined with each other and form desirable communities. Our proposed idea uses a measure inspired by the concept of h-index to improve the accuracy of community detection. In such a way that subgraphs are identified as communities that have at least p percent of vertices with at least degree k. The accuracy and efficiency of the proposed solution have been evaluated by applying it to known data sets in this field and it shows a significant improvement compared to existing similar methods.

References:

[1] H. Roghani, and A. Bouyer, "A Fast Local Balanced Label Diffusion Algorithm for Community Detection in Social Networks," IEEE Transactions on Knowledge and Data Engineering • January 2022.
[2] K. Berahmand, A. Bouyer, and M. Vasighi, "Community Detection in Complex Networks by Detecting and Expanding Core Nodes Through Extended Local Similarity of Nodes," IEEE Transactions on Computational Social Systems, vol. 5, no. 4, pp. 1021-1033, 2018, doi: 10.1109/TCSS.2018.2879494.
[3] A. Bouyer and H. Roghani, "LSMD: A fast and robust local community detection starting from low degree nodes in social networks," Future Generation Computer Systems, vol. 113, pp. 41-57, 2020/12/01/ 2020, doi: https://doi.org/10.1016/j.future.2020.07.011.
[4] Adamic LA, Glance N, editors. The political blogosphere and the 2004 US election: divided they blog. Proceedings of the 3rd international workshop on Link discovery; 2005.
[5] Z. Sun et al., "Community detection based on the Matthew effect," Knowledge-Based Systems, vol. 205, p. 106256, 2020.
[6] S. Aghaalizadeh, S. T. Afshord, A. Bouyer, and B. Anari, "A three-stage algorithm for local community detection based on the high node importance ranking in social networks," Physica A: Statistical Mechanics and its Applications, vol. 563, p. 125420, 2021.
[7] M. Zarezade, E. Nourani, and A. Bouyer, "Community detection using a new node scoring and synchronous label updating of boundary nodes in social networks," Journal of AI and Data Mining, vol. 8, no. 2, pp. 201-212, 2020.
[8] S. Taheri and A. Bouyer, "Community Detection in Social Networks Using Affinity Propagation with Adaptive Similarity Matrix," Big Data, vol. 8, no. 3, pp. 189-202, 2020.
[9] A. Clauset, M. E. Newman, and C. Moore, “Finding community structure in very large networks,” Physical Review E, vol. 70, no. 6, p. 066111, 2004.
[10] Yang Z, Algesheimer R, Tessone CJ. A comparative analysis of community detection algorithms on artificial networks. Scientific reports. 2016;6(1):30750.
[11] F. D. Zarandi and M. K. Rafsanjani, “Community detection in complex networks using structural [16]similarity,” Physica A: Statistical Mechanics and its Applications, vol. 503, pp. 882–891, 2018.
[12] M’barek MB, Hmida SB, Borgi A, Rukoz M. GA-PPI-Net Approach vs Analytical Approaches for Community Detection in PPI Networks. Procedia Computer Science. 2021;192:903-12.
[13] Patil SV, Kulkarni DB, editors. Graph partitioning using heuristic Kernighan-Lin algorithm for parallel computing. Next Generation Information Processing System: Proceedings of ICCET 2020, Volume 2; 2021: Springer.
[14] Gharehchopogh, F.S., 2023. An improved Harris Hawks optimization algorithm with multi-strategy for community detection in social network. Journal of Bionic Engineering, 20(3), pp.1175-1197.
[15] Hevey D. Network analysis: a brief overview and tutorial. Health psychology and behavioral medicine. 2018;6(1):301-28.
[16] V. A. Traag, L. Waltman, and N. J. van Eck, "From Louvain to Leiden: guaranteeing well-connected communities," Scientific reports, vol. 9, no. 1, pp. 1-12, 2019.