# Typical distances in a geometric model for complex networks 111 2010
_Mathematics Subject Classification_ : Primary: 05C80; Secondary: 05C12,
05C82. _Keywords_ : complex networks, random graphs, typical distances.

Mohammed Amin Abdullah222Mathematical and Algorithmic Sciences Lab, Huawei
Technologies Ltd. e-mail<EMAIL_ADDRESS>Michel Bode333School of
Mathematics, University of Birmingham, United Kingdom e-mail:
<EMAIL_ADDRESS>Nikolaos Fountoulakis444School of Mathematics, University
of Birmingham, United Kingdom e-mail<EMAIL_ADDRESS>This research
has been supported by a Marie Curie Career Integration Grant
PCIG09-GA2011-293619.

###### Abstract

The theme of this paper is the study of _typical_ distances in a random graph
model that was introduced by Krioukov et al. [25] and envisages basic
properties of complex networks as the expression of an underlying hyperbolic
geometry. This model gives rise to sparse random graphs on the hyperbolic
plane which exhibit power law degree distribution as well as local clustering
(i.e., they are locally dense). In this paper, we show that in fact these
random graphs are  _ultra-small_ worlds. When the parameters of the model
yield a power law degree distribution with exponent between 2 and 3, we show
that the distance between two given vertices conditional on belonging to the
same component is proportional to $\log\log N$ a.a.s., where $N$ is the number
of vertices of the random graph. To be more precise, we show that the distance
rescaled by $\log\log N$ converges  _in probability_ to a certain constant
that depends on the exponent of the power law. This constant actually emerges
in the same setting in the _Chung-Lu_ model.

We also consider the regime where the exponent of the power law is larger than
3. There we show that most pairs of vertices that belong to the same component
are within distance $poly(\log\log N)$ with high probability asymptotically as
$N\rightarrow\infty$.

##  1 Introduction

The  _small-world problem_ was first stated by Stanley Milgram in his 1967
paper [26] through which he gave strong evidence of the so-called _small-world
effect_. The simplest formulation of the small-world problem [26] is:
“Starting with any two people in the world, what is the probability that they
will know each other?”. A more sophisticated formulation of the problem asks
whether any two people, if they do not directly know of each other, have
common acquaintances. Milgram’s experiment indicated that this is indeed the
case within a relatively small random sample of the population of the United
States. In particular, it turned out the at least half of the sample was
within _six degrees of separation_ from the “target” individual. In graph
theoretic terms, in the graph of acquaintances the nodes that represent these
individuals are within distance 6 from the node that was representing the
target individual.

The small-world phenomenon is ubiquitous in natural and technological networks
such as neural networks, the Internet, the World-Wide-Web or the power grid –
see the book of Chung and Lu [14] as well as the book of Dorogovtsev [10] for
experimental evidence regarding such networks. For example, it was announced
relatively recently that between any two active users of Facebook there are
3.74 degrees of separation on average [31].

There have been numerous attempts to explain this phenomenon through the
theory of complex networks. Among the initial attempts was the “small-world”
model of Watts and Strogatz which is defined through random re-wiring of the
edges of a cyclic lattice. This model exhibits small average distance, but
lacks a basic feature of such large self-organizing networks which is the
_scale freeness_. Experimental evidence [1] suggests that these networks have
a distribution of degrees whose tail decays like a power law with exponent
usually between 2 and 3.

Of course the term “small-world” itself is somewhat vague. Loosely speaking,
the term refers to average distances that are slowly growing functions of the
number of vertices of the network. A possible candidate is the logarithmic
function. Thus, the classical Erdős-Rényi random graph may be thought of as a
small-world graph as it has logarithmic diameter – see [4]. However, it lacks
the scale freeness as well and, furthermore, it represents a very homogeneous
network. This is a very unrealistic feature as most large scale networks
contain vertices that have very different properties from each other. Sub-
logarithmic bounds on the diameter were established for the preferential
attachment model [2] by Bollobás and Riordan [6]. As it was shown by Bollobás
et al. [7], this is scale-free with exponent equal to 3.

Recent research that focused on models for complex networks that are scale
free with power law exponent between 2 and 3 identified cases of such networks
that are _ultrasmall_. This term is associated with models in which the
distance between two randomly chosen connected vertices grows _doubly
logarithmically_ in the number of vertices of the random graph. With $N$
denoting the number of vertices, the function $\log\log N$ is a very slowly
growing function. Presumably this is closer to empirical evidence which comes
from networks that have millions of vertices but whose average distance
between two randomly chosen vertices is very small.

An analytical relation between the two was first established by Cohen and
Havlin [8] and by Dorogovtsev, Mendes and Samukhin [11]. It was shown
rigorously for a variety of random graph models which exhibit power law degree
distribution such as the Chung-Lu model [12], the Noros-Reittu model [27], the
configuration model [20] as well as variations of the preferential attachment
model [15] [9].

###  1.1 A geometric framework for complex networks

Recently, Krioukov et al. [25] introduced a geometric framework in order to
represent the inherent inhomogeneity of a complex network. Their basic
assumption is that the intrinsic hierarchies that are present in a complex
network induce a tree-like structure. This suggests that the geometry of a
complex network is hyperbolic.

The most common representations of the hyperbolic plane are the upper-half
plane representation $\\{z=x+iy\ :\ y>0\\}$ as well as the Poincaré unit disk
which is simply the open disk of radius one, that is,
$\\{(u,v)\in\mathbb{R}^{2}\ :\ 1-u^{2}-v^{2}>0\\}$. Both spaces are equipped
with the hyperbolic metric; in the former case this is ${dx^{2}+dy^{2}\over
y^{2}}$ whereas in the latter this is
${4}~{}{du^{2}+dv^{2}\over(1-u^{2}-v^{2})^{2}}$. It is well-known that the
(Gaussian) curvature in both cases is equal to $-1$ and that the two spaces
are isometric. In fact, there are more representations of the hyperbolic plane
of curvature $-1$, which are isometrically equivalent to the above two. We
will denote by $\mathbb{H}^{2}$ the class of these spaces.

We are now ready to give the definition of the basic model introduced in [25].
Consider the Poincaré disk representation of the hyperbolic plane. Let $N$ be
the number of vertices of the random graph, of which we assume that it tends
to infinity. Consider also some fixed constant $\nu>0$ and let $R>0$ satisfy
$N=\nu e^{R/2}$. It turns out that this parameter determines the average
degree of the random graph. Let $V_{N}:=\\{v_{1},\ldots,v_{N}\\}$ be the set
of vertices, where each $v_{i}$ is a point selected randomly and independently
from the disk of radius $R$ centered at the origin of the Poincaré disk $O$;
we denote this disk by $\mathcal{D}_{R}$.

Each of these points is distributed as follows. Assume that a random point $u$
has _polar_ coordinates $(r,\theta)$. The angle $\theta$ is uniformly
distributed in $(0,2\pi]$ and the probability density function of $r$, which
we denote by $\rho_{N}(r)$, is determined by a parameter $\alpha>0$ and is
equal to

$\rho(r)=\rho_{N}(r)=\begin{cases}\alpha{\sinh\alpha r\over\cosh\alpha
R-1},&\mbox{if $0\leq r\leq R$}\\\ 0,&\mbox{otherwise}\end{cases}.$ (1.1)

The above distribution is simply the uniform distribution on
$\mathcal{D}_{R}$, but _on the hyperbolic plane of curvature $-\alpha^{2}$_.
With elementary but tedious calculations, it can be shown that the length of a
circle of radius $r$ (centered at the origin) on the hyperbolic plane of
curvature $-\alpha^{2}$ is $\frac{2\pi}{\alpha}~{}\sinh(\alpha r)$, whereas
the area of the circle of radius $R$ (centered at the origin) is
$\mathrm{Area}_{\alpha}(\mathcal{D}_{R})=\frac{2\pi}{\alpha^{2}}(\cosh(\alpha
R)-1)$. We will be using the function $\mathrm{Area}_{\alpha}(\cdot)$ to
denote the area of a measurable set in $\mathcal{D}_{R}$ on the hyperbolic
plane of curvature $-\alpha^{2}$. Thus, if we set $\alpha=1$, then the above
becomes the density of the uniform distribution.

Alternatively, consider the disk $\mathcal{D}_{R}^{\prime}$ of radius $R$
around the origin $O^{\prime}$ of (the Poincaré disk representing) the
hyperbolic plane of curvature $-\alpha^{2}$. We select $N$ points within
$\mathcal{D}_{R}^{\prime}$ independently of each other, uniformly at random.
These points are projected onto $\mathcal{D}_{R}$ preserving their polar
coordinates. The projections of these points will be the vertex set $V_{N}$ of
the random graph.

The curvature of the hyperbolic plane determines the rate of growth of the
space. A tedious calculation shows that the curvature of the hyperbolic plane
is $-\alpha^{2}$, if we multiply the metric by $1/\alpha^{2}$. Hence, when
$\alpha<1$, the $N$ points are distributed on a disk (namely
$\mathcal{D}_{R}^{\prime}$) which has smaller area compared to
$\mathcal{D}_{R}$. This naturally increases the density of those points that
are located closer to the origin. Similarly, when $\alpha>1$ the area of the
disk $\mathcal{D}_{R}^{\prime}$ is larger than that of $\mathcal{D}_{R}$, and
most of the $N$ points are significantly more likely to be located near the
boundary of $\mathcal{D}_{R}^{\prime}$, due to the exponential growth of the
volume.

Given the set $V_{N}$ on $\mathcal{D}_{R}$ we define the random graph
$\mathcal{G}(N;\alpha,\nu)$ on $V_{N}$, where two distinct vertices are joined
if and only if they are within (hyperbolic) distance $R$ from each other.

#### Notation

We now introduce some notation which we use throughout out proofs. Let
$a_{N},b_{N}$ be two sequences of positive real numbers. We write
$a_{N}\approx b_{N}$ to indicate that $a_{N}=\Theta(b_{N})$, that is, there
are real numbers $c,C>0$ such that $cb_{N}\leq a_{N}\leq Cb_{N}$, for all
natural numbers $N$. We also write $a_{N}\sim b_{N}$ to denote that
$a_{N}/b_{N}\rightarrow\infty$, as $N\rightarrow\infty$.

If $\mathcal{E}_{N}$ is an event on the probability space
$(\Omega_{N},\mathbb{P}_{N},\mathcal{F}_{N})$, for each $N\in\mathbb{N}$, we
say that $\mathcal{E}_{N}$ _occurs asymptotically almost surely (a.a.s.)_ if
$\mathbb{P}(\mathcal{E}_{N})\rightarrow 1$ as $N\rightarrow\infty$. In our
context, we mainly use the sequence of probability spaces that is induced by
$\mathcal{G}(N;\alpha,\nu)$. However, later we introduce a variant of this
model which is its _Poissonisation_. We will be using the term _a.a.s._ for
that model as well.

####  1.1.1 Some facts about $\mathcal{G}(N;\alpha,\nu)$

We argue that the above model can be thought of as a geometrization of the
random graph model that was introduced by F. Chung and L. Lu [12] [13] and is
a special case of an inhomogeneous random graph. The notion of _inhomogeneous
random graphs_ was introduced Söderberg [28], but was defined more generally
and studied in great detail by Bollobás, Janson and Riordan in [5]. In its
most general setting, there is an underlying compact metric space
$\mathcal{S}$ equipped with a measure $\mu$ on its Borel $\sigma$-algebra.
This is the space of _types_ of the vertices (defined below). A _kernel_
$\kappa$ is a bounded real-valued, non-negative function on
$\mathcal{S}\times\mathcal{S}$, which is symmetric and measurable. The
vertices of the random graph can be understood as points in $\mathcal{S}$. If
$x,y\in\mathcal{S}$, then the corresponding vertices are joined with
probability ${\kappa(x,y)\over N}\wedge 1$, independently of every other pair
($N$ is the total number of vertices). The points that are the vertices of the
graph are approximately distributed according to $\mu$. More specifically, the
empirical distribution function on the $N$ points converges weakly to $\mu$ as
$N\rightarrow\infty$.

Of particular interest is the case where the kernel function can be factorized
and can be written $\kappa(x,y)=t(x)t(y)$; this is called a _kernel of rank
1_. Intuitively, the function $t(x)$ can be thought of as the weight or the
type of vertex $x$. It is approximately its expected degree. In the special
case where $t(x)$ follows a distribution that has a power law tail, the model
becomes the so-called Chung-Lu model that was introduced in a series of papers
[12] [13] (see also [19]).

