A Method for Decentralized Clustering in Large Multi-Agent Systems

This paper examines a method of clustering within a fully decentralized multi-agent system. Our goal is to group agents with similar objectives or data, as is done in traditional clustering. However, we add the additional constraint that agents must remain in place on a network, instead of first being collected into a centralized database. To do this we connect agents in a random network and have them search in a peer-to-peer fashion for other similar agents. We thus aim to tackle the basic clustering problem on an Internet scale and create a method by which agents themselves can be grouped, forming coalitions. In order to investigate the feasibility of a decentralized approach, this paper presents a number of simulation experiments involving agents representing two-dimensional points. A comparison between our method's clustering ability and that of the k-means clustering algorithm is presented. Generated data sets containing 2,500 to 160,000 points (agents) grouped in 25 to 1,600 clusters are examined. Results show that our decentralized agent method produces a better clustering than the centralized k-means algorithm, quickly placing 95% to 99% of points correctly. The the time required to find a clustering depends on the quality of solution required; a fairly good solution is quickly converged on, and then slowly improved. Overall, our experiments indicate that the time to find a particular quality of solution increases less than linearly with the number of agents.