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 NP-hard 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 real-world 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 state-of-the-art 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 large-scale networks up to 5000 nodes.