Community Detection in Random NetworksReport as inadecuate




Community Detection in Random Networks - Download this document for free, or read online. Document in PDF available to download.

1 Math Dept, UCSD - Department of Mathematics, University of California, San Diego 2 MISTEA - Mathématiques, Informatique et STatistique pour l-Environnement et l-Agronomie

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. 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 p0. Under the composite alternative, there is a subgraph of n nodes where the probability of connection is p1 > p0. We derive a detection lower bound for detecting such a subgraph in terms of N, n, p0, p1 and exhibit a test that achieves that lower bound. We do this both when p0 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 n p0 is either bounded away from zero, or tends to zero slowly.

Mots-clés : community detection detecting a dense subgraph minimax hypothesis testing Erdös-Rényi random graph scan statistic planted clique problem sparse eigenvalue problem





Author: Ery Arias-Castro - Nicolas Verzelen -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents