STA 290: Ery Arias-Castro

Statistics Seminar Series

Monday, November 3, 4:10pm, MSB 2112 (Math Dept, 2nd floor)
Refreshments at 3:30pm in MSB 4110 (Statistics Lounge)

Speaker: Ery Arias-Castro (Dept of Mathematics, UC San Diego)

Title: Community detection in a random network”

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 detection lower bounds for detecting such a subgraph in terms of (N, n, p_0, p_1) in various regimes, and exhibit a number of tests that achieve that lower bound in some particular regime. The tests statistics that we analyze include: the scan statistic and variants, the size of the largest connected component, the total degree, the maximum degree, the number of triangles, the number of subtrees of given size, and some spectral methods. Our detection bounds are sharp, except in the Poisson regime where we were not able to fully characterize the constant arising in the bound.

Joint work with Nicolas Verzelen (INRA, France)