License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.48
URN: urn:nbn:de:0030-drops-163897
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16389/
Go to the corresponding LIPIcs Volume Portal

Dani, Varsha ; Díaz, Josep ; Hayes, Thomas P. ; Moore, Cristopher

Improved Reconstruction of Random Geometric Graphs

pdf-format:
LIPIcs-ICALP-2022-48.pdf (1 MB)

Abstract

Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n^α for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(n^β) where β = 1/2-(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O(√{log n}). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in ℝ³ and to hypercubes in any constant dimension.

BibTeX - Entry

@InProceedings{dani_et_al:LIPIcs.ICALP.2022.48,
  author =	{Dani, Varsha and D{\'\i}az, Josep and Hayes, Thomas P. and Moore, Cristopher},
  title =	{{Improved Reconstruction of Random Geometric Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16389},
  URN =		{urn:nbn:de:0030-drops-163897},
  doi =		{10.4230/LIPIcs.ICALP.2022.48},
  annote =	{Keywords: Reconstruction algorithm, distances in RGG, d-dimensional hypercube, 3 dimensional sphere}
}

Keywords: Reconstruction algorithm, distances in RGG, d-dimensional hypercube, 3 dimensional sphere
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI