2026-08-03T23:42:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11525 2024-03-06T10:48:13Z ddc:004 open_access

Local Cliques in ER-Perturbed Random Geometric Graphs Kahle, Matthew Tian, Minghao Wang, Yusu random graphs random geometric graphs edge clique number the probabilistic method metric recovery We study a random graph model introduced in [Srinivasan Parthasarathy et al., 2017] where one adds Erdős - Rényi (ER) type perturbation to a random geometric graph. More precisely, assume G_X^* is a random geometric graph sampled from a nice measure on a metric space X = (X,d). An ER-perturbed random geometric graph G^(p,q) is generated by removing each existing edge from G_X^* with probability p, while inserting each non-existent edge to G_X^* with probability q. We consider a localized version of clique number for G^(p,q): Specifically, we study the edge clique number for each edge in a graph, defined as the size of the largest clique(s) in the graph containing that edge. We show that the edge clique number presents two fundamentally different types of behaviors in G^(p,q), depending on which "type" of randomness it is generated from. As an application of the above results, we show that by a simple filtering process based on the edge clique number, we can recover the shortest-path metric of the random geometric graph G_X^* within a multiplicative factor of 3 from an ER-perturbed observed graph G^(p,q), for a significantly wider range of insertion probability q than what is required in [Srinivasan Parthasarathy et al., 2017]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthew Kahle and Minghao Tian and Yusu Wang 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.29 urn:nbn:de:0030-drops-115253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode