ارائه الگوریتم موازی و کارا به‌منظور شناسایی انجمن‌های همپوشان در شبکه‌های اجتماعی

چکیده مقاله :

شبکه‌های اجتماعی نه‌تنها به عنوان ابزاری برای ارتباطات، بلکه یکی از پتانسیل‌های مهم در کسب‌وکار و تجارت می‌باشند. یکی از مهم‌ترین مسائل تعریف‌شده در این حوزه، خوشه‌بندی گره‌ها و استخراج الگوهای مؤثر و مفید از آنهاست که به کشف انجمن معروف است. از چالش‌های مهم شناسایی انجمن در شبکه‌های اجتماعی می‌توان به حجم بسیار زیاد گره‌ها اشاره نمود که هر گونه تحلیلی بر روی آن را با مشکل مواجه می‌سازد. از دیگر چالش‌های پیش رو، اشتراک برخی از اعضای خوشه‌ها با یکدیگر می‌باشد که از آن به‌عنوان همپوشانی انجمن‌ها نام برده می‌شود. در چنین شبکه‌هایی هر گره می‌تواند به چند گروه تعلق پیدا کند. در نظر گرفتن همپوشانی بین انجمن‌ها به خصوص در شبکه‌های بزرگ، تشخیص و شناسایی انجمن را با مشکلات زیادی روبه‌رو می‌نمایند؛ از این رو در بیشتر پژوهش‌ها این مسئله نادیده گرفته می‌شود. در این مقاله، رویکردی به منظور رفع این مشکلات ارائه می‌شود. مرحله یافتن گره‌های تأثیرگذار شبکه که زمان‌برترین مرحله در الگوریتم پیشنهادی است، به‌صورت موازی انجام می‌شود و همچنین همپوشانی بین انجمن‌ها در نظر گرفته شده و تحلیل می‌گردد. نتایج حاصل از ارزیابی روش پیشنهادی در قیاس با روش‌های مورد مقایسه، حاکی از برتری آن در یکنواختی انجمن‌های کشف شده است.

چکیده انگلیسی :

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.

منابع و مأخذ:

[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.