A bound for the diameter of random hyperbolic graphs

Original · EN

Random hyperbolic graphs were recently introduced by Krioukov et. al. [KPKVB10] as a model for large networks. Gugelmann, Panagiotou, and Peter [GPP12] then initiated the rigorous study of random hyperbolic graphs using the following model: for α> 12, C, n, set R=2 n+C and build the graph G=(V,E) with |V|=n as follows: For each v∈ V, generate i.i.d. polar coordinates (rᵥ,θᵥ) using the joint density function f(r,θ), with θᵥ chosen uniformly from [0,2π) and rᵥ with density f(r)=α(αr)/(αR)-1 for 0≤ r< R. Then, join two vertices by an edge, if their hyperbolic distance is at most R. We prove that in the range 12 < α< 1 a.a.s. for any two vertices of the same component, their graph distance is O(ᶜ⁰⁺¹⁺ᵒ⁽¹⁾n), where C₀=2/(12-3/4α+α²4), thus answering a question raised in [GPP12] concerning the diameter of such random graphs. As a corollary from our proof we obtain that the second largest component has size O(²ᶜ⁰⁺¹⁺ᵒ⁽¹⁾n), thus answering a question of Bode, Fountoulakis and Müller [BFM13]. We also show that a.a.s. there exist isolated components forming a path of length Ω(n), thus yielding a lower bound on the size of the second largest component.