Testing for high-dimensional geometry in random graphs

DOI10.1002/rsa.20633zbMath1349.05315arXiv1411.5713OpenAlexW2963421284MaRDI QIDQ2830237

Miklós Z. Rácz, Jian Ding, Ronen Eldan, Sébastien Bubeck

Publication date: 9 November 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.5713

zbMATH Keywords

hypothesis testingrandom graphsrandom geometric graphshigh-dimensional geometric structuresigned triangles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (32)

Community detection and percolation of information in a geometric setting ⋮ Markov random geometric graph, MRGG: a growth model for temporal dynamic networks ⋮ Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients ⋮ A high-dimensional CLT in \(\mathcal {W}_2\) distance with near optimal convergence rate ⋮ High-dimensional regimes of non-stationary Gaussian correlated Wishart matrices ⋮ Power enhancement and phase transitions for global testing of the mixed membership stochastic block model ⋮ High-dimensional regime for Wishart matrices based on the increments of the solution to the stochastic heat equation ⋮ Random geometric graph: some recent developments and perspectives ⋮ A probabilistic view of latent space graphs and phase transitions ⋮ Limit theory of sparse random geometric graphs in high dimensions ⋮ Phase transition in noisy high-dimensional random geometric graphs ⋮ Threshold for detecting high dimensional geometry in anisotropic random geometric graphs ⋮ Guarantees for Spontaneous Synchronization on Random Geometric Graphs ⋮ Information and Dimensionality of Anisotropic Random Geometric Graphs ⋮ Unnamed Item ⋮ Phase transitions for detecting latent geometry in random graphs ⋮ A smooth transition from Wishart to GOE ⋮ Unnamed Item ⋮ Contiguity and non-reconstruction results for planted partition models: the dense case ⋮ Two-sample Hypothesis Testing for Inhomogeneous Random Graphs ⋮ Adaptive estimation of nonparametric geometric graphs ⋮ Gaussian fluctuations for edge counts in high-dimensional random geometric graphs ⋮ Limiting behavior of large correlated Wishart matrices with chaotic entries ⋮ Gaussian fluctuation for Gaussian Wishart matrices of overall correlation ⋮ Optimal adaptivity of signed-polygon statistics for network testing ⋮ Higher-order fluctuations in dense random graph models ⋮ Detecting a botnet in a network ⋮ The middle-scale asymptotics of Wishart matrices ⋮ Permutation Tests for Infection Graphs ⋮ Asymptotic behavior of large Gaussian correlated Wishart matrices ⋮ Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials ⋮ New error bounds in multivariate normal approximations via exchangeable pairs with applications to Wishart matrices and fourth moment theorems

Cites Work

• Unnamed Item
• Unnamed Item
• High-dimensional random geometric graphs and their clique number
• Reconstruction and estimation in the planted partition model
• The method of moments and degree distributions for network models
• Approximation of rectangular beta-Laguerre ensembles and large deviations
• Unit disk graph recognition is NP-hard
• On the distribution of the largest eigenvalue in principal components analysis
• Detecting positive correlations in a multivariate sample
• An efficiency upper bound for inverse covariance estimation
• Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
• Community detection in dense random networks
• Decompositions of Triangle-Dense Graphs
• Exact Recovery in the Stochastic Block Model
• An Introduction to Random Matrices
• Random Geometric Graphs
• Latent Space Approaches to Social Network Analysis
• Collective dynamics of ‘small-world’ networks

This page was built for publication: Testing for high-dimensional geometry in random graphs