# Network Cross-Validation for Determining the Number of Communities in Network Data

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2014.

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

- [A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning](https://mlsanity.com/paper/2101.01669/) (2021)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [Conformal Load Prediction with Transductive Graph Autoencoders](https://mlsanity.com/paper/2406.08281/) (2024)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [A statistically consistent measure of semantic uncertainty using Language Models](https://mlsanity.com/paper/2502.00507/) (2025)
- [LOBSTUR: A Local Bootstrap Framework for Tuning Unsupervised Representations in Graph Neural Networks](https://mlsanity.com/paper/2505.14867/) (2025)
- [Strongly Consistent Community Detection in Popularity Adjusted Block Models](https://mlsanity.com/paper/2506.07224/) (2025)
- [Rank Is Not Capacity: Spectral Occupancy for Latent Graph Models](https://mlsanity.com/paper/2605.11142/) (2026)
- [Fitting Low-rank Models on Egocentrically Sampled Partial Networks](https://mlsanity.com/paper/2303.11230/) (2023)
- [Fair Information Spread on Social Networks with Community Structure](https://mlsanity.com/paper/2305.08791/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Parallel Network Reconstruction with Multi-directional Regularization](https://mlsanity.com/paper/2411.11464/) (2024)
- [Review on Determining the Number of Communities in Network Data](https://mlsanity.com/paper/2503.00352/) (2025)
- [Simultaneous estimation of connectivity and dimensionality in samples of networks](https://mlsanity.com/paper/2508.12483/) (2025)
- [Adjacency Spectral Embeddings of Correlation Networks](https://mlsanity.com/paper/2602.21055/) (2026)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)
- [Scalable Graph Coreset Selection via Greedy Sampling](https://mlsanity.com/paper/2607.27602/) (2026)

## Abstract (arXiv)

The stochastic block model and its variants have been a popular tool in analyzing large network data with community structures. In this paper we develop an efficient network cross-validation (NCV) approach to determine the number of communities, as well as to choose between the regular stochastic block model and the degree corrected block model. The proposed NCV method is based on a block-wise node-pair splitting technique, combined with an integrated step of community recovery using sub-blocks of the adjacency matrix. We prove that the probability of under selection vanishes as the number of node increases, under mild conditions satisfied by a wide range of popular community recovery algorithms. The solid performance of our method is also demonstrated in extensive simulations and a data example.