# Testing for Global Network Structure Using Small Subgraph Statistics

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2017.

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

- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting](https://mlsanity.com/paper/2308.08198/) (2023)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [SIMPLE-RC: Group Network Inference with Non-Sharp Nulls and Weak Signals](https://mlsanity.com/paper/2211.00128/) (2022)
- [Phase transition for detecting a small community in a large network](https://mlsanity.com/paper/2303.05024/) (2023)
- [Spectral goodness-of-fit tests for complete and partial network data](https://mlsanity.com/paper/2106.09702/) (2021)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)

## Abstract (arXiv)

We study the problem of testing for community structure in networks using relations between the observed frequencies of small subgraphs. We propose a simple test for the existence of communities based only on the frequencies of three-node subgraphs. The test statistic is shown to be asymptotically normal under a null assumption of no community structure, and to have power approaching one under a composite alternative hypothesis of a degree-corrected stochastic block model. We also derive a version of the test that applies to multivariate Gaussian data. Our approach achieves near-optimal detection rates for the presence of community structure, in regimes where the signal-to-noise is too weak to explicitly estimate the communities themselves, using existing computationally efficient algorithms. We demonstrate how the method can be effective for detecting structure in social networks, citation networks for scientific articles, and correlations of stock returns between companies on the S&P 500.