We argue that in the random graph $\mathcal{G}(N;\alpha,\nu)$, the probability
that two vertices are adjacent has this form. The proof of this fact relies on
Lemma 2.5, which we will state later and is proved in [3]. It provides an
approximate characterization of what it means for two points $u,v$ to have
hyperbolic distance at most $R$ in terms of their _relative angle_ , which we
denote by $\theta_{u,v}$. For this lemma, we need the notion of the _type_ of
a vertex. For a vertex $v\in V_{N}$, if $r_{v}$ is the distance of $v$ from
the origin, that is, the radius of $v$, then we set $t_{v}=R-r_{v}$ – we call
this quantity the _type_ of vertex $v$. As we shall shortly see, the type of a
vertex is approximately exponentially distributed. If we substitute $R-t$ for
$r$ in (1.1), then assuming that $t$ is fixed that expression becomes
asymptotically equal to $\alpha e^{-\alpha t}$. Roughly speaking, Lemma 2.5
states that two vertices $u$ and $v$ of types $t_{u}$ and $t_{v}$ are within
distance $R$ (essentially) if and only if
$\theta_{u,v}<2\nu{e^{t_{u}/2}e^{t_{v}/2}}/N$. Hence, conditional on their
types the probability that $u$ and $v$ are adjacent is proportional to
${e^{t_{u}/2}e^{t_{v}/2}}/N$. If we set $t(u)=e^{t_{u}/2}$, then
$\mathbb{P}(t(u)\geq x)=\mathbb{P}(t_{u}\geq 2\ln x)\approx e^{-2\alpha\ln
x}=1/x^{2\alpha}$. In other words, the distribution of $t(u)$ has a power-law
tail with parameter $2\alpha$. Thus, the random graph
$\mathcal{G}(N;\alpha,\nu)$ is a _dependent_ version of the Chung-Lu model
that emerges naturally from the hyperbolic geometry of the underlying space.
The fact that this is a random geometric graph gives rise to local clustering,
which is missing in the Chung-Lu model. There, most vertices have tree-like
neighborhoods.

In fact, it can be shown that the degree of a vertex $u$ in
$\mathcal{G}(N;\alpha,\nu)$ that has type $t_{u}$ is approximately distributed
as a Poisson random variable with parameter proportional to $e^{t_{u}/2}$.

Gugelmann, Panagiotou and Peter [18] showed that the degree of a vertex has a
power law with exponent $2\alpha+1$. If $\alpha>1/2$, then the exponent of the
power law may take any value greater than 2. When $1>\alpha>1/2$, this
exponent is between 2 and 3. They also showed that the average degree is a
constant that depends on $\alpha$ and $\nu$, and that the clustering
coefficient (the probability of two vertices with a common neighbor to be
joined by an edge) of $\mathcal{G}(N;\alpha,\nu)$ is asymptotically bounded
away from $0$ with probability $1-o(1)$ as $N\rightarrow\infty$.

Furthermore, the last two authors together with Müller [3] showed that
$\mathcal{G}(N;\alpha,\nu)$ with high probability has a _giant component_ ,
that is, a connected component containing a linear number of vertices if
$1/2<\alpha<1$. When $\alpha>1$, the size of the largest component is bounded
by a function that is _sublinear_ in $N$. When $\alpha=1$, the existence of a
giant component depends on the value of $\nu$.

###  1.2 Results

In this contribution, we give an almost sure bound on the (graph) distance
between two randomly chosen vertices that belong to the same connected
component. We show that $\mathcal{G}(N;\alpha,\nu)$ is _ultrasmall_ when
$\frac{1}{2}<\alpha<1$, that is, when the degree distribution has a power law
tail with exponent between 2 and 3. More specifically, we show that a.a.s. the
graph distance between two randomly chosen vertices that belong to the same
component is of order $\log\log N$. However, the diameter of
$\mathcal{G}(N;\alpha,\nu)$ grows at least logarithmically in $N$. This is a
recent result of Kiwi and Mitsche [24], where they show that there is a
connected component of diameter proportional to $\log N$. They also derive an
upper bound on the diameter showing that the diameter is at most proportional
to $R^{1+C}$ a.a.s., for some positive constant $C$ that depends on the
parameters of the model. More recently, Friedrich and Krohmer [17] improved
the constant showing that the exponent is at most $1/(2(1-\alpha))$. They also
show that if $\nu$ is small enough, then the exponent is equal to 1. Note that
the Chung-Lu model exhibits logarithmic diameter [12].

For $\alpha>1$, we show that a.a.s. $\mathcal{G}(N;\alpha,\nu)$ is _almost_
ultrasmall: the graph distance between two randomly chosen vertices that
belong to the same component is a.a.s. bounded by some polynomial of $\log\log
N$. This range of $\alpha$ yields a power law degree distribution with
exponent greater than 3. For this range, Chung and Lu [12] proved that the
Chung-Lu model exhibits average distances of order $\log N$ asymptotically
with high probability.

Let $d_{G}(u,v)$ denote the graph distance between two vertices $u$ and $v$.

######  Theorem 1.1.

For $\zeta>0$, assume that $1/2<\alpha<1$ and $u,v\in V_{N}$. Let $\tau$ be
such that $\tau^{-1}=\log\left(\frac{1}{2\alpha-1}\right)$. A.a.s. if
$d_{G}(u,v)<\infty$, then $\left|\frac{d_{G}(u,v)}{\log
R}-2\tau\right|<\zeta$.

In this regime, $\mathcal{G}(N;\alpha,\nu)$ does have a giant component and
therefore for any two distinct vertices $u,v$ we have $d_{G}(u,v)<\infty$ with
probability that is asymptotically bounded away from 0. The upper bound (which
is probably the most important) in the above result was also derived by Chung
and Lu [12] for the Chung-Lu model with power law exponent between $2$ and
$3$. That was under the assumption that the average degree is greater than 1.
However, in our case a giant component is formed _independently_ of what the
average degree is, as long as $1/2<\alpha<1$. The full result for the Chung-Lu
model can be found in [19].

The above result was also derived in the case of random graphs with given
degree distribution that follows a power law with parameter between 2 and 3 by
van der Hofstad et al. [20] in a stronger form which involves convergence in
distribution.

Our second result provides an upper bound on the typical distance between two
connected vertices when $\alpha>1$. In this case there is no giant component
a.a.s. However, the largest component contains _polynomially many_ vertices as
there is a number of a vertices of degree that scales polynomially in $N$.
However, these components form also (almost) _ultrasmall_ worlds.

######  Theorem 1.2.

Let $\alpha>1$, $\varepsilon>0$. There is a subset $V^{\prime}$ of vertices of
$\mathcal{G}(N;\alpha,\nu)$ of size $(1-o(1))N$ so that if $u,v\in V^{\prime}$
and $d_{G}(u,v)<\infty$, then $d_{G}(u,v)\leq\log^{1+\varepsilon}\log N$.

In the next section, we introduce the _Poissonisation_ of
$\mathcal{G}(N;\alpha,\nu)$ which is convenient for our calculations.
Thereafter, we will state and prove some basic geometric facts regarding the
hyperbolic plane, which allow us to express distances on the hyperbolic plane
in terms of polar coordinates on $\mathcal{D}_{R}$. Subsequently, we proceed
with the proof of Theorems 1.1 and 1.2.

The main idea behind the proof of Theorem 1.1 makes use of the existence of a
very dense core that is formed by those vertices that have type at least
$R/2$. We show that if two vertices are connected, then most likely they have
short paths to the core which itself is a complete graph. These paths, which
we call _exploding_ , emerge also in the Chung-Lu model [12, 19].

##  2 Preliminary results

###  2.1 Poissonisation

It will be significantly easier to work in a setting where, instead of having
exactly $N$ random points, our vertex set consists of $\mathrm{Po}(N)$ points
on $\mathcal{D}_{R}$, in the hyperbolic plane of curvature $-\alpha^{2}$. Two
vertices/points are declared adjacent exactly as in
$\mathcal{G}(N;\alpha,\nu)$. We denote the resulting graph by
$\mathcal{P}(N;\alpha,\nu)$. More specifically, the vertex set consists of the
points of a Poisson point process in $\mathcal{D}_{R}$ (see [23]). In every
measurable set $U\subseteq\mathcal{D}_{R}$, the number of points in $U$
follows the Poisson distribution with parameter equal to
$N\frac{\mathrm{Area}_{\alpha}(U)}{\mathrm{Area}_{\alpha}(\mathcal{D}_{R})}$.
Moreover, the numbers of points in any finite collection of pairwise disjoint
measurable subsets of $\mathcal{D}_{R}$ are independent Poisson-distributed
random variables.

We prove the following lemma that allows us to transfer results from the
Poisson model into the $\mathcal{G}(N;\alpha,\nu)$ model. Let
$\mathcal{A}_{n}$ denote a set of graphs on $\mathrm{V}_{n}:=\\{1,\ldots,n\\}$
that is closed under automorphisms. We call a family
$\mathcal{A}=\\{\mathcal{A}_{n}\\}_{n\in\mathbb{N}}$ of graphs _(vertex-) non-
decreasing_ , if $G-v\in\mathcal{A}_{n-1}$ for any555$G-v\in\mathcal{A}_{n-1}$
means that $G-v$ is isomorphic to a member of $\mathcal{A}_{n-1}$ $v\in V(G)$
implies $G\in\mathcal{A}_{n}$. Similarly, we call the family _(vertex-) non-
increasing_ , if $G-v\notin\mathcal{A}_{n-1}$ for any $v\in V(G)$ implies
$G\notin\mathcal{A}_{n}$.

######  Lemma 2.1.

Assume that $\alpha>0$ is fixed. Let $\mathcal{A}$ be a (vertex-) non-
increasing family of graphs. For $N$ large enough we have
$\mathbb{P}(\mathcal{G}(N;\alpha,\nu)\notin\mathcal{A})<4\mathbb{P}(\mathcal{P}(N;\alpha,\nu)\notin\mathcal{A})$.
The same holds if $\mathcal{A}$ is (vertex-) non-decreasing.

###### Proof.

Denote by $E_{\mathrm{Po}}$ and $E$ the events that
$\mathcal{P}(N;\alpha,\nu)\notin\mathcal{A}$ and
$\mathcal{G}(N;\alpha,\nu)\notin\mathcal{A}$, respectively. We write

$\displaystyle\mathbb{P}(E_{Po})=$
$\displaystyle\sum_{N^{\prime}=0}^{\infty}\mathbb{P}(E_{Po}|Po(N)=N^{\prime})\cdot\mathbb{P}(Po(N)=N^{\prime})$
$\displaystyle\geq$
$\displaystyle\sum_{N^{\prime}=N}^{\infty}\mathbb{P}(E_{Po}|Po(N)=N^{\prime})\cdot\mathbb{P}(Po(N)=N^{\prime})$
$\displaystyle\geq$
$\displaystyle\sum_{N^{\prime}=N}^{\infty}\mathbb{P}(E_{Po}|Po(N)=N)\cdot\mathbb{P}(Po(N)=N^{\prime}),$

where we have used in the last line that, since $\mathcal{A}$ is non-
increasing, we have
$\mathbb{P}(E_{\mathrm{Po}}|\mathrm{Po}(N)=N^{\prime})\geq\mathbb{P}(E_{\mathrm{Po}}|\mathrm{Po}(N)=N)$
for $N^{\prime}\geq N$. Let us also note that
$\mathbb{P}(E_{\mathrm{Po}}|\mathrm{Po}(N)=N)=\mathbb{P}(E)$. Thus,

$\displaystyle\mathbb{P}(E_{\mathrm{Po}})$
$\displaystyle\geq\sum_{N^{\prime}=N}^{\infty}\mathbb{P}(E)\cdot\mathbb{P}(\mathrm{Po}(N)=N^{\prime})$
$\displaystyle=\mathbb{P}(E)\cdot\mathbb{P}(\mathrm{Po}(N)\geq N)$
$\displaystyle>\frac{1}{4}\cdot\mathbb{P}(E),$

where the last line holds $N$ large enough (by an application of, say, the
central limit theorem). The second part of the lemma follows similarly,
bounding the sum by taking only the terms where $N^{\prime}\leq N$. ∎

This implies that if
$\mathbb{P}(\mathcal{P}(N;\alpha,\nu)\notin\mathcal{A})=o(1)$, then
$\mathbb{P}(\mathcal{G}(N;\alpha,\nu)\notin\mathcal{A})=o(1)$.

During some of our proofs, we will need to bound probabilities of events that
are associated with a certain subset of vertices $X$, whose positions in
$\mathcal{D}_{R}$ have been realised. For a certain measurable subset
$U\subset\mathcal{D}_{R}$ which does not contain any vertex in $X$ so that
$\mathcal{D}_{R}\setminus U$ has positive Lebesgue measure, the vertices of
the random graph $\mathcal{P}_{X,U}(N;\alpha,\nu)$ consist of $X$ together
with set of points of a Poisson process on $\mathcal{D}_{R}\setminus U$ with
curvature $-\alpha^{2}$ with parameter $N-|X|$. Hence, this process “produces”
$N-|X|$ vertices on average, thus giving $N$ vertices in total on average. If
we condition on the number of vertices of this Poisson process being
$N^{\prime}$, then the resulting random graph is distributed as
$\mathcal{G}(N^{\prime};\alpha,\nu)$ conditional on $U$ _being empty_ and $X$
being located at its particular positions.

Let $\mathcal{A}_{X}$ be a graph property associated with the set $X$. We call
this _non-decreasing_ if

$\mathbb{P}_{\mathcal{P}_{X,U}(N;\alpha,\nu)}(\mathcal{A}_{X}\ |\
\mathrm{Po}(N-|X|)=N_{1})\leq\mathbb{P}_{\mathcal{P}_{X,U}(N;\alpha,\nu)}(\mathcal{A}_{X}\
|\ \mathrm{Po}(N-|X|)=N_{2}),$

