Replicator Graph Clustering

In this paper we introduce an efficient, effective and scalable clustering method denoted as Replicator Graph Clustering. Our method takes measures of similarity between pairs of data points (i. e. an affinity matrix) as input and identifies a set of clusters and unique cluster assignments in a fully unsupervised manner, where the cluster granularity is adaptable by a single parameter. We provide clustering results in three subsequent steps: (a) diffusing affinities by finding personalized evolutionary stable strategies of non-cooperative games (b) building a mutual k-nearest neighbor graph representing the underlying manifold and (c) applying a graph based clustering strategy which identifies the final clusters. Individual steps have low computational complexity which leads to an efficient clustering method, scaling well with an increasing number of data points. Experimental evaluation demonstrates competitive performance to state-of-the-art in several application fields.