Spectral clustering in multi-agent systems

We examine the application of spectral clustering for breaking up the behavior of a multi-agent system in space and time into smaller, independent elements. We propose clustering observations of individual entities in order to identify significant changes in the parameter space (like spatial position) and detect temporal alterations of behavior within the same framework. Available knowledge of important interactions (events) between entities is also considered. We describe a novel algorithm utilizing iterative subdivisions where clusters are pre-processed at each step to counter spatial scaling, rotation, replay speed, and varying sampling frequency. A method is presented to balance spatial and temporal segmentation based on the expected group size, and a validity measure is introduced to determine the optimal number of clusters. We demonstrate our results by analyzing the outcomes of computer games and compare our algorithm to K-means and traditional spectral clustering.