Hierarchical community detection by recursive partitioning
arXiv:1810.01509
Abstract
The problem of community detection in networks is usually formulated as finding a single partition of the network into some "correct" number of communities. We argue that it is more interpretable and in some regimes more accurate to construct a hierarchical tree of communities instead. This can be done with a simple top-down recursive partitioning algorithm, starting with a single community and separating the nodes into two communities by spectral clustering repeatedly, until a stopping rule suggests there are no further communities. This class of algorithms is model-free, computationally efficient, and requires no tuning other than selecting a stopping rule. We show that there are regimes where this approach outperforms K-way spectral clustering, and propose a natural framework for analyzing the algorithm's theoretical performance, the binary tree stochastic block model. Under this model, we prove that the algorithm correctly recovers the entire community tree under relatively mild assumptions. We apply the algorithm to a gene network based on gene co-occurrence in 1580 research papers on anemia, and identify six clusters of genes in a meaningful hierarchy. We also illustrate the algorithm on a dataset of statistics papers.
References in corpus (26)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Hierarchical structure and the prediction of missing links in networks
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Spectral redemption: clustering sparse networks
- Matrix estimation by Universal Singular Value Thresholding
- Subnetwork hierarchies of biochemical pathways
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Uncovering latent structure in valued graphs: A variational approach
- Modeling homophily and stochastic equivalence in symmetric relational data
- Finding Community Structure in Mega-scale Social Networks
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Coauthorship and Citation Networks for Statisticians
- Network histograms and universality of blockmodel approximation
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- Estimating the number of communities in networks by spectral methods
- Detecting Overlapping Communities in Networks Using Spectral Methods
- Testing for Global Network Structure Using Small Subgraph Statistics
- Finding Communities of Related Genes