تشخیص جوامع در شبکه‌های پیچیده با استفاده از آتاماتای یادگیر

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان

دانشکده مهندسی برق و کامپیوتر، دانشگاه کاشان، کاشان، ایران.

چکیده

شبکه‌‌های اجتماعی یکی از انواع شبکه‌‌های پیچیده است. تشخیص جوامع در شبکه‌‌های اجتماعی روشی مؤثر برای بهره‌گیری از اطلاعات این شبکه‌‌ها است که تاکنون الگوریتم‌‌های متعددی برای آن ارائه شده است. در این مقاله روش‌هایی جدید با استفاده از آتوماتاهای یادگیر پیشنهاد شده است که در آنها، یک آتوماتای یادگیر به هر گره شبکه الحاق می‌شود؛ تعداد اقدام آتوماتاهای یادگیر ثابت و برابر با تخمین تعداد جوامع شبکه است. در هر مرحله، هر کدام از آتوماتاهای یادگیر یک اقدام از مجموعه اقدامات خود را انتخاب می‌‌کند. انتخاب هر یک از این اقدام‌‌ها به‌منزله‌ی انتساب برچسب آن جامعه به گره است. اقدام انتخاب‌شده توسط هر آتوماتا بر اساس اقدام‌‌های انتخابی همسایگانش (بررسی محلی) و/یا جوامع تشخیص داده شده توسط کل روش (بررسی سراسری) ارزیابی می‌‌شود. نتیجه‌‌ی ارزیابی منجر به صدور پاداش و جریمه برای آتوماتاها می‌شود. با دریافت پاداش احتمال انتخاب مجدد اقدام انتخابی توسط آتوماتا، یا همان برچسب جامعه، افزایش می‌‌یابد و با دریافت جریمه احتمال این اقدام کاهش می‌‌یابد. با تکرار الگوریتم، اقدام بهینه مشخص می‌‌گردد تا آنجا که با تکرارهای بیشتر هیچ تغییری در برچسب انتخابی آتوماتای متناظر هر گره رخ نمی‌‌دهد و درنتیجه جوامع بهینه به‌‌عنوان خروجی الگوریتم مشخص می‌‌گردند. مقایسه نتایج حاصل از آزمایش‌های انجام‌شده، نشان می‌دهد روش‌های پیشنهادی نسبت به برخی روش‌‌های پیشین عملکرد بهتری را نشان می‌‌دهد؛ به خصوص بر اساس معیار NMI که یکی از معیارهای رایج در ارزیابی روش‌های تشخیص جامعه است.

کلیدواژه‌ها


