GANC: Greedy Agglomerative Normalized Cut

Abstract

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.

Submitted to Pattern Recognition. 27 pages, 5 figures

References in corpus (9)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding community structure in very large networks
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• The Dynamics of Viral Marketing
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• Uncovering latent structure in valued graphs: A variational approach

Cited by in corpus (2)

• A survey on trajectory clustering analysis
• Content Distribution Strategies in Opportunistic Networks