{"id":"arxiv/2603.24545","url":"https://arxiv.org/abs/2603.24545","tags":["math.ST","cs.CC","cs.DS","math.PR","stat.ML"],"score":0,"title":"Detection of local geometry in random graphs: information-theoretic and computational limits","domain":"math.ST","source":"arxiv","authors":["Jinho Bok","Shuangping Li","Sophie H. Yu"],"reviews":0,"subject":"math.ST","summary":"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 random geometric graph on $\\mathbb{S}^{d-1}$, while all remaining edges follow the Erdős--Rényi model $\\mathcal{G}(n, p)$. The random geometric graph is generated by thresholding inner products of latent vectors on $\\mathbb{S}^{d-1}$, with each edge having marginal probability equal to $p$. This implies that $\\mathcal{G}(n, p, d, k)$ and $\\mathcal{G}(n, p)$ are indistinguishable at the level of the marginals, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-25","reactions":{}}