# Nested stochastic block model for simultaneously clustering networks and nodes

arXiv: https://arxiv.org/abs/2307.09210 · HTML: https://mlsanity.com/paper/2307.09210/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 18 Jul 2023.

## Builds on (most cited first, 27 of 27)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [Estimating network edge probabilities by neighborhood smoothing](https://mlsanity.com/paper/1509.08588/) (2015)
- [Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction](https://mlsanity.com/paper/1501.06218/) (2015)
- [Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures](https://mlsanity.com/paper/1312.7857/) (2013)
- [Hypothesis Testing For Network Data in Functional Neuroimaging](https://mlsanity.com/paper/1407.5525/) (2014)
- [Temporal Graph Kernels for Classifying Dissemination Processes](https://mlsanity.com/paper/1911.05496/) (2019)
- [Modeling Network Populations via Graph Distances](https://mlsanity.com/paper/1904.07367/) (2019)
- [Network classification with applications to brain connectomics](https://mlsanity.com/paper/1701.08140/) (2017)
- [Global and Individualized Community Detection in Inhomogeneous Multilayer Networks](https://mlsanity.com/paper/2012.00933/) (2020)
- [Clustering Network Layers With the Strata Multilayer Stochastic Block Model](https://mlsanity.com/paper/1507.01826/) (2015)
- [Leveraging Node Attributes for Incomplete Relational Data](https://mlsanity.com/paper/1706.04289/) (2017)
- [On clustering network-valued data](https://mlsanity.com/paper/1606.02401/) (2016)
- [Search Algorithms and Loss Functions for Bayesian Clustering](https://mlsanity.com/paper/2105.04451/) (2021)
- [ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network](https://mlsanity.com/paper/2102.10226/) (2021)
- [Estimating a network from multiple noisy realizations](https://mlsanity.com/paper/1710.04765/) (2017)
- [Network Recovery from Unlabeled Noisy Samples](https://mlsanity.com/paper/2104.14952/) (2021)
- [Latent nested nonparametric priors](https://mlsanity.com/paper/1801.05048/) (2018)
- [Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks](https://mlsanity.com/paper/1904.05330/) (2019)
- [Hypothesis testing for populations of networks](https://mlsanity.com/paper/1911.03783/) (2019)
- [Bayesian community detection for networks with covariates](https://mlsanity.com/paper/2203.02090/) (2022)
- [Model-based clustering for populations of networks](https://mlsanity.com/paper/1806.00225/) (2018)
- [Stochastic blockmodels for exchangeable collections of networks](https://mlsanity.com/paper/1606.05277/) (2016)
- [Clustering of heterogeneous populations of networks](https://mlsanity.com/paper/2107.07489/) (2021)
- [Simultaneous prediction and community detection for networks with application to neuroimaging](https://mlsanity.com/paper/2002.01645/) (2020)

## Built on by (most cited first, 1 of 1)

- [Network two-sample test for block models](https://mlsanity.com/paper/2406.06014/) (2024)

## Abstract (arXiv)

We introduce the nested stochastic block model (NSBM) to cluster a collection of networks while simultaneously detecting communities within each network. NSBM has several appealing features including the ability to work on unlabeled networks with potentially different node sets, the flexibility to model heterogeneous communities, and the means to automatically select the number of classes for the networks and the number of communities within each network. This is accomplished via a Bayesian model, with a novel application of the nested Dirichlet process (NDP) as a prior to jointly model the between-network and within-network clusters. The dependency introduced by the network data creates nontrivial challenges for the NDP, especially in the development of efficient samplers. For posterior inference, we propose several Markov chain Monte Carlo algorithms including a standard Gibbs sampler, a collapsed Gibbs sampler, and two blocked Gibbs samplers that ultimately return two levels of clustering labels from both within and across the networks. Extensive simulation studies are carried out which demonstrate that the model provides very accurate estimates of both levels of the clustering structure. We also apply our model to two social network datasets that cannot be analyzed using any previous method in the literature due to the anonymity of the nodes and the varying number of nodes in each network.