[go: up one dir, main page]

Open Access
December 2015 Community detection in sparse random networks
Nicolas Verzelen, Ery Arias-Castro
Ann. Appl. Probab. 25(6): 3465-3510 (December 2015). DOI: 10.1214/14-AAP1080

Abstract

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_{0}$; under the alternative, there is an unknown subgraph on $n$ vertices where the connection probability is $p_{1}>p_{0}$. In Arias-Castro and Verzelen [Ann. Statist. 42 (2014) 940–969], we focused on the asymptotically dense regime where $p_{0}$ is large enough that $np_{0}>(n/N)^{o(1)}$. We consider here the asymptotically sparse regime where $p_{0}$ is small enough that $np_{0}<(n/N)^{c_{0}}$ for some $c_{0}>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.

Citation Download Citation

Nicolas Verzelen. Ery Arias-Castro. "Community detection in sparse random networks." Ann. Appl. Probab. 25 (6) 3465 - 3510, December 2015. https://doi.org/10.1214/14-AAP1080

Information

Received: 1 August 2013; Revised: 1 September 2014; Published: December 2015
First available in Project Euclid: 1 October 2015

zbMATH: 1326.05145
MathSciNet: MR3404642
Digital Object Identifier: 10.1214/14-AAP1080

Subjects:
Primary: 05C80 , 62C20

Keywords: Community detection , detecting a dense subgraph , Erdős–Rényi random graph , largest connected component , minimax hypothesis testing , planted subgraph problem , scan statistic

Rights: Copyright © 2015 Institute of Mathematical Statistics

Vol.25 • No. 6 • December 2015
Back to Top