When does bottom-up beat top-down in hierarchical community detection?

Hierarchical community detection consists in finding a tree of communities where deeper levels of the hierarchy reveal finer-grained structures. There are two main classes of algorithms for this task. Divisive (topdown) algorithms recursively partition nodes into smaller communities until a stopping criterion indicates that no further splits are necessary. In contrast, agglomerative (bottom-up) algorithms first identify the smallest community structures and then repeatedly merge the communities by using a linkage method. In this work, we prove that a bottom-up algorithm recovers the hierarchy of a hierarchical stochastic block model (HSBM) when the average degree grows unbounded. We also establish the informationtheoretic threshold for exact recovery at intermediate depths of the hierarchy and highlight its significance in understanding the limitations of top-down algorithms. Numerical experiments on both synthetic and real datasets demonstrate the superiority of bottom-up methods. In particular, a notable drawback of topdown algorithms is their tendency to produce dendrograms with inversions. These findings contribute to a better understanding of hierarchical clustering techniques and their applications in network analysis. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.