Increasing Community Detection Accuracy in Social Networks using Improved Label Diffusion Approach

Subject Areas : New technologies in distributed systems and algorithmic computing

Nafiseh Afkhami ¹ , Nazbanou Farzaneh Bahalgardi ² , Hassan Shakeri ^{3 *}

1 - Department of Computer Engineering, Imam Reza International University, Mashhad, Iran
2 - Department of Computer Engineering, Imam Reza International University, Mashhad, Iran
3 - Department of Computer Engineering, Mashhad Branch, Islamic Azad University, Mashhad, Iran

Received: 2024-11-21 Accepted : 2025-06-01 Published : 2025-06-07

Keywords: Community detection, Social network modeling, Label propagation algorithm, Clustering,

Abstract :

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.

References:

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

Full-Text:



Journal of New Technologies in Distributed Systems and Algorithmic Computing

Islamic Azad University of Sabzevar

E-ISSN: 3115-705X

https://sanad.iau.ir/journal/ntds

 

 

Reaserch Article

Increasing Community Detection Precision in Social Networks using Improved Label Diffusion Approach

 

Nafiseh Afkhami 1  | Nazbanoo Farzaneh 2  | Hassan Shakeri 3* 

 

1Deprtment of Computer Engineering, Imam Reza International University, Mashhad, Iran,  [e-mail]     2Deprtment of Computer Engineering, Imam Reza International University, Mashhad, Iran, [e-mail]     3Deprtment of Computer Engineering, Ma.C.,  Islamic Azad University, Mashhad, Iran, [e-mail]             Corresponding Author *Hassan Shakeri, Associate Professor, Deprtment of Computer Engineering, Ma.C., Islamic Azad University, Mashhad, Iran, [e-mail]

 

Abstract

https://doi.org/10.82195/ntds.2025.1191172

Main Subjects: Community Detection in Social Networks Received: 21 November 2024 Revised: 30 May 2025 Accepted: 29 April 2025

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

 

Keywords: Community Detection, Social Network Modeling, Label Propagation Algorithm, Clustering

 

 

 

 

 

 

 

پژوهشی

افزایش دقت شناسایی جوامع در شبکه‏های اجتماعی با بهبود رویکرد انتشار برچسب

نفیسه افخمی1| نازبانو فرزانه2 | حسن شاکری*3‌‌ 

 

1 گروه مهندسی کامپیوتر، دانشگاه بین‏المللی امام رضا، مشهد، ایران، [e-mail]       2 گروه مهندسی کامپیوتر، دانشگاه بین‏المللی امام رضا، مشهد، ایران، Nazbanou@[e-mail]     3گروه مهندسی کامپیوتر، واحد مشهد، دانشگاه آزاد اسلامی، مشهد، ایران، [e-mail]           نویسنده مسئول *حسن شاکری، دانشیار، گروه مهندسی کامپیوتر، واحد مشهد، دانشگاه آزاد اسلامی، مشهد، ایران، [e-mail]

چکیده:

عنوان اصلی: شناسایی جوامع در شبکه‏های اجتماعی تاریخ دریافت: 1/9/1403 تاریخ بازنگری: 9/3/1404 تاریخ پذیرش: 11/3/1404

  شناسایی جوامع در شبکه‏های بزرگ یک موضوع پرکاربرد در تحلیل شبکه‏های اجتماعی است و ارائه الگوریتم بادقت و کارایی مطلوب برای استخراج جوامع اهمیت زیادی دارد. رویکردهای مختلفی برای شناسایی جامعه‏ها وجود دارد. ازجمله می‏توان به رویکرد انتشار برچسب اشاره کرد که در آن ابتدا مهم‏ترین رأس‏های شبکه بر مبنای معیارهای مرکزیت تعیین می‏شوند و برچسب‏های جامعه متفاوت به آنها انتساب داده می‏شود. سپس برچسب هر یک از این رأس‏ها به رأس‏های اطراف آنها انتشار می‏یابد. هدف این پژوهش، بهبود یک الگوریتم شناسایی جامعه موسوم به LBLD است. این الگوریتم ابتدا بر اساس یک معیار شباهت، تعدادی از مهم‏ترین رأس‏های شبکه را تعیین می‏کند. سپس با یک رویکرد متوازن، جوامع توسعه داده می‏شوند و در نهایت یک‌فاز ادغام اجرا می‏شود تا جوامع کوچک با یکدیگر ترکیب شوند. ایده پیشنهادی ما استفاده از یک معیار الهام‏گرفته از مفهوم h-index برای بهبود دقت تشخیص جوامع است به‌این‌ترتیب که زیرگراف‏هایی به‌عنوان جامعه شناسایی شوند که حداقل p درصد از رأس‏های آنها درجه حداقل k داشته باشد. اعمال روش پیشنهادی بر روی مجموعه‏داده‏های شناخته‏شده در این حوزه و مقایسه نتایج نشان می‏دهد که روش پیشنهادی نسبت به روش‏های مشابه باعث بهبود دقت در استخراج جوامع شده است.

https://doi.org/10.82195/ntds.2025.1191172

 

کلیدواژه‌ها: شناسایی جوامع، مدل‏سازی شبکه‏های اجتماعی، الگوریتم انتشار برچسب، خوشه‏بندی.

 

 

 

 

 

 

 

 

 

 

 

1-مقدمه

  رشد سریع رسانه‏ها و شبکه‏های اجتماعی تأثیر شگرفی بر ابعاد مختلف زندگی انسان‏ها گذاشته است به‌طوری‌که مدل‏سازی و تحلیل شبکه‏های اجتماعی به یک مبحث مطرح در تحقیقات و نیز در کاربردهای مختلف تبدیل شده است. مدل‏سازی و تحلیل شبکه‏های اجتماعی زمینه‏های مختلفی را شامل می‏شود که از جمله می‏توان به تعیین مرکزیت و اهمیت رأس‏های گراف شبکه، پیش‏بینی رفتار کاربران، طبقه‏بندی کاربران و شناسایی جوامع اشاره کرد و در حوزه‏های مختلفی مانند بهبود کارآمدی سیستم‏های پیشنهاددهنده، تحلیل‏های زیست‏شناسی از قبیل بررسی شبکه پروتئین - پروتئین و مدل‏سازی شبکه‏های ارجاع کاربرد دارد [1]. برای مدل‏سازی شبکه‏های اجتماعی، از مفاهیم نظریه گراف استفاده می‏شود. برای این منظور شبکه اجتماعی به صورت یک گراف بازنمایی می‏شود که اعضای شبکه به عنوان رأس‏های گراف و روابط بین آنها (ازقبیل روابط دوستی یا دنبال‏کردن) به عنوان یال‏ها یا لبه‏های گراف در نظر گرفته می‏شود.