whenever $N_{1}\leq N_{2}$. If the opposite inequality holds, we call the
property _non-increasing_. Note that
$\mathbb{P}_{\mathcal{P}_{X,U}(N;\alpha,\nu)}(\mathcal{A}_{X}\ |\
\mathrm{Po}(N-|X|)=N^{\prime})$ is the probability of $\mathcal{A}_{X}$ in the
space $\mathcal{G}(N^{\prime}+|X|;\alpha,\nu)$ conditional on $X$ being at
certain positions in $\mathcal{D}_{R}$ and $U$ being empty – we denote this by
$\mathcal{G}_{X,U}(N;\alpha,\nu)$. Hence, arguing as in the proof of the
previous lemma we have

######  Lemma 2.2.

If $\mathcal{A}_{X}$ is either a non-decreasing or a non-increasing property
that is associated with a certain set of vertices $X$, then

$\mathbb{P}_{\mathcal{P}_{X,U}(N;\alpha,\nu)}(\mathcal{A}_{X})\geq\frac{1}{4}\mathbb{P}_{\mathcal{G}_{X,U}(N;\alpha,\nu)}(\mathcal{A}_{X}),$

for any measurable $U\subset\mathcal{D}_{R}$ such that $X\cap U=\emptyset$ and
$\mathcal{D}_{R}\setminus U$ has positive Lebesgue measure.

The following useful fact follows directly from the definition of the process,
using the measure defined for the distribution of the points.

######  Fact 2.3.

Let $A$ be a subset of $\mathcal{D}_{R}\setminus U$, for some measurable
subset $U\subset\mathcal{D}_{R}$, and $X$ be a set of vertices located in
$\mathcal{D}_{R}$, such that $X\cap U,A\cap U=\emptyset$. Let $N_{A}$ be the
expected number of vertices in $A$, in $\mathcal{G}_{X,U}(N;\alpha,\nu)$, and
denote by $\mathcal{E}_{A}$ the event that $A$ is empty. We have

$\mathbb{P}_{\mathcal{P}_{X,U}(N;\alpha,\nu)}(\mathcal{E}_{A})=\exp(-N_{A}).$

###  2.2 Geometric properties of $\mathcal{D}_{R}$

We state a simple geometric fact, which we will use in the following sections.
With $O$ being the origin, we say that a vertex $v$ lies _above_ some edge
$uw$ when $v$ is inside the (hyperbolic) triangle $Ouw$, where $uw$ is the
geodesic path in $\mathcal{D}_{R}$ that joins $u$ with $w$. Similarly, $v$
lies _below_ the edge $uw$, if $v$ does not lie above $uw$ but some radial
projection of $v$ towards $O$ lies above $uw$.

######  Fact 2.4.

If the vertex $w$ lies above the edge $u^{\prime}u^{\prime\prime}$, then $w$
is adjacent to $u^{\prime}$ and to $w^{\prime}$. Moreover, the geodesic
segments connecting $w$ to $u^{\prime}$ and $u^{\prime\prime}$ lie entirely in
the triangle $Ou^{\prime}u^{\prime\prime}$.

###### Proof.

The hyperbolic triangle $Ou^{\prime}u^{\prime\prime}$ has only sides of length
at most $R$. The vertex $w$ lies inside this triangle, so it has distance at
most $R$ from $O$, $u^{\prime}$ and $u^{\prime\prime}$. This is the case for
any point $v$ in the triangle $Ou^{\prime}u^{\prime\prime}$. The geodesic from
$v$ to $u^{\prime}$ is entirely in the triangle, since otherwise it would have
to cross one of the sides. A crossing point would therefore have two paths of
minimum length to $u^{\prime}$, which is a contradiction. The same argument
also works for the geodesic segment between $v$ and $u^{\prime\prime}$. ∎

The following lemma provides a useful (almost) characterization of the fact
that two vertices are within hyperbolic distance $R$, given their types.
Recall first that for any two points/vertices $u,v$ on $\mathcal{D}_{R}$,
their _relative angle_ $\theta_{u,v}$ is defined as
$\min\\{\hat{uOv},2\pi-\hat{uOv}\\}$. Note that $\theta_{u,v}\leq\pi$ always.
The lemma reduces a statement about hyperbolic distances to a statement about
the relative angle between two points. Its proof can be found in [16] and [3].
For two points $p,v$, let

$\hat{\theta}_{p,v}:=\min\left\\{2(1+\varepsilon)e^{\frac{t_{p}+t_{v}-R}{2}},\pi\right\\}=\min\left\\{2(1+\varepsilon)\frac{\nu}{N}e^{\frac{t_{p}+t_{v}}{2}},\pi\right\\}\text{,
and}$
$\check{\theta}_{p,v}:=\min\left\\{2(1-\varepsilon)e^{\frac{t_{p}+t_{v}-R}{2}},\pi\right\\}=\min\left\\{2(1-\varepsilon)\frac{\nu}{N}e^{\frac{t_{p}+t_{v}}{2}},\pi\right\\}\text{.}$

For $c_{0}=c_{0}(\varepsilon)$, that depends on $\varepsilon$ as in the
following lemma, we call the set

$T_{\varepsilon}^{+}(v):=\left\\{p\in D_{R}\ :\ t_{p}+t_{v}-R<-c_{0},\
\theta_{p,v}\leq\hat{\theta}_{p,v}\right\\}$

the _outer tube_ of $v$. Similarly, we call the set

$T_{\varepsilon}^{-}(v):=\left\\{p\in D_{R}\ :\ t_{p}+t_{v}-R<-c_{0},\
\theta_{p,v}\leq\check{\theta}_{p,v}\right\\}$

the _inner tube_ of $v$.

######  Lemma 2.5.

For any $\varepsilon>0$ there exists an $N_{0}>0$ and a $c_{0}>0$ such that
for any $N>N_{0}$ and $u,v\in\mathcal{D}_{R}$ with $t_{u}+t_{v}<R-c_{0}$ the
following hold.

  * •

If $u\in T_{\varepsilon}^{-}(v)$, then $d(u,v)<R$.

  * •

If $u\not\in T_{\varepsilon}^{+}(v)$, then $d(u,v)>R$.

###  2.3 Properties of $\mathcal{G}(N;\alpha,\nu)$

We state some general results about the graphs, the proofs of which can be
found in [3].

######  Lemma 2.6.

Let $\bar{\rho}(t)$ be the distribution of the types. For any
$\varepsilon\in(0,1)$, uniformly for $0\leq t<(1-\varepsilon)R$ we have

$\bar{\rho}(t)=\rho(R-t)=(1+o(1))\alpha e^{-\alpha t}.$ (2.1)

The following fact is an immediate consequence of the above.

######  Corollary 2.7.

Let $\omega:\mathbb{N}\rightarrow\mathbb{N}$ be an increasing function such
that $\omega(N)\rightarrow\infty$ as $N\rightarrow\infty$. The expected number
of vertices of type at least $R/(2\alpha)+\omega(N)$ in
$\mathcal{G}(N;\alpha,\nu)$ is $o(1)$. Hence, with probability $1-o(1)$ all
vertices in $V_{N}$ have type at most $\frac{1}{2\alpha}R+\omega(N)$.

##  3 Proof of Theorem 1.1: upper bound

In this section we assume $1/2<\alpha<1$.

######  Definition 3.1.

For $G\in\mathcal{P}(N;\alpha,\nu)$ or $G\in\mathcal{G}(N;\alpha,\nu)$, let
$\operatorname{Core}(G)=\\{v\in V(G)\ :\ t_{v}\geq R/2\\}$ be the core of $G$.

Note that for every pair of vertices $u,v\in\operatorname{Core}(G)$, by the
triangle inequality the distance between $u$ and $v$ is at most $R$, so $uv\in
E(G)$. In other words, the subgraph that is induced by the vertices in
$\operatorname{Core}(G)$ is complete.

######  Lemma 3.2.

Let $\omega(N)$ be such that $\omega(N)\rightarrow\infty$ as
$N\rightarrow\infty$ but $\omega(N)=o(R)$. Let $x$ be a vertex such that
$t_{x}<\log\log R$ and $U\subset\mathcal{D}_{R}$ an open subset of
$\mathcal{D}_{R}$ which does not contain any points of type at least $\log\log
R$ and has
$\mathrm{Area}_{\alpha}(U)=o(\mathrm{Area}_{\alpha}(\mathcal{D}_{R}))$. Let
$G\in\mathcal{P}_{{x},U}(N;\alpha,\nu)$. A.a.s. there is a vertex
$u\in\operatorname{Core}(G)$ such that $uv\in E(G)$ for every vertex $v$ with
$t_{v}\geq\frac{2\alpha-1}{2\alpha}R+\omega(N)$.

###### Proof.

By the triangle inequality, any such vertex $v$ is adjacent to any vertex of
radius at most $R(2\alpha-1)/(2\alpha)+\omega(N)$, so it is sufficient to show
that a.a.s. the disc $D_{r}$ of radius
$r:=\frac{2\alpha-1}{2\alpha}R+\omega(N)$ is non-empty. Note that $r<R/2$, for
any $N$ large enough, as $\omega(N)=o(R)$ and $\alpha<1$, so any vertex in
$D_{r}$ belongs to the core. Let $N_{r}$ be the number of vertices in $D_{r}$.

Note first that $\frac{2\alpha-1}{2\alpha}-1=-\frac{1}{2\alpha}$. Thus
$r-R=-\frac{R}{2\alpha}+\omega(N)$, whereby
$\alpha(r-R)=-R/2+\alpha\omega(N)$. As $D_{r}\cap U=\emptyset$, these
identities imply that

$\begin{split}\mathbb{E}\left[\,N_{r}\,\right]&=(N-2)\frac{\cosh(\alpha
r)-1}{\mathrm{Area}_{\alpha}(\mathcal{D}_{R})-\mathrm{Area}_{\alpha}(U)}=(N-2)\frac{\cosh(\alpha
r)-1}{\cosh(\alpha R)(1-o(1))}\\\ &\sim
Ne^{\alpha(r-R)}=Ne^{-R/2+\omega(N)}\stackrel{{\scriptstyle N=\nu
e^{R/2}}}{{=}}\nu e^{\alpha\omega(N)}.\end{split}$

Using this and Fact 2.3 we get

$\displaystyle\mathbb{P}(N_{r}\neq 0)$ $\displaystyle=1-e^{-(1+o(1))\nu
e^{\alpha\omega(N)}}=1-o(1).$

∎

In fact, the only component we consider is the one containing the vertices in
the core. We show that most pairs of vertices that are connected have a short
path into the core. These paths naturally give short paths connecting all the
vertices in the component. We are interested in the following paths in which
the type of the vertices increases exponentially along the path.

######  Definition 3.3.

For $\delta>0$, we call a path $P=v_{1},v_{2},\dots,v_{m}$ in $G$ a
$\delta$-_exploding path_ if $v_{m}\in\operatorname{Core}(G)$ and
$t_{v_{i+1}}\geq(1+\delta)t_{v_{i}}$ for $1\leq i\leq m-2$.

Not every vertex in the giant component has an exploding path into the core.
However, the vertices that do not have such a path are more likely to have a
very low type. In particular, we prove that any vertex of type at least
$\log\log R$ has an exploding path into the core with probability $1-o(1)$. We
actually show this lemma for the Poisson model. The result does transfer to
$\mathcal{G}(N;\alpha,\nu)$, due to its monotonicity, but we are going to use
it later in this form.

######  Lemma 3.4.

Let $\delta=2\frac{1-\alpha}{2\alpha-1}$ and $\zeta<\delta$ be a positive real
number. Assume that $v$ and $x$ are vertices such that $t_{v}\geq\log\log
R\geq t_{x}$ and $U\subset\mathcal{D}_{R}$ an open subset which does not
contain any points of type at least $t_{v}$ so that $U$ is contained in a
sector of $\mathcal{D}_{R}$ that spans a $o(1)$ angle. With probability (in
the space $\mathcal{P}_{\\{v,x\\},U}(N;\alpha,\nu)$)
$1-e^{-\Theta(\log^{(\alpha-\frac{1}{2})\zeta}R)}$, there is a
$(\delta-\zeta)$-exploding path starting at $v$.

###### Proof.

Take any $\varepsilon<\frac{1}{4}$ and assume that $N>N_{0}$, where $N_{0}$ is
as in Lemma 2.5.

By Lemma 3.2, if $v$ satisfies
$t_{v}\geq\frac{2\alpha-1}{2\alpha}R+\omega(N)$, then a.a.s. there is a vertex
$u\in G$ with $t_{u}\geq R/2$ and $vu\in E(G)$. In other words, if
$t_{v}\geq\frac{2\alpha-1}{2\alpha}R+\omega(N)$, then we are done.

Assume now that $t_{v}<\frac{2\alpha-1}{2\alpha}R+\omega(N)$. As
$1+\delta=\frac{1}{2\alpha-1}$, it follows that
$(1+\delta)t_{v}<\frac{1}{2\alpha}R+\frac{\omega(N)}{2\alpha-1}$. Note that by
Corollary 2.7, it suffices to consider only points of type no larger than
$\frac{1}{2\alpha}R+\frac{\omega(N)}{2\alpha-1}$.

