2021/12/16 by Bogdan-Adrian Manghiuc, He Sun, Manghiuc, Bogdan-Adrian +1
Computer Science · Physics and Astronomy · Social Sciences · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Human Mobility and Location-Based Analysis #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2112.09055
openalex publication_date 2021/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hierarchical clustering studies a recursive partition of a data set into clusters of successively smaller size, and is a fundamental problem in data analysis. In this work we study the cost function for hierarchical clustering introduced by Dasgupta, and present two polynomial-time approximation algorithms: Our first result is an O(1)-approximation algorithm for graphs of high conductance. Our simple construction bypasses complicated recursive routines of finding sparse cuts known in the literature. Our second and main result is an O(1)-approximation algorithm for a wide family of graphs that exhibit a well-defined structure of clusters. This result generalises the previous state-of-the-art, which holds only for graphs generated from stochastic models. The significance of our work is demonstrated by the empirical analysis on both synthetic and real-world data sets, on which our presented algorithm outperforms the previously proposed algorithm for graphs with a well-defined cluster structure.