COMMUNITY DETECTION IN DENSE RANDOM NETWORKS

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 Erdos-Renyi 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), P1 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.