شناسایی جوامع یکی از مهم‏ترین و پرکاربردترین حوزه‏های مدل‏سازی و تحلیل شبکه‏های اجتماعی است. هر جامعه عبارت است از گروهی از اعضای شبکه‏های اجتماع (به‌عبارت‌دیگر یک زیرگراف از گراف اصلی) که عناصر آن شباهت زیادی از نظر ویژگی‏ها و ارتباطات زیادی با یکدیگر دارند (شکل 1). در واقع، مبحث شناسایی جوامع معادل مفهوم خوشه‏بندی است که به صورت کلی در مباحث داده‏کاوی مطرح است اما در شبکه‏های اجتماعی، به جای اصطلاح خوشه‏بندی، عمدتاً از اصطلاح «شناسایی جوامع» استفاده می‏شود و ضمناً در شناسایی جوامع، علاوه بر رویکردها و تکنیک‏های خوشه‏بندی کلاسیک از مفاهیم شبکه‏های اجتماعی به ویژه ارتباطات بین کاربران شبکه به‏صورت گسترده استفاده می‏شود. یک معیار مهم در کیفیت تفکیک شبکه به جوامع مختلف این است که اتصالات و لینک‏ها در داخل هر جامعه تا حدامکان زیاد ولی در بین هر دو جامعه مختلف، تا حد امکان کم باشد. استخراج جوامع به درک ساختار آنها و ارتباطات بین گره‏ها و نحوه کارکردن شبکه کمک می‏کند [2].

 

شکل 1. استخراج جوامع در شبکه‏های اجتماعی [2]

Figure 1. Extraction of communities in social networks

 

رویکردهای مختلفی برای شناسایی جامعه‏ها در شبکه‏های اجتماعی وجود دارد که ازجمله می‏توان به روش‏های مبتنی بر الگوریتم‏های کلاسیک خوشه‏بندی بر اساس معیارهای شباهت در ویژگی‏ها اشاره کرد. ازجمله الگوریتم K-means به‌عنوان یکی از معروف‏ترین الگوریتم‏های کلاسیک خوشه‏بندی با معیارهای شباهت مختلف از قبیل شباهت کسینوسی و یا شباهت جاکارد در استخراج جوامع در شبکه‏های اجتماعی نیز مورداستفاده قرار می‏گیرند. دسته‏ای دیگر از روش‌ها بر یافتن زیرگراف‏های با ارتباطات داخلی زیاد مبتنی هستند که از جمله می‏توان به کشف جوامع مبتنی بر مفهوم Clique اشاره کرد. یک رویکرد جدید برای استخراج جوامع، انتشار برچسب است که یک تکنیک سریع برای توسعه جوامع اولیه به گره‏های اطراف آنها است. به‌عنوان نمونه می‏توان به الگوریتم ارائه‏شده در مرجع [3] به نام LSMD¹ اشاره کرد که یک الگوریتم انتشار چندسطحی شباهت محلی است و بر اساس این رویکرد عمل می‏کند. 

باوجود ارائه کارهای تحقیقاتی مختلف در حوزه استخراج جوامع در شبکه‏های اجتماعی، همچنان افزایش دقت و کاهش مرتبه زمانی الگوریتم‏ها در این زمینه به‌عنوان مسائل باز تحقیقاتی مطرح هستند [1]. به همین دلیل در این تحقیق ما قصد داریم راهکاری برای بهبود یک الگوریتم شناسایی جوامع معرفی‏شده در [1] موسوم به الگوریتم‏ LBLD² ارائه کنیم. الگوریتم LBLD ابتدا براساس یک معیار شباهت، پنج‏درصد از مهم‏ترین رأس‏های شبکه را تعیین می‏کند. سپس با یک رویکرد متوازن، جوامع هم از مرکز و هم از مرزها توسعه داده می‏شوند و در نهایت یک فاز ادغام اجرا می‏شود تا جوامع کوچک با یکدیگر ترکیب شوند و جوامع مطلوب را تشکیل دهند.

در این تحقیق یک راهکار بهبودیافته بر اساس روش ارائه‏شده در مرجع [1] پیشنهاد می‏کنیم. ایده پیشنهادی ما استفاده از یک معیار الهام‏گرفته از مفهوم h-index برای بهبود دقت تشخیص جوامع است. به این ترتیب که زیرگراف‏هایی به عنوان جامعه شناسایی شوند که حداقل تعداد n رأس آنها درجه حداقل k داشته باشد. رویکرد کلی مورد استفاده در روش پیشنهادی، مشابه روش پایه، انتشار برچسب جامعه از گره‏های مهم به گره‏های مجاور آنها است. با وجود این تغییرات و نوآوری‏های عمده‏ای در روش پیشنهادی نسبت به الگوریتم پایه اعمال شده که باعث افزایش دقت شناسایی جوامع شده است. مهم‏ترین نوآوری‏ها و تغییرات پیشنهادی نسبت به روش پایه عبارتند از:

1. استفاده از معیار جاکارد برای تعیین میزان شباهت گره‏ها از نظر همسایه‏های مشترک و استفاده از آن در تعیین میزان اهمیت گره‏ها که براساس آن، جوامع اولیه شکل می‏گیرند. دلیل استفاده از معیار شباهت جاکارد، کارآمدی آن در مسائل مبتنی بر گراف و مشخصاً حوزه مدل‏سازی و تحلیل شبکه‏های اجتماعی است که تأثیر آن در ارزیابی روش پیشنهادی در بخش 4 نیز مشهود است.

2. استفاده از یک معیار الهام‏گرفته از معیار h-index مربوط به رتبه‏بندی محققان برای انتخاب نهایی جوامع.

در ادامه این مقاله در بخش 2 کارهای تحقیقاتی مرتبط در این حوزه مورد بررسی قرار می‏گیرد.. در بخش 3 به توصیف روش پیشنهادی جهت افزایش دقت شناسایی جوامع در شبکه‏های اجتماعی پرداخته می‌شود. بخش 4، ارزیابی روش پیشنهادی و مقایسه آن با کارهای پژوهشی‌ پیشین را ارائه می‌دهد و در نهایت، در بخش 5 نتیجه‌گیری و ایده‏های پیشنهادی برای کارهای آینده مطرح می‌گردد.

2- پیشینه تحقیق

  باتوجه‌به اهمیت شناسایی جوامع به‌عنوان یک ابزار ضروری برای تحلیل اطلاعات پنهان شبکه‏ها، الگوریتم‏های متنوعی برای این منظور ارائه شده است که ازجمله می‏توان به رویکردهای محلی، مبتنی بر ماژولاریتی و مبتنی بر تجزیه ماتریس اشاره کرد. یکی از روش‏های ارائه‏شده برای کشف جوامع، LP-LPA³ نام دارد که مقدار قدرت لینک‏ها را برای یال‏ها و مقدار تأثیرگذاری برچسب‏ها را برای رأس استفاده می‏کند تا از انتخاب تصادفی حالت‏های قطع اتصال جلوگیری کند. روش ارائه‏شده در [4] موسوم به LPA⁴ یا NI-LPA⁵ از ترکیب اندیس جاکارد و انتشار سیگنال بین گره‏ها استفاده می‏کند تا امتیاز اهمیت دقیق‏تری به رأس‏ها انتساب دهد. به طور کلی روش‏های مبتنی بر LPA اغلب بر تعریف ملاک‏های اهمیت، مرتب‏سازی رأس‏ها بر مبنای میزان اهمیت آنها و تعریف معیارهایی برای حالت‏های شکستن اتصال مبتنی هستند. اما این روش‏ها هم با مشکلاتی از قبیل پایین‏بودن دقت، مرتبه زمانی بالا و ناپایداری الگوریتم مواجه هستند.

