Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier

DOI10.1016/j.ejc.2023.103842zbMath1548.0529MaRDI QIDQ6612518

Josep Diaz, Varsha Dani, Thomas P. Hayes, Moore, Cristopher

Publication date: 30 September 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

Euclidean distances

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connectivity of soft random geometric graphs
• Reconstruction and estimation in the planted partition model
• Random geometric graph diameter in the unit ball
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• On the estimation of latent distances using graph distances
• Testing for high-dimensional geometry in random graphs
• The small-world phenomenon
• Random Plane Networks
• Random Geometric Graphs
• Latent Space Approaches to Social Network Analysis
• Community Detection and Stochastic Block Models
• A Quest to Unravel the Metric Structure Behind Perturbed Networks
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Learning random points from geometric graphs or orderings
• Low-Distortion Inference of Latent Similarities from a Multiplex Social Network
• Algorithmic Aspects of Wireless Sensor Networks
• Consistency of maximum likelihood for continuous-space network models. I

This page was built for publication: Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier