Detecting a community in Random Networks – Nicolas Verzelen
Nicolas Verzelen
INRA Montpellier
http://nicolas.verzelen.free.fr/
Date(s) : 12/06/2015 iCal
11h00 - 12h00
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.
https://www6.montpellier.inra.fr/mistea_eng/Members/List/VERZELEN-Nicolas
Catégories