Let $v_{1}=v$. We will construct inductively a series of (random) sets
$T_{i}\subset\mathcal{D}_{R}$, for $i\geq 2$, in each of which we find a
vertex $v_{i}$, which will be the $i$th vertex in the exploding path.

For two points $p,p^{\prime}$, let
$\vartheta_{p,p^{\prime}}=\theta_{p,p^{\prime}}$ if $p^{\prime}$ is in the
anti-clockwise direction from $p$, but
$\vartheta_{p,p^{\prime}}=-\theta_{p,p^{\prime}}$, otherwise.

Assume that we have exposed $v_{i}$. For any point $p\in\mathcal{D}_{R}$ we
let

$\hat{T}_{\varepsilon}^{-}(p):=\left\\{p^{\prime}\in\mathcal{D}_{R}\ :\
|t_{p^{\prime}}-(1+\delta)t_{p}|<\zeta t_{p},\
\frac{\varepsilon\nu}{N}e^{\frac{t_{p}+t_{p^{\prime}}}{2}}\leq\vartheta_{p^{\prime},p}\leq\frac{2(1-\varepsilon)\nu}{N}e^{\frac{t_{p^{\prime}}+t_{p}}{2}}\right\\}.$

We take $T_{i}:=\hat{T}_{\varepsilon}^{-}(v_{i})$. Let $A$ be the set of
vertices that are located in $\hat{T}_{\varepsilon}^{-}(v_{i})$. Note that, as
the angle covered by $U$ is $o(1)$, we have that
$\mathrm{Area}_{\alpha}(U)=o(\mathrm{Area}_{\alpha}(\mathcal{D}_{R}))$. Hence,
the area of a set in $\mathcal{D}_{R}\setminus U$ is within a $1-o(1)$ factor
from the area in $\mathcal{D}_{R}$ (both on the hyperbolic plane of curvature
$-\alpha^{2}$).

So, for any $\varepsilon\in(0,1/4)$ and for $N$ large enough we have

$\displaystyle\mathbb{E}\left[\,|A|\,\right]$ $\displaystyle\geq
2(1-\frac{3}{2}\varepsilon)\frac{N-2}{2\pi}\int_{(1+\delta-\zeta)t_{v_{i}}}^{(1+\delta+\zeta)t_{v_{i}}}e^{\frac{1}{2}(t_{v_{i}}+t-R)}(1-o(1))e^{-\alpha
t}dt$ $\displaystyle\geq
2(1-\frac{3}{2}\varepsilon)(1-o(1))\frac{N}{2\pi}\frac{\nu}{N}e^{\frac{t_{v_{i}}}{2}}\int_{(1+\delta-\zeta)t_{v_{i}}}^{(1+\delta+\zeta)t_{v_{i}}}e^{(\frac{1}{2}-\alpha)t}dt$
$\displaystyle\stackrel{{\scriptstyle\varepsilon<1/4}}{{\geq}}\frac{\nu}{2\pi}e^{\frac{1}{2}t_{v_{i}}}\frac{1}{2\alpha-1}\left(e^{(\frac{1}{2}-\alpha)(1+\delta-\zeta)t_{v_{i}}}-e^{(\frac{1}{2}-\alpha)(1+\delta+\zeta)t_{v_{i}}}\right).$

But $(1+\delta+\zeta)t_{v_{i}}-(1+\delta)t_{v_{i}}+\zeta t_{v_{i}}>2\zeta
t_{v_{i}}\rightarrow\infty$, whereby the above becomes:

$\displaystyle\mathbb{E}\left[\,|A|\,\right]$
$\displaystyle\geq\frac{\nu}{2\pi}\frac{1}{2\alpha-1}e^{\frac{1}{2}t_{v_{i}}-(\alpha-\frac{1}{2})(1+\delta-\zeta)t_{v_{i}}}(1-o(1)).$

Furthermore,
$(\alpha-\frac{1}{2})(1+\delta)=\frac{2\alpha-1}{2}\frac{1}{2\alpha-1}=\frac{1}{2}$
and finally, we have

$\mathbb{E}\left[\,|A|\,\right]\geq\frac{\nu}{2\pi}\frac{1}{2\alpha-1}e^{(\alpha-\frac{1}{2})\zeta
t_{v_{i}}}(1-o(1))\stackrel{{\scriptstyle
2\alpha-1<1}}{{\geq}}\frac{\nu}{2\pi}e^{(\alpha-\frac{1}{2})\zeta t_{v_{i}}},$

for $N$ large enough. Hence, by Fact 2.3 we have

$\displaystyle\mathbb{P}(|A|>0)$ $\displaystyle=1-\mathbb{P}(|A|=0)$
$\displaystyle\geq 1-\exp\left(-\frac{\nu}{2\pi}e^{(\alpha-\frac{1}{2})\zeta
t_{v_{i}}}\right).$

As $t_{v_{i}}\geq\log\log R$, we have
$\mathbb{P}(|A|=0)\leq\exp\left(-\frac{\nu}{\pi}(\log
R)^{(\alpha-\frac{1}{2})\zeta}\right)$. If $|A|>0$, then there are vertices
that are located inside $T_{i}$ and we let $v_{i+1}$ be one of them – the
choice is arbitrary. The following claim guarantees that
$T_{i+1}=\hat{T}_{\varepsilon}^{-}(v_{i+1})$ is disjoint from $T_{i}$ and when
we repeat the argument there is no danger to expose again area which we have
already exposed.

######  Claim 3.5.

For all $N$ large enough and for all $i\geq 1$ the following holds. For all
$p\in\hat{T}_{\varepsilon}^{-}(v_{i})$ we have
$T_{\varepsilon}^{+}(v_{i})\cap\hat{T}_{\varepsilon}^{-}(p)=\emptyset$.

###### Proof of Claim 3.5.

Consider a point $p\in\hat{T}_{\varepsilon}^{-}(v_{i})$ and let
$p^{\prime}\in\hat{T}_{\varepsilon}^{-}(p)$. We will show that

$\vartheta_{p^{\prime},v_{i}}\gg
2(1+\varepsilon)\frac{\nu}{N}e^{\frac{t_{v}+t_{p^{\prime}}}{2}}.$

We write
$\vartheta_{p^{\prime},v_{i}}=\vartheta_{p^{\prime},p}+\vartheta_{p,v_{i}}$.
Since $p^{\prime}\in\hat{T}_{\varepsilon}^{-}(p)$ and
$p\in\hat{T}_{\varepsilon}^{-}(v_{i})$ we have

$\vartheta_{p^{\prime},p}\geq\varepsilon\frac{\nu}{N}e^{\frac{t_{p^{\prime}}+t_{p}}{2}}\
\mbox{and}\
\vartheta_{p,v_{i}}\geq\varepsilon\frac{\nu}{N}e^{\frac{t_{p}+t_{v_{i}}}{2}}.$

Hence

$\begin{split}\vartheta_{p^{\prime},p}+\vartheta_{p,v_{i}}&\geq\varepsilon\frac{\nu}{N}\left(e^{\frac{t_{p^{\prime}}+t_{p}}{2}}+e^{\frac{t_{p}+t_{v_{i}}}{2}}\right)\\\
&=\varepsilon\frac{\nu}{N}e^{\frac{t_{p^{\prime}}+t_{v_{i}}}{2}}\left(e^{\frac{t_{p}-t_{v_{i}}}{2}}+e^{\frac{t_{p}-t_{p^{\prime}}}{2}}\right)>\varepsilon\frac{\nu}{N}e^{\frac{t_{p^{\prime}}+t_{v_{i}}}{2}}e^{\frac{t_{p}-t_{v_{i}}}{2}}\\\
&\geq\varepsilon\frac{\nu}{N}e^{\frac{t_{p^{\prime}}+t_{v_{i}}}{2}}e^{(\delta-\zeta)t_{v_{i}}}\stackrel{{\scriptstyle(\delta-\zeta)t_{v_{i}}\rightarrow\infty}}{{\gg}}2(1+\varepsilon)\frac{\nu}{N}e^{\frac{t_{p^{\prime}}+t_{v_{i}}}{2}}.\end{split}$

In fact, $(\delta-\zeta)t_{v_{i}}\geq(\delta-\zeta)\log\log R$, and therefore
the inequality holds uniformly for all $N$ that are large enough. ∎

If we start at type at least $\log\log R$, it takes $O(\log R)$ steps to reach
type $\frac{2\alpha-1}{2\alpha}R+\omega(N)$; at that point we can complete the
exploding path using the vertex whose existence is guaranteed by Lemma 3.2.
Thus for any given vertex $v$ with $t_{v}>\log\log R$ we have

$\displaystyle\mathbb{P}(\exists\text{ sequence of vertices $v_{2},\ldots$})$
$\displaystyle=\left(1-\exp\left(-\frac{\nu}{\pi}(\log
R)^{(\alpha-\frac{1}{2})\zeta}\right)\right)^{O(\log R)}$
$\displaystyle=1-O(\log R)\exp\left(-\frac{\nu}{\pi}(\log
R)^{(\alpha-\frac{1}{2})\zeta}\right)$
$\displaystyle=1-\exp\left(-\Theta\left(\log^{(\alpha-\frac{1}{2})\zeta}R\right)\right),$

as $xe^{-ax^{b}}=o(1)$ for $0<a,b$ and $x\rightarrow\infty$.

∎

######  Remark 3.6.

In fact, if the type of $v$ is $O(1)$, that is, $v$ is a typical vertex, then
the probability that there is a $(\delta-\zeta)$-exploding path starting at
$v$ is bounded away from $0$. With slightly more work, one can show that two
vertices $u$ and $v$ have both an exploding path with probability that is
asymptotically bounded away from $0$. Thus, $d_{G}(u,v)<\infty$ with
probability that is asymptotically bounded away from $0$. Alternatively, this
follows from the main theorem in [3], according to which
$\mathcal{G}(N;\alpha,\nu)$ has giant component a.a.s. if $1/2<\alpha<1$.

We are now ready to proceed with the upper bound in Theorem 1.1

###### Proof of Theorem 1.1: upper bound.

Let $u,v$ be two vertices. We will show that the event $d_{G}(u,v)<\infty$ but
$d_{G}(u,v)\geq(2\tau+\zeta^{1/2})\log R$ occurs with probability $o(1)$. Note
that this is in the $\mathcal{G}(N;\alpha,\nu)$ space. Also, for convenience,
we have taken the $\zeta$ that appears in the statement of Theorem 1.1 as
$\zeta^{1/2}$. We denote this event by $\mathcal{E}_{N}(\tau,\zeta)$. Also,
let $\mathcal{A}_{N}$ denote the event that the relative angle between $u$ and
$v$ is greater than $\nu\frac{2\zeta_{\varepsilon}\log R}{N}$, where
$\zeta_{\varepsilon}:=\zeta(1-\varepsilon)$, for some $\varepsilon\in(0,1)$.
Of course, the probability of $\overline{\mathcal{A}_{N}}$ is $o(1)$ and
therefore it suffices to prove that
$\mathbb{P}\left[\,\mathcal{E}_{N}(\tau,\zeta)\cap\mathcal{A}_{N}\,\right]=o(1)$.

If $\mathcal{E}_{N}(\tau,\zeta)$ is realised, then there must be a _minimal_
path between vertices $u$ and $v$. In this context, a minimal path is meant to
be an induced path. Let $P_{\min}$ denote such a path. Assume, in addition,
that $\mathcal{A}_{N}$ is simultaneously realised, that is,
$\theta_{u,v}>\nu\frac{2\zeta_{\varepsilon}\log R}{N}$. With this assumption,
let $P_{\min}(u)$ denote the sub-path of $P_{\min}$ starting at $u$ and ending
at the first vertex whose relative angle with $u$ exceeds
$\nu\frac{\zeta_{\varepsilon}\log R}{N}$. Similarly, let $P_{\min}(v)$ denote
the sub-path of $P_{\min}$ starting at $v$ and ending at the first vertex
whose relative angle with $v$ exceeds $\nu\frac{\zeta_{\varepsilon}\log
R}{N}$. Clearly, as $\mathcal{A}_{N}$ is realized, the two paths may overlap,
but they have at most one edge in common.

Assume without loss of generality that $v$ is at angle $\theta_{u,v}\leq\pi$
in the anti-clockwise direction from $u$. Consider the sectors consisting of
points of relative angle at most $\nu\frac{\zeta_{\varepsilon}\log R}{N}$ from
a point $x$:

$S_{h}^{+}(x):=\left\\{p\in\mathcal{D}_{R}\ :\ t_{p}>\log\log R,\
0<\vartheta_{x,p}<\nu\frac{\zeta_{\varepsilon}\log R}{N}\right\\}$

and

$S_{h}^{-}(x):=\left\\{p\in\mathcal{D}_{R}\ :\ t_{p}>\log\log R,\
-\nu\frac{\zeta_{\varepsilon}\log R}{N}<\vartheta_{x,p}<0\right\\}\text{.}$

There are two cases:

  1. 1.

