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