When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
Maximilien Dreveton Daichi Kuroda Matthias Grossglauser Patrick Thiran
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.