# Phase transition for detecting a small community in a large network

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 36 references that are in the map.
- First posted on arXiv 9 Mar 2023.

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

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Testing for Global Network Structure Using Small Subgraph Statistics](https://mlsanity.com/paper/1710.00862/) (2017)
- [Community Detection Based on the L_∞ convergence of eigenvectors in DCBM](https://mlsanity.com/paper/1906.06713/) (2019)
- [The SCORE normalization, especially for highly heterogeneous network and text data](https://mlsanity.com/paper/2204.11097/) (2022)

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

- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)

## Abstract (arXiv)

How to detect a small community in a large network is an interesting problem, including clique detection as a special case, where a naive degree-based chi2-test was shown to be powerful in the presence of an ErdHos-Renyi background. Using Sinkhorn's theorem, we show that the signal captured by the chi2-test may be a modeling artifact, and it may disappear once we replace the ErdHos-Renyi model by a broader network model. We show that the recent SgnQ test is more appropriate for such a setting. The test is optimal in detecting communities with sizes comparable to the whole network, but has never been studied for our setting, which is substantially different and more challenging. Using a degree-corrected block model (DCBM), we establish phase transitions of this testing problem concerning the size of the small community and the edge densities in small and large communities. When the size of the small community is larger than √n, the SgnQ test is optimal for it attains the computational lower bound (CLB), the information lower bound for methods allowing polynomial computation time. When the size of the small community is smaller than √n, we establish the parameter regime where the SgnQ test has full power and make some conjectures of the CLB. We also study the classical information lower bound (LB) and show that there is always a gap between the CLB and LB in our range of interest.