PHYSICAL REVIEW E
109
, 054131 (2024)
Random hyperbolic graphs in
d
+
1 dimensions
Gabriel Budel
,
1
,
*
Maksim Kitsak
,
1
Rodrigo Aldecoa
,
2
,
3
Konstantin Zuev
,
4
and Dmitri Krioukov
5
,
3
1
Faculty of Electrical Engineering, Mathematics and Computer Science,
Delft University of Technology
, 2628 CD, Delft, the Netherlands
2
Department of Physics,
Northeastern University
, Boston, Massachusetts 02115, USA
3
Network Science Institute,
Northeastern University
, Boston, Massachusetts 02115, USA
4
Department of Computing and Mathematical Sciences,
California Institute of Technology
, Pasadena, California 91125, USA
5
Department of Physics, Department of Mathematics, Department of Electrical & Computer Engineering,
Northeastern University
, Boston, Massachusetts 02115, USA
(Received 4 March 2024; accepted 23 April 2024; published 30 May 2024)
We consider random hyperbolic graphs in hyperbolic spaces of any dimension
d
+
1
2. We present a
rescaling of model parameters that casts the random hyperbolic graph model of any dimension to a unified
mathematical framework, leaving the degree distribution invariant with respect to the dimension. Unlike the
degree distribution, clustering does depend on the dimension, decreasing to 0 at
d
→∞
. We analyze all of the
other limiting regimes of the model, and we release a software package that generates random hyperbolic graphs
and their limits in hyperbolic spaces of any dimension.
DOI:
10.1103/PhysRevE.109.054131
I. INTRODUCTION
Random hyperbolic graphs (RHGs) [
1
,
2
] are a latent space
network model [
3
,
4
], in which the latent space is the hyper-
bolic plane
H
2
: nodes are random points on the plane, while
connections between nodes are established with distance-
dependent probabilities. RHGs reproduce many structural
properties of real networks, including sparsity, self-similarity,
power-law degree distribution, strong clustering, small world-
ness, and community structure [
2
,
5
–
8
]. They are also expo-
nential random graphs with just two sufficient statistics—the
number of links and the sum of their hyperbolic lengths [
9
].
Using the RHG as a null model, one can map real networks to
hyperbolic spaces [
10
–
12
], the applications of which include
routing and navigation [
10
,
13
–
18
], link prediction [
11
,
19
–
25
], network scaling [
5
,
8
,
17
], semantic analysis [
26
–
29
], in-
ference of shortest paths [
30
], and many others [
31
].
While two-dimensional RHGs have been studied exten-
sively in the literature, their higher-dimensional generaliza-
tions have not received a lot of attention. Here, we aim to fill
this gap by offering a systematic analysis of the RHG model in
a hyperbolic space
H
d
+
1
of arbitrary dimensionality
d
+
1
2.
Apart from purely academic interest, our work is inspired
by several practical questions. Hyperbolic spaces expand ex-
ponentially for any dimension
d
+
1
2. Thus, intuitively,
RHGs should have similar topological properties regardless
of the dimensionality of their latent hyperbolic spaces. We aim
to verify this intuition here. Second, the dimensionality of the
latent space has been shown to affect the accuracy of graph
embedding tasks [
32
]. Finally, a recent study suggests that the
dimensionality of the hyperbolic space allows one to generate
more realistic and diverse community structures [
33
].
*
Corresponding author: gabybudel@gmail.com
Spatial graphs in hyperbolic spaces comprise an area of
active research, and many results were obtained recently.
RHGs are equivalent to geometric inhomogeneous random
graphs (GIRGs), as mentioned in [
2
] and formalized in [
34
].
This GIRG formulation is followed in [
9
,
35
–
37
], where the
small-world, clustering, and other properties of GIRGs are
analyzed for any dimension
d
. The work by Yang and Rideout
[
38
] contains rigorous mathematical proofs for degree distri-
butions and degree correlations of the high-dimensional RHG
model. The related popularity-similarity optimization (PSO)
model has recently been extended to arbitrary dimensionality
d
+
1
2in[
39
]. Whereas RHGs are a static network model,
the (
d
+
1)-dimensional PSO model is a growing network
model in hyperbolic space that possesses similar structural
properties.
Here, we conduct a systematic analysis of the structural
properties of RHGs and their limiting regimes. In Sec.
II
,
we define the RHG model in hyperbolic spaces
H
d
+
1
of any
dimension
d
+
1
2. We present a rescaling of the model
parameters that renders the degree distribution invariant with
respect to
d
, Sec.
III
, focusing on the three connectivity
regimes—cold, critical, and hot—in the model, Sec.
IV
.
In Sec.
V
, we analyze the limiting regimes of the model when
its parameters tend to their extreme values. These regimes
are Erd
̋
os-Rényi random graphs, the configuration model, and
(soft) random geometric graphs on spheres. Section
VI
intro-
duces our software package that generates RHGs and their
limits for any
d
, generalizing the
d
=
1 generator in [
40
]. The
concluding remarks are in Sec.
VII
.
II. RANDOM HYPERBOLIC GRAPH MODEL
IN
d
+
1 DIMENSIONS
A random hyperbolic graph (RHG) in the (
d
+
1)-
dimensional hyperbolic space
H
d
+
1
is defined as follows.
Every node
i
of the RHG corresponds to a point
x
i
in
H
d
+
1
. Points are selected uniformly at random with a pdf
2470-0045/2024/109(5)/054131(17)
054131-1
©2024 American Physical Society
GABRIEL BUDEL
et al.
PHYSICAL REVIEW E
109
, 054131 (2024)
ρ
(
x
), which is prescribed by the model. Connections be-
tween node pairs in the RHG are established with independent
probabilities
p
:
R
+
→
[0
,
1] that are functions of the dis-
tances in
H
d
+
1
. The probability
p
ij
of a link between nodes
i
and
j
is
p
ij
=
p
(
d
H
d
+
1
(
x
i
,
x
j
)
)
, where
d
H
d
+
1
(
x
i
,
x
j
)isthe
distance between points
x
i
and
x
j
in
H
d
+
1
.
The RHG model, as a result, is fully defined by its latent
space
H
d
+
1
, node pdf
ρ
(
x
), and the connection probability
function
p
(
d
).
To justify our choices for
ρ
(
x
) and
p
(
d
), we first recall
the definition of the
d
-dimensional hyperbolic space and its
basic geometric properties. To this end, we consider the upper
sheet of the (
d
+
1)-dimensional hyperboloid of curvature
K
=−
ζ
2
,
x
2
0
−
x
2
1
−···−
x
2
d
+
1
=
1
ζ
2
,
x
0
>
0
,
(1)
in the (
d
+
2)-dimensional Minkowski space with metric
d
s
2
=−
d
x
2
0
+
d
x
2
1
+···+
d
x
2
d
+
1
.
(2)
The spherical coordinate system on the hyperboloid
(
r
,θ
1
,...,θ
d
) is defined by
x
0
=
1
ζ
cosh
ζ
r
,
x
1
=
1
ζ
sinh
ζ
r
cos
θ
1
,
x
2
=
1
ζ
sinh
ζ
r
sin
θ
1
cos
θ
2
,
.
.
.
x
d
=
1
ζ
sinh
ζ
r
sin
θ
1
···
sin
θ
d
−
1
cos
θ
d
,
x
d
+
1
=
1
ζ
sinh
ζ
r
sin
θ
1
···
sin
θ
d
−
1
sin
θ
d
,
(3)
where
r
>
0 is the radial coordinate, and (
θ
1
,...,θ
d
)are
the standard angular coordinates on the unit
d
-dimensional
sphere
S
d
.
The coordinate transformation in (
3
) yields the spheri-
cal coordinate metric in the (
d
+
1)-dimensional hyperbolic
space
H
d
+
1
,
d
s
2
=
d
r
2
+
1
ζ
2
sinh
2
(
ζ
r
)
d
2
d
,
(4)
d
2
d
=
d
θ
2
1
+
sin
2
(
θ
1
)d
θ
2
2
+···
+
sin
2
(
θ
1
)
···
sin
2
(
θ
d
−
1
)d
θ
2
d
,
(5)
resulting in the volume element in
H
d
+
1
:
d
V
=
(
1
ζ
sinh
ζ
r
)
d
d
r
d
∏
k
=
1
sin
d
−
k
(
θ
k
)d
θ
k
.
(6)
The distance between two points
i
and
j
in
H
d
+
1
is given
by the hyperbolic law of cosines:
cosh
ζ
d
ij
=
cosh
ζ
r
i
cosh
ζ
r
j
−
sinh
ζ
r
i
sinh
ζ
r
j
cos
θ
ij
,
(7)
where
θ
ij
is the angle between
i
and
j
:
cos(
θ
ij
)
=
cos
θ
i
,
1
cos
θ
j
,
1
+
sin
θ
i
,
1
sin
θ
j
,
1
cos
θ
i
,
2
cos
θ
j
,
2
+···
+
sin
θ
i
,
1
sin
θ
j
,
1
···
sin
θ
i
,
d
−
1
sin
θ
j
,
d
−
1
cos
θ
i
,
d
cos
θ
j
,
d
+
sin
θ
i
,
1
sin
θ
j
,
1
···
sin
θ
i
,
d
−
1
sin
θ
j
,
d
−
1
sin
θ
i
,
d
sin
θ
j
,
d
,
(8)
where (
θ
i
,
1
,...,θ
i
,
d
) and (
θ
j
,
1
,...,θ
j
,
d
) are the coordinates
of the points
i
and
j
on
S
d
.
For sufficiently large
ζ
r
i
and
ζ
r
j
values, the hyperbolic law
of cosines in Eq. (
7
) is closely approximated by
d
ij
≈
r
i
+
r
j
+
2
ζ
ln[sin(
θ
ij
/
2)]
.
(9)
The hyperbolic ball
B
d
+
1
of radius
R
>
0 is defined as the
set of points with
r
∈
[0
,
R
]
.
(10)
Nodes of the RHG are points in
B
d
+
1
selected at random
with density
ρ
x
(
x
)
≡
ρ
r
(
r
)
ρ
θ
1
(
θ
1
)
···
ρ
θ
d
(
θ
d
), where
ρ
r
(
r
)
=
[
sinh(
α
r
)
]
d
/
C
d
,α
ζ/
2
,
(11a)
C
d
≡
∫
R
0
[sinh(
α
r
)]
d
d
r
,
(11b)
ρ
θ
k
(
θ
k
)
=
[sin(
θ
k
)]
d
−
k
/
I
d
,
k
,
k
=
1
,...,
d
,
(11c)
I
d
,
k
≡
∫
π
0
[
sin(
θ
k
)
]
d
−
k
d
θ
k
=
√
π
[
d
−
k
+
1
2
]
[
1
+
d
−
k
2
]
,
k
<
d
,
(11d)
I
d
,
d
≡
2
π.
(11e)
In other words, nodes are uniformly distributed on unit sphere
S
d
with respect to their angular coordinates. In the special
case of
α
=
ζ
, nodes are also uniformly distributed in
B
d
+
1
.
Pairs of nodes
i
and
j
are connected independently with
connection probability
p
ij
=
p
(
d
ij
)
=
1
1
+
exp[
ζ
(
d
ij
−
μ
)
/
2
T
]
,
(12)
where
μ>
0 and
T
>
0 are model parameters, and
d
ij
is the
distance between points
i
and
j
in
B
d
+
1
, given by Eq. (
7
).
We refer to parameters
T
and
μ
as the temperature and the
chemical potential, respectively, using the analogy with the
Fermi-Dirac statistics. We note that the factors of 2 and
ζ
in
054131-2
RANDOM HYPERBOLIC GRAPHS IN
d
+
1 DIMENSIONS
PHYSICAL REVIEW E
109
, 054131 (2024)
3
,
1
,
2
RHG
1
1
2
2
3
1
2
3
<
>
FIG. 1. A visualization of an RHG for
d
=
2in
B
3
. The spherical
coordinates (
r
,θ
1
,θ
2
) of a point in
B
3
are shown. A subgraph of
three nodes is shown with geodesics between the nodes. Node pairs
(1,2) and (2,3) are connected with high probability because
d
12
<
R
and
d
23
<
R
(green), while node pair (1,3) is disconnected with high
probability because
d
23
>
R
(red).
Eq. (
12
) are to agree with the two-dimensional RHG [
2
] that
corresponds to
d
=
1.
Thus, the RHG is formed in a three-step network
generation process:
(i) Randomly select
n
points in
B
d
+
1
with pdf
ρ
x
(
x
)
in Eq. (
11
).
(ii) Calculate distances in
B
d
+
1
between all node pairs
i
-
j
using Eq. (
7
).
(iii) Connect node pairs
i
-
j
independently at random with
distance-dependent connection probabilities
p
ij
=
p
(
d
ij
),
prescribed by Eq. (
12
).
Taken together, RHGs in
B
d
+
1
are fully defined by six
parameters: properties of the hyperbolic ball,
R
and
ζ
; num-
ber of nodes
n
; radial component
α
of the node distribution;
chemical potential
μ
, and temperature
T
. Figure
1
visualizes
an RHG for
d
=
2.
Only the four parameters (
n
,α,
T
,
R
) are independent,
however. It follows from (
7
) that
ζ
is merely a rescaling
parameter for the distances
{
d
ij
}
and can be absorbed into the
radial coordinates
r
by the appropriate rescaling. Chemical
potential
μ
controls the expected number of links and the
sparsity of the resulting networks. We demonstrate below
that the sparsity requirement uniquely determines
R
and
μ
as
functions of the network size
n
,
R
=
R
(
n
) and
μ
=
μ
(
n
).
III. DEGREE DISTRIBUTION AND CLUSTERING
COEFFICIENT IN THE RHG
The structural properties of the RHG can be computed with
the hidden variable formalism, Ref. [
41
], by treating node
coordinates as hidden variables.
We begin by calculating the expected degree of node
l
located at point
x
l
={
r
l
,θ
l
1
,...,θ
l
d
}
:
k
(
x
l
)
=
(
n
−
1)
∫
d
x
k
ρ
x
k
(
x
k
)
1
+
e
ζ
(
d
lk
−
μ
)
2
T
.
(13)
The symmetry in the angular distribution of points ensures
that the expected degree of the node depends only on its radial
coordinate
r
l
and not on its angular coordinates,
k
(
x
l
)
=
k
(
r
l
,
0
,...,
0)
≡
k
(
r
l
)
. This allows us to integrate out the
d
angular coordinates in Eq. (
13
).
We also note that the choice for the radial coordinate dis-
tribution given by Eq. (
11a
) with
α
ζ/
2 results in most of
the nodes having large radial coordinates,
r
i
≈
R
1. This
fact allows us to approximate the distances using Eq. (
9
):
k
(
r
l
)
≈
∫
R
0
∫
π
0
(
n
−
1)
ρ
r
(
r
)d
r
ρ
θ
1
(
θ
1
)d
θ
1
1
+
[
e
ζ
(
r
+
r
l
−
μ
)
[
sin
(
θ
1
2
)]
2
]
1
2
T
.
(14)
To further simplify the calculations, we perform the fol-
lowing change of variables and parameters:
{
r
,
r
l
,
R
,
m
}=
d
ζ
2
{
r
,
r
l
,
R
,μ
}
,
(15a)
τ
=
dT
,
(15b)
a
=
2
α/ζ,
(15c)
where Eq. (
15a
) corresponds to four equations, each corre-
sponding to one variable or parameter in the brackets.
In terms of the rescaled variables, the connection
probability is
p
ij
≈
1
1
+
e
r
i
+
r
j
−
m
τ
[
sin
(
θ
ij
2
)]
d
τ
,
(16)
while Eq. (
14
) now reads
k
(
r
l
)
≈
∫
R
0
∫
π
0
(
n
−
1)
ρ
r
(
r
)d
r
ρ
θ
1
(
θ
1
)d
θ
1
1
+
e
r
+
r
l
−
m
τ
[
sin
(
θ
1
2
)]
d
τ
,
(17)
where the rescaled density
ρ
r
(
r
)
=
a
C
d
[
sinh
(
a
r
d
)]
d
,
0
r
R
,
(18)
with
C
d
as defined in Eq. (
11b
). In our analysis below, we
operate with
R
1 and a
>
1. In this case, most nodes are
characterized by large
r
values, and the density
ρ
r
(
r
)isap-
proximated as
ρ
r
(
r
)
≈
a
e
a
(
r
−
R
)
.
(19)
The density
ρ
r
(
r
)inEq.(
19
) is normalized only approxi-
mately under the assumptions of
R
1 and a
>
1:
∫
R
0
ρ
r
(
r
)
d
r
≈
1
−
e
−
a
R
.
(20)
The expected degree of the graph is given by
k
=
∫
R
0
d
r
ρ
r
(
r
)
k
(
r
)
,
(21)
and the degree distribution of the RHG can be expressed as
P
(
k
)
=
∫
R
0
d
r
ρ
r
(
r
)
P
(
k
|
r
)
,
(22)
054131-3
GABRIEL BUDEL
et al.
PHYSICAL REVIEW E
109
, 054131 (2024)
where
P
(
k
|
r
) is a conditional probability that a node with
radial coordinate
r
has exactly
k
connections.
In the case of sparse graphs,
P
(
k
|
r
) is closely approximated
by the Poisson distribution:
P
(
k
|
r
)
≈
1
k
!
e
−
k
(
r
)
[
k
(
r
)
]
k
,
(23)
see Ref. [
41
], and the resulting degree distribution
P
(
k
)isa
mixed Poisson distribution:
P
(
k
)
≈
1
k
!
∫
R
0
e
−
k
(
r
)
[
k
(
r
)
]
k
ρ
r
(
r
)d
r
(24)
with mixing parameter
k
(
r
)
.
The clustering coefficient of a node
i
with degree
k
i
>
1is
defined as the ratio
c
i
=
t
i
(
k
i
2
)
(25)
of the number of triangles
t
i
adjacent to
i
, to the maximum
such number
(
k
i
2
)
. Since nodes with degrees
k
=
0 and
k
=
1
do not form triangles, their clustering coefficients are unde-
fined. Therefore, the average clustering coefficient is defined
over nodes with
k
>
1.
The hidden variable formalism [
41
] allows for expressing
the average clustering coefficient of an RHG as a multiple
integral over triples of hidden variables. Apart from a few
special cases of the RHG, however, these integrals do not
have simple closed-form solutions [
42
]. Therefore, we restrict
ourselves to studying the clustering coefficient of RHGs nu-
merically in this work.
IV. CONNECTIVITY REGIMES OF THE RHG
Depending on the value of the rescaled temperature
τ
=
dT
, there exist three distinct regimes of the RHG: (i) cold
(
τ<
1), (ii) critical (
τ
=
1), and (iii) hot (
τ>
1). We provide
detailed analyses of the properties of RHGs in these regimes
below, and we summarize our findings in Fig.
15
.
A. Cold regime,
τ<
1
Since the inner integral in Eq. (
17
) does not have a closed-
form solution, we need to employ several approximations to
derive
k
(
r
l
)
. We note that most nodes have large radial co-
ordinates,
e
r
+
r
l
−
m
1, and the dominant contribution to the
inner integral in (
17
) comes from small
θ
1
values. This allows
us to estimate the integral by replacing sin(
θ
1
) and sin(
θ
1
/
2)
with the leading Taylor series terms, as sin(
x
)
=
x
+
O
(
x
3
),
resulting in
k
(
r
l
)
≈
(
n
−
1)
π
d
dI
d
,
1
×
∫
R
0
d
r
ρ
r
(
r
)
2
F
1
(1
,τ,
1
+
τ,
−
[
u
max
(
r
l
,
r
,
m
)]
1
τ
)
,
(26)
with
u
max
(
r
l
,
r
,
m
)
≡
(
π
2
)
d
e
r
l
+
r
−
m
,
(27)
and where
2
F
1
is Gauss’ hypergeometric function, and
I
d
,
1
≡
∫
π
0
sin
d
−
1
(
θ
1
)d
θ
1
=
√
π
[
d
2
]
/
[
d
+
1
2
]
(28)
for
d
>
1, and
I
1
,
1
=
2
π
.
In the
τ<
1 regime, the hypergeometric function in (
26
)
can be approximated as
2
F
1
(1
,τ,
1
+
τ,
−
[
u
max
(
r
l
,
r
,
m
)]
1
τ
)
≈
[
u
max
(
r
l
,
r
,
m
)]
−
1
πτ
sin
(
πτ
)
,
(29)
and
k
(
r
l
)
and
k
are then approximately given by
k
≈
(
n
−
1)
2
d
dI
d
,
1
πτ
sin
(
πτ
)
e
−
r
2
e
m
,
(30)
k
(
r
)
≈
k
e
−
r
e
−
r
,
(31)
where
e
−
r
≡
∫
R
0
d
r
ρ
r
(
r
)
e
−
r
, and the explicit approximation
for
e
−
r
follows from (
18
):
e
−
r
≈
a
a
−
1
(
e
−
R
−
e
−
a
R
)
.
(32)
We next discuss the choice of the rescaled chemical po-
tential
m
. To do so, we discuss the leading-order behavior of
k
n
in the thermodynamic limit. Since a
>
1, we neglect the
second term in (
32
) to obtain
k
(
r
)
n
∼
ne
m
−
r
−
R
,
(33a)
k
n
∼
ne
m
−
2
R
.
(33b)
Henceforth, we write
f
(
x
)
∼
g
(
x
) when lim
x
→∞
f
(
x
)
g
(
x
)
=
K
,
where
K
>
0 is a constant.
We note that
k
(
r
)
decreases exponentially as a function
of
r
with the largest (smallest) expected degree corresponding
to
r
=
0(
r
=
R
). By demanding that the largest and smallest
expected degrees scale as
k
max
n
=
k
(0)
n
∼
n
,
(34a)
k
min
n
=
k
(
R
)
n
∼
1
,
(34b)
we obtain
R
∼
ln
n
and
m
=
R
+
λ
, where
λ
is an arbitrary
constant.
First, we note that the scaling for
R
is consistent with our
initial assumption of
R
1 for large graphs. We also note
that the exact value of the parameter
λ
is not important as long
as it is independent of
n
. To be consistent with the original
H
2
formulation, we set
λ
=
0, obtaining
m
=
R
=
ln
(
n
/ν
)
,
(35)
where
ν
is a parameter controlling the expected degree of
the RHG.
Applying the scaling relationships (
35
)to(
30
) and (
31
), we
obtain
k
n
≈
ν
2
d
dI
d
,
1
(
a
a
−
1
)
2
πτ
sin(
πτ
)
×
[
1
−
2
(
n
ν
)
1
−
a
+
(
n
ν
)
2(1
−
a)
]
(36)
and
k
(
r
)
n
≈
n
ν
a
−
1
a
k
e
−
r
∞
∑
=
0
(
ν
n
)
(a
−
1)
,
(37)
see Figs.
16(a)–16(c)
.
As seen from Eq. (
36
) and Fig.
2
, RHGs are sparse in
the cold (
τ<
1) regime. Henceforth, we call graphs sparse
054131-4
RANDOM HYPERBOLIC GRAPHS IN
d
+
1 DIMENSIONS
PHYSICAL REVIEW E
109
, 054131 (2024)
(a)
(b)
5
10
10
3
10
4
10
5
Network size
e
e
r
g
e
d
e
g
a
r
e
v
A
〈
〉
5
10
10
3
10
4
10
5
Network size
e
e
r
g
e
d
e
g
a
r
e
v
A
〈
〉
5
10
10
10
10
20
10
30
Observed,
a=1.1(
=2.1)
Observed,
a=1.5(
=2.5)
Observed,
a=2.5(
=3.5)
Asymptote
=10
Theory,
a=1.1(
=2.1)
Theory,
a=1.5(
=2.5)
Theory,
a=2.5(
=3.5)
5
10
10
10
10
20
10
30
=1,
=0.5
=3,
=0.5
FIG. 2. Expected degree
k
as a function of network size
n
for
RHGs in the cold (
τ
=
0
.
5) regime with (a)
d
=
1and(b)
d
=
3.
Each panel includes the results for (red) a
=
1
.
1(
γ
=
2
.
1), (green)
a
=
1
.
5(
γ
=
2
.
5), and (blue) a
=
2
.
5(
γ
=
3
.
5). Each point is the
average of 100 simulations, and the error bars display standard devia-
tions. Solid lines are theoretical values for
k
prescribed by Eqs. (
17
)
and (
21
), and the dashed line is the thermodynamic limit of Eq. (
36
).
The insets in (a) and (b) correspond to extended domains of
n
values
for the cases a
=
1
.
1 and 1.5. Note that the a
=
1
.
1 case converges to
the asymptotic value at a much slower rate compared to the a
=
1
.
5
and 2.5 cases.
if their expected degree converges to a finite constant in the
thermodynamic limit. The slow convergence to the asymptotic
value of
k
=
10 in the a
=
1
.
1 case is due to the breakdown
of the sin(
x
)
≈
x
approximation in Eq. (
26
) for small a val-
ues. Indeed, at small a values a larger fraction of nodes is
characterized by small
r
values, for which the
e
(
r
+
r
l
−
m
)
1
assumption fails.
Finally, using Eqs. (
23
) and (
24
) we obtain the Pareto-
mixed Poisson distribution, which is a power law,
P
(
k
)
≈
a
κ
a
0
[
k
−
a
,κ
0
]
[
k
+
1]
∼
k
−
(a
+
1)
,
(38)
where
[
s
,
x
] is the upper incomplete gamma function, and
κ
0
≡
(
a
−
1
a
)
k
, as confirmed by simulations in Fig.
3
.
Hence, the cold regime corresponds to sparse power-law
graphs,
P
(
k
)
∼
k
−
γ
, with
γ
=
a
+
1
∈
(2
,
∞
). We note that
the degree distribution is a power law if it takes the form
of
P
(
k
)
=
(
k
)
k
−
γ
, where
(
k
) is a slowly varying function,
10
-6
10
-4
10
-2
10
0
10
2
10
4
10
0
10
1
10
2
10
3
10
4
Degree
Probability
(
)
10
-6
10
-4
10
-2
10
0
10
2
10
4
10
0
10
1
10
2
10
3
10
4
Degree
Probability
(
)
(a)
(b)
=3.5
=2.5
=2.1
=2.1
=3.5
=2.5
=1,
=0.5
=3,
=0.5
a
=1.1(
=2.1)
Theory
a
=1.5(
=2.5)
a
=2.5(
=3.5)
FIG. 3. Degree distribution
P
(
k
) for RHGs with (a)
d
=
1and
(b)
d
=
3at
τ
=
0
.
5and
n
=
1000
×
2
7
. Each panel includes the
degree distributions for (red) a
=
1
.
1(
γ
=
2
.
1), (green) a
=
1
.
5
(
γ
=
2
.
5), and (blue) a
=
2
.
5(
γ
=
3
.
5). Probabilities
P
(
k
) are ob-
tained from a single network realization. Degree distributions are
binned logarithmically to suppress noise at large
k
values. Solid
lines are theoretical values for
P
(
k
) prescribed by Eq. (
38
). For
visibility, the probabilities corresponding to
γ
=
2
.
5 and 2.1 are
multiplied by 10
2
and 10
4
, respectively. The scaling constant
ν
=
10
×
dI
d
,
1
2
d
(
a
−
1
a
)
2
sin(
πτ
)
πτ
, corresponding to
k
=
10 in the thermody-
namic limit.
i.e., a function that varies slowly at infinity, see Ref. [
43
].
Any function converging to a constant is slowly varying, and,
in the case of Eq. (
38
),
(
k
)
→
a
κ
a
0
as
k
→∞
. The degree
distribution is called scale-free if
γ
∈
(2
,
3).
The special case of a
=
1(
γ
=
2) is also well defined. In
this case the expressions for
k
and
k
(
r
)
given by Eqs. (
30
)
and (
31
) remain valid, but
e
−
r
is now given by
e
−
r
≈
R
e
−
R
.
(39)
It is straightforward to verify that the scaling of
R
=
m
=
ln(
n
/ν
)inthea
=
1 case does not lead to the desired calibra-
tion of node degrees,
k
max
∼
n
and
k
min
∼
1. Instead, the
proper scaling is
R
=
ln
(
n
/ν
)
,
(40a)
m
=
R
−
ln
R
,
(40b)
resulting in
k
n
≈
ν
2
d
dI
d
,
1
πτ
sin(
πτ
)
ln
(
n
/ν
)
,
(41)
k
(
r
)
n
≈
n
ν
k
ln
(
n
/ν
)
e
−
r
.
(42)
054131-5