Community Detection in Random Networks

Ery Arias-Castro (1) , Nicolas Verzelen (2)

1 MATH - UC San Diego - Department of Mathematics [Univ California San Diego]
2 MISTEA - Mathématiques, Informatique et STatistique pour l'Environnement et l'Agronomie

We formalize the problem of detecting a community in a network into testing whether in a given (random) graph there is a subgraph that is unusually dense. We observe an undirected and unweighted graph on N nodes. Under the null hypothesis, the graph is a realization of an Erdös-Rényi graph with probability p0. Under the (composite) alternative, there is a subgraph of n nodes where the probability of connection is p1 > p0. We derive a detection lower bound for detecting such a subgraph in terms of N, n, p0, p1 and exhibit a test that achieves that lower bound. We do this both when p0 is known and unknown. We also consider the problem of testing in polynomial-time. As an aside, we consider the problem of detecting a clique, which is intimately related to the planted clique problem. Our focus in this paper is in the quasi-normal regime where n p0 is either bounded away from zero, or tends to zero slowly.

Mots clés: community detection; detecting a dense subgraph; minimax hypothesis testing; Erdös-Rényi random graph; scan statistic; planted clique problem; sparse eigenvalue problem

Domaines: Théorie [stat.TH]; Machine Learning [stat.ML]

Ery Arias-Castro, Nicolas Verzelen. Community Detection in Random Networks. 2013. ⟨hal-00795376⟩