ارائه الگوریتمی جدید برای تشخیص اجتماع با استفاده از یادگیری تقویتی چندعاملی

مساله تشخیص اجتماع، یکی از مسائل چالش‌برانگیز بهینه‌سازی است که شامل جستجو برای اجتماعاتی است که به یک شبکه یا گراف تعلق دارند و گره‌های عضو هر یک از آن‌ها دارای ویژگی‌های مشترک هستند، که تشخیص ویژگی‌های جدید یا روابط خاص در شبکه را ممکن می‌سازند. اگرچه برای مساله تشخیص اجتماع الگوریتم‌های متعددی ارائه‌شده است، اما بسیاری از آن‌ها در مواجه با شبکه‌های با مقیاس بزرگ قابل‌استفاده نیستند و از هزینه محاسباتی بسیار بالایی برخوردارند. در این مقاله، الگوریتم جدیدی مبتنی بر یادگیری تقویتی چندعاملی برای تشخیص اجتماع در شبکه‌های پیچیده ارائه خواهیم کرد که در آن، هر عامل یک موجودیت مستقل با پارامترهای یادگیری متفاوت هستند و بر اساس همکاری بین عامل‌ها، الگوریتم پیشنهادی به‌صورت تکرارشونده و بر اساس مکانیزم یادگیری تقویتی، به جستجوی اجتماعات بهینه می‌پردازد. کارایی الگوریتم پیشنهادی را بر روی چهار شبکه واقعی و تعدادی شبکه مصنوعی ارزیابی شده است، و با تعدادی از الگوریتم‌های مشهور در این زمینه مقایسه می‌کنیم. بر اساس ارزیابی‌ انجام‌گرفته، الگوریتم پیشنهادی علاوه بر دقت بالا در تشخیص اجتماع، از سرعت و پایداری مناسبی برخوردار است و قابلیت رقابت و حتی غلبه بر الگوریتم‌های مطرح در زمینه تشخیص اجتماع را نیز داشته و نتایج الگوریتم پیشنهادی بر اساس معیارهای qماجولاریتی و nmi متوسط بر روی شبکه‌های واقعی و مصنوعی به‌ترتیب 12.33%، 9.85% و بیش از 21 % بهتر از الگوریتم‌های مورد مقایسه است.

A Multiagent Reinforcement Learning algorithm to solve the Community Detection Problem

Recent researches show that diverse systems in many different areas can be represented as complex networks. Examples of these include the Internet, social networks and so on. In each case, the system can be modeled as a complex and very large network consisting of a large number of entities and associations between them. Most of these networks are generally sparse in global yet dense in local. They have vertices in a group structure and the vertices within a group have higher density of edges while vertices among groups have lower density of edges. Such a structure is called community and is one of the important features of the network and is able to reveal many hidden characteristics of the networks. Today, community detection is used to improve the efficiency of search engines and discovery of terrorist organizations on the World Wide Web. Community detection is a challenging NPhard optimization problem that consists of searching for communities. It is assumed that the nodes of the same community share some properties that enable the detection of new characteristics or functional relationships in a network. Although there are many algorithms developed for community detection, most of them are unsuitable when dealing with large networks due to their computational cost.Nowadays, multiagent systems have been used to solve different problems, such as constraint satisfaction problems and combinatorial optimization problems with satisfactory results. In this paper, a new multiagent reinforcement learning algorithm is proposed for community detection in complex networks. Each agent in the multiagent system is an autonomous entity with different learning parameters. Based on the cooperation among the learning agents and updating the action probabilities of each agent, the algorithm interactively will identify a set of communities in the input network that are more densely connected than other communities. In other words, some independent agents interactively attempt to identify communities and evaluate the quality of the communities found at each stage by the normalized cut as objective function; then, the probability vectors of the agents are updated based on the results of the evaluation. If the quality of the community found by an agent in each of the stages is better than all the results produced so far, then it is referred to as the successful agent and the other agents will update their probability vectors based on the result of the successful agent. In the experiments, the performance of the proposed algorithm is validated on four realworld benchmark networks: the Karate club network, Dolphins network, Political books network and College football network, and synthetic LFR benchmark graphs with scales of 1000 and 5000 nodes. LFR networks are suitable for systematically measuring the property of an algorithm.Experimental results show that proposed approach has a good performance and is able to find suitable communities in large and small scale networks and is capable of detecting the community in complex networks In terms of speed, precision and stability. Moreover, according to the systematic comparison of the results obtained by the proposed algorithm with four stateoftheart community detection algorithms, our algorithm outperforms the these algorithms in terms of modularity and NMI; also, it can detect communities in small and large scale networks with high speed, accuracy, and stability, where it is capable of managing largescale networks up to 5000 nodes.