Phase transitions for detecting latent geometry in random graphs

DOI10.1007/S00440-020-00998-3MaRDI QIDQ2210754zbMATH OpenOpenAlexFDO

Authors Matthew D. Brennan, Guy Bresler, Dheeraj Nagaraj

Publication date 8 November 2020

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

graph comparisonbinomial random graphslatent geometry

Mathematics Subject Classification ID

Hypothesis testing in multivariate analysis (62H15) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These graphs are also of purely theoretical interest within computer science, probability and statistics. A fundamental initial question regarding these models is: when are these random graphs affected by their latent geometry and when are they indistinguishable from simpler models without latent structure, such as the ErdH{o}s-R'{e}nyi graph $mathcalG(n,p)$? We address this question for two of the most well-studied models of random graphs with latent geometry -- the random intersection and random geometric graph. Our results are as follows: (1) we prove that the random intersection graph converges in total variation to $mathcalG(n,p)$ when $d=ildeomega(n^3)$, and does not if $d=o(n^3)$, resolving an open problem in Fill et al. (2000), Rybarczyk (2011) and Kim et al. (2018); (2) we provide conditions under which the matrix of intersection sizes of random family of sets converges in total variation to a symmetric matrix with independent Poisson entries, yielding the first total variation convergence result for $au$-random intersection graphs to $mathcalG(n,p)$; and (3) we show that the random geometric graph on $mathbb{S}^{d-1}$ with edge density $p$ converges in total variation to $mathcalG(n,p)$ when $d=ildeomegaleft(minp{n}^3,p^2{n}^{7/2}ight)$, yielding the first progress towards a conjecture of Bubeck et al. (2016). The first of these three results was obtained simultaneously and independently by Bubeck, Racz and Richey.

Recommendations

• A probabilistic view of latent space graphs and phase transitions
• Testing for high-dimensional geometry in random graphs
• On the total variation distance between the binomial random graph and the random intersection graph
• Information and dimensionality of anisotropic random geometric graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models

Cites work

• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• A smooth transition from Wishart to GOE
• Approximation of rectangular beta-Laguerre ensembles and large deviations
• Asymptotic equivalence and contiguity of some random graphs
• Basic models and questions in statistical network analysis
• Birthday inequalities, repulsion, and hard spheres
• Component evolution in a secure wireless sensor network
• Computational barriers in minimax submatrix detection
• Concentration of measure without independence: a unified approach via the martingale method
• Connectivity of the uniform random intersection graph
• Degree and clustering coefficient in sparse random intersection graphs
• Detecting positive correlations in a multivariate sample
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Entropic CLT and phase transition in high-dimensional Wishart matrices
• Epidemics on Random Graphs with Tunable Clustering
• Epidemics on random intersection graphs
• Equivalence of a random intersection graph and G (n ,p )
• Gaussian fluctuations for edge counts in high-dimensional random geometric graphs
• High-dimensional random geometric graphs and their clique number
• Information and dimensionality of anisotropic random geometric graphs
• Introduction to Random Graphs
• Large cliques in sparse random intersection graphs
• Large independent sets in general random intersection graphs
• Latent Space Approaches to Social Network Analysis
• On Choosing and Bounding Probability Metrics
• On Random Intersection Graphs: The Subgraph Problem
• On the total variation distance between the binomial random graph and the random intersection graph
• Optimal detection of sparse principal components in high dimension
• Random Geometric Graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Reconstruction and estimation in the planted partition model
• Sharp threshold functions for random intersection graphs via a coupling method
• Some applications of the Stein-Chen method for proving Poisson convergence
• Tail-Sensitive Gaussian Asymptotics for Marginals of Concentrated Measures in High Dimension
• Testing for high-dimensional geometry in random graphs
• The degree of a typical vertex in generalized random intersection graph models
• The middle-scale asymptotics of Wishart matrices
• The vertex degree distribution of random intersection graphs

Cited in

(12)

• Random geometric graph: some recent developments and perspectives
• Information and dimensionality of anisotropic random geometric graphs
• A probabilistic view of latent space graphs and phase transitions
• High-dimensional regimes of non-stationary Gaussian correlated Wishart matrices
• Clique and cycle frequencies in a sparse random graph model with overlapping communities
• 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
• Guarantees for Spontaneous Synchronization on Random Geometric Graphs
• Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
• On the total variation distance between the binomial random graph and the random intersection graph
• Maximal persistence in random clique complexes

This page was built for publication: Phase transitions for detecting latent geometry in random graphs

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