A Parallel and Efficient Algorithm for Detecting Overlapping Communities in Social Networks

Mostafa Sabzekar ¹ ( Department of Computer Engineering, Birjand University of Technology )
Shima Baradaran Nejad ² ( Department of Computer Engineering, Islamic Azad University, Birjand Branch, Birjand, Iran )
Mahdi Khazaiepoor ³ ( Department of Computer Engineering, Islamic Azad University, Birjand Branch, Birjand,Iran )
Mehdi Kherad ⁴ ( 2- Ph.D. Student of Information Technology, Faculty of Engineering, Department of computer Engineering, University of Qom, Iran )

Submited date : 2023-08-10 Accepted date : 2024-03-17

Keywords: Social networks, parallelization, community detection, overlapping communities.,

Abstract :

Social networks are not only tools for communication but also represent one of the key potentials in business and commerce. One of the most significant issues in this field is clustering nodes and extracting effective and useful patterns from them, known as community detection. A major challenge in community detection within social networks is the vast number of nodes, which makes any kind of analysis difficult. Another challenge is the overlap of cluster members, referred to as overlapping communities. In such networks, each node may belong to multiple groups. Considering overlaps between communities—especially in large-scale networks—poses significant challenges in accurately detecting and identifying communities. Therefore, many studies tend to overlook this issue. In this paper, an approach is proposed to address these challenges. The most time-consuming step in the proposed algorithm, identifying influential nodes, is performed in parallel. Moreover, overlaps between communities are taken into account and analyzed. The results of evaluating the proposed method, in comparison with other existing methods, indicate its superiority in terms of the uniformity of the detected communities.

References:

[1] [1] A. Reihanian, M. R. Feizi-Derakhshi, and H. S. Aghdasi, "An enhanced multi-objective biogeography-based optimization for overlapping community detection in social networks with node attributes," Information Sciences, vol. 622, pp. 903-929, Apr. 2023.
[2] S. K. Gupta and D. P. Singh, "Seed community identification framework for community detection over social media," Arab. J. Sci. Eng., vol. 48, no. 2, pp. 1829-1843, 2023.
[3] S. Mishra, S. S. Singh, S. Mishra, and B. Biswas, "Multi-objective based unbiased community identification in dynamic social networks," Comput. Commun., vol. 214, pp. 18-32, 15 Jan. 2024.
[4] M. Sabzekar, S. BaradaranNejad, and M. Khazaeipoor, "A node-centric approach for community detection in dynamic networks," J. Electr. Comput. Eng. Innov., vol. 12, no. 2, pp. 305-318, Jul. 2024.
[5] X. Li, Y. Xin, C. Zhao, Y. Yang, and Y. Chen, "Graph convolutional networks for privacy metrics in online social networks," Applied Sciences, vol. 10, no. 4, Article ID: 1327, 2020.
[6] Z. Ma and S. Nandy, "Community detection with contextual multilayer networks," IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 3203-3239, May 2023.
[7] M. Rostami, M. Oussalah, K. Berahmand, and V. Farrahi, "Community detection algorithms in healthcare applications: a systematic review," IEEE Access, vol. 11, pp. 30247-30272, 2023.
[8] F. S. Gharehchopogh, "An improved harris hawks optimization algorithm with multi-strategy for community detection in social network," J. Bionic Eng., vol. 20, pp. 1175-1197, 2023.
[9] D. Jin, et al., "A survey of community detection approaches: from statistical modeling to deep learning," IEEE Trans. Knowl. Data Eng., vol. 35, no. 2, pp. 1149-1170, Feb. 2023.
[10] M. Seifikar, S. Farzi, and M. Barati, "C-Blondel: an efficient louvain-based dynamic community detection algorithm," IEEE Trans. Comput. Soc. Syst., vol. 7, no. 2, pp. 308-318, Apr. 2020.
[11] S. Ahajjam, M. El Haddad, and H. Badir, "A new scalable leader-community detection approach for community detection in social networks," Soc. Networks, vol. 54, pp. 41-49, Jul. 2018.
[12] S. Bahadori, H. Zare, and P. Moradi, "PODCD: probabilistic overlapping dynamic community detection," Expert Syst. Appl., vol. 174, Article ID: 114650, 15 Jul. 2021.
[13] C. Bothorel, V. L. Dao, and P. Lenca, "Community structure: a comparative evaluation of community detection methods," Netw. Sci., vol. 8, no. 1, pp. 1-41, Mar. 2020.
[14] S. Fortunato, "Community detection in graphs," Phys. Rep., vol. 486, no. 3-5, pp. 75-174, Feb. 2010.
[15] M. E. J. Newman, "Modularity and community structure in networks," in Proc. Natl. Acad. Scivol. 103, no. 23, pp. 8577-8582, Jun. 2006.
[16] W. Li, X. Zhou, C. Yang, Y. Fan, Z. Wang, and Y. Liu, "Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery," Inf. Fusion, vol. 79, no. C, pp. 110-123, Mar. 2022.
[17] Q. Ni, J. Guo, W. Wu, and H. Wang, "Influence-based community partition with sandwich method for social networks," IEEE Trans. Comput. Soc. Syst., vol. 10, no. 2, pp. 819-830, Apr. 2023.
[18] H. Long, X. Li, X. Liu, and W. Wang, "BBTA: detecting communities incrementally from dynamic networks based on tracking of backbones and bridges," Appl. Intell., vol. 53, pp. 1084-1100, 2023.
[19] H. Safdari, M. Contisciani, and C. De Bacco, "Reciprocity, community detection, and link prediction in dynamic networks," J. Phys. Complex., vol. 3, no. 1, Article ID: 15010, 2022.
[20] S. Kumar, A. Mallik, and S. S. Sengar, "Community detection in complex networks using stacked autoencoders and crow search algorithm," J. Supercomput., vol. 79, no. 3, pp. 3329-3356, 2023.
[21] T. Ma, Q. Liu, J. Cao, Y. Tian, A. Al-Dhelaan, and M. Al-Rodhaan, "LGIEM: global and local node influence based community detection," Futur. Gener. Comput. Syst., vol. 105, pp. 533-546, Apr. 2020.
[22] T. Wang, S. Chen, X. Wang, and J. Wang, "Label propagation algorithm based on node importance," Phys. A Stat. Mech. its Appl., vol. 551, Article ID: 124137, Aug. 2020.
[23] C. Li, et al., "NANI: an efficient community detection algorithm based on nested aggregation of node influence," 2017.
[24] D. Zhuang, M. Chang, and M. Li, "DynaMo: dynamic community detection by incrementally maximizing modularity," IEEE Trans. Knowl. Data Eng., vol. 33, no. 5, pp 1934-1945, May 2021.
[25] S. A. Seyedi, A. Lotfi, P. Moradi, and N. N. Qader, "Dynamic graph-based label propagation for density peaks clustering," Expert Syst. Appl., vol. 115, pp. 314-328, Jan. 2019.
[26] F. Liu, J. Wu, C. Zhou, and J. Yang, "Evolutionary community detection in dynamic social networks," in Proc. Int. Joint Conf. on Neural Networks, 7 pp. , Budapest, Hungary, 14-19 Jul. 2019.
[27] X. Su, J. Cheng, H. Yang, M. Leng, W. Zhang, and X. Chen, "IncNSA: detecting communities incrementally from time-evolving networks based on node similarity," Int. J. Mod. Phys. C, vol. 31, no. 7, Article ID: 2050094, 2020.
[28] M. Cordeiro, R. P. Sarmento, and J. Gama, "Dynamic community detection in evolving networks using locality modularity optimization," Soc. Netw. Anal. Min., vol. 6, Article ID: 15, 2016.
[29] J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graphs over time: densification laws, shrinking diameters and possible explanations," in Proc. of the 11th ACM SIGKDD Int. Conf. on Knowledge Discovery in Data Mining, pp. 177-187, Chicago, IL, USA, 21-24 Aug. 2005.
[30] A. Paranjape, A. R. Benson, and J. Leskovec, "Motifs in temporal networks," in Proc. of the 10th ACM Int. Conf. on Web Search and Data Mining, pp. 601-610, Cambridge, UK, 6-10 Dec. 2017.
[31] P. Panzarasa, T. Opsahl, and K. M. Carley, "Patterns and dynamics of users' behavior and interaction: network analysis of an online community," J. Am. Soc. Inf. Sci. Technol., vol. 60, no. 5, pp. 911-932, May 2009.