Learning random points from geometric graphs or orderings

DOI10.1002/RSA.20922MaRDI QIDQ5136918zbMATH OpenOpenAlexFDO

Authors D. Mitsche, J. Díaz, Colin McDiarmid

Publication date 30 November 2020

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

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

zbMATH Keywords

approximate embeddingrandom geometric graphsunit-disk graphsvertex orders

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Suppose that there is a family of $n$ random points $X_v$ for $vinV$, independently and uniformly distributed in the square $left[-sqrtn/2,sqrtn/2ight{]}^2$ of area $n$. We do not see these points, but learn about them in one of the following two ways. Suppose first that we are given the corresponding random geometric graph $G$, where distinct vertices $u$ and $v$ are adjacent when the Euclidean distance $d_E(X_u,X_v)$ is at most $r$. If the threshold distance $r$ satisfies $n^{3/14}llrll{n}^{1/2}$, then the following holds with high probability. Given the graph $G$ (without any geometric information), in polynomial time we can approximately reconstruct the hidden embedding, in the sense that, `up to symmetries', for each vertex $v$ we find a point within distance about $r$ of $X_v$; that is, we find an embedding with `displacement' at most about $r$. Now suppose that, instead of being given the graph $G$, we are given, for each vertex $v$, the ordering of the other vertices by increasing Euclidean distance from $v$. Then, with high probability, in polynomial time we can find an embedding with the much smaller displacement error $O(sqrtlogn)$.

Recommendations

• Point-based polygonal models for random graphs
• scientific article; zbMATH DE number 1420916
• scientific article; zbMATH DE number 5942363
• Random Geometric Graphs
• Exact and efficient generation of geometric random variates and random graphs
• Structural, Syntactic, and Statistical Pattern Recognition
• Sampling geometric inhomogeneous random graphs in linear time
• Lectures on random geometric graphs

Cited in

(6)

• Recovering the structure of random linear graphs
• Reconstruction of line-embeddings of graphons
• Localization in 1D non-parametric latent space models from pairwise affinities
• Projective, sparse and learnable latent position network models
• Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
• Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs

This page was built for publication: Learning random points from geometric graphs or orderings

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