2011/01/01 by Seyed Salim Tabatabaei, Mark Coates, Tabatabaei, Seyed Salim +3 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Artificial Intelligence (cs.AI) #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Computer and information sciences #cs.AI
paper · pdf · doi:10.48550/arxiv.1105.0974
Submitted to Pattern Recognition. 27 pages, 5 figures
openalex publication_date 2011/01/01 · arxiv created 2011/05/05 · arxiv updated 2011/05/06 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/02
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 log2 n), a major improvement over the 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.