Detection of local geometry in random graphs: information-theoretic and computational limits

Jinho Bok, Shuangping Li, Sophie H. Yu

We study the problem of detecting local geometry in random graphs. We introduce a model $\mathcal{G}(n,p,d,k)$, where a hidden community of average size $k$ has edges drawn as a…