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