either each one of $S_{h}^{+}(u),S_{h}^{-}(u),S_{h}^{+}(v),S_{h}^{-}(v)$
contains a vertex that is the starting vertex of a $(\delta-\zeta)$-exploding
path,

  2. 2.

or at least one of them is either empty or all of its vertices are not the
endpoints of a $(\delta-\zeta)$-exploding path.

Let $\mathcal{S}$ denote the former and let $\overline{\mathcal{S}}$ denote
the latter.

$u$$u^{-}$$u^{+}$$u^{\prime}$$u^{\prime\prime}$$S_{h}^{+}(u)$$S_{h}^{-}(u)$$P_{\min}(u)$
Figure 1: Creating a short path into the core under $\mathcal{S}$.

We will show that $\mathbb{P}(\overline{\mathcal{S}})=o(1)$. First consider,
without loss of generality, the set $S_{h}^{+}(u)$. The probability that this
set is empty is $o(1)$. Indeed, let $N_{S_{h}^{+}(u)}$ be the number of
vertices that appear into this sector. Then

$\mathbb{E}\left[\,N_{S_{h}^{+}(u)}\,\right]=N\frac{\cosh(\alpha(R-\log\log
R))-1}{\cosh(\alpha R)-1}~{}\frac{1}{2\pi}~{}\nu\frac{\zeta_{\varepsilon}\log
R}{N}\approx\log^{1-\alpha}R\rightarrow\infty.$

The distribution of $N_{S_{h}^{+}(u)}$ is binomial and the application of a
standard Chernoff bound implies that
$\mathbb{P}\left[\,N_{S_{h}^{+}(u)}=0\,\right]=o(1)$.

If $S_{h}^{+}(u)$ is not empty and all of its vertices are not the beginnings
of a $(\delta-\zeta)$\- exploding path, then the vertex with lowest type in
$S_{h}^{+}(u)$ does not have a $(\delta-\zeta)$-exploding path starting at it
as well. We call this vertex the _first_ vertex in $S_{h}^{+}(u)$.

######  Claim 3.7.

The probability that the first vertex in $S_{h}^{+}(u)$ does not have a
$(\delta-\zeta)$-exploding path starting at it is o(1).

###### Proof of Claim 3.7.

Conditional on having at least one vertex in $S_{h}^{+}(u)$, let $u^{\prime}$
be the first vertex (with probability 1 there will be exactly one such vertex)
which we expose and assume that the area in $S_{h}^{+}(u)$ that consists of
points with type greater than $t_{u^{\prime}}$ has not been exposed. Let us
switch temporarily to $\mathcal{P}_{X,U}(N;\alpha,\nu)$, where
$X={u,u^{\prime}}$ and $U$ the subset of $S_{h}^{+}(u)$ below $u^{\prime}$.
Then by Lemma 3.4, there is a $(\delta-\zeta)$-exploding path starting at
$u^{\prime}$ with probability $1-o(1)$ uniformly over
$t_{u^{\prime}}\geq\log\log R$. This lemma can be applied as the area above
$u^{\prime}$ has not been exposed in the corresponding Poisson process and the
proof of Lemma 3.4 deals only only with that area. The result transfers to
$\mathcal{G}(N;\alpha,\nu)$ (conditional on $U$ being empty and on the
realisations of $u$ and $u^{\prime}$), through Lemma 2.2, due to the fact that
this property is non-decreasing. ∎

Then, since the probability that $S_{h}^{+}(u)$ is empty is $o(1)$, the union
bound implies that $\mathbb{P}\left[\,\overline{\mathcal{S}}\,\right]=o(1)$.

We will show that
$\mathbb{P}\left[\,\mathcal{E}_{N}(\tau,\zeta)\cap\mathcal{A}_{N}\cap\mathcal{S}\,\right]=0$.
Observe that any vertex which belongs to $S_{h}^{+}(u)\cup S_{h}^{-}(u)$ (or
to $S_{h}^{+}(v)\cup S_{h}^{-}(v)$, respectively) will be adjacent to a vertex
in $P_{\min}(u)$ ($P_{\min}(v)$, resp.). Indeed, if $P_{\min}(u)$ contains a
vertex in $S_{h}^{+}(u)\cup S_{h}^{-}(u)$, then this must be adjacent to any
other vertex in $S_{h}^{+}(u)\cup S_{h}^{-}(u)$. This is the case as
$S_{h}^{+}(u)\cup S_{h}^{-}(u)\subseteq T_{\varepsilon}^{-}(u^{\prime})$ for
any $u^{\prime}\in S_{h}^{+}(u)\cup S_{h}^{-}(u)$, provided that $\zeta<1$. To
see this, note that any two points in $S_{h}^{+}(u)\cup S_{h}^{-}(u)$ have
relative angle at most $2\zeta_{\varepsilon}\frac{\nu}{N}$. However, for any
point in $S_{h}^{+}(u)\cup S_{h}^{-}(u)$, its inner tube consists of all
points of relative angle at most $2(1-\varepsilon)\frac{\nu e^{\log\log
R}}{N}$ from it. Thus, if $\zeta_{\varepsilon}<1-\varepsilon$ (that is,
$\zeta<1$), then the containment follows. In this case, some vertex of
$P_{\min}(u)$ will be connected to the first vertex in $S_{h}^{+}(u)\cup
S_{h}^{-}(u)$.

Suppose now that all vertices of $P_{\min}(u)$ do not belong to
$S_{h}^{+}(u)\cup S_{h}^{-}(u)$. Let $u^{+},u^{-}$ be vertices in
$S_{h}^{+}(u)$ and $S_{h}^{-}(u)$ respectively, which are the starting
vertices of $(\delta-\zeta)$-exploding paths $P_{u^{+}}$ and $P_{u^{-}}$.
There are two _consecutive_ vertices in $P_{\min}(u)$ say
$u^{\prime},u^{\prime\prime}$ such that either
$\vartheta_{u^{\prime\prime},u^{+}}>0>\vartheta_{u^{\prime},u^{+}}$ or
$\vartheta_{u^{\prime\prime},u^{-}}>0>\vartheta_{u^{\prime},u^{-}}$. Thus,
either $u^{+}$ or $u^{-}$ is “above” the edge $u^{\prime}u^{\prime\prime}$ and
therefore by Fact 2.4 either $u^{+}$ or $u^{-}$ is adjacent to both
$u^{\prime}u^{\prime\prime}$. The length of any exploding path is at most
$\log R/\log(1+\delta-\zeta)$. Thus, $|P_{u^{+}}|,|P_{u^{-}}|\leq\log
R/\log(1+\delta-\zeta)$. The following bounds the length of
$P_{\min}(u),P_{\min}(v)$:

######  Claim 3.8.

Both $P_{\min}(u)$ and $P_{\min}(v)$ have length at most $\zeta\log R$.

###### Proof of Claim 3.8.

Consider $P_{\min}(u)$ (the proof for $P_{\min}(v)$ is identical). Since
$P_{\min}(u)$ is part of a minimal path, it follows that if we take the set of
vertices of $P_{\min}$ that are at even distance from $u$, then there cannot
be an edge between any two of them, for this would contradict the minimality
of $P_{\min}$. Let $P^{e}_{\min}(u)$ be this set of vertices. For any vertex
$u^{\prime}\in P^{e}_{\min}(u)$ consider the sector
$T(u^{\prime}):=\\{p\in\mathcal{D}_{R}\ :\
\theta_{u^{\prime},p}<(1-\varepsilon){\nu\over N}\\}$. There cannot be
distinct $u^{\prime},u^{\prime\prime}\in P^{e}_{\min}(u)$ such that
$T(u^{\prime})\cap T(u^{\prime\prime})\not=\emptyset$. If this were the case,
then their relative angle would be at most $2(1-\varepsilon){\nu\over N}$ and
by Lemma 2.5 they would be adjacent. But there are at most
$\nu\frac{\zeta_{\varepsilon}\log R}{N}/\left(2(1-\varepsilon){\nu\over
N}\right)=\frac{\zeta}{2}\log R$ such sectors inside the sector of angle
$\nu\frac{\zeta_{\varepsilon}\log R}{N}$ in the anti-clockwise direction from
$u$. Thus $|P^{e}_{\min}(u)|\leq\frac{\zeta}{2}\log R$, whereby the length of
$P_{\min}$ is at most $\zeta\log R$. ∎

Thus

$\begin{split}d_{G}(u,v)&\leq|P_{\min}(u)|+|P_{u^{+}}|+1+|P_{u^{-}}|+|P_{\min}(v)|\\\
&\leq 2\left(\frac{1}{\log(1+\delta-\zeta)}+\zeta+o(1)\right)\log
R\end{split}$

Hence, there exists a $\zeta$ such that for all $N$ large enough
$\frac{1}{\log(1+\delta-\zeta)}+\zeta+o(1)<\tau+\zeta^{1/2}$. This implies
that $\mathcal{E}_{N}(\tau,\zeta)$ is not realised. ∎

######  Remark 3.9.

If we replace the angles that determine the domains $S_{h}^{+}$ and
$S_{h}^{-}$ by a quantity that is proportional to $R^{\frac{1}{1-\alpha}}/N$
and the lower bound on the type by $\frac{1}{2(1-\alpha)}\log R$, then the
probabilities that appear above become $o(N^{-2})$. Thus, the analogous of the
above bound on $d_{G}(u,v)$ holds for all pairs of vertices, and implies that
the diameter is proportional to $R^{\frac{1}{1-\alpha}}$ a.a.s. This upper
bound is worse than the one obtained in [17].

##  4 Proof of Theorem 1.1: lower bound

For given vertices $u,v\in V_{N}$, let $\mathcal{L}_{\zeta,N}(u,v)$ be the
event that $d_{G}(u,v)<(2\tau-\zeta)\log R=:L$, for some $\zeta>0$. Assume
that $t_{u},t_{v}<\log\log R$ \- by Lemma 2.6 this event occurs with
probability $1-o(1)$. Let $\mathcal{T}_{u,v}$ denote this event. By Lemma 2.5,
for any $T\leq R/2-2\log\log R$, if $u$ and $v$ are connected through a path
of length at most $\ell_{u}$ where the intermediate vertices have type at most
$T$, then

$\theta_{u,v}\leq 4\nu\frac{e^{T}}{N}L\leq
4\nu\frac{e^{R/2}}{N}\frac{L}{\log^{2}R}=4\frac{L}{\log^{2}R}.$

Conditional on $\mathcal{T}_{u,v}$, the probability of this event is
$O(L/\log^{2}R)=o(1)$. Now, if there is a path of length at most $L$ that
joins $u$ to $v$ that contains an intermediate vertex of type at least
$R/2-2\log\log R$, then there must be a path of length at most $L/2$ either
from $u$ or from $v$ to this vertex. Denote by $d_{G}(u,core)$ the graph
distance of the vertex $u$ to a vertex of type at least $R/2-2\log\log R$. The
following lemma proves that almost all vertices are, in some sense, far away
from vertices this type, immediately proving the lower bound.

######  Lemma 4.1.

Assume that $t_{u}\leq\log\log R$. For $\zeta>0$, we have

$\mathbb{P}(d_{G}(u,core)\leq(\tau-\zeta^{1/2})\log R)=o(1)\text{.}$

We appeal to Lemma 2.2 on the event $\\{d(u,core)\leq(\tau-\zeta^{1/2})\log
R\\}$. Clearly, this is a non-decreasing event in the sense that is used in
that lemma. So, it suffices to prove Lemma 4.1 in the
$\mathcal{P}_{\\{u\\},\emptyset}(N;\alpha,\nu)$ space.

To prove this statement, we keep track of the highest type in the
neighbourhood of the vertex $u$. Let $N^{(0)}(u)=\\{u\\}$,
$\theta_{r}^{(0)}=\theta_{\ell}^{(0)}=0$. For $i\geq 0$, define $N^{(i)}(u)$
as the neighbours of vertices in $N^{(i-1)}(u)$ that are in clockwise
direction of $u$ and have relative angle greater than $\theta_{\ell}^{(i-1)}$
with $u$ or that are in anticlockwise direction of $u$ and have relative angle
with $u$ greater than $\theta_{r}^{(i-1)}$. Define $\theta_{r}^{(i)}$ as the
maximum relative angle between $u$ and any vertex in $N^{(i)}(u)$ that is in
anticlockwise direction of $u$, setting it to $\theta_{r}^{(i-1)}$ if there is
no such vertex. Similarly, define $\theta_{\ell}^{(i)}$ as the maximum
relative angle between $u$ and any vertex in $N^{(i)}(u)$ that is in clockwise
direction of $u$, setting it to $\theta_{\ell}^{(i-1)}$ if there is no such
vertex. This is the simultaneous breadth exploration process that will be
defined in more detail in the next section.

