During the last years, a wide range of huge networks has been made available to researchers. The discovery of natural groups, a task called
, in such datasets is a challenge arising in many applications such as the analysis of neural, social, and communication networks.
We here present
, a new graph clustering algorithm, which operates locally and hierarchically contracts the input. In contrast to most existing graph clustering algorithms, which operate globally,
is able to cluster inputs with hundreds of millions of edges in less than 2.5 hours, identifying clusterings with measurably high quality. Our approach explicitly avoids maximizing any single index value such as
, but instead relies on simple and sound structural operations. We present and discuss the
algorithm and evaluate its performance with respect to both clustering quality and running time, compared to other graph clustering algorithms.