Hierarchical Community Detection in Hierarchical Stochastic Block Models

Speaker: Sayeh Khaniha
Abstract
In this session of our reading group, I will discuss community detection in hierarchical clustering of networks, based on the paper “When Does Bottom-up Beat Top-down in Hierarchical Community Detection?” by Maximilien Dreveton et al. Hierarchical clustering involves constructing a tree of communities, with lower levels revealing finer-grained structures. Two main approaches address this problem: divisive (top-down) algorithms, which recursively split nodes, and agglomerative (bottom-up) algorithms, which start by identifying the smallest communities and then merge them using a linkage method. This talk will focus on establishing theoretical guarantees for the exact recovery of the hierarchical tree under a Hierarchical Stochastic Block Model (HSBM) using a bottom-up algorithm. The findings show that bottom-up methods can achieve the information-theoretic threshold for exact recovery at intermediate hierarchy levels, offering less restrictive conditions than top-down algorithms and expanding the feasible region for accurate community detection.
Check out our website:
www.lincs.fr/