دوره 19، شماره 1 - ( 3-1401 )
جلد 19 شماره 1 صفحات 100-87 |
برگشت به فهرست نسخه ها
گروه مهندسی کامپیوتر، دانشگاه بناب
چکیده: (1441 مشاهده)
مسأله تشخیص اجتماع، یکی از مسائل چالش‌برانگیز بهینه‌سازی است که شامل جستجو برای اجتماعاتی است که به یک شبکه یا گراف تعلق دارند و گره‌های عضو هر یک از آن‌ها دارای ویژگی‌های مشترک هستند، که تشخیص ویژگی‌های جدید یا روابط خاص در شبکه را ممکن می‌سازند. اگرچه برای مسأله تشخیص اجتماع الگوریتم‌های متعددی ارائه‌شده است، اما بسیاری از آن‌ها در مواجه با شبکه‌های با مقیاس بزرگ قابل‌استفاده نیستند و از هزینه محاسباتی بسیار بالایی برخوردارند. در این مقاله، الگوریتم جدیدی مبتنی بر یادگیری تقویتی چندعاملی برای تشخیص اجتماع در شبکه‌های پیچیده ارائه خواهیم کرد که در آن، هر عامل یک موجودیت مستقل با پارامترهای یادگیری متفاوت هستند و بر اساس همکاری بین عامل‌ها، الگوریتم پیشنهادی به‌صورت تکرارشونده و بر اساس مکانیزم یادگیری تقویتی، به جستجوی اجتماعات بهینه می‌پردازد. کارایی الگوریتم پیشنهادی را بر روی چهار شبکه واقعی و تعدادی شبکه مصنوعی ارزیابی شده است، و با تعدادی از الگوریتم‌های مشهور در این زمینه مقایسه می‌کنیم. بر اساس ارزیابی انجام‌گرفته، الگوریتم پیشنهادی علاوه بر دقت بالا در تشخیص اجتماع، از سرعت و پایداری مناسبی برخوردار است و قابلیت رقابت و حتی غلبه بر الگوریتم‌های مطرح در زمینه تشخیص اجتماع را نیز داشته و نتایج الگوریتم پیشنهادی بر اساس معیارهای Q-ماجولاریتی و NMI متوسط بر روی شبکه‌های واقعی و مصنوعی به‌ترتیب 33/12%، 85/9% و بیش از 21 % بهتر از الگوریتم‌های مورد مقایسه است.
شماره‌ی مقاله: 7
نوع مطالعه: پژوهشي |
موضوع مقاله:
مقالات پردازش داده‌های رقمی
دریافت: 1398/7/23 | پذیرش: 1400/9/15 | انتشار: 1401/4/1 | انتشار الکترونیک: 1401/4/1
دریافت: 1398/7/23 | پذیرش: 1400/9/15 | انتشار: 1401/4/1 | انتشار الکترونیک: 1401/4/1
فهرست منابع
1. [1] D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world'networks," nature, vol. 393, no. 6684, pp. 440, 1998. [DOI:10.1038/30918] [PMID]
2. [2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, "Complex networks: Structure and dynamics," Physics reports, vol. 424, no. 4-5, pp. 175-308, 2006. [DOI:10.1016/j.physrep.2005.10.009]
3. [3] M. E. Newman, "The structure and function of complex networks," SIAM review, vol. 45, no. 2, pp. 167-256, 2003. [DOI:10.1137/S003614450342480]
4. [4] S. Wasserman and K. Faust, Social network analysis: Methods and applications. Cambridge university press, 1994. [DOI:10.1017/CBO9780511815478]
5. [5] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: simple building blocks of complex networks," Science, vol. 298, no. 5594, pp. 824-827, 2002. [DOI:10.1126/science.298.5594.824] [PMID]
6. [6] U. Brandes et al., "On modularity clustering," IEEE transactions on knowledge and data engineering, vol. 20, no. 2, pp. 172-188, 2007. [DOI:10.1109/TKDE.2007.190689]
7. [7] J. Liu, W. Zhong, and L. Jiao, "A multiagent evolutionary algorithm for combinatorial optimization problems," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, no. 1, pp. 229-240, 2009. [DOI:10.1109/TSMCB.2009.2025775] [PMID]
8. [8] J. Liu, W. Zhong, and L. Jiao, "A multiagent evolutionary algorithm for constraint satisfaction problems," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 36, no. 1, pp. 54-73, 2006. [DOI:10.1109/TSMCB.2005.852980] [PMID]
9. [9] M. M. Alipour and S. N. Razavi, "A new multiagent reinforcement learning algorithm to solve the symmetric traveling salesman problem," Multiagent and Grid Systems, vol. 11, no. 2, pp. 107-119, 2015. [DOI:10.3233/MGS-150232]
10. [10] M. M. Alipour, S. N. Razavi, M. R. F. Derakhshi, and M. A. Balafar, "A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem," Neural Computing and Applications, pp. 1-17, 2017. [DOI:10.1007/s00521-017-2880-4]
11. [11] M. M. Alipour and M. Abdolhosseinzadeh, "A multiagent reinforcement learning algorithm to solve the maximum independent set problem," Multiagent and Grid Systems, vol. 16, no. 1, pp. 101-115, 2020. [DOI:10.3233/MGS-200323]
12. [12] M. E. Newman, "Modularity and community structure in networks," Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577-8582, 2006. [DOI:10.1073/pnas.0601602103] [PMID] [PMCID]
13. [13] 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. [DOI:10.1103/PhysRevE.70.066111] [PMID]
14. [14] J. M. Kumpula, J. Saramäki, K. Kaski, and J. Kertész, "Limited resolution and multiresolution methods in complex network community detection," Fluctuation and Noise Letters, vol. 7, no. 03, pp. L209-L214, 2007. [DOI:10.1142/S0219477507003854]
15. [15] S. Fortunato, "Community detection in graphs," Physics reports, vol. 486, no. 3-5, pp. 75-174, 2010. [DOI:10.1016/j.physrep.2009.11.002]
16. [16] L. Donetti and M. A. Munoz, "Detecting network communities: a new systematic and efficient algorithm," Journal of Statistical Mechanics: Theory and Experiment, vol. 2004, no. 10, pp. P10012, 2004. [DOI:10.1088/1742-5468/2004/10/P10012]
17. [17] M. Girvan and M. E. Newman, "Community structure in social and biological networks," Proceedings of the national academy of sciences, vol. 99, no. 12, pp. 7821-7826, 2002. [DOI:10.1073/pnas.122653799] [PMID] [PMCID]
18. [18] M. E. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical review E, vol. 69, no. 2, pp. 026113, 2004. [DOI:10.1103/PhysRevE.69.026113] [PMID]
19. [19] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, "Defining and identifying communities in networks," Proceedings of the national academy of sciences, vol. 101, no. 9, pp. 2658-2663, 2004. [DOI:10.1073/pnas.0400054101] [PMID] [PMCID]
20. [20] L. Hagen and A. B. Kahng, "A new approach to effective circuit clustering," in ICCAD, 1992, vol. 92, pp. 422-427. [DOI:10.1109/ICCAD.1992.279334]
21. [21] P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti, "Mixing local and global information for community detection in large networks," Journal of Computer and System Sciences, vol. 80, no. 1, pp. 72-87, 2014. [DOI:10.1016/j.jcss.2013.03.012]
22. [22] J. Cao, Z. Bu, Y. Wang, H. Yang, J. Jiang, and H.-J. Li, "Detecting prosumer-community groups in smart grids from the multiagent perspective," IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 8, pp. 1652-1664, 2019. [DOI:10.1109/TSMC.2019.2899366]
23. [23] C.-K. Han, S.-F. Cheng, and P. Varakantham, "A Homophily-Free Community Detection Framework for Trajectories with Delayed Responses," in Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019: International Foundation for Autonomous Agents and Multiagent Systems, pp. 2003-2005.
24. [24] X. Feng and X. Yang, "Fast convergent average consensus of multiagent systems based on community detection algorithm," Advances in Difference Equations, vol. 2018, no. 1, pp. 1-13, 2018. [DOI:10.1186/s13662-018-1901-7]
25. [25] P. Pons and M. Latapy, "Computing communities in large networks using random walks," J. Graph Algorithms Appl., vol. 10, no. 2, pp. 191-218, 2006. [DOI:10.7155/jgaa.00124]
26. [26] P. Ronhovde and Z. Nussinov, "Multiresolution community detection for megascale networks by information-based replica correlations," Physical Review E, vol. 80, no. 1, p. 016109, 2009. [DOI:10.1103/PhysRevE.80.016109] [PMID]
27. [27] M. Zhou and J. Liu, "A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks," Physica A: Statistical Mechanics and its Applications, vol. 410, pp. 131-143, 2014. [DOI:10.1016/j.physa.2014.05.002]
28. [28] T. N. Bui and B. R. Moon, "Genetic algorithm and graph partitioning," IEEE Transactions on computers, vol. 45, no. 7, pp. 841-855, 1996. [DOI:10.1109/12.508322]
29. [29] M. Tasgin, A. Herdagdelen, and H. Bingol, "Community detection in complex networks using genetic algorithms," arXiv preprint arXiv:0711.0491, 2007.
30. [30] C. Pizzuti, "Ga-net: A genetic algorithm for community detection in social networks," in International conference on parallel problem solving from nature, 2008: Springer, pp. 1081-1090. [DOI:10.1007/978-3-540-87700-4_107]
31. [31] A. Gog, D. Dumitrescu, and B. Hirsbrunner, "Community detection in complex networks using collaborative evolutionary algorithms," in European Conference on Artificial Life, 2007: Springer, pp. 886-894. [DOI:10.1007/978-3-540-74913-4_89]
32. [32] M. Gong, B. Fu, L. Jiao, and H. Du, "Memetic algorithm for community detection in networks," Physical Review E, vol. 84, no. 5, p. 056101, 2011. [DOI:10.1103/PhysRevE.84.056101] [PMID]
33. [33] J. Liu, W. Zhong, H. A. Abbass, and D. G. Green, "Separated and overlapping community detection in complex networks using multiobjective evolutionary algorithms," in IEEE Congress on Evolutionary Computation, 2010: IEEE, pp. 1-7. [DOI:10.1109/CEC.2010.5586522]
34. [34] X. Liu and T. Murata, "Advanced modularity-specialized label propagation algorithm for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, vol. 389, no. 7, pp. 1493-1500, 2010. [DOI:10.1016/j.physa.2009.12.019]
35. [35] J. Duch and A. Arenas, "Community detection in complex networks using extremal optimization," Physical review E, vol. 72, no. 2, p. 027104, 2005. [DOI:10.1103/PhysRevE.72.027104] [PMID]
36. [36] B. Yang and D.-Y. Liu, "Force-based incremental algorithm for mining community structure in dynamic network," Journal of Computer Science and Technology, vol. 21, no. 3, pp. 393-400, 2006. [DOI:10.1007/s11390-006-0393-1]
37. [37] I. Gunes and H. Bingol, "Community detection in complex networks using agents," arXiv preprint cs/0610129, 2006.
38. [38] Z. Li and J. Liu, "A multi-agent genetic algorithm for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, vol. 449, pp. 336-347, 2016. [DOI:10.1016/j.physa.2015.12.126]
39. [39] J. Huang, B. Yang, D. Jin, and Y. Yang, "Decentralized mining social network communities with agents," Mathematical and Computer Modelling, vol. 57, no. 11-12, pp. 2998-3008, 2013. [DOI:10.1016/j.mcm.2013.03.005]
40. [40] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," nature, vol. 435, no. 7043, p. 814, 2005. [DOI:10.1038/nature03607] [PMID]
41. [41] S. J. Russell and P. Norvig, Artificial intelligence: a modern approach. Malaysia; Pearson Education Limited, 2016.
42. [42] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. Cambridge: MIT press, 1998. [DOI:10.1109/TNN.1998.712192]
43. [43] L. P. Kaelbling, M. L. Littman, and A. W. Moore, "Reinforcement learning: A survey," Journal of Artificial Intelligence Research, vol. 4, pp. 237-285, 1996. [DOI:10.1613/jair.301]
44. [44] P. Stone and M. Veloso, " Multiagent systems: A survey from the machine learning perspective," Autonomous Robots, vol. 8, no. 3, pp. 345-383, 2000. [DOI:10.1023/A:1008942012299]
45. [45] S. Sen and G. Weiss, "Learning in multiagent systems," in Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, G. Weiss Ed.: MIT Press, 1999, ch. 6, pp. 259-298.
46. [46] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. MIT Press, 1998. [DOI:10.1109/TNN.1998.712192]
47. [47] I. S. Dhillon, Y. Guan, and B. Kulis, "Kernel k-means: spectral clustering and normalized cuts," in Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, 2004: ACM, pp. 551-556. [DOI:10.1145/1014052.1014118] [PMID]
48. [48] J. Shi and J. Malik, "Normalized cuts and image segmentation," Departmental Papers (CIS), pp. 107, 2000.
49. [49] W. W. Zachary, "An information flow model for conflict and fission in small groups," Journal of anthropological research, vol. 33, no. 4, pp. 452-473, 1977. [DOI:10.1086/jar.33.4.3629752]
50. [50] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations," Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396-405, 2003. [DOI:10.1007/s00265-003-0651-y]
51. [51] V. Krebs, "Books about us politics," unpublished, http://www.orgnet.com, 2004.
52. [52] A. Lancichinetti, S. Fortunato, and F. Radicchi, "Benchmark graphs for testing community detection algorithms," Physical review E, vol. 78, no. 4, p. 046110, 2008. [DOI:10.1103/PhysRevE.78.046110] [PMID]
53. [53] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, "Comparing community structure identification," Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 09, pp. P09008, 2005. [DOI:10.1088/1742-5468/2005/09/P09008]
54. [54] M. Tokic, F. Schwenker, and G. Palm, "Meta-learning of exploration and exploitation parameters with replacing eligibility traces," presented at the In IAPR International Workshop on Partially Supervised Learning (pp. 68-79). Springer Berlin Heidelberg, 2013, May. [DOI:10.1007/978-3-642-40705-5_7]
55. [55] K. Kobayashi, H. Mizoue, T. Kuremoto, and M. Obayashi, "A meta-learning method based on temporal difference error," presented at the In International Conference on Neural Information Processing (pp. 530-537). Springer Berlin Heidelberg, 2009, December. [DOI:10.1007/978-3-642-10677-4_60]
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |