← Research

GANC: Greedy Agglomerative Normalized Cut

Seyed Salim Tabatabaei, Mark Coates, Michael Rabbat

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(n log^2 n), a major improvement over the O(n^3) 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.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace