Partitioning networks into clusters and residuals with average association

We investigate the problem of detecting clusters exhibiting higher-than-average internal connectivity in networks of interacting systems. We show how the average association objective formulated in the context of spectral graph clustering leads naturally to a clustering strategy where each system is assigned to at most one cluster. A residual set is formed of the systems that are not members of any cluster. Maximization of the average association objective leads to a discrete optimization problem, which is difficult to solve, but a relaxed version can be solved using an eigendecomposition of the connectivity matrix. A simple approach to extracting clusters from a relaxed solution is described and developed by applying a variance maximizing solution to the relaxed solution, which leads to a method with increased accuracy and sensitivity. Numerical studies of theoretical connectivity models and of synchronization clusters in a lattice of coupled Lorenz oscillators are conducted to show the efficiency of the proposed approach. The method is applied to an experimentally obtained human resting state functional magnetic resonance imaging dataset and the results are discussed.