Kahle, Matthew ;
Tian, Minghao ;
Wang, Yusu
Local Cliques in ERPerturbed 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 ERperturbed random geometric graph G^(p,q) is generated by removing each existing edge from G_X^* with probability p, while inserting each nonexistent 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 shortestpath metric of the random geometric graph G_X^* within a multiplicative factor of 3 from an ERperturbed 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 ERPerturbed Random Geometric Graphs}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {29:129:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11525},
URN = {urn:nbn:de:0030drops115253},
doi = {10.4230/LIPIcs.ISAAC.2019.29},
annote = {Keywords: random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery}
}
28.11.2019
Keywords: 

random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 