Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs
Steinar Laenen Bogdan-Adrian Manghiuc He Sun
This paper presents two efficient hierarchical clustering (HC) algorithms
with respect to Dasgupta's cost function. For any input graph $G$ with a clear
cluster-structure, our designed algorithms run in nearly-linear time in the
input size of $G$, and return an $O(1)$-approximate HC tree with respect to
Dasgupta's cost function. We compare the performance of our algorithm against
the previous state-of-the-art on synthetic and real-world datasets and show
that our designed algorithm produces comparable or better HC trees with much
lower running time.