A bound for the diameter of random hyperbolic graphs

Random hyperbolic graphs were recently introduced by Krioukov et. al. [KPK+10] 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 α > 1/2, C ∈ R, n ∈ N, set R = 2 ln n + C and build the graph G = (V,E) with |V| = n as follows: For each v ∈ V, generate i.i.d. polar coordinates (rv, θv) using the joint density function f(r, θ), with θv chosen uniformly from [0; 2π) and rv with density f(r) = [EQUATION] 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 1/2 < α < 1 a.a.s. for any two vertices of the same component, their graph distance is O([EQUATION]), where C0 = 2/([EQUATION]), 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([EQUATION] n), thus answering a question of Bode, Fountoulakis and Muller [BFM13]. We also show that a.a.s. there exist isolated components forming a path of length Ω(log n), thus yielding a lower bound on the size of the second largest component.