روش CDME⁶ که در [5] توسط سان و همکاران ارائه شده است، یک تکنیک مبتنی بر اثر متیو است که از رویکرد محلی استفاده می‏کند. هدف این روش، مشخص کردن پارامترهای روال‏های بهینه‏سازی است و مزیت عمده این روش در این راستا کاهش زمان این بهینه‏سازی‏ها است. در این تحقیق، شبکه به عنوان یک سیستم اجتماعی در نظر گرفته شده است و با الهام‏گیری از اثر متیو رویکردی ارائه شده است که جوامع با کیفیت بالا و پویا را استخراج می‏کند. یک مزیت دیگر این الگوریتم این است که به صورت محلی عمل می‏کند و فقط نیاز به محاسبه میزان جذابیت گره‏های همسایه دارد که این ویژگی باعث می‏شود که پردازش شبکه‏های با مقیاس بالا امکان‏پذیر باشد.

 LCDR⁷ [6] یک روش محلی دیگر است که بر اساس رتبه‏بندی گره‏ها با ایده کرشهف یا ذخیره‏سازی بار مبتنی است. در این تحقیق ابتدا مزایا و معایب روش‏های محلی شناسایی جوامع موردبررسی قرار گرفته است. مهم‏ترین مزیت روش‏های محلی، بالابردن کارایی آنها است. در مقابل، این روش‏ها چند مشکل عمده دارند که پایین‏بودن دقت و مقیاس‏پذیری و ناپایداری جوامع استخراج‏شده جزو مهم‏ترین معایب روش‏های مذکور هستند. در واقع، دقت و کیفیت جوامع در روش‏های محلی وابستگی زیادی به انتخاب گره‏های مهم دارد که به‌عنوان هسته‏های اولیه جوامع انتخاب می‏شوند. برای حل این مشکلات، در این مرجع یک الگوریتم محلی جدید کشف جوامع معرفی می‏کند که بر رتبه‏بندی گره‏های بااهمیت بالا مبتنی است. در این الگوریتم یک شاخص جدید برای محاسبه اهمیت گره‏ها ارائه شده است. این شاخص می‏تواند با توجه به محلی بودن شبکه، اهمیت همه گره‏های شبکه را به‌صورت کامل بازتاب دهد. الگوریتم LCDR ابتدا گره‏های مهم را برای بسط جوامع اولیه بر اساس یک معیار شباهت محلی انتخاب می‏کند تا این که همه گره‏ها عضو جوامع شوند. در انتها جوامع شناسایی‏شده ادغام می‏شوند تا جوامع نهایی شکل بگیرند.

زارع‏زاده و همکاران در [7] یک گونه بهبودیافته از الگوریتم موسوم به GCN⁸ را ارائه کرده‏اند که از امتیازدهی ترکیبی به گره‏ها و بروزرسانی برچسب‏های همگام برای افزایش دقت تشخیص جوامع استفاده می‏کند. در این مقاله ابتدا مشکلات الگوریتم‏های موجود در راستای افزایش دقت شناسایی جوامع مورد تحلیل قرار گرفته است که مهم‏ترین آنها عبارتند از دقت پایین، تصادفی‏بودن و ناپایداری. برای حل این مشکلات، این تحقیق یک روش بهبودیافته برای شناسایی جوامع پیشنهاد می‏کند که از یک امتیازدهی ترکیبی برای گره‏ها و بروزرسانی همگام برچسب گره‏های مرزی استفاده می‏کند و همچنین مشکل بروزرسانی تصادفی را برطرف می‏کند. برای بروزرسانی برچسب گره‏های مرزی از معیارهای مرکزیت درجه‏ای⁹ و همسایه‏های مشترک استفاده می‏شود. همچنین یک روش جدید برای ادغام جوامع پیشنهاد شده است که نسبت به روش‏های مبتنی بر پیمانگی¹⁰ سریع‏تر است.

همچنین یک روش دیگر به نام ¹¹APAS در [8] معرفی شده است که از الگوریتم مبتنی بر انتشار استفاده می‏کند که جوامع را با بهره‏گیری از یک ماتریس شباهت نامتقارن تطبیقی شناسایی می‏کند و می‏تواند به صورت کارآمد احتمالات رهبری را بین نقاط داده نشان دهد. ایده اصلی این الگوریتم این است که مقدار شباهت بین دو گره i و k متقارن نیست و بنابراین یک ماتریس شباهت با عنوان ماتریس انتشار وابستگی با شباهت تطبیقی معرفی شده است که می‏تواند به صورت کارا احتمالات رهبری بین نقاط داده را نشان دهد. این ماتریس، شباهت متقارن را تبدیل به شباهت نامتقارن می‏کند که نتیجه آن بهبود کارآمدی الگوریتم شناسایی جوامع در شبکه‏های جهان واقعی بوده است.

همچنین برخی از منابع مانند [9] و [10] به بررسی کاربردهای شناسایی جوامع در زمینه‏های مختلف پرداخته‏اند. یکی از مهم‏ترین کاربردها که در مرجع [9] مورد اشاره قرار گرفته است تحلیل یک شبکه از اقلام (کالاها) برای فروش در وب‏سایت‏های فروش آنلاین بزرگ است. اقلام به عنوان یک شبکه درنظر گرفته می‏شوند و در صورتی که توسط یک خریدار واحد خریداری شوند بین آنها لینک برقرار می‏شود. این رویکرد باعث خوشه‏بندی کالاها به صورت مناسب و در نتیجه تأثیر مثبت و مطلوب بر رفتار خرید مشتریان شده است.

در مرجع [10] با بررسی تکنیک‏های مختلف شناسایی جوامع، براساس ویژگی‏های شبکه‏ها راهنمایی‏هایی برای کمک به انتخاب بهترین روش کشف جوامع برای هر شبکه و کاربرد معین ارائه شده است. همچنین قواعد ارائه‏شده در این تحقیق، محدودیت‏های استفاده از هر الگوریتم مشخص برای هر شبکه را با توجه به ویژگی‏های ماکروسکوپی شبکه بیان می‏کند. همچنین از ترکیب پارامترها به عنوان یک شاخص قابل‏اندازه‏گیری برای یافته محدوده‏های اتکاپذیری الگوریتم‏های مختلف استفاده شده است و نیز میزان وابستگی قدرت شناسایی و زمان پردازش هر الگوریتم به اندازه شبکه مورد بررسی قرار گرفته است.

