3/3/14: Ery Arias-Castro


Community detection in a random network

Ery Arias-Castro
Department of Mathematics
UCSD

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 scan statistic and variants, the size of the largest connected component, the number of triangles, the eigengap of the adjacency matrix, etc.  We also consider the problem of testing in polynomial-time.  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).

Ery Arias-Castro is an associate professor of statistics at UCSD. He received his PhD in Statistics from Stanford University in 2004. His M.A. is in artificial intelligence, from the Ecole Normal Superieure de Cachan (France) and Washington University, Saint Louis, while his B.S. is in mathematics from the  Ecole Normal Superieure de Cachan. He joined the faculty in the mathematics department at UCSD in 2005. His research interests are in high-dimensional statistics, machine learning, spatial statistics, image processing, and applied probability.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.