Hierarchical Clustering of Networks via Hierarchical Distance Matrices

2026/07/31 by Li Chen, Nathaniel Josephs, Eric D. Kolaczyk +1
Mathematics · #stat.ME

paper · pdf

28 pages, 7 figures

arxiv created 2026/07/31 · arxiv updated 2026/08/03

Abstract

Clustering populations of networks while recovering their latent hierarchical organization is a fundamental yet largely unexplored problem in network analysis. To formalize this, we introduce the Hierarchical Distance Matrix, a specific class of population-level distance matrices that encodes latent hierarchical organization through recursively nested distance separation, accommodating unbalanced tree depths. Building on this framework, we propose a fully data-driven top-down procedure: network hierarchical clustering based on two-sample testing (NHC-TST). The algorithm recursively splits networks via spectral clustering and uses a graph-based two-sample stopping rule. The procedure adaptively determines the branching structure without requiring prior knowledge of the number of clusters or tree depth. Theoretically, we establish exact recovery of the population-level hierarchical structure and statistical consistency in the empirical procedure. Simulation studies demonstrate highly accurate recovery of both cluster memberships and hierarchical relationships across a wide range of settings. Applied to a global migration dataset, NHC-TST uncovers interpretable multi-resolution temporal structures that are not revealed by conventional flat clustering approaches.

Citations

• Measuring Global Migration Flows using Online Data
• Nested stochastic block model for simultaneously clustering networks and nodes
• Model-based clustering of multiple networks with a hierarchical algorithm
• Communication network dynamics in a large organizational hierarchy
• ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network
• Global and Individualized Community Detection in Inhomogeneous Multilayer Networks
• Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Estimating a network from multiple noisy realizations
• Stochastic blockmodels for exchangeable collections of networks
• On clustering network-valued data
• Estimating network edge probabilities by neighborhood smoothing
• A useful variant of the Davis--Kahan theorem for statisticians
• A tutorial on spectral clustering