در پژوهش [11]‏، یک الگوریتم ژنتیک به نام الگوریتم ژنتیک-NET ارائه شد که مفهومی از امتیاز جامعه را برای نشان دادن کیفیت از بخش‏بندی شبکه‏های اجتماعی به کار می‏گیرد. امتیاز جامعه، به حداکثر رساندن ارتباطات داخلی در ساختار جامعه است. این روش‏ جستجوی نامعتبر را زمانی به طور موثر کاهش می‏دهد که فقط همبستگی واقعی تمام گره‏ها در هر عملگر در نظر گرفته شود.

در پژوهش [12]، یک الگوریتم‏ اکتشافی برای بخش‏بندی گراف‏ها ارائه شد. این الگوریتم هنوز هم در ترکیب با تکنیک‌های دیگر به کار می‌رود. هدف آن به حداقل رساندن یک تابع ارزیابی است که تفاوت لینک‏های درون جامعه و بین جامعه است. انگیزه پشت این روش‏، مسأله تقسیم‌بندی مدارهای الکترونیکی بر روی بوردها بود که در آن رأس‏ها در بوردهای مختلف قرار بود با حداقل تعداد اتصالات به هم متصل شوند. در واقع، تابع بهینه‏سازی برمبنای حداقل تعداد اتصالات بین بوردهای مختلف تعریف می‏شود که این تابع را می‏توان به صورت تفاوت بین تعداد یال‏های داخل مجموعه‏ها و تعداد یال‏های قرار گرفته بین آنها تعریف کرد.

مرجع [13] یک الگوریتم مبتنی بر الگوریتم بهینه‏سازی شاهین هریس و چند تابع تکاملی دیگر به عنوان یک تکنیک یادگیری بهبودیافته ارائه می‏کند که هدف از آنها برقراری تعادل بین استخراج و اکتشاف است. این رویکرد باعث افزایش قابل ملاحظه دقت و صحت شناسایی جوامع در شبکه‏های اجتماعی شده است.

در مرجع [14] یک چارچوب مبتنی بر موقعیت جغرافیایی و اعتماد ارائه شده است که با الگوریتم‏های تشخیص جوامع ترکیب شده است تا کاربران بدخواه را در جوامع شناسایی و فیلتر کند. این عملکرد در شبکه‏های اجتماعی نسل پنجم مورد توجه قرار گرفته است. چارچوب ارائه‏شده از اطلاعات جغرافیایی و اعتماد اجتماعی در داخل شبکه و رویکرد مبتنی بر هوش مصنوعی در کشف جوامع بهره می‏گیرد تا کاربرانی را که باعث آسیب‏رساندن به دیگران می‏شوند شناسایی کند. مزیت این چارچوب نسبت به الگوریتم‏های مشابه این است که خصوصیت‏هایی را که یک کاربر بدخواه و آسیب‏رسان نمی‏توان به راحتی جعل کند، مورد استفاده قرار می‏دهد. مؤلفان این مقاله، چارچوب پیشنهادی خود را بر روی داده‏های شبکه اجتماعی مصنوعی مورد ارزیابی قرار داده‏اند که نتیجه آن بهبود دقت شناسایی کاربرانی بوده است که بالقوه بدخواه هستند.

الگوریتم‌های انتشار برچسب جزو روش‏های یادگیری نیمه‏نظارت‏شده و سریع در حوزه شناسایی جوامع هستند. اما ناپایداری و تصادفی بودن آنها چالش مهمی محسوب می‏شود. بسیاری از محققان، راهکارهایی برای بهبود تکنیک انتشار برچسب ارائه کرده‏اند که اغلب آنها برای کشف جوامع بزرگ مناسب نیست؛ زیرا پیچیدگی زمانی آنها بسیار بالا است؛ بنابراین در مرجع [15] یک الگوریتم انتشار برچسب بر مبنای معیار h-index تطبیقی ارائه شده است که پایداری و دقت LPA را با استفاده از معیار h-index اصلاح‏شده به‌عنوان یک ملاک اهمیت گره، بهبود می‏بخشد. با آن که روش پیشنهادی در این پایان‏نامه نیز از ترکیب معیار h-index با رویکرد انتشار برچسب استفاده می‏کند، تفاوت‏های قابل‌ملاحظه‌ای نسبت به روش مرجع [16] دارد؛ زیرا اولاً روش پیشنهادی بر مبنای بهبود الگوریتم LBLD طراحی شده و ثانیاً در معیار h-index به‌منظور متناسب شدن با کاربرد شناسایی جوامع، اصلاحاتی پیشنهاد شده است که جزئیات این تغییرات و نوآوری‏ها را در فصل بعد که به توصیف روش پیشنهادی می‏پردازد ارائه خواهیم کرد.

کار تحقیقاتی که به‌عنوان راهکار پایه در این پژوهش موردمطالعه و بررسی قرار گرفته است در مرجع [1] ارائه شده است. الگوریتم پیشنهادی در این روش LBLD نام دارد که برگرفته از سرنام کلمات عبارت «انتشار برچسب متوازن محلی» است. این الگوریتم ابتدا براساس یک معیار شباهت، ‏درصدی از گره‏های شبکه را که بیشترین میزان اهمیت را دارند، شناسایی می‏کند. به این گره‏ها برچسب‏های متوالی و متفاوت انتساب داده می‏شود. سپس با یک رویکرد متوازن و با انتشار برچسب از گره‏های اولیه به رأس‏های مجاور آنها، جوامع توسعه داده می‏شوند. در انتها یک مرحله ادغام جوامع اجرا می‏شود تا جوامع کوچک با یکدیگر ترکیب شوند و جوامع با بزرگی مطلوب و در عین حال قوی را تشکیل دهند.

شکل 2 فرآیند انتشار برچسب در الگوریتم LBLD در یک شبکه نمونه را نشان می‏دهد. در شکل سمت چپ، مهم‏ترین گره‏ها شناسایی شده و برچسب‏های متفاوت به آنها انتساب داده شده که با رنگ‏های متمایز نشان داده شده است. در شکل سمت راست، بروزرسانی برچسب‏ها برمبنای انتشار برچسب انجام شده است.

 

شکل 2. نمونه‏ای از فرایند شناسایی جوامع براساس الگوریتم LBLD [1]

Figure 2. An example of the community detection process based on the LBLD algorithm.

3- راهکار پیشنهادی

