When Does Bottom-Up Beat Top-Down in Hierarchical Community Detection?

• 成果类型: Article
• 署名作者: Dreveton, Maximilien; Kuroda, Daichi; Grossglauser, Matthias; Thiran, Patrick
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459; 1537-274X
• DOI: 10.1080/01621459.2025.2569711
• 发表日期: 2026-04-03
• 页码: 1284-1295
• 关键词: Community Detection; Hierarchical clustering; stochastic block model; Agglomerative clustering

摘要

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 (top-down) 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 information-theoretic 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 top-down 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.