GANC: Greedy agglomerative normalized cut for graph clustering

This paper describes a graph clustering algorithm that aims to minimize the normalized cut criterion and has a model order selection procedure. The performance of the proposed algorithm is comparable to spectral approaches in terms of minimizing normalized cut. However unlike spectral approaches, the proposed algorithm scales to graphs with millions of nodes and edges. The algorithm consists of three components that are processed sequentially: a greedy agglomerative hierarchical clustering procedure, model order selection, and a local refinement.For a graph of n nodes and O(n  ) edges, the computational complexity of the algorithm is O(nlog2n), a major improvement over the O(n3)O(n3) complexity of spectral methods. Experiments are performed on real and synthetic networks to demonstrate the scalability of the proposed approach, the effectiveness of the model order selection procedure, and the performance of the proposed algorithm in terms of minimizing the normalized cut metric.

► Novel graph clustering algorithm that strives to minimize the normalized cut metric. ► Includes effective and efficient model selection technique. ► Scalable to graphs of millions of nodes and edges. ► Performs comparably to much more computationally complex spectral methods. ► Quantitative and qualitative comparison with state-of-the-art clustering methods.