License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.29
URN: urn:nbn:de:0030-drops-115253
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11525/
Kahle, Matthew ;
Tian, Minghao ;
Wang, Yusu
Local Cliques in ER-Perturbed Random Geometric Graphs
Abstract
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].
BibTeX - Entry
@InProceedings{kahle_et_al:LIPIcs:2019:11525,
author = {Matthew Kahle and Minghao Tian and Yusu Wang},
title = {{Local Cliques in ER-Perturbed Random Geometric Graphs}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {29:1--29:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11525},
URN = {urn:nbn:de:0030-drops-115253},
doi = {10.4230/LIPIcs.ISAAC.2019.29},
annote = {Keywords: random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery}
}
Keywords: |
|
random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery |
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
Issue Date: |
|
2019 |
Date of publication: |
|
28.11.2019 |