Note that any vertex in $N^{(i)}(u)$ has graph distance $i$ to $u$, but not
every vertex of distance $i$ is in $N^{(i)}(u)$. However, we claim that the
process cannot leave a vertex that has type larger than the maximum type of
any vertex in $N_{i}(u):=\bigcup_{j=0}^{i}N^{(j)}(u)$ and is within the
sectors exposed undiscovered. For the sake of contradiction, assume that $v$
is a vertex whose type is larger than the types of all vertices discovered in
$N_{i}(u)$, but its angle with $u$ satisfies
$\theta_{r}^{(k-1)}<\vartheta_{u,v}\leq\theta_{r}^{(k)}$, for some $1\leq
k\leq i$. Then there are two vertices $v_{k-1}\in N^{(k-1)}(u)$ and $v_{k}\in
N^{(k)}$ such that $v$ is between them; that is,
$\vartheta_{v,v_{k-1}}<0\leq\vartheta_{v,v_{k}}$. But the following holds (the
second part will be used in the next section).

######  Claim 4.2.

Consider three vertices $z,y$ and $w$, on $\mathcal{D}_{R}$ (in the hyperbolic
plane with curvature $-1$), such that $d_{H}(z,w)<R$ and $w$ is at the
anticlockwise direction of $z$ whereas $y$ is between $z$ and $w$. If
$t_{y}>t_{w}$, then $d_{H}(y,z)<R$. Also, if $t_{y}>t_{z}$, then
$d_{H}(y,w)<R$.

###### Proof of Claim 4.2.

This is the case as the point $y^{\prime}$ of type equal to that of $y$ with
$\theta_{y^{\prime}w}=0$ is still at distance less than $R$ from $z$. If we
move this clockwise towards $z$, the distance will remain smaller than $R$, as
$w$ will be at the anticlockwise side of $y^{\prime}$. An analogous argument
shows the second statement. ∎

The first part of the above claim with $v_{k-1},v,v_{k}$ playing the role of
$z,y,w$ implies that $v$ is adjacent to $v_{k-1}$ and therefore should have
been discovered and become a member of $N^{(k)}(u)$.

The above claim has also the following consequence. Denote by $t^{(i-1)}$ the
maximum type of a vertex in $N_{i-1}(u)$. As every vertex in $N^{(i-1)}(u)$ is
further in the anticlockwise or in the clockwise direction, in terms of
relative angle from $u$, than all the vertices in $N_{i-2}(u)$, all vertices
in $N^{(i)}(u)$ are either within (hyperbolic) distance $R$ and in the
clockwise direction of the point $p_{\ell}^{(i-1)}$ of type $t^{(i-1)}$ and of
clockwise relative angle $\theta^{(i-1)}_{\ell}$ to $u$, or within
(hyperbolic) distance $R$ and in the anticlockwise direction of the point
$p_{r}^{(i-1)}$ of type $t^{(i-1)}$ and of clockwise relative angle
$\theta^{(i-1)}_{r}$ to $u$. Thus the highest type of a vertex in $N^{(i)}(u)$
is stochastically dominated from above by the highest type among all vertices
that have hyperbolic distance at most $R$ from a certain point of type
$t^{(i-1)}$ (namely $p_{r}^{(i-1)}$ or $p_{\ell}^{(i-1)}$). Due to this we can
bound the distribution function of $t^{(i)}$ from below using Fact 2.3. Let
$\hat{t}^{(i)}:=(1+\delta+\zeta)^{i}t_{u}$, for any integer $i\geq 0$.

######  Claim 4.3.

For $i\geq 1$, assuming that $\hat{t}^{(i-1)}<\frac{R/2-2\log\log
R}{1+\delta+\zeta}$, we have

$\mathbb{P}(t^{(i)}<(1+\delta+\zeta)\hat{t}^{(i-1)}\ |\
t^{(i-1)}<\hat{t}^{(i-1)})\geq\exp\left(-\frac{2\nu}{(\alpha-1/2)\pi}e^{-(\alpha-1/2)\zeta\hat{t}^{(i-1)}}\right)\text{.}$

###### Proof.

By the assumption of the claim, if $t^{(i-1)}<\hat{t}^{(i-1)}$, then
$t^{(i-1)}<(1/(1+\delta+\zeta))(R/2-2\log\log R)<(2\alpha-1)R/2$. Lemma 2.5
works for types $t$ such that $t+t^{(i-1)}<R-c_{0}$ for a given constant
$c_{0}$, so $t<R-(1/(1+\delta))R/2$ will do. Recall that
$1/(1+\delta)=2\alpha-1$, so $t<R(3/2-\alpha)$ is sufficient. But
$3/2-\alpha>1/(2\alpha)$, and so if we take $\hat{t}=R/(2\alpha)+\omega(N)$,
for some sufficiently slowly growing function $\omega(N)$, we are able to use
Lemma 2.5 for points of type at most $\hat{t}$. The first part of Corollary
2.7 implies that the expected number of vertices of type at least $\hat{t}$ in
$\mathcal{G}_{\\{u\\},\emptyset}(N;\alpha,\nu)$ is $o(1)$.

As discussed above, the event where
$t^{(i)}\leq(1+\delta+\zeta)\hat{t}^{(i-1)}$ has no smaller probability than
the event that a vertex of type $\hat{t}^{(i-1)}$ has no neighbour of type at
least $\hat{t}^{(i)}$. Thus by Fact 2.3 and Lemma 2.5, for $\varepsilon>0$
small enough so that $(1+2\varepsilon)\alpha<1$ we have

$\displaystyle\mathbb{P}\left(t^{(i)}<(1+\delta+\zeta)\hat{t}^{(i-1)}\ |\
t^{(i-1)}<\hat{t}^{(i-1)}\right)$
$\displaystyle\geq\exp\left(-N\int_{(1+\delta+\zeta)\hat{t}^{(i-1)}}^{\hat{t}}\frac{4(1+\varepsilon)}{2\pi}e^{1/2(t+\hat{t}^{(i-1)}-R)}\alpha
e^{-\alpha t}dt+o(1)\right)$
$\displaystyle\geq\exp\left(-\frac{2(1+2\varepsilon)\alpha\nu}{\pi}e^{\frac{\hat{t}^{(i-1)}}{2}}\int_{(1+\delta+\zeta)\hat{t}^{(i-1)}}^{\infty}e^{(1/2-\alpha)t}dt\right)$
$\displaystyle\geq\exp\left(-\frac{2(1+2\varepsilon)\alpha\nu}{\pi}e^{\frac{\hat{t}^{(i-1)}}{2}}\frac{1}{\alpha-1/2}e^{(1/2-\alpha)(1+\delta+\zeta)\hat{t}^{(i-1)}}\right)$
$\displaystyle\geq\exp\left(-\frac{2(1+2\varepsilon)\alpha\nu}{\pi}e^{\frac{\hat{t}^{(i-1)}}{2}}\frac{1}{\alpha-1/2}e^{(-1/2+(1/2-\alpha)\zeta)\hat{t}^{(i-1)}}\right)$
$\displaystyle\geq\exp\left(-\frac{2\nu}{(\alpha-1/2)\pi}e^{-(\alpha-1/2)\zeta\hat{t}^{(i-1)}}\right)\text{,}$

as $(\alpha-1/2)(1+\delta)=1/2$. ∎

We repeatedly apply this bound to bound the distance from the core. Assume
that $t_{u}=\log\log R$. Denote by $\mathcal{U}$ the event that if we explore
as above the neighbours $u$ for every $i<(\tau-\zeta^{1/2})\log R$ we have
$t^{(i)}<\hat{t}^{(i)}$.

######  Claim 4.4.

Assume that $t_{u}=\log\log R$. For $\zeta>0$ small enough (depending on
$\alpha$), the event $\mathcal{U}$ has probability $1-o(1)$ and after the
steps are completed the maximum type reached is less than $R/2-2\log\log R$,
if $N$ is sufficiently large.

###### Proof.

On this event, after executing the $(\tau-\zeta^{1/2})\log R$ steps we have
reached type less than

$\displaystyle(1+\delta+\zeta)^{(\tau-\zeta^{1/2})\log R}\log\log
R=e^{\log(1+\delta+\zeta)(\tau-\zeta)\log R}\log\log R$ $\displaystyle\leq
R^{(\log(1+\delta)+\zeta)(\tau-\zeta^{1/2})}\log\log R$
$\displaystyle=R^{(\tau^{-1}+\zeta)(\tau-\zeta^{1/2})}\log\log R$
$\displaystyle=R^{1-\tau^{-1}\zeta^{1/2}+\tau\zeta-\zeta^{3/2}}\log\log
R=o(R/2-2\log\log R).$

Moreover, we are able to apply Claim 4.3 repeatedly for this number of steps
and deduce that $\mathcal{U}$ has probability

$\displaystyle\mathbb{P}(\mathcal{U})$
$\displaystyle\geq\prod_{i=0}^{(\tau-\zeta^{1/2})\log
R}\exp\left(-\frac{2\nu}{(\alpha-1/2)\pi}e^{-(\alpha-1/2)\zeta(1+\delta+\zeta)^{i}\log\log
R}\right)$ $\displaystyle\geq\prod_{i=0}^{(\tau-\zeta^{1/2})\log
R}\left(1-\frac{2\nu}{(\alpha-1/2)\pi}e^{-(\alpha-1/2)\zeta(1+\delta+\zeta)^{i}\log\log
R}\right)$ $\displaystyle\geq 1-\sum_{i=0}^{(\tau-\zeta^{1/2})\log
R}\frac{2\nu}{(\alpha-1/2)\pi}e^{-(\alpha-1/2)\zeta(1+\delta+\zeta)^{i}\log\log
R}$ $\displaystyle\geq
1-\frac{4\nu}{(\alpha-1/2)\pi}e^{-(\alpha-1/2)\zeta\log\log R}=1-o(1)\text{.}$

∎

###### Proof of Lemma 4.1.

Fact 2.4 implies that increasing the type of a vertex will keep all edges
intact, so any path will stay a path if we increase the type of one of its
vertices. Thus by a simple coupling argument we have that
$\mathbb{P}(d(u,core)\leq d|t_{u})\leq\mathbb{P}(d(u,core)\leq
d|t_{u}^{\prime})$ for $t_{u}\leq t_{u}^{\prime}$. We can thus assume that
$t_{u}=\log\log R$. By Claim 4.4, a.a.s. executing $(\tau-\zeta^{1/2})\log R$
steps yields maximum type that is less than $R/2-2\log\log R$, so

$\mathbb{P}(d(u,core)\leq(\tau-\zeta^{1/2})\log R)=o(1)\text{.}$

∎

##  5 Proof of Theorem 1.2

Here, we consider the case where $\alpha>1$. In this case, the main result in
[3] implies that all components contain at most sublinear number of vertices.
More precisely, we show that a.a.s. all components contain at most
$N^{1/\alpha}$ vertices (up to a poly-logarithmic factor). In fact, there are
many components of polynomial size (as there are many vertices of polynomial
degree which do not belong to the same component).

To prove Theorem 1.2, for any given vertex we explore a path that in some
sense traverses its component. We show that almost all vertices are close to
such a spanning path, which itself is short. This results in short distances
for most pairs of vertices which belong to the same component.

Note that since $\alpha>1$, a.a.s. there is no component whose convex hull
contains the origin. In fact, components are included in a section of the disc
spanning $o(1)$ of all angles. Due to this, it creates no ambiguity to talk of
clockwise and anticlockwise directions in a component.

######  Definition 5.1.

We call a path $P=v_{1},\dots,v_{\ell}$ in a component $C$ a _spanning path_
of $C$ if $v_{1}$ is the vertex of $C$ that is farthest in clockwise and
$v_{\ell}$ is the vertex of $C$ that is farthest in anticlockwise direction.

An _umbrella_ $U$ with root vertex $v$ is a spanning path $P$ of the component
of $v$ together with a path connecting $v$ to $P$. The _size_ of the umbrella
$U$ is the maximum among the distances of $v$ from the two endpoints of the
associated spanning path.

Figure 2: Example of an umbrella.

Note that any vertex in $C$ that is above a spanning path $P$ of $C$ is
directly connected to one of the vertices of $P$ by Fact 2.4. Since there is
no restriction on the length of the paths, if $v$ is on some spanning path
$P$, then $P$ is an umbrella with root $v$.

The following follows immediately as the vertices of a component that are to
the farthest in clockwise and anticlockwise direction are always in a spanning
path:

######  Corollary 5.2.

If $P$ and $P^{\prime}$ are spanning paths of the same component, then $P\cap
P^{\prime}\neq\emptyset$.

This fact allows us to do the following: Given any pair of vertices $u$ and
$v$ in the same component, construct a $u$-$v$-path by traversing the umbrella
$U_{u}$ of $u$ until the first vertex $z$ that is on the umbrella $U_{v}$ of
$v$ is reached. Then $uU_{u}zU_{v}v$ is a path connecting $u$ and $v$. Thus
the following lemma is key to the proof of Theorem 1.2.

######  Lemma 5.3.

Let $\varepsilon>0$. For a vertex $v$ of $\mathcal{G}(N;\alpha,\nu)$, a.a.s.
there is an umbrella for $v$ of size at most $\log^{1+\varepsilon}\log N$.