3-1- توصیف کلی راهکار پیشنهادی

  در این بخش، توصیف کلی ایده پیشنهادی ارائه می‏گردد. سپس در بخش 3-2 روش پیشنهادی به تفصیل ارائه و تشریح می‏شود. در مدل‏سازی و تحلیل شبکه‏های اجتماعی، یکی از مهم‏ترین ملاک‏های تخمین میزان شباهت بین گره‏ها شباهت ساختاری رأس‏ها بر مبنای تعداد همسایه‏های مشترک است. برای این منظور، معیارهای شباهت مختلفی مانند شباهت کسینوسی و شباهت جاکارد استفاده می‏شوند. در روش پیشنهادی [1] معیار دیگری توسط مؤلفان ارائه شده است. اما پیشنهاد ما این است که از معیار جاکارد برای این منظور استفاده شود. دلیل استفاده از معیار شباهت جاکارد این است که این معیار در مسائل حوزه مدل‏سازی و تحلیل شبکه‏های اجتماعی و به‌طورکلی در ارزیابی شباهت بین گره‏ها در گراف بسیار کارآمد است و نتایج ارزیابی‏های ما در بخش 4 نیز این موضوع را تأیید می‏کند.

 این معیار شباهت بین دو رأس گراف را با تقسیم تعداد همسایه‏های مشترک آن دو بر تعداد همسایه‏های مشترک و غیرمشترک آنها تخمین می‏زند. به‌عبارت‌دیگر شباهت جاکارد برای دو رأس A و B در یک شبکه اجتماعی برابر است با تعداد اعضای مجموعه اشتراک همسایه‏های A و B تقسیم بر تعداد اعضای مجموعه اجتماع آنها. رابطه (1) معیار جاکارد را نشان می‏دهد [20]:

 از طرف دیگر برای بهبود دقت کشف جوامع، در روش پیشنهادی معیاری برگرفته از معیار h-index استفاده می‏کنیم. h-index یک معیار برای رتبه‏بندی پژوهشگران بر اساس تعداد ارجاعات به کارهای تحقیقاتی آن است. تعریف این معیار به این صورت است که اگر h-index یک محقق برابر با k باشد به این معنی است که حداقل k تا از مقالات او حداقل k بار مورد ارجاع قرار گرفته‏اند. در واقع هر چه مقالات بیشتری به تعداد بیشتری مورد ارجاع قرار گرفته باشند، اهمیت و تأثیرگذاری پژوهشگر موردنظر بیشتر است. از این ایده می‏توان برای تعیین میزان قوی‏بودن یک جامعه در شبکه‏های اجتماعی استفاده کرد به‌این‌ترتیب که هر چه تعداد بیشتری از رأس‏های (افراد) جامعه تعداد لینک‏ها (همسایه‏های) بیشتری داشته باشند، آن جامعه قوی‏تر است؛ بنابراین در راهکار پیشنهادی معیاری به نام sk تعریف می‏شود که اگر برابر با p باشد نشان می‏دهد که حداقل p تا از گره‏های جامعه حداقل k همسایه دارند. ایده پیشنهادی این است که با محاسبه مقدار sk برای یک جامعه که در مرحله اول شناسایی شده است، جوامعی که sk آنها از حد معینی کمتر است به جوامع کوچک‏تر و قوی‏تری تفکیک شوند. بادقت در تعریف معیار sk که در این مقاله معرفی ‏شده است، ملاحظه می‏شود که این مفهوم، عیناً معادل معیار h-index نیست؛ بلکه یک معیار تعمیم‏یافته از h-index است و بنابراین تعریف معیار sk یکی از نوآوری‏های روش پیشنهادی محسوب می‏شود.

3-2 شرح کامل روش پیشنهادی

  همان‏طور که در بخش قبلی اشاره شد، راهکار پیشنهادی تا حدودی بر الگوریتم انتشار برچسب با توازن محلی یا LBLD [1] منطبق است؛ ولی یک سری تغییرات عمده در الگوریتم مذکور به‌منظور بهبود کیفیت و قوی‏بودن خوشه‏ها اعمال شده است.

گام 1: اولین قدم در الگوریتم پیشنهادی، کنارگذاشتن گره‏های با درجه صفر از روال خوشه‏بندی است. این موضوع به این دلیل است که گره‏های با درجه صفر یعنی گره‏هایی که با هیچ گرهی مجاور نیستند، خود یک جامعه تک‏عضوی جداگانه محسوب می‏شوند و در واقع به دلیل ایزوله بودن آنها معیار خاصی برای انتساب آنها به یک جامعه خاص مبتنی بر لینک‏های بین گره‏ها وجود ندارد. البته این امکان وجود دارد که پس از مشخص‏شدن جامعه‏ها از الگوریتم اصلی، هر یک از گره‏های منفرد و ایزوله یا به صورت تصادفی و یا براساس ملاک‏های دیگری غیر از اتصالات (یال‏ها) به یکی از جوامع استخراج‏شده اضافه شوند.

در این گام همچنین گره‏های با درجه 1 از مجموعه گره‏هایی که شانس سرخوشه‏شدن خواهند داشت کنار گذاشته می‏شوند. علت این است که همان طور که خواهیم داد الگوریتم پیشنهادی و نیز الگوریتم LBLD [1] برای تعیین سرخوشه‏ها بین هر دو گره مجاور، میزان اهمیت آن دو را از نظر مشابهت در همسایه‏هایشان مبنا قرار می‏دهند و بنابراین این موضوع برای گره‏های درجه 1 که فقط یک گره مجاور دارند منتفی است. البته بدیهی است که ماهیت و دلیل کنارگذاشتن گره‏های درجه 1 با گره‏های درجه صفر متفاوت است. در واقع گره‏های درجه صفر به کلی از جامعه‏بندی اولیه کنار گذاشته می‏شوند و هر کدام به تنهایی به عنوان یک جامعه تک‏عضوی در نظر گرفته می‏شوند ولی گره‏های درجه 1 فقط احتمال سرخوشه‏بودن را از دست می‏دهند ولی به عنوان یک عضو عادی از یکی از جوامع شناسایی‏شده گروه‏بندی خواهند شد.

گام 2: در گام بعدی الگوریتم به ازای هر دو عنصر از شبکه (گراف) میزان شباهت آن دو براساس معیار شباهت جاکارد محاسبه می‏شود. این معیار که در رابطه (1) بیان شد، یکی از مهم‏ترین معیارهای شباهت در بین رأس‏های گراف است و برای دو رأس i و j از گراف نسبت تعداد رأس‏هایی که همسایه‏های مشترک هر دو رأس i و j هستند به تعداد رأس‏هایی که همسایه حداقل یکی از این دو هستند را نشان می‏دهد.

گام 3: هر گرهی که بیشترین مشابهت را با همسایه‏هایش داشته باشند به این معنی است که یک زیرگراف با اتصالات زیاد در پیرامون آن وجود دارد و بنابراین این گره، کاندید خوبی برای انتخاب‏شدن به عنوان عنصر مرکزی جامعه یا همان سرخوشه است. به همین دلیل، مشابه الگوریتم LBLD، معیار اهمیت گره (NI)¹² طبق رابطه زیر تعریف می‏شود[1]:

