文章基本信息
- 标题：Local Cliques in ER-Perturbed Random Geometric Graphs
- 本地全文：下载
- 作者：Matthew Kahle ; Minghao Tian ; Yusu Wang 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2019
- 卷号：149
- 页码：1-22
- DOI：10.4230/LIPIcs.ISAAC.2019.29
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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].
- 关键词：random graphs; random geometric graphs; edge clique number; the probabilistic method; metric recovery