For the proof of this lemma we define the simultaneous breadth exploration
process starting at a vertex $v$ similar to the one that we introduced in [3].
Here, we keep track of two sets of vertices $V_{\ell}$ and $V_{r}$, which both
start out as $\\{v\\}$. Roughly speaking, we update the two sets adding the
neighbours of the current sets that are located in the clockwise and
anticlockwise direction from the “current” vertices, respectively. If there
are no neighbours that are farther in the clockwise direction of $V_{r}$ and
no neighbours that are farther in the anticlockwise direction of $V_{\ell}$,
then the process stops. We define the process starting at vertex $v$ as the
following steps:

  1. (i)

Let $V_{\ell}^{(0)}=V_{r}^{(0)}=\\{v\\}$ and let $i:=1$.

  2. (ii)

Let $V_{\ell}^{(i)}$ be the set of vertices not in $V_{\ell}^{(i-1)}\cup
V_{r}^{(i-1)}$ that are neighbours of some vertex in $V_{\ell}^{(i-1)}\cup
V_{r}^{(i-1)}$ and are in the clockwise direction of every vertex in
$\bigcup_{j=0}^{i-1}\\{V_{\ell}^{(j)}\cup V_{r}^{(j)}\\}$. We define similarly
the set $V_{r}^{(i)}$ as the set of vertices not in $V_{\ell}^{(i-1)}\cup
V_{r}^{(i-1)}$ that are neighbours of some vertex in $V_{\ell}^{(i-1)}\cup
V_{r}^{(i-1)}$ and are in the anticlockwise direction of every vertex in
$\bigcup_{j=0}^{i-1}\\{V_{\ell}^{(j)}\cup V_{r}^{(j)}\\}$.

  3. (iii)

If $V_{\ell}^{(i)}=\emptyset=V_{r}^{(i)}$, then stop. Otherwise, let $i:=i+1$
and go to step (ii).

We call a repetition of steps (ii) and (iii) a _round_. To prove Lemma 5.3, we
show that this process yields an umbrella and bound the number of steps needed
until completion.

######  Lemma 5.4.

If the simultaneous breadth exploration process starting at a vertex $v$ stops
after $k$ rounds, then there is an umbrella for $v$ that has size at most $k$.

###### Proof.

Let $C(v)$ denote the connected component that $v$ belongs to. Let
$V^{\prime}_{i}=\bigcup_{j=0}^{i}\\{V_{\ell}^{(j)}\cup V_{r}^{(j)}\\}$, that
is, the set of vertices discovered up to round $i$. We denote by
$v_{\ell}^{\prime}$ the vertex in $V_{i}^{\prime}$ with the largest relative
angle with $v$ in the clockwise direction. We let $\theta_{\ell}^{(i)}$ be
this angle and let $t_{\ell}^{(i)}$ be the type of this vertex. Similarly, let
$v_{r}^{\prime}$ be the vertex of $V_{i}^{\prime}$ that is the farthest in the
anticlockwise direction, and let $\theta_{r}^{(i)}$ and $t_{r}^{(i)}$ denote
its angle and type. Note that there is an edge between some vertex $v_{\ell}$
in $V^{\prime}_{i-1}$ to the vertex $v_{\ell}^{\prime}$ in $V_{\ell}^{(i)}$
and also an edge between some vertex $v_{r}\in V^{\prime}_{i-1}$ and the
vertex $v_{r}^{\prime}$.

We now claim that if the process stops at round $k$, then the vertices
$\hat{v}_{r}$ and $\hat{v}_{\ell}$ that are the farthest to the anticlockwise
and clockwise direction of $C(v)$ belong to $V^{\prime}_{k-1}$. Note that
$V_{\ell}^{(k)}=V_{r}^{(k)}=\emptyset$, so $V^{\prime}_{k-1}=V^{\prime}_{k}$.
Assume this is not the case, so without loss of generality $\hat{v}_{r}\notin
V^{\prime}_{k-1}$. As $v$ and $\hat{v}_{r}$ are in the same component, there
is a path $P$ from $v$ to $\hat{v}_{r}$. Let $w$ be the first vertex on $P$
that is outside the range of angles from $\theta_{\ell}^{(k-1)}$ to
$\theta_{r}^{(k-1)}$. Since $\hat{v}_{r}$ is the vertex that is farthest in
the anticlockwise direction and $\hat{v}_{r}\notin V^{\prime}_{k}$ this vertex
must exist. Let $u$ be the predecessor of $w$ on $P$. We cannot have $u\in
V^{\prime}_{k}$ as otherwise $w$, being farther in the clockwise or
anticlockwise direction than any other vertex in $V^{\prime}_{k}$, must also
be in $V^{\prime}_{k}$ by the choice made in step (ii). There exists an $i<k$
and two _adjacent_ vertices $x$ and $y$ such that $x$ has been discovered at
round $i-1$ and $y$ has been discovered at round $i$ and $u$ is between $x$
and $y$. Now, if $t_{u}\geq t_{y}$, then by Claim 4.2 ($x,u,y$ playing the
role of $w,y,z$) it follows that $u$ is adjacent to $x$ as well. If
$t_{u}<t_{y}$, then again Claim 4.2 implies that $y$ is adjacent to $w$.
Hence, in either case $w$ would have been discovered by round $i+1$, whereby
$w\in V_{r}^{(i+1)}\cup V_{\ell}^{i+1}\subseteq V^{\prime}_{k}$; a
contradiction.

So both $\hat{v}_{\ell}$ and $\hat{v}_{r}$ are in $V^{\prime}_{k}$. Note that
every vertex in $V_{\ell}^{(i)}\cup V_{r}^{(i)}$ has a neighbour in
$V_{\ell}^{(i-1)}\cup V_{r}^{(i-1)}$, so we can find a paths $P_{\ell}$ and
$P_{r}$ of length at most $k$ from $\hat{v}_{\ell}$ to $v$ and from
$\hat{v}_{r}$ to $v$, respectively. Together, possibly deleting redundant
subpaths in $v_{\ell}P_{\ell}vP_{r}v_{r}$, we have an umbrella for $v$ of size
at most $k$. ∎

We are now ready to prove Lemma 5.3

###### Proof of Lemma 5.3.

We aim to bound the number of rounds it takes for the simultaneous breadth
exploration process started at some vertex $v$ to stop. By Corollary 2.7, it
would be sufficient to consider a variation of the simultaneous breadth
exploration process where we expose only those vertices that have type at most
$R/(2\alpha)+\omega(N)$, for some slowly growing function
$\omega(N)\rightarrow\infty$. We will use the same notation for the parameters
of the process as in the unmodified process.

Let $T$ denote the stopping time of this process. Without loss of generality,
assume that $V_{\ell}^{(i)},V_{r}^{(i)}\neq\emptyset$ for $i=1,\dots,T-1$.
Define $V^{\prime}_{i}$, $\theta_{\ell}^{(i)}$ and $\theta_{r}^{(i)}$ as in
the previous proof (but for the modified process). Unlike the last proof, let
$t_{\ell}^{(i)}$ and $t_{r}^{(i)}$ be the maximum types of vertices in
$V_{\ell}^{(i)}$ and $V_{r}^{(i)}$, respectively, and they are set to $0$, if
the corresponding set contains no vertices. Let
$t_{i}=\max\\{t_{\ell}^{(i)},t_{r}^{(i)}\\}$. Let $p_{\ell}^{(i)}$ be the
point of type $t_{i}$ and angle $\theta_{\ell}^{(i)}$ in the clockwise
direction from $v$. Similarly, let $p_{r}^{(i)}$ be the point of type $t_{i}$
and angle $\theta_{r}^{(i)}$ in the anticlockwise direction from $v$.

######  Claim 5.5.

We have $V_{\ell}^{(i+1)}\subset T_{\varepsilon}^{+}(p_{\ell}^{(i)})$ and
$V_{r}^{(i+1)}\subset T_{\varepsilon}^{+}(p_{r}^{(i)})$.

###### Proof of Claim 5.5.

Let $p$ be a point that is within hyperbolic distance $R$ from $u\in
V_{\ell}^{(i)}\cup V_{r}^{(i)}$ and satisfies
$\vartheta_{p,v}>\theta_{\ell}^{(i)}$. Let $u^{\prime}$ be the point of type
$t_{\ell}^{(i)}$, which has $\theta_{u,u^{\prime}}=0$.

Note that $\vartheta_{p,p_{\ell}^{(i)}}\leq\vartheta_{p,u}$. Since $p\in
T_{\varepsilon}^{+}(u)$, we have $\vartheta_{p,u}\leq
2(1+\varepsilon)\frac{\nu}{N}e^{\frac{t_{p}+t_{u}}{2}}$. As $t_{u}\leq
t_{u^{\prime}}=t_{\ell}^{(i)}$, it follows that $\vartheta_{p,u}\leq
2(1+\varepsilon)\frac{\nu}{N}e^{\frac{t_{p}+t_{\ell}^{(i)}}{2}}$. In other
words, $p\in T_{\varepsilon}^{+}(p_{\ell}^{(i)})$. Thereby,
$V_{\ell}^{(i+1)}\subset T_{\varepsilon}^{+}(p_{\ell}^{(i)})$.

The proof that $V_{r}^{(i+1)}\subset T_{\varepsilon}^{+}(p_{r}^{(i)})$ is
analogous. ∎

The above claim implies that the highest type of a vertex in
$V_{\ell}^{(i+1)}$, which we denoted by $t_{\ell}^{(i)}$, is stochastically
dominated by the highest type among the vertices in $\left\\{p\in
T_{\varepsilon}^{+}(p_{\ell}^{(i)})\ :\ \vartheta_{p,p_{\ell}^{(i)}}>0,\
t_{p}<R/(2\alpha)+\omega(N)\right\\}$ . Similarly, the highest type of a
vertex in $V_{r}^{(i+1)}$, which we denoted by $t_{r}^{(i)}$ is stochastically
dominated by the highest type among the vertices in $\left\\{p\in
T_{\varepsilon}^{+}(p_{r}^{(i)})\ :\ \vartheta_{p,p_{r}^{(i)}}<0,\
t_{p}<R/(2\alpha)+\omega(N)\right\\}$ . Let $T_{\ell}(p_{\ell}^{(i)})$ and
$T_{r}(p_{r}^{(i)})$ denote these two sets.

Thus, $t_{i+1}$ is stochastically bounded from above by the largest type in
$T_{\ell}(p_{\ell}^{(i)})\cup T_{r}(p_{r}^{(i)})$. In turn, this is
stochastically bounded from above by the maximum type of a vertex in
$T_{\ell}(p^{(i)})\cup T_{r}(p^{(i)})$ for a point $p^{(i)}$ of type
$t_{i}=\max\\{t_{\ell}^{(i)},t_{r}^{(i)}\\}$. We shall proceed with the
estimation of the cdf of the latter random variable.

Observe first that Claim 5.5 implies that for all $0<i\leq T$ we have
$V_{i}^{\prime}\subset\bigcup_{j=0}^{i-1}\\{T_{\varepsilon}^{+}(p_{\ell}^{(j)})\cup
T_{\varepsilon}^{+}(p_{r}^{(j)})\\}$, assuming that
$p_{\ell}^{(0)},p_{r}^{(0)}$ are both set to the point of $\mathcal{D}_{R}$
where $v$ is located. Let $\mathcal{N}_{i}$ be the set of vertices that belong
to $V_{i}^{\prime}$. For a vertex $u\in V_{N}\setminus V_{i}^{\prime}$, the
distribution on $\mathcal{D}_{R}$ is uniform (within the plane of curvature
$-\alpha^{2}$) on the subset of $\mathcal{D}_{R}$ that excludes the union of
the balls of radius $R$ around each vertex in $V_{i}^{\prime}$. Recall that
$\mathrm{Area}_{\alpha}(\cdot)$ denotes the area of a measurable subset of
$\mathcal{D}_{R}$ on the hyperbolic plane of curvature $-\alpha^{2}$. By Lemma
2.5 and the above observation, the area of the latter is at most
$\sum_{j=0}^{i-1}\mathrm{Area}_{\alpha}(T_{\varepsilon}^{+}(p_{\ell}^{(j)})\cup
T_{\varepsilon}^{+}(p_{r}^{(j)}))$. But for each $j$, the angle that is
spanned by $T_{\varepsilon}^{+}(p_{\ell}^{(j)})\cup
T_{\varepsilon}^{+}(p_{r}^{(j)})$ is proportional to
$e^{R/(2\alpha)-R+\omega(N)}=o(1)$. Thus, if $i<R$, then we have
$\sum_{j=0}^{i-1}\mathrm{Area}_{\alpha}(T_{\varepsilon}^{+}(p_{\ell}^{(j)})\cup
T_{\varepsilon}^{+}(p_{r}^{(j)}))=o(\mathrm{Area}_{\alpha}(\mathcal{D}_{R}))$.

Using this, we conclude that the conditional probability that a vertex $u\in
V_{N}\setminus\mathcal{N}_{i}$ belongs to $T_{\varepsilon}^{+}(p^{(i)})$ and
has type $t_{u}$ that satisfies $t\leq t_{u}<R/(2\alpha)+\omega(N)$ is at most