[1] A. Rezvanian, M. Rahmati, and M. R. Meybodi, “Sampling from complex networks using distributed learning automata,” Physica A: Statistical Mechanics and its Applications, vol. 396. pp. 224–234, 2014.
[2] R. Albert and A. L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, no. 1, pp. 47–97, 2002.
[3]  R. Rabbany, M. Takaffoli, J. Fagnan, O. R. Zaïane, and R. J. G. B. Campello, “Communities validity: methodical evaluation of community mining algorithms,” Social Network Analysis and Mining, vol.3, pp.1039-1062, 2013.
[4]  B. Krishnamurthy and J. Wang, “On network-aware clustering of Web clients,” Computer Communication Review, vol.30, pp. 97-110, 2000.
[5] S. Fortunato and M. Barthé, “Resolution limit in community detection,” Proceedings of the National Academy of Sciences of the United States of America, vol.104, no.1, pp. 36-41, 2007.
[6] M. A. L. Thathachar and P. S. Sastry, “Varieties of learning automata: An overview,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 32, no. 6. pp. 711–722, 2002.
[7] J. Kim and T. Wilhelm, “What is a complex graph?” Physica A: Statistical Mechanics and its Applications. vol. 387, no. 11, pp. 2637–2652, 2008.
[8] T. S. Evans, Complex networks, Contemporary Physics, vol. 45, no. 6, pp. 455-474, 2004.
[9] S. Forman and B. K. Samanthula, “Secure Similar Document Detection: Optimized Computation Using the Jaccard Coefficient,” IEEE 4th International Conference on Big Data Security on Cloud (BigDataSecurity), pp. 1–4, 2018.
[10] C. A. Bliss, M. R. Frank, C. M. Danforth, and P. S. Dodds, “An evolutionary algorithm approach to link prediction in dynamic social networks,” Journal of Computational Science, vol. 5, no. 5, pp. 750–764, 2014.
[11] S. Fortunato, “Community detection in graphs,” Physics Reports. vol. 486, no. 3–5, pp. 75–174, 2010.
[12] J. Cheng, M. Leng, L. Li, H. Zhou, and X. Chen, “Active semi-supervised community detection based on must-link and cannot-link constraints,” PLoS ONE, vol. 9, no. 10. 2014.
[13] M. M. D. Khomami, A. Rezvanian, and M. R. Meybodi, “Distributed learning automata-based algorithm for community detection in complex networks,” International Journal of Modern Physics B, vol. 30, no. 8. 2016.
[14] M. Ghamgosar, M. M. D. Khomami, N. Bagherpour, and M. Reza, “An extended distributed learning automata based algorithm for solving the community detection problem in social networks,” Iran. Conf. Electr. Eng. ICEE 2017, pp. 1520–1526, 2017.
[15] M. M. D. Khomami, A. Rezvanian, and M. R. Meybodi, “A new cellular learning automata-based algorithm for community detection in complex social networks”, Journal of Computational Science. vol. 24, no.1, pp. 413–426, 2018.
[16] M. M. Daliri Khomami, A. Rezvanian, A. M. Saghiri, and M. R. Meybodi, “Utilizing Cellular Learning Automata for Finding Communities in Weighted Networks,” the 6th International Conference on Web Research, ICWR 2020. pp. 325–329, 2020.
[17] M. M. Daliri Khomami, A. Rezvanian, A. M. Saghiri, and M. R. Meybodi, “Overlapping Community Detection in Social Networks Using Cellular Learning Automata,” the 28th Iran. Conf. Electr. Eng. pp. 1–6, 2020.
[18] A. Fathinavid, “Multilayer cellular learning automata: A computational model to solve multilayer infrastructure problems with its application in community detection for multilayer networks”, Journal of Computational Science, vol. 61, p. 101683, 2022.
[19] S. A. H. Minoofam, A. Bastanfard, and M. R. Keyvanpour, "A transfer learning algorithm to improve the convergence rate and accuracy in cellular learning automata", Nashriyyah-i Muhandisi-i Barq va Muhandisi-i Kampyutar-i Iran, vol. 88, no. 2, p. 69, 2021.
[20] M. M. D, Khomami, A. Rezvanian, and M. R. Meybodi, “CFIN: A community-based algorithm for finding influential nodes in complex social networks”, Journal of Supercomput, vol. 77, pp. 2207–2236, 2021.
[21] J. A. Almendral, I. Leyva, D. Li, I. Sendiña-Nadal, S. Havlin, and S. Boccaletti, “Dynamics of overlapping structures in modular networks,” Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, vol. 82, no. 1. 2010.
[22] M. Hamann, U. Meyer, M. Penschuck, H. Tran, and D. Wagner, “I/O-efficient generation of massive graphs following the LFR benchmark,” ACM Journal of Experimental Algorithmics, vol.23, 2018.
[23] M. E. J. Newman, “Spectral methods for community detection and graph partitioning,” Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. vol. 88, no. 4, pp. 042822, 2013.
[24] F. Hu, J. Liu, L. Li, and J. Liang, “Community detection in complex networks using Node2vec with spectral clustering,” Phys. A Stat. Mech. its Appl. vol. 545, pp. 123633, 2020.
[25] B. He, L. Gu, and X. D. Zhang, “Nodal domain partition and the number of communities in networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2012, no. 2. 2012.
[26] P. Wu and L. Pan, “Multi-Objective Community Detection Based on Memetic Algorithm,”, PLoS ONE, vol.10, no.5 2015.