Information and dimensionality of anisotropic random geometric graphs

DOI10.1007/978-3-030-36020-7_13MaRDI QIDQ5115958zbMATH OpenOpenAlexFDO

Authors Ronen Eldan, Dan Mikulincer

Publication date 21 August 2020

Published in Lecture Notes in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphsRandom graphsErdős-Rényi modeldimensionality of embeddings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Inequalities; stochastic orderings (60E15) Central limit and other weak theorems (60F05)

Abstract: This paper deals with the problem of detecting non-isotropic high-dimensional geometric structure in random graphs. Namely, we study a model of a random geometric graph in which vertices correspond to points generated randomly and independently from a non-isotropic $d$-dimensional Gaussian distribution, and two vertices are connected if the distance between them is smaller than some pre-specified threshold. We derive new notions of dimensionality which depend upon the eigenvalues of the covariance of the Gaussian distribution. If $alpha$ denotes the vector of eigenvalues, and $n$ is the number of vertices, then the quantities $left(frac||alpha|{|}_2||alpha|{|}_{3}ight{)}^6/n^3$ and $left(frac||alpha|{|}_2||alpha|{|}_{4}ight{)}^4/n^3$ determine upper and lower bounds for the possibility of detection. This generalizes a recent result by Bubeck, Ding, R'acz and the first named author from [BDER14] which shows that the quantity $d/n^3$ determines the boundary of detection for isotropic geometry. Our methods involve Fourier analysis and the theory of characteristic functions to investigate the underlying probabilities of the model. The proof of the lower bound uses information theoretic tools, based on the method presented in [BG15].

Recommendations

• Testing for high-dimensional geometry in random graphs
• A probabilistic view of latent space graphs and phase transitions
• High-dimensional random geometric graphs and their clique number
• Phase transitions for detecting latent geometry in random graphs
• Gaussian fluctuations for edge counts in high-dimensional random geometric graphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• scientific article; zbMATH DE number 6026126 (Why is no real title available?)
• A Lyapunov-type Bound in R^d
• Banach-Mazur distances and projections on random subgaussian polytopes
• Elements of Information Theory
• Entropic CLT and phase transition in high-dimensional Wishart matrices
• Normal approximations with Malliavin calculus. From Stein's method to universality
• Probability. Theory and examples.
• Testing for high-dimensional geometry in random graphs
• The analysis of linear partial differential operators. I: Distribution theory and Fourier analysis.

Cited in

(8)

• A smooth transition from Wishart to GOE
• Random geometric graph: some recent developments and perspectives
• A probabilistic view of latent space graphs and phase transitions
• Testing for high-dimensional geometry in random graphs
• Phase transition in noisy high-dimensional random geometric graphs
• Threshold for detecting high dimensional geometry in anisotropic random geometric graphs
• The CLT in high dimensions: quantitative bounds via martingale embedding
• Phase transitions for detecting latent geometry in random graphs

This page was built for publication: Information and dimensionality of anisotropic random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115958)