Community detection in dense random networks

The Annals of Statistics · 2014 · Volume 42 · Issue 3

Abstract

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. Specifically, 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 $p_{0}$. Under the (composite) alternative, there is an unknown subgraph of $n$ nodes where the probability of connection is $p_{1}>p_{0}$. We derive a detection lower bound for detecting such a subgraph in terms of $N$, $n$, $p_{0}$, $p_{1}$ and exhibit a test that achieves that lower bound. We do this both when $p_{0}$ 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 $np_{0}$ is either bounded away from zero, or tends to zero slowly.

Keywords

62C20, 62H30, 94A13, Community detection, dense $k$-subgraph problem, detecting a dense subgraph, Erdős–Rényi random graph, minimax hypothesis testing, planted clique problem, scan statistic, sparse eigenvalue problem

Enable JavaScript for citation tools and additional paper interactions.