Testing for high-dimensional geometry in random graphs
Preprint
Abstract
We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erd\H{o}s-R\'enyi random graph $G(n,p)$. Under the alternative, the graph is generated from the $G(n,p,d)$ model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere $\mathbb{S}^{d-1}$, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., $p$ is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in $G(n,p,d)$.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Community detection in sparse random networksThe Annals of Applied Probability, 2015
- Exact Recovery in the Stochastic Block ModelIEEE Transactions on Information Theory, 2015
- An efficiency upper bound for inverse covariance estimationIsrael Journal of Mathematics, 2015
- On the Influence of the Seed Graph in the Preferential Attachment ModelIEEE Transactions on Network Science and Engineering, 2015
- Reconstruction and estimation in the planted partition modelProbability Theory and Related Fields, 2014
- Community detection in dense random networksThe Annals of Statistics, 2014
- Approximation of Rectangular Beta-Laguerre Ensembles and Large DeviationsJournal of Theoretical Probability, 2013
- Spectral Analysis of Large Dimensional Random Matrices2010
- Collective dynamics of ‘small-world’ networksNature, 1998
- Unit disk graph recognition is NP-hardComputational Geometry, 1998