(1)

·       این معیار برای هر یک از رأس‏های گراف محاسبه می‏شود و رأس‏ها بر اساس مقدار NI به‌صورت نزولی مرتب می‏شوند.

·       برای استخراج جوامع، ابتدا همه گره‏های گراف با برچسب صفر برچسب‏گذاری می‏شوند و سپس مراحل زیر برای تمامی گره‏ها (به‌جز گره‏های درجه صفر و 1 که قبلاً کنار گذاشته شده بودند) تکرار می‏شود:

·       گره i و شبیه‏ترین گره به آن به نام j انتخاب می‏شوند.

·       اگر similarity(i,j) ≠ 0 باشد، به هریک از دو گره i و j که NI آن بیشتر است، برچسب جدید انتساب داده می‏شود.

·       در غیر این صوت (اگر similarity(i,j) = 0 باشد) به این معنی است که گره‏ i نه‌تنها با گره j بلکه با هر گره دیگر گراف، هیچ همسایه مشترکی ندارد و در نتیجه بالاترین شباهت گره i با بقیه گره‏ها برابر با صفر شده است. در این صورت برچسب همسایه با بالاترین درجه را به هر دو گره انتساب داده می‏شود.

گام 4: درگام بعدی پنج درصد گره‏های با بیشترین اهمیت انتخاب می‏شود و برچسب آنها به شبیه‏ترین همسایه‏های آنها انتشار (تعمیم) داده می‏شود. اگر تعداد اعضای بعضی از جوامع از حد آستانه معینی کمتر باشد، این جوامع در هم ادغام می‏شوند تا جوامعی با تعداد اعضای مناسب تشکیل شود.

گام 5: ایده و نوآوری اصلی راهکار پیشنهادی ما در این گام اعمال می‏گردد:

·       برای هر یک از جوامع (خوشه‏های) شناسایی‏شده در مرحله قبل مثل c، معیار sk به‌صورت زیر تعریف می‏شود:

 

(2)

 

·       سپس برای هر جامعه بررسی می‏شود که آیا مقدار sk آن از یک مقدار حد آستانه p بیشتر است یا نه. اگر بیشتر باشد، جامعه به همین صورت حفظ می‏شود. در غیر این صورت جامعه باید به جوامع کوچک‏تر و قوی‏تری تفکیک شود. برای این منظور الگوریتم شناسایی جوامع به‌صورت بازگشتی روی جامعه موردنظر اجرا می‏شود. مقدار k به میزان قوی‏بودن مطلوب جامعه بستگی دارند و بدیهی است که حداقل آن 1 و حداکثر آن n-1 است که n تعداد رأس‏های جامعه (زیرگراف) را نشان می‏دهد.

نکته قابل‌ذکر در آخرین مرحله الگوریتم پیشنهادی یعنی مرحله شکستن (تفکیک) جوامع ضعیف و تشکیل جوامع قوی‏تر با یک رویکرد بازگشتی صورت می‏گیرد به‌این‌ترتیب که مجدداً در این مرحله، الگوریتم انتشار برچسب با استفاده از معیار h-index بهبودیافته بر روی جوامعی که نیاز به تفکیک بیشتر دارند، اجرا می‏گردد.

مقدار k و p به میزان قوی‏بودن مطلوب جامعه بستگی دارند. بدیهی است که حداقل مقدار k برابر با 1 و حداکثر آن n-1 است که n تعداد رأس‏های جامعه (زیرگراف) را نشان می‏دهد. مقدار p نیز درصد اعضایی از جامعه را نشان می‏دهد که حداقل با k عضو دیگر اتصال مستقیم دارند و بنابراین عددی بین صفر تا صددرصد است.

فلوچارت روش پیشنهادی در شکل (3) نشان داده شده است.

 

 

شکل 3. فلوچارت روش پیشنهادی

Figure 3. Flowchart of the proposed method

4- ارزیابی روش پیشنهادی

4-1- رویکرد ارزیابی و ابزار پیاده‏سازی

برای ارزیابی روش پیشنهادی، این روش پیاده‏سازی و بر روی چند مجموعه‏داده شناخته‏شده در این حوزه اعمال شده است و بر اساس معیارهای متداول در زمینه شناسایی جوامع با روش ارائه‏شده در مرجع [1] مقایسه صورت گرفته است.

پیاده‏سازی روش پیشنهادی با استفاده از نرم‏افزار Gephi انجام شده است. این نرم‏افزار یک محیط متن‏باز و رایگان است که به‌عنوان یکی از متداول‏ترین و کارآمدترین ابزارهای تحلیل و بصری‏سازی گراف‏ها و شبکه‏ها به‌صورت گسترده استفاده می‏شود و کارهای تحقیقاتی متعددی از جمله [17-19] از آن برای پیاده‏سازی الگوریتم‏های پیشنهادی خود در حوزه مدل‏سازی و تحلیل شبکه‏های اجتماعی استفاده کرده‏اند.

4-2- معیارهای ارزیابی

در حوزه شناسایی جوامع، برای ارزیابی و مقایسه کیفیت جوامع (خوشه‏های) استخراج‏شده، معیارهای مختلفی مورداستفاده قرار می‏گیرند که از جمله می‏توان به NMI (اطلاعات متقابل نرمال‏شده¹³) و پیمانگی (ماژولاریتی) اشاره کرد. این دو معیار هر دو نشان می‏دهند که تا چه حد میزان اتصالات در داخل هر جامعه قوی و اتصالات بین جوامع مختلف، ضعیف است.

معیارهای دیگری که برای این منظور استفاده می‏شوند عبارت‌اند از دقت¹⁴، یادآور یا فراخوانی¹⁵ و ¹⁶F1 که روابط مربوط به آنها به‌صورت زیر است [1]:

(3)

که در رابطه‏های فوق CD جامعه‏های شناسایی‏شده توسط الگوریتم موردبررسی و CR جامعه‏های واقعی بر اساس آنچه در مجموعه‏داده مشخص شده است را نشان می‏دهد. در واقع معیار دقت نشان می‏دهد که چه کسری از افراد یک جامعه شناسایی‏شده واقعاً عضو آن جامعه هستند و معیار فراخوانی نشان می‏دهد که چه کسری از افراد یک جامعه واقعی در جامعه شناسایی‏شده انتخاب شده‏اند و معیار F1 نوعی میانگین بین دو معیار قبلی است.

4-3- مجموعه‏داده‏های مورد استفاده در ارزیابی

چندین مجموعه‌داده مطرح برای ارزیابی الگوریتم‏های شناسایی جوامع در کارهای تحقیقاتی مشابه مورداستفاده قرار گرفته است که مهم‏ترین آنها که برای ارزیابی این تحقیق مورداستفاده قرار گرفته است، عبارتند از:

