Incremental pairwise clustering for large proximity matrices

Pairwise clustering methods are able to handle relational data, in which a set of objects is described via a matrix of pairwise (dis)similarities. Using the framework of source coding, it has been shown that pairwise clustering can be considered as entropy maximization problem under the constraint of keeping the distortion at a small value. This can be optimized via deterministic annealing. For the purpose of improving this optimization procedure, we have previously suggested two incremental pairwise clustering methods. However, they either only allow an even number of clusters, or cannot be applied to large proximity matrices. In this paper, we propose an incremental pairwise clustering method that resolves these issues. We compare the computational efficiency of the proposed algorithm to the previous incremental methods using simulations. Moreover, we apply the method to identify functionally connected brain networks by clustering a high-dimensional connectivity matrix obtained from resting state functional magnetic resonance imaging data.