ALMOST OPTIMAL SPARSIFICATION OF RANDOM GEOMETRIC GRAPHS

• 成果类型: Article
• 署名作者: Broutin, Nicolas; Devroye, Luc; Lugosi, Gabor
• 署名单位: McGill University; Pompeu Fabra University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/15-AAP1170
• 发表日期: 2016
• 页码: 3078-3109
• 关键词: connectivity; expansion

摘要

A random geometric irrigation graph Gamma(n)(r(n), xi) has n vertices identified by n independent uniformly distributed points X-1, ..., X-n in the unit square [0, 11(2). Each point X-i selects xi(i) neighbors at random, without replacement, among those points X-i (j not equal i) for which parallel to X-i - X-j parallel to < r(n), and the selected vertices are connected to X-i by an edge. The number xi(i) of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each X-i such that xi(i) satisfies xi(i) >= 1. We prove that when r(n) = gamma(n)root logn/n for gamma(n) -> infinity with gamma(n) = o(n(1/6)/log(5/6) n), the random geometric irrigation graph experiences explosive percolation in the sense that if E xi(i) = 1, then the largest connected component has o(n) vertices but if E xi(i) > 1, then the number of vertices of the largest connected component is, with high probability, n - o(n). This offers a natural noncentralized sparsification of a random geometric graph that is mostly connected.