1- مجموعه‏داده باشگاه کاراته زاخاری: این مجموعه‌داده، یک شبکه اجتماعی است که از یک باشگاه کاراته به مدت سه سال از سال ۱۹۷۰ تا ۱۹۷۲ توسط واین زاخاری موردمطالعه قرار گرفت. این شبکه 34 عضو یک باشگاه کاراته را جذب می‏کند و 78 ارتباط بین جفت عضوهایی که در خارج از باشگاه تعامل دارند، وجود دارد. در طول مطالعه، اختلاف بین مدیر «جان.ای» و مربی «آقای های» (نام مستعار) به وجود آمد که منجر به تقسیم باشگاه به دو بخش شد. نیمی از اعضا در اطراف «­آقای های» یک باشگاه جدید تشکیل دادند؛ اعضای بخش دیگر یک مربی جدید پیدا کردند یا از کاراته دست کشیدند. در نهایت بر اساس داده‏های جمع‌‏آوری‌شده زاخاری، دو جامعه شکل گرفتند.

2- مجموعه داده دلفین‏ها: این مجموعه‌داده، یک شبکه اجتماعی بدون جهت از ارتباطات مکرر بین ۶۲ دلفین که با هم ‌بازی می‏کنند، تشکیل شده است. این دلفین‏ها در نیوزیلند زندگی می‏کنند. گروه دلفین‏ها عمدتاً به دو جامعه تقسیم می‏شوند: دلفین‏های نر و دلفین‏های ماده. 

3- مجموعه‏داده فوتبال: این مجموعه‌داده، شبکه‏ای از بازی‏های فوتبال آمریکایی است که بین دانشگاه‏های بخش آیووا برگزار شده است. این شبکه دارای 115 بازیکن و 613 یال است. یال‏های بین بازیکن‏ها نشان دهنده تعداد پاس‏هایی است که هر بازیکن به بازیکن دیگر می دهد. و به دوازده جامعه تقسیم می‏شوند که شامل مجموعه بازیکن‏های فوتبالی است، که در طول فصل پاییز سال 2000 با هم به رقابت پرداختند.

4- مجموعه‏داده آمازون: این مجموعه‏‌داده، شبکه‏ای از کتاب‏های مربوط به سیاست ایالات متحده است که نزدیک به انتخابات ریاست جمهوری ایالات متحده در سال 2004 منتشر شده است. این شبکه دارای 105 کتاب و 441 یال است. یال‏های بین کتاب‏ها نشان‏ دهنده خرید مشترک مکرر آن کتاب‏ها توسط همان خریداران است. این شبکه توسط والدیس کربس گردآوری شده است و توسط شرکت آمازون به فروش رسید و به سه جامعه تقسیم می‏شوند که شامل سه مجموعه کتاب‏های مرتبط به هم است.

 مشخصات این مجموعه‏داده‏ها در جدول (1) نشان داده شده و توضیح مختصر هریک از آنها در ادامه ارائه شده است.

 

جدول 1: مجموعه‏داده‏های درنظرگرفته‏شده برای ارزیابی و مقایسه راهکار پیشنهادی

Table 1: The datasets considered for evaluating and comparing the proposed solution.

	(4)
	(5)
	(6)

نام مجموعه‌داده	تعداد رأس‏ها (افراد)	تعداد یال‏ها (لینک‏ها)	تعداد جوامع (خوشه‏ها)
باشگاه کاراته زاخاری	34	78	2
دلفین‏ها	62	159	2
فوتبال	115	613	12
آمازون	334863	925872	75149

4-4- نتایج ارزیابی و مقایسه

اولین آزمایش به‌منظور تعیین مقدار اطلاعات متقابل نرمال‏شده (NMI) بر اساس روش پیشنهادی انجام شده است. این بررسی برای چهار مجموعه‌داده مورد ارزیابی قرار گرفته است. نتایج به‏دست‏آمده در جدول (2) نشان داده شده و با نتایج روش‏های موجود مقایسه شده است.

جدول 2: مقادیر NMI حاصل از روش پیشنهادی و مقایسه آن با نتایج روش‏های موجود

Table 2: NMI values obtained from the proposed method and a comparison with the results of existing methods.

نام مجموعه‌داده	الگوریتم LBLD [1]	الگوریتم LSMD [3]	الگوریتم مرجع [16]	روش پیشنهادی
باشگاه کاراته زاخاری	1	1	1	1
دلفین‏ها	1	1	0.98	1
فوتبال	0.91	0.93	0.92	0.95
آمازون	0.97	0.95	0.97	0.98

همان‏گونه که در جدول (2) مشاهده می‏شود، برای دو مجموعه داده باشگاه کاراته و دلفین‏ها که مجموعه‏هایی با تعداد کم رکورد هستند، الگوریتم پیشنهادی ما مانند دو الگوریتم مورد مقایسه، بهترین نتیجه ممکن یعنی مقدار NMI برابر با 1 را ارائه می‏کند. در مورد مجموعه‏داده‏های فوتبال و آمازون، مقدار NMI حاصل از راهکار پیشنهادی بیشتر از دو الگوریتم مورد مقایسه است که به معنی انتخاب جوامع قوی‏تر است.

آزمایش بعدی باهدف محاسبه F-measure بر اساس روش پیشنهادی و مقایسه آن با الگوریتم‏های قبلی است. نتایج این ارزیابی در جدول (3) نشان داده شده است.

جدول 3: مقادیر F-measure حاصل از روش پیشنهادی و مقایسه آن با نتایج روش‏های موجود

Table 3: F-measure values obtained from the proposed method and its comparison with the results of existing methods

نام مجموعه‌داده	الگوریتم LBLD [1]	الگوریتم LSMD [3]	الگوریتم مرجع [16]	روش پیشنهادی
باشگاه کاراته زاخاری	1	1	1	1
دلفین‏ها	1	1	0.99	1
فوتبال	0.916	0.910	0.914	0.923
آمازون	0.90	0.84	0.87	0.92

مطابق جدول 3 در مورد معیار F-measure هم نتایج روش پیشنهادی برابر یا قدری بهتر از نتایج دو الگوریتم مورد مقایسه است.

آزمایش بعدی به‌منظور محاسبه معیار پیمانگی در روش پیشنهادی و مقایسه آن با الگوریتم‏های موجود انجام شد که نتایج آن در شکل 4 ارائه شده است. لازم به ذکر است که با توجه به این که در مرجع [1] مقدار این معیار برای مجموعه داده آمازون گزارش شده است بنابراین ارزیابی و مقایسه روش پیشنهادی نیز بر روی همین مجموعه داده انجام گرفته است. شکل 4 نشان می‏دهد که راهکار پیشنهادی مقدار معیار پیمانگی را به میزان 2 درصد نسبت به الگوریتم و به میزان 5 درصد نسبت به الگوریتم LSMD بهبود داده است.

