Accession Number:

ADA610113

Title:

Community Detection in Sparse Random Networks

Descriptive Note:

Electronic preprint

Corporate Author:

CALIFORNIA UNIV SAN DIEGO LA JOLLA DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

2013-08-13

Pagination or Media Count:

59.0

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 Erdos-Renyi graph on N vertices and with connection probability p0 under the alternative, there is an unknown subgraph on n vertices where the connection probability is p1 p0. In Arias-Castro and Verzelen, 2012, we focused on the asymptotically dense regime where p0 is large enough that log1 V np0 exp -1 ologNn. We consider here the asymptotically sparse regime where p0 is small enough that logNn Olog1 V np0exp -1. As before, we derive information theoretic lower bounds, and also establish the performance of various tests. Compared to our previous work Arias-Castro and Verzelen, 2012, 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 statistics such as the size of the largest connected component, the number of triangles, the eigengap of the adjacency matrix, etc. Our detection bounds are sharp, except in the Poisson regime where we were not able to fully characterize the constant arising in the bound.

Descriptors:

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE