Computer Science – Artificial Intelligence
Scientific paper
2011-05-05
Computer Science
Artificial Intelligence
Submitted to Pattern Recognition. 27 pages, 5 figures
Scientific paper
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.
Coates Mark
Rabbat Michael
Tabatabaei Seyed Salim
No associations
LandOfFree
GANC: Greedy Agglomerative Normalized Cut does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with GANC: Greedy Agglomerative Normalized Cut, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and GANC: Greedy Agglomerative Normalized Cut will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-689081