نکته قابل‌ملاحظه در نتایج حاصل این است که اگرچه اندازه مطلق بهبود مقادیر معیارهای NMI و F-measure در روش پیشنهادی نسبت به سایر روش‏های مورد مقایسه، جزئی به نظر می‌رسد؛ ولی اولاً در این حوزه تحقیقاتی، چون مقدار معیارهای ارزیابی بین صفر و یک است، اغلب بهبودها در این معیارها جزئی است و ثانیاً اگر مقدار نسبی و درصدی بهبود معیارهای ارزیابی موردتوجه قرار گیرد، ملاحظه می‏شود که درصد افزایش مقادیر NMI و F-measure قابل‌ملاحظه است و نشان می‏دهد که روش پیشنهادی کارایی قابل‌قبولی در شناسایی جوامع دقیق‏تر از خود نشان داده است.

آخرین آزمایش انجام‏شده برای تعیین مقدار بهینه پارامترهای k و p صورت گرفت که نتایج آن در جدول (4) ارائه شده است. همان طور که نتایج این جدول نشان می‏دهد بهترین مقادیر F-measure به ازای k=5, p=70% حاصل شده است یعنی شرایطی که در هر جامعه حداقل هفتاد درصد از اعضای جامعه هر یک حداقل با پنج عضو دیگر همان جامعه در ارتباط باشند.

 

شکل 4. مقدار معیار پیمانگی حاصل از روش پیشنهادی در مقایسه با الگوریتم‏های LBLD [1] و LSMD [3] بر روی مجموعه داده آمازون

Figure 4. The value of the evaluation metric obtained from the proposed method compared to the LBLD and LSMD algorithms on the Amazon dataset.

 

جدول 4: مقادیر F-measure حاصل از روش پیشنهادی به ازای مقادیر مختلف k و p

Table 4: F-measure values obtained from the proposed method for various values of k and p

نام مجموعه‌داده	k=5, p=60%	k=5, p=70%	k=7, p=60%	k=7, p=70%
باشگاه کاراته زاخاری	0.982	1	0.990	0.991
دلفین‏ها	0.976	1	0.968	1
فوتبال	0.903	0.923	0.909	0.916
آمازون	0.914	0.92	0.905	0.912

5- نتیجه‏گیری و کارهای آینده

مسئله استخراج جوامع در شبکه‏های اجتماعی در سال‏های اخیر توجه محققان را به خود جلب کرده است. به دلیل گسترش روزافزون کاربردهای این حوزه و باتوجه‌به اهمیت افزایش دقت استخراج جوامع، در این پایان‏نامه، راهکار جدیدی با بهبود یک الگوریتم موجود در این زمینه موسوم به LBLD [1] ارائه شد. برای این منظور از معیار شباهت جاکارد برای تعیین میزان مشابهت رأس‏های شبکه از نظر همسایه‏های مشترک استفاده شد. همچنین یک معیار جدید مبتنی بر مفهوم معیار h-index برای افزایش دقت شناسایی جوامع معرفی و استفاده شد. ایده پیشنهادی بر این اصل مبتنی است که برای قوی‏تر بودن یک جامعه شناسایی‏شده لازم است تعداد بیشتری از اعضای جامعه، اتصالات بیشتری با بقیه اعضای جامعه داشته باشند؛ بنابراین جوامعی که این شرط را برآورده نمی‏کنند در الگوریتم پیشنهادی به جوامع کوچک‏تر و قوی‏تری تفکیک می‏شوند.

در نهایت، راهکار پیشنهادی با پیاده‏سازی و اعمال بر روی چند مجموعه‏داده شناخته‏شده ارزیابی و با کار مرجع [1] مقایسه گردید. نتایج ارزیابی‏های انجام‏شده نشان‏دهنده بهبود میزان قوی‏بودن جوامع استخراج‏شده نسبت به روش‏های مورد مقایسه از نظر معیارهای NMI، ماژولاریتی و F-measure است. میزان بهبود این سه معیار بر روی مجموعه‏داده‏های مختلف نسبت به الگوریتم‏های مورد مقایسه به طور متوسط برابر با 3.2درصد، 3.5 درصد و 2.9درصد بوده است.

پیشنهادهای مختلفی در راستای ادامه کار این پژوهش و بهبود آن قابل‌طرح است که از جمله می‏توان به موارد زیر اشاره کرده:

·       برای بررسی کیفیت جوامع شناسایی‏شده، علاوه بر ارزیابی میزان اتصالات داخل هر جامعه، میزان اتصالات بین جوامع نیز مورد ارزیابی قرار گیرد؛ زیرا شناسایی جوامع به‌صورت مطلوب، زمانی حاصل می‏شود که ارتباطات در داخل هر جامعه، بیشینه و بین جوامع مختلف، کمینه باشد.

·       پیشنهاد دیگر، استفاده از الگوریتم‏های یادگیری ماشین یا روش‏های فراابتکاری و تکاملی برای تعیین مقدار پارامترهای k و p در روش پیشنهادی است.

·       همچنین می‏توان از ترکیب ایده پیشنهادی در این مقاله با الگوریتم‏های خوشه‏بندی کلاسیک و شناخته‏شده به‌منظور افزایش دقت شناسایی جوامع استفاده کرد.

مراجع

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

[17] Hernández-García, Á., Cuenca-Enrique, C., Traxler, A., López-Pernas, S., Conde-González, M. Á., & Saqr, M. (2024). Community detection in learning networks using R. In Learning analytics methods and tutorials: a practical guide using R (pp. 519-540). Cham: Springer Nature Switzerland.

[18 Yilmaz, C. B., Dagdeviren, Z. A., & Unalir, M. O. (2024, September). Identifying Social Connections: An Empirically-Driven Evaluation of Community Detection Methods on Twitter. In 2024 8th International Artificial Intelligence and Data Processing Symposium (IDAP) (pp. 1-8). IEEE.

[19] Rostami, M., Oussalah, M., Berahmand, K., & Farrahi, V. (2023). Community detection algorithms in healthcare applications: A systematic review. IEEE Access, 11, 30247-30272.

[20] Su, S., Guan, J., Chen, B., & Huang, X. (2023). Nonnegative matrix factorization based on node centrality for community detection. ACM Transactions on Knowledge Discovery from Data, 17(6), 1-21.

---

[1]  Local Similarity Multi-level Diffusion

[2]  Local Balanced Label Diffusion

[3]  Label influence Policy for Label Propagation Algorithm

[4]  Label Propagation Algorithm

[5]   Importance based Label Propagation Algorithm

[6]  Community Detection based on the Matthew Effect

[7]  Local Community Detection based on high importance nodes Ranking 

[8]  Graph Convolutional Network

[9]  Degree centrality

[10]  modularity-based

[11]  Affinity Propagation with Adaptive Similarity

[12]  Node Importance

[13]  Normalized Mutual Information

[14]  Precision

[15]  Recall

[16]  F-Score /F-measure