COMMUNITY DETECTION IN SPARSE RANDOM NETWORKS

• 成果类型: Article
• 署名作者: Verzelen, Nicolas; Arias-Castro, Ery
• 署名单位: INRAE; University of California System; University of California San Diego
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1080
• 发表日期: 2015
• 页码: 3465-3510
• 关键词: Anomaly Detection; graphs

摘要

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 p(0); under the alternative, there is an unknown subgraph on n vertices where the connection probability is p(1) > p(0). In Arias-Castro and Verzelen [Ann. Statist. 42 (2014) 940- 969], we focused on the asymptotically dense regime where p(0) is large enough that np(0) > (n/N)(o(1)). We consider here the asymptotically sparse regime where p(0) is small enough that np(0) < (n/N)(c0) for some c(0) > 0. As before, we derive information theoretic lower bounds, and also establish the performance of various tests. Compared to our previous work [Ann. Statist. 42 (2014) 940-969], 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 tests statistics such as the size of the largest connected component, the number of triangles, and the number of subtrees of a given size. Our detection bounds are sharp, except in the Poisson regime where we were not able to fully characterize the constant arising in the bound.