Hierarchical clustering of networks consists in finding a tree of
communities, such that lower levels of the hierarchy reveal finer-grained
community structures. There are two main classes of algorithms tackling this
problem. Divisive ($\textit{top-down}$) algorithms recursively partition the
nodes into two communities, until a stopping rule indicates that no further
split is needed. In contrast, agglomerative ($\textit{bottom-up}$) algorithms
first identify the smallest community structure and then repeatedly merge the
communities using a $\textit{linkage}$ method. In this article, we establish
theoretical guarantees for the recovery of the hierarchical tree and community
structure of a Hierarchical Stochastic Block Model by a bottom-up algorithm. We
also establish that this bottom-up algorithm attains the information-theoretic
threshold for exact recovery at intermediate levels of the hierarchy. Notably,
these recovery conditions are less restrictive compared to those existing for
top-down algorithms. This shows that bottom-up algorithms extend the feasible
region for achieving exact recovery at intermediate levels. Numerical
experiments on both synthetic and real data sets confirm the superiority of
bottom-up algorithms over top-down algorithms. We also observe that top-down
algorithms can produce dendrograms with inversions. These findings contribute
to a better understanding of hierarchical clustering techniques and their
applications in network analysis.

本文介绍了一种基于 自上而下 (top-down) 算法 的层次聚类的算法；通过实验，发现了这种算法与传统的 自下而上 (bottom-up) 的算法相比，可以更好地恢复精细的社区结构，并可在模型的中间层次上取得信息学门槛下的恢复。