Testing for high-dimensional geometry in random graphs
From MaRDI portal
Publication:2830237
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 ErdH{o}s-R'enyi random graph . Under the alternative, the graph is generated from the model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere , and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., 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 .
Recommendations
- A probabilistic view of latent space graphs and phase transitions
- Phase transitions for detecting latent geometry in random graphs
- Information and dimensionality of anisotropic random geometric graphs
- A nonparametric two-sample hypothesis testing problem for random graphs
- High-dimensional random geometric graphs and their clique number
Cites work
- scientific article; zbMATH DE number 1303602 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- An efficiency upper bound for inverse covariance estimation
- An introduction to random matrices
- Approximation of rectangular beta-Laguerre ensembles and large deviations
- Collective dynamics of `small-world' networks
- Community detection in dense random networks
- Detecting positive correlations in a multivariate sample
- Exact Recovery in the Stochastic Block Model
- High-dimensional random geometric graphs and their clique number
- Latent Space Approaches to Social Network Analysis
- On the distribution of the largest eigenvalue in principal components analysis
- Random Geometric Graphs
- Reconstruction and estimation in the planted partition model
- The method of moments and degree distributions for network models
- Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
- Unit disk graph recognition is NP-hard
Cited in
(43)- Contiguity and non-reconstruction results for planted partition models: the dense case
- Asymptotic behavior of large Gaussian correlated Wishart matrices
- Limit behavior in high-dimensional regime for the Wishart tensors in Wiener chaos
- The middle-scale asymptotics of Wishart matrices
- Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
- Limit theory of sparse random geometric graphs in high dimensions
- A smooth transition from Wishart to GOE
- New error bounds in multivariate normal approximations via exchangeable pairs with applications to Wishart matrices and fourth moment theorems
- Random geometric graph: some recent developments and perspectives
- Information and dimensionality of anisotropic random geometric graphs
- High-dimensional random geometric graphs and their clique number
- Adaptive estimation of nonparametric geometric graphs
- Permutation Tests for Infection Graphs
- Optimal adaptivity of signed-polygon statistics for network testing
- A probabilistic view of latent space graphs and phase transitions
- Markov random geometric graph, MRGG: a growth model for temporal dynamic networks
- A high-dimensional CLT in \(\mathcal {W}_2\) distance with near optimal convergence rate
- Detecting a botnet in a network
- High-dimensional regimes of non-stationary Gaussian correlated Wishart matrices
- scientific article; zbMATH DE number 7626706 (Why is no real title available?)
- Community detection and percolation of information in a geometric setting
- Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
- Local and global expansion in random geometric graphs
- scientific article; zbMATH DE number 7379432 (Why is no real title available?)
- Phase transition in noisy high-dimensional random geometric graphs
- Threshold for detecting high dimensional geometry in anisotropic random geometric graphs
- High-dimensional regime for Wishart matrices based on the increments of the solution to the stochastic heat equation
- Limiting behavior of large correlated Wishart matrices with chaotic entries
- Fundamental limits of low-rank matrix estimation with diverging aspect ratios
- Guarantees for Spontaneous Synchronization on Random Geometric Graphs
- Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
- Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
- Phase transitions for detecting latent geometry in random graphs
- Testing multivariate uniformity based on random geometric graphs
- Maximal persistence in random clique complexes
- Limit behavior in high-dimensional regime for Wishart tensors with Rosenblatt entries
- Searching for (sharp) thresholds in random structures: where are we now?
- Gaussian fluctuation for Gaussian Wishart matrices of overall correlation
- A nonparametric two-sample hypothesis testing problem for random graphs
- Two-sample hypothesis testing for inhomogeneous random graphs
- Higher-order fluctuations in dense random graph models
- Gaussian fluctuations for edge counts in high-dimensional random geometric graphs
- Graph-theoretic multisample tests of equality in distribution for high dimensional data
This page was built for publication: Testing for high-dimensional geometry in random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830237)
