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 $\alpha> \tfrac{ 1}{ 2}$, $C\in\mathbb{ R}$, $n\in\mathbb{ N}$, set $R=2\ln n+C$ and build the graph $G=(V,E)$ with $|V|=n$ as follows: For each $v\in V$, generate i.i.d. polar coordinates $(r_{ v},\theta_{ v})$ using the joint density function $f(r,\theta)$, with $\theta_{ v}$ chosen uniformly from $[0,2\pi)$ and $r_{ v}$ with density $f(r)=\frac{ \alpha\sinh(\alpha r)}{ \cosh(\alpha R)-1}$ for $0\leq r< R$. Then, join two vertices by an edge, if their hyperbolic distance is at most $R$. We prove that in the range $\tfrac{ 1}{ 2} < \alpha < 1$ a.a.s. for any two vertices of the same component, their graph distance is $O(\log^{ C_0+1+o(1)}n)$, where $C_0=2/(\tfrac{ 1}{ 2}-\frac{ 3}{ 4}\alpha+\tfrac{ \alpha^2}{ 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(\log^{ 2C_0+1+o(1)}n)$, thus answering a question of Bode, Fountoulakis and M\"{ u}ller [BFM13]. We also show that a.a.s. there exist isolated components forming a path of length $\Omega(\log n)$, thus yielding a lower bound on the size of the second largest component.
Categories: math.CO math.PR