رویکردی نوین چند مرحلهای برای تشخیص انجمن در شبکههای اجتماعی مبتنی بر خوشهبندی فازی DBSCAN و بهینهسازی جستجوی خزنده
کلمات کلیدی:
تشخیص انجمن, شبکههای پیچیده, DBSCAN, الگوریتم جستجوی خزنده (RSA), ماژولاریتی, شاخص NMIچکیده
تشخیص انجمن یکی از مسائل بنیادی در تحلیل شبکههای پیچیده و اجتماعی است که هدف آن شناسایی گروههایی از گرهها با ارتباطات درونی متراکمتر نسبت به سایر بخشهای شبکه میباشد. چالش اصلی در این حوزه، عدم آگاهی از تعداد دقیق جوامع و حجم بالای گرهها در شبکههای واقعی است. در این پژوهش، یک رویکرد چندمرحلهای نوین ارائه میشود که از ترکیب الگوریتم خوشهبندی مبتنی بر چگالی (DBSCAN) و الگوریتم بهینهسازی جستجوی خزنده (RSA) بهره میگیرد. در مرحله اول، با استفاده از DBSCAN و ویژگیهای استخراجشده از گرهها بهویژه لیست همسایگان، خوشهبندی اولیه شبکه انجام میشود. در مرحله دوم، الگوریتم RSA با سه فاز مقداردهی اولیه، اکتشاف و بهرهبرداری، جوامع نهایی را شناسایی میکند. تابع هدف بر پایه دو معیار ماژولاریتی (Q) و پراکندگی (Cond) تعریف شده است. روش پیشنهادی روی هشت مجموعهداده واقعی شامل ca-GrQc، ca-HepPh، ca-HepTh، ca-AstroPh، ca-CondMat، شبکه کاراته، فوتبال کالج آمریکایی و شبکه دلفین در محیط MATLAB ارزیابی شده است. نتایج آزمایشها نشان میدهد که روش پیشنهادی در اکثر موارد عملکرد بهتری نسبت به روشهای موجود دارد و مقادیر بالاتری از شاخصهای NMI و ماژولاریتی Q را به دست میآورد.
مراجع
1. Plantié, M. and M. Crampes, Survey on Social Community Detection, in Social Media Retrieval, P. Springer, Editor. 2013, Springer Publishers. p. 65–85.
2. Aghaalizadeh, S., et al., 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, 2021. 563: p. 125420.
3. Zhang, W., R. Shang, and L. Jiao, Large-scale community detection based on core node and layer-by-layer label propagation. Information Sciences, 2023. 632: p. 1–18.
4. Ullah, A., et al., A novel relevance-based information interaction model for community detection in complex networks. Expert Systems with Applications, 2022. 196: p. 116607.
5. Gharehchopogh, F.S., An improved Harris Hawks optimization algorithm with multi-strategy for community detection in social network. Journal of Bionic Engineering, 2023. 20(3): p. 1175–1197.
6. Gmati, H., et al., A new algorithm for communities detection in social networks with node attributes. Journal of Ambient Intelligence and Humanized Computing, 2024. 15(2): p. 1779–1791.
7. Aliabadi, M. and H. Ghaffari, Community detection using Jaya optimization algorithm based on deep learning methods and KNN graph-based clustering. Journal of Modelling in Management, 2025. 20(3): p. 872–893.
8. Xu, R., et al., Stacked autoencoder-based community detection method via an ensemble clustering framework. Information sciences, 2020. 526: p. 151–165.
9. Park, N., et al., CGC: Contrastive Graph Clustering for Community Detection and Tracking. 2022.
10. Tang, X., et al., Link community detection by non-negative matrix factorization with multi-step similarities. Modern Physics Letters B, 2016. 30(32n33): p. 1650370.
11. Zhang, D., et al., A novel two-step community detection approach based on community tree and the N-players cooperative game in large-scale social networks. Journal of Computational Methods in Science and Engineering, 2018. 18(4): p. 1007–1020.
12. Aynaud, T. and J.-L. Guillaume, Multi-Step Community Detection and Hierarchical Time Segmentation in Evolving Networks. Âl' ACM, 2011.
13. Jain, A.K., M.N. Murty, and P.J. Flynn, Data clustering: a review. ACM computing surveys (CSUR), 1999. 31(3): p. 264–323.
14. Saxena, A., et al., A review of clustering techniques and developments. Neurocomputing, 2017. 267: p. 664–681.
15. Liu, Y., et al., Hierarchical community discovery for multi-stage IP bearer network upgradation. Journal of Network and Computer Applications, 2021. 189: p. 103151.
16. Li, H., et al., LMFLS: A new fast local multi-factor node scoring and label selection-based algorithm for community detection. Chaos, Solitons & Fractals, 2024. 185: p. 115126.
17. Abualigah, L., et al., Reptile Search Algorithm (RSA): A nature-inspired meta-heuristic optimizer. Expert Systems with Applications, 2022. 191: p. 116158.
18. Bouyer, A. and H. Roghani, LSMD: A fast and robust local community detection starting from low degree nodes in social networks. Future Generation Computer Systems, 2020. 113: p. 41–57.
19. Ding, X., J. Zhang, and J. Yang, A robust two-stage algorithm for local community detection. Knowledge-Based Systems, 2018. 152: p. 188–199.
20. Newman, M.E., Modularity and community structure in networks. Proc Natl Acad Sci U S A, 2006. 103(23): p. 8577–82.
21. Blondel, V., et al., Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics Theory and Experiment, 2008. 2008.
22. Rosvall, M. and C.T. Bergstrom, Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci U S A, 2008. 105(4): p. 1118–23.
23. Girvan, M. and M.E. Newman, Community structure in social and biological networks. Proc Natl Acad Sci U S A, 2002. 99(12): p. 7821–6.
24. حسینی, م. and ا. گلوی, تشخیص اجتماع در شبکههای اجتماعی با رویکرد یادگیری عمیق. مطالعات مدیریت کسب و کار هوشمند, 2023. 12(44): p. 83–112.
25. Bouguettaya, A., et al., Efficient agglomerative hierarchical clustering. Expert Systems with Applications, 2015. 42.
26. Ester, M., et al. A density-based algorithm for discovering clusters in large spatial databases with noise. in kdd. 1996.
27. Aynaud, T. and J.-L. Guillaume. Détection de communautés à long terme dans les graphes dynamiques. in Journée thématique: Fouille de grands graphes. 2010.
28. برهمند, ک. and ح. احمدی بنی, یک طبقه بندی برای روشهای تشخیص انجمن در شبکههای اجتماعی, in اولین کنفرانس ملی محاسبات توزیعی و پردازش دادههای بزرگ. 1394.
29. شفیعی موسوی, ع. and م. مزینانی, مروری بر روشهای تشخیص جوامع در شبکههای اجتماعی, in دوازدهمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات. 1400.
30. طباطبائی, آ. and م. زندی نژاد, الگوریتمی مبتنی بر انتطار برچسب در تشخیص اجتماعات در شبکههای اجتماعی, in هشتمین کنفرانس بین المللی وب پژوهی. 1401.
31. abdar, s.e., Using garter snakes optimization algorithm for community detection in dynamic social networks. journal of Information and communication Technology in policing, 2020. 1(2): p. 45–54.
32. خفائی, ط., et al., تشخیص انجمنهای پایدار در شبکههای اجتماعی پویا با استفاده از گرههای با نفوذ. 1401.
33. میرزایی, م. and ا.ا. مه آبادی, روش ترکیبی تشخیص ناهنجاری با استفاده از تشخیص انجمن در گراف و انتخاب ویژگی. 1399.
34. هوشمندنژاد, ت. and م. نوش فر, تشخیص انجمن در گراف شبکههای اجتماعی با استفاده از شباهت ساختاری بین افراد, in اولین کنفرانس بین المللی چشم اندازهای نو در مهندسی برق و کامپیوتر. 1395.
35. Deypir, M. and E. Bayat, Identifying Community Structures in Social Networks using Discrete Harmony Search Algorithm. Signal and Data Processing, 2023. 20(3): p. 47–60.
36. Shahriari, M., Proposing a Model for Data Clustering Based on Harmonic Search Algorithm. Journal of Operational Research In Its Applications (Applied Mathematics)-Lahijan Azad University, 2016. 13(3): p. 1–7.
37. Mir Mohammad, A. and A. Mohsen, A Multiagent Reinforcement Learning algorithm to solve the Community Detection Problem. Signal and Data Processing, 2022. 19(1): p. 87–100.
38. فائزه شریف, ز., ک. سمیه, and ب. مرتضی, ارائه روشی جدید برای شناسایی گرههای فعال و تاثیرگذار در شبکههای اجتماعی, in همایش ملی مهندسی رایانه و مدیریت فناوری اطلاعات. 1393.
39. کریمی, ح., الگوریتم خوشه بندی گرههای حسگر با توجه به تراکم گرهها در شبکه-های حسگر بی سیم. 1400.
40. رضایی, ع., م. باستانی, and س. آدابی, الگوریتم مکان یابی پویا مبتنی بر خوشه برای مکان یابی گرهها در شبکه موردی متحرک, in دومین کنفرانس بین المللی یافتههای نوین پژوهشی در علوم،مهندسی و فناوری. 1395.
41. علیخانی, م. and م. ابادی, روشی مبتنی بر خوشه بندی برای تشخیص ناهنجاری پویا در شبکههای اقتضایی متحرک با پروتکل مسیریابیAODV, in هفتمین کنفرانس انجمن رمز ایران. 1389.
42. عثمانی, ا., ا. طرقی حقیقت, and ح. پوراکبر, طراحی و ارزیابی یک الگوریتم مقیاس پذیر برای مدیریت مکان گرههای سیار در پروتکلهای مسیریابی مبتنی بر مکان در شبکههای سیار موردی, in پانزدهمین کنفرانس کامپیوتر سالانه انجمن کامپیوتر ایران. 1388.
43. Behnamian, J. and A.H. Safargholi, A Hybirid Algorithm for Hub Location Problem in Multimodal Logistic Networks. Journal of Transportation Engineering, 2018. 10(2): p. 335–355.
دانلود
گاهشمار انتشار
- ارسال
- بازنگری
- پذیرش
شماره
نوع مقاله
مجوز
حق نشر 1405 مصطفی علی آبادی, حمیدرضا غفاری (نویسنده)

این پروژه تحت مجوز بین المللی Creative Commons Attribution-NonCommercial 4.0 می باشد.