ارائه الگوریتم موازی و کارا به‌منظور شناسایی انجمن‌های همپوشان در شبکه‌های اجتماعی
الموضوعات :مصطفی سبزه کار 1 , شیما برادران نژاد 2 , مهدی خزاعی پور 3 , مهدی خرد 4
1 - گروه مهندسی کامپیوتر، دانشگاه صنعتی بیرجند
2 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد بیرجند، بیرجند، ایران
3 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد بیرجند، بیرجند، ایران
4 - دانشجوی دکتری، گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی - دانشگاه قم - قم - ایران
الکلمات المفتاحية: شبکه‌های اجتماعی, موازی‌سازی, کشف انجمن, انجمن‌های همپوشان.,
ملخص المقالة :
شبکه‌های اجتماعی نه‌تنها به عنوان ابزاری برای ارتباطات، بلکه یکی از پتانسیل‌های مهم در کسب‌وکار و تجارت می‌باشند. یکی از مهم‌ترین مسائل تعریف‌شده در این حوزه، خوشه‌بندی گره‌ها و استخراج الگوهای مؤثر و مفید از آنهاست که به کشف انجمن معروف است. از چالش‌های مهم شناسایی انجمن در شبکه‌های اجتماعی می‌توان به حجم بسیار زیاد گره‌ها اشاره نمود که هر گونه تحلیلی بر روی آن را با مشکل مواجه می‌سازد. از دیگر چالش‌های پیش رو، اشتراک برخی از اعضای خوشه‌ها با یکدیگر می‌باشد که از آن به‌عنوان همپوشانی انجمن‌ها نام برده می‌شود. در چنین شبکه‌هایی هر گره می‌تواند به چند گروه تعلق پیدا کند. در نظر گرفتن همپوشانی بین انجمن‌ها به خصوص در شبکه‌های بزرگ، تشخیص و شناسایی انجمن را با مشکلات زیادی روبه‌رو می‌نمایند؛ از این رو در بیشتر پژوهش‌ها این مسئله نادیده گرفته می‌شود. در این مقاله، رویکردی به منظور رفع این مشکلات ارائه می‌شود. مرحله یافتن گره‌های تأثیرگذار شبکه که زمان‌برترین مرحله در الگوریتم پیشنهادی است، به‌صورت موازی انجام می‌شود و همچنین همپوشانی بین انجمن‌ها در نظر گرفته شده و تحلیل می‌گردد. نتایج حاصل از ارزیابی روش پیشنهادی در قیاس با روش‌های مورد مقایسه، حاکی از برتری آن در یکنواختی انجمن‌های کشف شده است.
[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.