$\begin{split}&\int_{t}^{\frac{R}{2\alpha}+\omega(N)}\frac{4(1+\varepsilon)}{2\pi}e^{\frac{t_{i}+t^{\prime}-R}{2}}\frac{\alpha\sinh(\alpha(R-t^{\prime}))}{\cosh(\alpha
R)(1-o(1))}dt^{\prime}\\\
&\leq\frac{2\alpha(1+2\varepsilon)}{\pi}e^{\frac{t_{i}-R}{2}}\int_{t}^{\frac{R}{2\alpha}+\omega(N)}e^{t^{\prime}/2}\frac{e^{\alpha(R-t^{\prime})}}{2\cosh(\alpha
R)(1-o(1))}dt^{\prime}\\\
&\leq\frac{2\alpha(1+3\varepsilon)}{\pi}e^{\frac{t_{i}-R}{2}}\int_{t}^{\frac{R}{2\alpha}+\omega(N)}e^{\left(\frac{1}{2}-\alpha\right)t^{\prime}}dt^{\prime}\\\
&=\frac{2\alpha\nu(1+3\varepsilon)}{\pi}\frac{e^{t_{i}/2}}{N}\int_{t}^{\frac{R}{2\alpha}+\omega(N)}e^{\left(\frac{1}{2}-\alpha\right)t^{\prime}}dt^{\prime}<\frac{4\alpha\nu(1+3\varepsilon)}{\pi(2\alpha-1)}\frac{e^{t_{i}/2}}{N}e^{\left(\frac{1}{2}-\alpha\right)t},\end{split}$

for $N$ sufficiently large. Therefrom, the conditional probability that _none_
of the vertices in $V_{N}\setminus\mathcal{N}_{i}$ satisfies this is at least

$\begin{split}&\left(1-\frac{4\alpha\nu(1+3\varepsilon)}{\pi(2\alpha-1)}\frac{e^{t_{i}/2}}{N}e^{\left(\frac{1}{2}-\alpha\right)t}\right)^{|V_{N}\setminus\mathcal{N}_{i}|}>\left(1-\frac{4\alpha\nu(1+3\varepsilon)}{\pi(2\alpha-1)}\frac{e^{t_{i}}/2}{N}e^{\left(\frac{1}{2}-\alpha\right)t}\right)^{N}\\\
&>\exp\left(-D_{\alpha,\nu,\varepsilon}e^{\frac{t_{i}}{2}-(\alpha-1/2)t}\right),\end{split}$
(5.1)

for some $D_{\alpha,\nu,\varepsilon}>0$ and any $N$ sufficiently large.

Therefore, for $i<R$ the random variable
$\max\\{t_{\ell}^{(i+1)},t_{r}^{(i+1)}\\}$ conditional on the history of the
process up to step $i$ is stochastically dominated by a random variable that
follows the Gumbel distribution. The expectation of the latter is

$\frac{t_{i}+2\ln(2D_{\alpha,\nu,\varepsilon})}{2\alpha-1}+\frac{2\gamma}{2\alpha-1},$

where $\gamma$ is Euler’s constant. Therefore, the following inequality holds:

$\mathbb{E}\left[\,t_{i+1}|\mathcal{F}_{i}\,\right]\leq\frac{t_{i}+2\ln(2D_{\alpha,\nu,\varepsilon})}{2\alpha-1}+\frac{2\gamma}{2\alpha-1},$

where $\mathcal{F}_{i}$ denotes the sub-$\sigma$-algebra generated by the
process up to step $i$. There exists a constant $U_{\alpha,\nu,\varepsilon}>0$
such that when $t_{i}>U_{\alpha,\nu,\varepsilon}$, we have

$\mathbb{E}\left[\,t_{i+1}|\mathcal{F}_{i}\,\right]\leq\frac{t_{i}+2\ln(2D_{\alpha,\nu,\varepsilon})}{2\alpha-1}+\frac{2\gamma}{2\alpha-1}<\frac{\alpha}{2\alpha-1}t_{i}=:\lambda_{\alpha}t_{i}<t_{i}.$
(5.2)

On the other hand, (5.1) implies that if $t_{i}\leq
U_{\alpha,\nu,\varepsilon}$, then

$\mathbb{P}(t_{i+1}=0)\geq p>0,$ (5.3)

for some positive constant $p$.

With these tools, we can bound the stopping time $T$ of the process. Let
$[T_{1}^{(s)},T_{2}^{(s)}\wedge R]$ denote the $s$th interval of indices in
which the process stays above $U_{\alpha,\nu,\varepsilon}$. By (5.2), for
$T_{1}^{(s)}<i\leq T_{2}^{(s)}\wedge R$ the process $(t_{i})$ is a
supermartingale with decay rate at most $\lambda_{\alpha}$.

######  Claim 5.6.

For any $\varepsilon^{\prime}>0$

$\mathbb{P}((T_{2}^{(s)}\wedge
R)-T_{1}^{(s)}\geq\log_{1/\lambda_{\alpha}}^{1+\varepsilon^{\prime}}R)=o(1).$

###### Proof of Claim 5.6.

Let $S:=\log_{1/\lambda_{\alpha}}^{1+\varepsilon^{\prime}}R$ and let
$T^{(s)}:=T_{2}^{(s)}\wedge R$. Note that $\mathbb{E}\left[\,t_{i\wedge
T^{(s)}}\mid\mathcal{F}_{T_{1}^{(s)}}\,\right]\leq\lambda_{\alpha}^{i\wedge
T^{(s)}-T_{1}^{(s)}}t_{T_{1}^{(s)}}\leq\lambda_{\alpha}^{i\wedge
T^{(s)}-T_{1}^{(s)}}R$. Let $A$ be the event $\\{T^{(s)}>S+T_{1}^{(s)}\\}$. If
$\omega\in A$, then $\lambda_{\alpha}^{(S+T_{1}^{(s)}(\omega))\wedge
T^{(s)}(\omega)-T_{1}^{(s)}}t_{T_{1}^{(s)}}(\omega)<\lambda_{\alpha}^{S}R=o(1)$.
By the definition of the conditional expectation, we deduce that
$\mathbb{E}\left[\,t_{(S+T_{1}^{(s)})\wedge
T^{(s)}}\mathbf{1}_{A}\,\right]=o(1)$ and since
$\mathbb{E}\left[\,t_{(S+T_{1}^{(s)})\wedge
T^{(s)}}\mathbf{1}_{A}\,\right]>U_{\alpha,\nu,\varepsilon}\mathbb{P}(A)$, we
finally deduce that $\mathbb{P}(A)=o(1)$. ∎

Now, the length of the (discrete) interval $(T_{2}^{(s)},T_{1}^{(s+1)}\wedge
T\wedge R)$ is stochastically bounded from above by a geometric random
variable that has parameter at least $p$.

We call the union of these intervals an _epoch_ , that is, we call an epoch
the interval $[T_{1}^{(s)},T_{1}^{(s+1)}\wedge T\wedge R)$, for some $s>0$. By
the above claim, for any $\varepsilon^{\prime}>0$, with probability $1-o(1)$,
we have $(T_{2}^{(s)}\wedge
R)-T_{1}^{(s)}\leq\log_{1/\lambda_{\alpha}}^{1+\varepsilon^{\prime}}R$.
Additionally, the stochastic upper bound on the interval
$(T_{2}^{(s)},T_{1}^{(s+1)})$ implies that this is at most
$\log_{1/\lambda_{\alpha}}^{\varepsilon^{\prime}}R$ with probability $1-o(1)$.
Hence, with probability $1-o(1)$ an epoch lasts for at most
$\log_{1/\lambda_{\alpha}}^{1+2\varepsilon^{\prime}}R$ steps. Finally, since
every epoch has probability at least $p$ to be the final one, it follows that
the process hits $0$ within
$\log_{1/\lambda_{\alpha}}^{1+3\varepsilon^{\prime}}R$ steps with probability
$1-o(1)$. In other words, a.a.s. we have
$T\leq\log_{1/\lambda_{\alpha}}^{1+3\varepsilon^{\prime}}R$.

∎

Using the previous lemmas we prove Theorem 1.2.

###### Proof of Theorem 1.2.

Let $0<\varepsilon^{\prime}<\varepsilon$. Let $V^{\prime}$ be the set of
vertices in $\mathcal{G}(N;\alpha,\nu)$ that have an umbrella of size at most
$\log^{1+\varepsilon^{\prime}}\log N$. By Lemma 5.3 we have
$|V^{\prime}|=(1-o(1))N$ a.a.s. For any $u,v\in V^{\prime}$, if they are in
the same component, by Corollary 5.2 the umbrellas are not disjoint. Thus
there is a $u$-$v$-path of length at most $|U_{u}|+|U_{v}|\leq
2\log^{1+\varepsilon^{\prime}}\log N<\log^{1+\varepsilon}\log N$ for $N$ large
enough. ∎

## References

  * [1] R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, _Reviews of Modern Physics_ 74 (2002), 47–97.
  * [2] A.-L. Barabási and R. Albert, Emergence of scaling in random networks, _Science_ 286 (1999), 509–512.
  * [3] M. Bode, N. Fountoulakis and T. Müller, On the geometrization of the Chung-Lu model and its component structure, preprint, 48 pages.
  * [4] B. Bollobás, _Random graphs_ , Cambridge University Press, 2001, xviii+498 pages.
  * [5] B. Bollobás, S. Janson and O. Riordan, The phase transition in inhomogeneous random graphs, _Random Structures and Algorithms_ 31 (2007), 3–122.
  * [6] B. Bollobás and O. Riordan, The diameter of a scale-free random graph, _Combinatorica_ 24 (2004), 5–34.
  * [7] B. Bollobás, O. Riordan, J. Spencer and G. Tusnády, The degree sequence of a scale-free random graph process, _Random Structures and Algorithms_ 18 (2001), 279–290.
  * [8] R. Cohen and S. Havlin, Scale-free networks are ultrasmall, _Physical Review Letters_ 90 (2003), 058701\.
  * [9] S. Dereich, C. Mönch and P. Mörters, Typical distances in ultrasmall random networks, _Advances in Applied Probability_ 44 (2012), 583–601.
  * [10] S. N. Dorogovtsev, _Lectures on Complex Networks_ , Oxford University Press, 2010, xi+134 pages.
  * [11] S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, Metric structure of random networks, _Nuclear Physics B_ 653 (2003), 307–338.
  * [12] F. Chung and L. Lu, The average distances in random graphs with given expected degrees, _Proc. Natl. Acad. Sci. USA_ 99 (2002), 15879–15882.
  * [13] F. Chung and L. Lu, Connected components in random graphs with given expected degree sequences, _Annals of Combinatorics_ 6 (2002), 125–145.
  * [14] F. Chung and L. Lu, _Complex Graphs and Networks_ , AMS, 2006.
  * [15] S. Dommers, R. van der Hofstad and G. Hooghiemstra, Diameters in preferential attachment models, _Journal of Statistical Physics_ 139 (2010), 72–107.
  * [16] N. Fountoulakis, On a geometrization of the Chung-Lu model for complex networks, _Journal of Complex Networks_ , to appear.
  * [17] T. Friedrich and A. Krohmer, On the diameter of hyperbolic random graphs, In _Prooceedings of the 42nd International Colloquium on Automata, Languages and Programming_ , 2015, to appear.
  * [18] L. Gugelmann, K. Panagiotou and U. Peter, Random hyperbolic graphs: degree sequence and clustering, In _Proceedings of the 39th International Colloquium on Automata, Languages and Programming (A. Czumaj et al. Eds.)_ , Lecture Notes in Computer Science 7392, 2012, pp. 573–585.
  * [19] R. van der Hofstad, _Random Graphs and Complex Networks_ , preprint available at http://www.win.tue.nl/$\sim$rhofstad/.
  * [20] R. van der Hofstad and G. Hooghiemstra, Universality for distances in power-law random graphs, _Journal of Mathematical Physics_ 49 (2008), 125209.
  * [21] R. van der Hofstad, G. Hooghiemstra and D. Znamenski, Distances in random graphs with finite mean and infinite variance degrees, _Electronic Journal of Probability_ 12 (2007), 703–766.
  * [22] S. Janson, T. Łuczak and A. Ruciński, _Random Graphs_ , Wiley, New York, 2000.
  * [23] J. F. C. Kingman, _Poisson processes_ , Oxford University Press, New York, 1993.
  * [24] M. Kiwi and D. Mitsche, A bound on the diameter of random hyperbolic graphs, In _Proceedings of 12th workshop on analytic algorithmics and combinatorics (ANALCO)_ , 2015, pp. 26–39.
  * [25] D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat and M. Boguñá, Hyperbolic Geometry of Complex Networks, _Phys. Rev. E_ 82 (2010), 036106.
  * [26] S. Milgram, The small-world problem, _Psychology Today_ 2 (1967), 60–67.
  * [27] I. Noros and H. Reittu, On a conditionally Poissonian graph process, _Advances in Applied Probability_ 38 (2006), 59–75.
  * [28] B. Söderberg, General formalism for inhomogeneous random graphs, _Phys. Rev. E_ 66(3) (2002), 066121.
  * [29] J. Stillwell, _Geometry of Surfaces_ , Springer, 1992.
  * [30] D.J. Watts and S.H. Strogatz, Collective dynamics of “small-world” networks, _Nature_ 393 (1998), 440–442.
  * [31] http://www.bbc.co.uk/news/technology-15844230.