Community detection in sparse random networks

We consider the problem of detecting a tight community in a sparse random network. This is formalized as testing for the existence of a dense random subgraph in a random graph. Under the null hypothesis, the graph is a realization of an Erdős–Rényi graph on N vertices and with connection probability p₀; under the alternative, there is an unknown subgraph on n vertices where the connection probability is p₁>p₀. In Arias-Castro and Verzelen [Ann. Statist. 42 (2014) 940–969], we focused on the asymptotically dense regime where p₀ is large enough that np₀>(n/N)ᵒ⁽¹⁾. We consider here the asymptotically sparse regime where p₀ is small enough that np₀<(n/N)^c₀ for some c₀>0. As before, we derive information theoretic lower bounds, and also establish the performance of various tests. Compared to our previous work [Ann. Statist. 42 (2014) 940–969], the arguments for the lower bounds are based on the same technology, but are substantially more technical in the details; also, the methods we study are different: besides a variant of the scan statistic, we study other tests statistics such as the size of the largest connected component, the number of triangles, and the number of subtrees of a given size. Our detection bounds are sharp, except in the Poisson regime where we were not able to fully characterize the constant arising in the bound.