COMMUNITY DETECTION IN DENSE RANDOM NETWORKS

• 成果类型: Article
• 署名作者: Arias-Castro, Ery; Verzelen, Nicolas
• 署名单位: University of California System; University of California San Diego; INRAE
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/14-AOS1208
• 发表日期: 2014
• 页码: 940-969
• 关键词: Anomaly Detection; HIGHER CRITICISM; SPARSE

摘要

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.