Phase transitions for detecting latent geometry in random graphs

DOI10.1007/S00440-020-00998-3zbMATH Open1468.60011arXiv1910.14167OpenAlexW3087982197MaRDI QIDQ2210754FDOQ2210754

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)

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.

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

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

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)

Cites Work

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

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)