Phase transitions for detecting latent geometry in random graphs
- PDF / 873,777 Bytes
- 75 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 290 Views
Phase transitions for detecting latent geometry in random graphs Matthew Brennan1
· Guy Bresler1 · Dheeraj Nagaraj1
Received: 14 November 2019 / Revised: 1 August 2020 / Published online: 22 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These graphs are also of purely theoretical interest within computer science, probability and statistics. A fundamental initial question regarding these models is: when are these random graphs affected by their latent geometry and when are they indistinguishable from simpler models without latent structure, such as the Erd˝os– Rényi graph G(n, p)? We address this question for two of the most well-studied models of random graphs with latent geometry—the random intersection and random geometric graph. Our results are as follows: (a) The random intersection graph is defined by sampling n random sets S1 , S2 , . . . , Sn by including each element of a set of size d in each Si independently with probability δ, and including the edge {i, j} if Si ∩ S j = ∅. We prove that the random intersection graph converges in total variation to an Erd˝os–Rényi graph if d = ω(n ˜ 3 ), and does not if d = o(n 3 ), for both dense and sparse edge densities p. This resolves an open problem in Fill et al. (Random Struct Algorithms 16(2):156–176, 2000), Rybarczyk (Random Struct Algorithms 38(1–2):205–234, 2011) and Kim et al. (Random Struct Algorithms 52(4):662–679, 2018). The same result was obtained simultaneously and independently by Bubeck et al. (When random intersection graphs lose geometry. Manuscript, 2019). (b) We strengthen the preceding argument to show that the matrix of random intersection sizes |Si ∩ S j | converges in total variation to a symmetric matrix with independent Poisson entries. This yields the first total variation convergence result for τ -random intersection graphs, where the edge {i, j} is included if |Si ∩ S j | ≥ τ . More precisely, our results imply that, if p is bounded away from 1, then the τ -random intersection graph with edge density p converges to G(n, p) if d = ω(τ 3 n 3 ). (c) The random geometric graph on Sd−1 is defined by sampling X 1 , X 2 , . . . , X n uniformly at random from Sd−1 and including the edge {i, j} if X i − X j 2 ≤ τ . A result of Bubeck et al. (Random Struct Algorithms 49:503–532, 2016) showed that this model converges to G(n, p) in total variation, where p is chosen so that the models have matching edge densities, as long as d = ω(n 3 ). It was conjectured in Bubeck et al. (2016) that this
Extended author information available on the last page of the article
123
1216
M. Brennan et al.
threshold decreases drastically for p small. We towards this make the first progress conjecture by showing convergence if d = ω˜ min{ pn 3 , p 2 n 7/2 } . Our proofs are a hybrid of combinatorial arguments, direct couplings and applications of inf
Data Loading...
