# Detecting hyperbolic geometry in networks:
why triangles are not enough

Nelly Litvak  Riccardo Michielan  Clara Stegehuis  Faculty of Electrical
Engineering, Mathematics and Computer Science, University of Twente

###### Abstract

In the past decade, geometric network models have received vast attention in
the literature. These models formalize the natural idea that similar vertices
are likely to connect. Because of that, these models are able to adequately
capture many common structural properties of real-world networks, such as
self-invariance and high clustering. Indeed, many real-world networks can be
accurately modeled by positioning vertices of a network graph in hyperbolic
spaces. Nevertheless, if one observes only the network connections, the
presence of geometry is not always evident. Currently, triangle counts and
clustering coefficients are the standard statistics to signal the presence of
geometry. In this paper we show that triangle counts or clustering
coefficients are insufficient because they fail to detect geometry induced by
hyperbolic spaces. We therefore introduce a novel triangle-based statistic
$W$, which weighs triangles based on their strength of evidence for geometry.
We show analytically, as well as on synthetic and real-world data, that $W$ is
a powerful statistic to detect hyperbolic geometry in networks.

##  I Introduction

Network geometry is one of the most important features of real-world networks
[1], as it explains frequently observed network properties, including scale-
invariance, high clustering, and overlapping community structures. The concept
of geometry is intimately connected to the idea of similarity in networks,
that two similar vertices are likely to connect. Typical examples are social
networks, where people sharing the same interests or living in the same region
are more likely to interact, or the world wide web, where webpages sharing
similar contents are often linked. The similarity of vertices can be modeled
through geometry in a random graph. More specifically, two individuals can be
modeled as vertices in a geometric space, and their similarity is then
associated with a small distance between them. This class of models is often
called geometric network models.

In the past decades, several geometric models have been introduced, aiming to
model and understand real network properties [2, 3, 4, 5]. The simplest
example of geometric models are the random geometric graphs [6, 7], where an
underlying Euclidean space is fixed, and nodes within a given radius are
connected. However, random geometric graphs fail to describe the typical
scale-free nature of real-world networks, where many nodes of low degree
coexist with a few nodes of extremely large degrees. Instead, the hyperbolic
space has been found to be extremely useful for modeling real-world networks
[2], as it explains the heavy-tailed degree distributions that many networks
posses, their efficient routing [8, 9] and their community structures [10].
Interestingly, the hyperbolic model is equivalent to the renown
$\mathbb{S}^{1}$ model, where nodes are uniformly distributed on the circle,
and a soft constraint is assigned to the degrees [5]. Recently, a very
intuitive network model called geometric inhomogeneous random graph has been
proposed as generalization of hyperbolic random graphs [3]. GIRGs combine the
essential real-world properties of the hyperbolic random graph with simpler
mathematical formulations that make them mathematically more tractable than
hyperbolic random graphs. In these models each vertex is positioned in a
geometric space, and has a weight representing its genuine ability to attract
connections. Then, the probability of a connection between two vertices in the
GIRG is an increasing function of the weight of each vertex, and a decreasing
function of a distance between them.

Although in many cases network geometry is a natural assumption, networks may
not be directly endowed with a metric space, and in principle they could also
not posses any kind of geometry. Determining whether a given network has an
underlying latent hyperbolic geometric space has been highlighted as a major
open problem [1, 11]. Indeed, usually we can only observe the network
connections, and not the network features which can cause geometry. The main
question is then: can we assess whether these connections were formed by some
underlying geometry?

It has often been assumed that high clustering, or a large amount of
triangles, implies the presence of geometry [12]. Intuitively, in a geometric
space, the triangle inequality ensures that two neighbors of a vertex are
likely to be close to each other, and therefore likely to be connected. In
fact, triangles are a powerful statistic to distinguish geometric and non-
geometric networks, when assuming that the former can be endowed with an
Euclidean space [13, 14, 15]. In this paper however, we show that pure
triangle counts, as well as the average clustering coefficient, have
limitations in detecting geometry induced by hyperbolic spaces. In fact,
network models without any source of geometry may contain the same amount of
triangles as hyperbolic random graphs, and may have arbitrary large average
clustering coefficients. This is essentially due to the trade-off between
weights and geometry in the GIRG representation of the hyperbolic model:
connections can either be formed between high-weight nodes, or between
close–by nodes. When the degree distribution has a particularly heavy tail,
this trade-off favors triangles formed by high weighted vertices. Therefore,
the underlying geometry cannot always be detected by triangle counts or
clustering coefficients.

In this work we develop a novel and powerful statistic called _weighted
triangles_ to detect hyperbolic geometry in networks, where triangles are
weighted based on how likely they are to be caused by geometry. Triangles that
carry low evidence for geometry are discounted, so that our statistic is able
to differentiate hyperbolic geometry from non-geometric networks in a regime
where standard triangle counts or clustering coefficients are not [16, 17]. We
also provide experimental evidence that weighted triangles can successfully
detect a geometric nature of real-world networks.

##  II Models

In this paper, our benchmark model is the Geometric Inhomogeneous random graph
(GIRG) [18]. This is a powerful, but tractable, random graph model that
generalizes the hyperbolic random graph defined by Krioukov et al. in [2]. In
the GIRG model, each vertex $i\in\\{1,2,\ldots,n\\}$ is equipped with a weight
$h_{i}$ and a uniformly sampled position $x_{i}$ on a $d$-dimensional torus
$[0,1]^{d}$ endowed with the infinity norm. Weights are sampled independently
from the Pareto distribution, with density

$\rho(h)=K_{1}h^{-\tau},$ (1)

for any $h>h_{0}>0$, where $K_{1}$ is the normalizing constant and
$\tau\in(2,3)$. Two nodes $i$ and $j$, are then connected independently with
probability

$p(h_{i},h_{j},x_{i},x_{j})=K_{2}\min\left(\frac{h_{i}h_{j}}{\mu
n}||x_{i}-x_{j}||^{-d},1\right)^{\gamma},$ (2)

for some $\gamma>1$ and where $\mu$ denotes the average weight. The constant
$K_{2}$ is a correction factor, which ensures that the expected degree of any
vertex $i$ is proportional to its weight $h_{i}$ (see Appendix A).

In its original formulation, Bringmann et al. [3] defined the GIRG as an
entire class of models, where the connection probability (2) is only required
to hold asymptotically. Here we focus on a specific element of this class, to
have a practical and tractable comparison with non-geometric models. An
important reason to study the GIRG is that for $d=1,\gamma=\infty$ it is
asymptotically equivalent to the hyperbolic random graph, as shown in [18,
19]. Thus, the asymptotic results on the GIRG shown here are valid for the
hyperbolic random graph as well.

To determine when geometry can be detected, we compare the GIRG to the
inhomogeneous random graph (IRG). This model differs from the GIRG only in the
sense that it is non-geometric. Specifically, the vertices now possess only
weights $h_{i}$, sampled from the Pareto distribution as in (1), and are
connected with probability

$p(h_{i},h_{j})=\min\left(\frac{h_{i}h_{j}}{\mu n},1\right).$ (3)

The two models have the same weight, and degree distribution [20, 21], and
differ only in their connection probability through the presence of geometry.
We will therefore show that under classical triangle-based statistics, these
models cannot be distinguished, making it impossible to distinguish hyperbolic
geometry from simple scale-free networks.

##  III Triangle counts

The most intuitive statistic to detect geometry is the triangle count in the
network, $\triangle$. Indeed, one would expect a high number of triangles in
geometric networks due to the triangle inequality. The number of triangles in
the IRG scales as $n^{3(3-\tau)/2}$ [22]. In the GIRG on the other hand, the
triangle count undergoes a phase transition: when $\tau<7/3$ it scales as
$n^{3(3-\tau)/2}$, and when $\tau>7/3$ it scales as $n$ [23, 24, 17]. Then,
for small values of $\tau$, we cannot distinguish geometry from the triangle
counts scaling, as in both models the number of triangles is proportional to
$n^{3(3-\tau)/2}$. In Figures 1a and 1b we clearly see that when $\tau=2.1$,
the number of triangles in geometric and non-geometric models grow with the
same scaling.

(a) $\tau=2.9$

(b) $\tau=2.1$

(c) $\tau=2.9$

(d) $\tau=2.1$

(e) $\tau=2.9$

(f) $\tau=2.1$

Figure 1: Triangle counts, clustering coefficient and weighted triangles for
the Inhomogeneous random graph (IRG) and Geometric Inhomogeneous random graph
(GIRG). Dots are the averages over 100 samples of IRG and GIRG, against the
number of vertices $n$. Grey lines are linear interpolations between dots. (a)
When $\tau>7/3$, the number of triangles increases linearly in GIRG, but
slower than linearly for IRG. (b) When $\tau<7/3$, the triangles in the non-
geometric and geometric model share the same scaling. (c) When $\tau$ is
large, $\overline{C}$ differs significantly between the non-geometric and
geometric model. (d) When $\tau$ is small, $\overline{C}$ is qualitatively
similar in both models. (e) (f) $W$ is significantly different both for small
and large values of $\tau$. In particular, in non-geometric models $W$ remains
bounded below 1/6.

Theoretically, even when $\tau$ is small, it could still be possible to
distinguish geometric/non-geometric inhomogeneous models through triangle
counts. Indeed, if the number of triangles is
$\triangle=An^{3(3-\tau)/2}(1+o(1))$, we may be able to establish the correct
underlying model, by identifying the leading order term $A$. To this end, we
can use precise asymptotic results from our earlier work [22, 17]:

  * •

In the IRG,

$\frac{\triangle}{n^{3(3-\tau)/2}}\stackrel{{\scriptstyle\mathbb{P}}}{{\longrightarrow}}A_{\text{IRG}}.$

  * •

In the GIRG, when $\tau<7/3$,

$\frac{\triangle}{n^{3(3-\tau)/2}}\stackrel{{\scriptstyle\mathbb{P}}}{{\longrightarrow}}A_{\text{GIRG}}.$

Here, $A_{\text{IRG}}$ and $A_{\text{GIRG}}$ are explicit constants that
depend on the parameters of the two models. If these are all known, then the
two models could be distinguished using the difference between
$A_{\text{IRG}}$ and $A_{\text{GIRG}}$. However, in realistic situations, one
observes a network only through its connections, while the possible underlying
geometry of the network and the vertex weights are usually not known.
Therefore, in practice, we cannot estimate the parameters of the underlying
models, and thus it is impossible to establish whether the triangle count is
close to $A_{\text{IRG}}n^{3(3-\tau)/2}$ or $A_{\text{GIRG}}n^{3(3-\tau)/2}$.

We conclude that the number of triangles is not a satisfactory statistic for
inferring the hyperbolic geometry.

##  IV Average clustering coefficient

Another common network statistic to measure the tendency of the nodes to form
triangles, is the clustering coefficient, which has also been ascribed to
indicate a network geometry [12].

The average clustering coefficient captures the probability that two randomly
chosen neighbors of a randomly chosen vertex are connected as well.
Equivalently, it is the average fraction of realized triangles out of all
possible triangles that include a randomly chosen vertex:

$\overline{C}=\frac{1}{n}\sum_{i\in V}C_{i}=\frac{1}{n}\sum_{i\in
V}\frac{2\triangle_{i}}{d_{i}(d_{i}-1)},$ (4)

where $\triangle_{i}$ is the number of triangles containing vertex $i$, and
$d_{i}$ is the degree of vertex $i$. Typically, if the value of $\overline{C}$
does not vanish in $n$, then this is considered to be evidence for geometry.

The average clustering in GIRGs is $\Omega(1)$, that is, non-vanishing as $n$
increases [18]. In particular, in hyperbolic random graphs, $\overline{C}$
converges in probability to a positive constant [25]. For the IRG on the other
hand, $\overline{C}$ decays asymptotically, as $n^{\tau-2}\ln(n)$ [26, 27].
Even though $\overline{C}$ vanishes for large $n$, the decay of $\overline{C}$
is extremely slow when $\tau\approx 2$, as we can observe in Figure 1c. Thus,
the average clustering coefficient is impractical to detect geometry when
$\tau$ is small.

Even more importantly, in non-geometric models with a different heavy-tailed
degree distribution, $\overline{C}$ can even be constant. For example,
consider an inhomogeneous random graph with weights

$h_{i}=\begin{cases}2,&\text{with probability }1-1/(\sqrt{\mu n}),\\\
\sqrt{\mu n},&\text{with probability }1/(\sqrt{\mu n}).\end{cases}$

We show in Appendix F that $\overline{C}=\Theta(1)$ in this IRG, even though
the model does not contain any source of geometry. Hence, $\overline{C}$ too,
is not a good statistic to distinguish between geometric and non-geometric
networks.

##  V Weighted triangles

We will now describe our proposed statistic that, contrary to standard
clustering-based statistics, is able to detect hyperbolic geometry. This
statistic is again triangle-based so that it has the same computational
complexity as other clustering-based statistics. The difference between our
statistic and the average clustering coefficient or triangle count, is that
all triangles are weighted based on their evidence for geometry. Indeed, in a
hyperbolic space, triangles can be formed because of popularity (high-degree
vertices), or similarity (close–by vertices). Thus, we weigh each triangle, so
that triangles which carry low evidence for geometry have low weight, and
triangles which carry high evidence for being formed due to geometry have high
weight. More precisely, we define

$W:=\sum_{\begin{subarray}{c}i,j,k\in V\\\
i<j<k\end{subarray}}\frac{1}{d_{i}d_{j}d_{k}}\mathbbm{1}_{\\{(i,j,k)=\triangle\\}},$
(5)

where $\mathbbm{1}_{\\{(i,j,k)=\triangle\\}}$ is the indicator function of the
event that the vertices $i,j,k$ form a triangle in the network. The intuition
behind the weights $(d_{i}d_{j}d_{k})^{-1}$ is that, in non-geometric power-
law models, a typical triangle is formed between vertices of high degrees
[23]. Thus, when we discount the triangles formed by high-degree vertices, $W$
remains small. On the other hand, in the GIRG, there is a large number of
triangles formed by close–by vertices with small degrees. Therefore, $W$ is
significantly greater for GIRGs than for IRGs.

Indeed, as we show in Appendix E,

$W=\begin{cases}O(1),&\text{ w.h.p. in IRG},\\\ \Omega(n),&\text{ w.h.p. in
GIRG}.\end{cases}$

Thus, weighted triangles make a very powerful statistic to infer hyperbolic
geometry: in the absence of geometry, the statistic remains bounded, while it
scales at least linearly under a geometric model. Moreover, this different
behaviour is independent of $\tau$. This is clearly seen in Figures
LABEL:fig:weighted_triangles_models_large and 1f, where $W$ shows different
scaling in non-geometric/geometric models, regardless of $\tau$.

It is interesting to observe that the average clustering coefficient can be
seen as a specific way of weighing triangles as well:

$\begin{split}&n\overline{C}=\sum_{\begin{subarray}{c}i,j,k\in V\\\
i<j<k\end{subarray}}\left[\frac{1}{\binom{d_{i}}{2}}+\frac{1}{\binom{d_{j}}{2}}+\frac{1}{\binom{d_{k}}{2}}\right]\mathbbm{1}_{\\{i,j,k=\triangle\\}}\\\
&\approx n\overline{C}_{h}:=\sum_{\begin{subarray}{c}i,j,k\in V\\\
i<j<k\end{subarray}}2\left(\frac{1}{h_{i}^{2}}+\frac{1}{h_{j}^{2}}+\frac{1}{h_{k}^{2}}\right)\mathbbm{1}_{\\{i,j,k=\triangle\\}}.\end{split}$
(6)

On the other hand,

$W\approx W_{h}:=\sum_{\begin{subarray}{c}i,j,k\in V\\\
i<j<k\end{subarray}}\frac{1}{h_{i}h_{j}h_{k}}\mathbbm{1}_{\\{i,j,k=\triangle\\}}.$
(7)

By [23, 24, 17], triangles containing high-weighted vertices are likely to
appear in scale-free models regardless of the geometry of the system. Thus, an
effective statistic for geometry detection should discount triangles formed by
high-degree vertices. From (6) and (7) we see that such discounting occurs in
both $n\overline{C}_{h}$ and $W_{h}$. However, in $W_{h}$, the factor
$1/(h_{i}h_{j}h_{k})$ is small as soon as at least one of the three vertices
has high weight. On the contrary, in $n\overline{C}_{h}$, the factor
$1/h_{i}^{2}+1/h_{j}^{2}+1/h_{k}^{2}$ is small if and only if all three
vertices have high weights. Therefore, $W$ discounts triangles formed by high-
weight vertices more effectively than $n\overline{C}$ does. Indeed, Appendix F
shows that the average clustering coefficient may also be constant for non-
geometric networks, while weighted triangles are able to detect the non-
geometric nature of the underlying network. This makes weighted triangles $W$
a better geometry detector than the average clustering coefficient.

##  VI Real-world networks

We will now investigate the performance of our statistic on real-world data.
As our statistic was designed to infer hyperbolic geometry, we focus only on
networks with a heavy-tailed degree distribution. Furthermore, we investigate
data sets that contain multiple snapshots of different sizes of the same
network, to compare the theoretical scaling of $W$ with the scaling found in
the data. These networks are described in detail in Table 1.

Table 1:  Overview of the data sets. ArXiv collab collects coauthorships between scientists posting preprints on the Condensed Matter E-Print Archive, from 1999 to 2005 [28]; CAIDA AS contains the CAIDA autonomous systems relationship, from January 2004 to November 2007 [29]; Gnutella p2p collects all Gnutella peer-to-peer file sharing connections from August 2002 [30]. Name | # snapshots | avg. $n$ per snapshot
---|---|---
ArXiv collab [28] | 3 | 29437
CAIDA AS [29] | 122 | 22550
Gnutella p2p [30] | 8 | 22811

Figure 2 shows the behavior of triangle counts $\triangle$, the average
clustering coefficient $\overline{C}$ and weighted triangles $W$.

(a) ArXiv collab

(b) CAIDA AS

(c) Gnutella p2p

Figure 2: Triangle counts $\triangle$ (blue), average clustering coefficient
$\overline{C}$ (orange), and weighted triangles $W$ (green), computed for the
data sets: (a) ArXiv collaboration (cond-mat); (b) CAIDA autonomous systems
relationship; (c) gnutella peer-to-peer connections. The red line is the
simple linear regression of $W$.

In all three data sets, $W$ behaves roughly linearly in $n$, as our
theoretical analysis predicts for geometric networks. The clustering
coefficient as well as the pure triangle counts on the other hand, has more
erratic behavior that is difficult to interpret. We will now discuss the
results for each network in some more detail.

$W$ grows linearly for the ArXiv collaboration networks (Figure 2a): this
suggests that geometry is present in the network. This corresponds to an
intuition that ArXiv collaborations have a natural geometric structure:
researchers working in the same group, region, or country are more likely to
write a paper together. Moreover, a collaboration between two researchers is
more likely if they work on similar topics.

The average clustering coefficient $\overline{C}$ is rather small for the
CAIDA AS networks (Figure 2b), and it seems to be decreasing, as the network
size increases. On the other hand, the weighted triangles show a linear
growth, revealing a source of geometry, that, in fact, is consistent with the
domain knowledge about this network. Indeed, interactions between autonomous
systems occur through peering or transit. An important part of peer selection
is the following: internet service providers (ISPs) have a set of points-of-
presence, that are the locations where they have routers/servers and related
equipment/personnel across the world. An ISP can peer with another ISP only at
locations where both have a point-of-presence. Such location-dependent
connectivity rules naturally suggest the presence of an implicit geometry in
the network formation.

Lastly, the Gnutella peer-to-peer networks (Figure 2c) show an extremely small
average clustering coefficient, failing to detect geometry. On the contrary,
the weighted triangles reveal geometry, as $W$ increases linearly with the
network size. Indeed, it is reasonable to expect a geometric structure in this
network because peer-to-peer file transfers are more likely between users who
share similar interests. Then, we could construct an hidden metric space, by
embedding users into this space according to their interests.

Overall, the plots in Figure 2 suggest that weighted triangles can be an
effective statistic to detect geometry in real-world networks.

##  VII Conclusion and discussion

In this paper we have analyzed in detail different methods to detect
hyperbolic geometry in networks, when only the connections of the network are
known. For theoretical purposes, we used the IRG and GIRG as benchmark models,
on which we established analytical results. In both random graph models, the
probability of connection depends on the popularity features of individuals
vertices, expressed through their weights, so that the empirical degree
distribution is power law with parameter $\tau$. However, GIRG also models
similarity of individuals, by locating the graph vertices randomly in a
$d$-dimensional torus endowed with a metric.

First, we have established that triangle counts and the average clustering
coefficient have serious limitations in detecting the presence of geometry
when the degree distribution has a particular heavy tail (when $\tau<7/3$).
Using numerical simulations we confirmed these limitations, by comparing the
number of triangles and the average clustering coefficient in different
models.

Next, we have introduced a new statistic, weighted triangles $W$, that
effectively discounts triangles formed by high degree vertices. The underlying
intuition is that such triangles carry low evidence for geometry because they
are common in power law networks with or without an underlying geometric
space. Our main result states that $W$ is a suitable statistic for detecting
geometry, because, asymptotically in the network size, $W$ remains bounded in
IRGs, while it grows linearly in GIRGs. Numerical experiments on the real-
world data show a remarkable agreement with this analysis, and confirm the
high potential of the $W$ statistic for uncovering a hidden network geometry.

For practical applications, it would be interesting to provide some rule of
thumb, how large $W$ should be to signal geometry. In Appendix B we obtain
that $\mathbb{E}\left[W\right]=O(1)$, in IRGs. Then from Markov’s inequality
it follows that for sufficiently large $n$,

$\mathbb{P}\left(W\geq
n^{\alpha}\right)\leq\frac{1}{n^{\alpha-\varepsilon}}\to 0$

for any $0<\varepsilon<\alpha<1$. Furthermore, in GIRGs, we have that
$\mathbb{E}\left[W\right]=\Omega(n)$, while $\operatorname{Var}(W)=O(n)$ (see
Appendices C-D). Hence, from Chebyshev’s inequality, we get

$\mathbb{P}\left(W\leq\sqrt{n}\right)\to 0$

in the large network limit. This suggests $\sqrt{n}$ as a possible threshold
for $W$ to detect geometry. However, if $n$ is not sufficiently large, this
asymptotic approach could fail. Indeed, even though $W=\Omega(n)$ in GIRGs,
the leading order term can be very small. For example, in Figure 2c, for
$n=50000$, the estimated $W$ is still smaller than 2. In fact, a smaller
cutoff of for example $n^{0.1}$ seems to work better. These empirical
observations require further investigations. Based on our results that $W$ is
an asymptotically powerful statistic, designing statistical tests for finite
$n$ is a natural next step in the quest of detecting network geometry.

##  Appendix A Expected degree in GIRG

In this appendix, we calculate the expected degree of a vertex with weight
$h_{i}$ in a GIRG. We will consistently use notation $\mathbb{E}_{y}$ meaning
that the averaging occurs with respect to random element $y$.

First we show that in GIRGs the marginal connection probability, given the
weight sequence $(h_{i})$, is

$\mathbb{E}_{x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]=\Theta\left(\frac{h_{i}h_{j}}{n\mu}\wedge
1\right).$

Indeed, assuming that $x_{i}$ is fixed and $x_{j}$ is uniformly distributed,
whence $\mathbb{P}(||x_{i}-x_{j}||\leq r)=\mathbb{P}(||x_{j}||\leq r)$, and
denoting $V(r)=\mathbb{P}(||x_{j}||\leq r)=(2r)^{d}$, we obtain

$\displaystyle\mathbb{E}_{x_{j}}[p(h_{i},h_{j},x_{i},x_{j})]$
$\displaystyle=\int_{[0,1]^{d}}K_{2}\left[\frac{h_{i}h_{j}}{n\mu||x_{i}-x_{j}||^{d}}\wedge
1\right]^{\gamma}dx_{j}$
$\displaystyle=K_{2}\int_{0}^{1/2}\left[\frac{h_{i}h_{j}}{n\mu r^{d}}\wedge
1\right]^{\gamma}dV(r)$
$\displaystyle=K_{2}\int_{0}^{1/2}\left[\frac{h_{i}h_{j}2^{d}}{n\mu
V(r)}\wedge 1\right]^{\gamma}dV(r).$

Then, averaging over $x_{i}$, and applying integral substitution, we get

$\begin{split}&\mathbb{E}_{x_{i}}\left[\mathbb{E}_{x_{j}}[p(h_{i},h_{j},x_{i},x_{j})]\right]\\\
&=\int_{[0,1]^{d}}\left(K_{2}\int_{0}^{1}\left[\frac{h_{i}h_{j}}{n\mu
2^{-d}V}\wedge 1\right]^{\gamma}dV\right)dx_{i}\\\
&=K_{2}\int_{0}^{1}\left[\frac{h_{i}h_{j}}{n\mu 2^{-d}V}\wedge
1\right]^{\gamma}dV.\end{split}$

Defining $r_{0}:=\frac{h_{i}h_{j}2^{d}}{n\mu}$, consider the next two cases.

  * •

If $r_{0}\geq 1$, then the latter integrand is always $1$. In such case we
conclude $\mathbb{E}_{x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]=1$.

  * •

If $r_{0}<1$, then

$\displaystyle\mathbb{E}_{x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]$
$\displaystyle=K_{2}\left(\int_{0}^{r_{0}}1dV+\int_{r_{0}}^{1}\left(\frac{r_{0}}{V}\right)^{\gamma}dV\right)$
$\displaystyle=K_{2}\left(r_{0}+\left[\frac{r_{0}^{\gamma}}{\gamma-1}\left(r_{0}^{-\gamma+1}-1\right)\right]\right)$
$\displaystyle=r_{0}K_{2}(1+(\gamma-1)^{-1})+O(r_{0}^{\gamma}).$

Hence, setting the correction factor to the value
$K_{2}=(1-\gamma^{-1})2^{-d}$,

$\mathbb{E}_{x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]\\\
=\begin{cases}1,&\text{ if $\frac{h_{i}h_{j}}{n}\geq\frac{\mu}{2^{d}}$},\\\
\frac{h_{i}h_{j}}{n\mu}+o(\frac{h_{i}h_{j}}{n\mu}),&\text{ otherwise}.\\\
\end{cases}$ (8)

Next, we can compute the marginal connection probability of the vertices
$i,j$, only given the weight $h_{i}$. Substituting (1) and (8), we obtain

$\begin{split}\mathbb{E}_{h_{j},x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]&=\mathbb{E}_{h_{j}}[\mathbb{E}_{x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]]\\\
&\approx\int_{\frac{n\mu}{h_{i}2^{d}}}^{\infty}K_{1}h^{-\tau}dh\\\ &\hskip
28.45274pt+\int_{h_{0}}^{\frac{n\mu}{h_{i}2^{d}}}K_{1}\frac{h_{i}}{n\mu}h^{-\tau+1}dh,\end{split}$

where the approximation follows by dropping the lower order terms. Then:

$\begin{split}&\mathbb{E}_{h_{j},x_{i},x_{j}}\left[p(h_{i},h_{j},x_{i},x_{j})\right]\\\
&\hskip
28.45274pt=K_{1}\frac{h_{i}h_{0}^{2-\tau}}{n\mu(\tau-2)}+O\left((h_{i}/n)^{\tau-1}\right)\\\
&\hskip 28.45274pt=\frac{h_{i}}{n}(1+o(1)),\end{split}$ (9)

where the latter equality follows from the fact that
$K_{1}=(\tau-1)h_{0}^{\tau-1}$, $\mu=\frac{\tau-1}{\tau-2}h_{0}$. In other
words, Equation (9) tells that a vertex $i$ with weight $h_{i}$ connects to
any other vertex with probability $h_{i}/n$, in the large $n$ limit.

Finally, the expected degree of a vertex $i$ with weight $h_{i}$ is

$\begin{split}\mathbb{E}[\text{deg}(i)]&=\mathbb{E}\left[\sum_{j\neq
i}\mathbbm{1}_{\\{(i\leftrightarrow j|h_{i})\\}}\right]\\\
&=(n-1)\mathbb{E}_{h_{j},x_{i},x_{j}}[p(h_{i},h_{j},x_{i},x_{j})],\end{split}$

and from Equation 9 we conclude that

$\mathbb{E}[\text{deg}(i)]\approx h_{i}.$

##  Appendix B Upper bound for $\mathbb{E}[W]$ in IRGs

The expected value of $W$ in a IRG is given by

$\mathbb{E}[W]=\sum_{i<j<k}\mathbb{E}\left[\frac{1}{d_{i}d_{j}d_{k}}\mathbbm{1}_{\\{(i,j,k)=\triangle\\}}\right].$
(10)

To obtain the order of magnitude of (10), we compute the upper bound of a
similar quantity, where the degrees are replaced by the corresponding
independent weights. In other words, $\mathbb{E}[W]$ is roughly approximated
by

$\mathbb{E}[W_{h}]=\binom{n}{3}\int_{[h_{0},\infty]^{3}}(h_{1}h_{2}h_{3})^{-1}\prod_{1\leq\alpha<\beta\leq
3}\left(\frac{h_{\alpha}h_{\beta}}{\mu n}\wedge 1\right)\\\
\times\rho(h_{1})\rho(h_{2})\rho(h_{3})\;dh_{1}\;dh_{2}\;dh_{3},$

where the binomial term arises from counting the possible combination of three
vertices in $V$.

Since $\left(\frac{h_{\alpha}h_{\beta}}{\mu n}\wedge
1\right)\leq\frac{h_{\alpha}h_{\beta}}{\mu n}$ for all $\alpha,\beta$, the
latter integral is upper bounded by

$\left(\frac{K_{1}}{\mu
n}\right)^{3}\int_{[h_{0},\infty]^{3}}(h_{1}h_{2}h_{3})^{1-\tau}dh_{1}dh_{2}dh_{3},$

where $K_{1}$ is given by the Pareto power-law distribution for the weights.
Then,

$\displaystyle\mathbb{E}[W_{h}]$
$\displaystyle\leq\binom{n}{3}\left(\frac{K_{1}}{\mu
n}\right)^{3}\left(\int_{h_{0}}^{\infty}h^{1-\tau}dh\right)^{3}$
$\displaystyle=\binom{n}{3}\left(\frac{K_{1}}{\mu
n}\right)^{3}\left(\frac{h_{0}^{-\tau+2}}{\tau-2}\right)^{3}$
$\displaystyle=\binom{n}{3}\frac{1}{n^{3}}\leq\frac{1}{6},$

where in the second equality we used the fact that
$K_{1}/\mu=(\tau-2)h_{0}^{\tau-2}$. Since the degrees $d_{i}$ in the IRG are
concentrated around their means $h_{i}$, we conclude that
$\mathbb{E}[W]=O(1)$.

##  Appendix C Lower bound for $\mathbb{E}[W]$ in GIRGs

The expected value of $W$ in GIRGs is

$\mathbb{E}[W]=\sum_{i,j,k\in
V}\mathbb{E}\left[\frac{1}{d_{i}d_{j}d_{k}}\mathbbm{1}_{\\{(i,j,k)=\triangle\\}}\right].$
(11)

In a similar way as in Appendix B, to obtain the order of magnitude of (11) we
lower bound a similar quantity, where the degrees are replaced by the
corresponding independent weights. That is, $\mathbb{E}[W]$ is roughly
approximated by

$\mathbb{E}[W_{h}]=\binom{n}{3}\int_{[h_{0},\infty]^{3}}K_{1}^{3}(h_{1}h_{2}h_{3})^{-\tau-1}\int_{[0,1]^{3d}}\prod_{1\leq\alpha<\beta\leq
3}K_{2}\left(\frac{h_{\alpha}h_{\beta}}{\mu
n||x_{\alpha}-x_{\beta}||^{d}}\wedge
1\right)^{\gamma}\;dx_{1}\;dx_{2}\;dx_{3}\;dh_{1}\;dh_{2}\;dh_{3}.$ (12)

Observe that $||x_{2}-x_{3}||\leq 2\max\\{||x_{1}-x_{3}||,||x_{1}-x_{2}||\\}$
by the triangle inequality.

Then

$\begin{split}\frac{1}{||x_{2}-x_{3}||^{d}}&\geq\frac{1}{2^{d}\max\\{||x_{1}-x_{3}||^{d},||x_{1}-x_{2}||^{d}\\}}\\\
&=\left(\frac{1}{2^{d}||x_{1}-x_{2}||^{d}}\wedge\frac{1}{2^{d}||x_{1}-x_{3}||^{d}}\right).\end{split}$

Substituting
$(x_{1},x_{2},x_{3})\to(z_{1},z_{2},z_{3}):=(x_{1},x_{2}-x_{1},x_{3}-x_{1})$,
the integral in (12) is bounded from below by

$\int_{[h_{0},\infty]^{3}}K_{1}^{3}(h_{1}h_{2}h_{3})^{-\tau-1}\\\ \times
K_{2}^{3}\int_{[-1/2,1/2]^{2d}}\left(\frac{h_{2}h_{3}}{\mu
n2^{d}||z_{2}||^{d}}\wedge\frac{h_{2}h_{3}}{\mu n2^{d}||z_{3}||^{d}}\wedge
1\right)^{\gamma}\\\ \times\left(\frac{h_{1}h_{2}}{\mu n||z_{2}||^{d}}\wedge
1\right)^{\gamma}\left(\frac{h_{1}h_{3}}{\mu n||z_{3}||^{d}}\wedge
1\right)^{\gamma}\\\ \times dz_{2}\;dz_{3}\;dh_{1}\;dh_{2}\;dh_{3}.$ (13)

Now, consider the cube

$\mathcal{C}:=\left[-\left(\frac{h_{0}^{2}}{\mu
n2^{d}}\right)^{1/d},\left(\frac{h_{0}^{2}}{\mu
n2^{d}}\right)^{1/d}\right]^{d}.$

If $z_{2}\in\mathcal{C}$ and $z_{3}\in\mathcal{C}$, then all the minima in the
integrand of (13) are equal to 1. Therefore, after restricting the spatial
integrals to the subset $\mathcal{C}^{2}$, (13) is lower bounded by

$\int_{[h_{0},\infty]^{3}}(K_{1}K_{2})^{3}(h_{1}h_{2}h_{3})^{-\tau-1}\;dh_{1}\;dh_{2}\;dh_{3}\int_{\mathcal{C}^{2}}dz_{2}\;dz_{3}.$

Then, we obtain

$\begin{split}\mathbb{E}[W_{h}]&\geq\binom{n}{3}\left(\int_{h_{0}}^{\infty}K_{1}K_{2}h^{-\tau-1}\;dh\right)^{3}\left(\int_{\mathcal{C}^{2}}dz\right)^{2}\\\
&=\binom{n}{3}(K_{1}K_{2})^{3}\frac{h_{0}^{3\tau}}{\tau^{3}}\left(\frac{h_{0}^{2}}{\mu
n}\right)^{2}\\\ &=K_{3}n(1+o(1)),\end{split}$

where $K_{3}$ is a non-null constant depending on the GIRG parameters
$\tau,h_{0},\gamma,d$. Since the degrees $d_{i}$ in the GIRG are concentrated
around their means $h_{i}$, we conclude that $\mathbb{E}[W]=\Omega(n)$.

##  Appendix D Upper bound for $\operatorname{Var}(W)$ in GIRGs

Observe that

$\begin{split}&\operatorname{Var}(W_{h})=\operatorname{Var}\left(\sum_{i<j<k}\frac{\mathbbm{1}_{\\{i,j,k=\triangle\\}}}{h_{i}h_{j}h_{k}}\right)\\\
&=\sum_{\begin{subarray}{c}i_{1}<j_{1}<k_{1}\\\
i_{2}<j_{2}<k_{2}\end{subarray}}\operatorname{Cov}\left(\frac{\mathbbm{1}_{\\{i_{1},j_{1},k_{1}=\triangle\\}}}{h_{i_{1}}h_{j_{1}}h_{k_{1}}},\frac{\mathbbm{1}_{\\{i_{2},j_{2},k_{2}=\triangle\\}}}{h_{i_{2}}h_{j_{2}}h_{k_{2}}}\right)\\\
&\leq\sum_{\begin{subarray}{c}i_{1}<j_{1}<k_{1}\\\
i_{2}<j_{2}<k_{2}\end{subarray}}\mathbb{E}\left[\frac{\mathbbm{1}_{\\{i_{1},j_{1},k_{1}=\triangle\\}}\mathbbm{1}_{\\{i_{2},j_{2},k_{2}=\triangle\\}}}{h_{i_{1}}h_{j_{1}}h_{k_{1}}h_{i_{2}}h_{j_{2}}h_{k_{2}}}\right]\\\
&=\sum_{\begin{subarray}{c}i_{1}<j_{1}<k_{1}\\\
i_{2}<j_{2}<k_{2}\end{subarray}}\mathbb{E}_{\overline{h},\overline{x}}\left[\frac{\mathbb{P}\left(i_{1},j_{1},k_{1}=\triangle\right)\mathbb{P}\left(i_{2},j_{2},k_{2}=\triangle\right)}{h_{i_{1}}h_{j_{1}}h_{k_{1}}h_{i_{2}}h_{j_{2}}h_{k_{2}}}\right],\end{split}$
(14)

where indices $\overline{h},\overline{x}$ mean that the expectation is
performed over all the random variables $(h_{i})_{i\in[n]}$ and
$(x_{i})_{i\in[n]}$. There are now 4 different cases for the choices of
$i_{1},j_{1},k_{1},i_{2},j_{2},k_{2}$:

  1. (i)

$(i_{1},j_{1},k_{1})$ and $(i_{2},j_{2},k_{2})$ do not intersect.
In this case the covariance is 0, because the two random variables
$\frac{\mathbbm{1}_{\\{i_{1},j_{1},k_{1}=\triangle\\}}}{h_{i_{1}}h_{j_{1}}h_{k_{1}}}$
and
$\frac{\mathbbm{1}_{\\{i_{2},j_{2},k_{2}=\triangle\\}}}{h_{i_{2}}h_{j_{2}}h_{k_{2}}}$
are independent.

  2. (ii)

$(i_{1},j_{1},k_{1})$ and $(i_{2},j_{2},k_{2})$ intersect at 1 vertex (wlog
$i_{1}=i_{2}$). There are $O(n^{5})$ ways to choose the vertices. We can bound
the probabilities

$\begin{split}\mathbb{P}\left(i_{1},j_{1},k_{1}=\triangle\right)&\leq
p(h_{i_{1}},h_{j_{1}},x_{i_{1}},x_{j_{1}})p(h_{j_{1}},h_{k_{1}},x_{j_{1}},x_{k_{1}})\\\
\mathbb{P}\left(i_{2},j_{2},k_{2}=\triangle\right)&\leq
p(h_{i_{2}},h_{j_{2}},x_{i_{2}},x_{j_{2}})p(h_{j_{2}},h_{k_{2}},x_{j_{2}},x_{k_{2}})\end{split}$

Moreover, for any sequence of nodes $(\alpha_{1},...,\alpha_{m})$,

$\mathbb{E}_{\overline{x}}\left[\prod_{\ell=1}^{m-1}p(h_{\alpha_{\ell}},h_{\alpha_{\ell+1}},x_{\alpha_{\ell}},x_{\alpha_{\ell+1}})\right]\\\
=\prod_{\ell=1}^{m-1}\mathbb{E}_{\overline{x}}\left[p(h_{\alpha_{\ell}},h_{\alpha_{\ell+1}},x_{\alpha_{\ell}},x_{\alpha_{\ell+1}})\right].$

This is a consequence of the fact that the positions are i.i.d. uniformly
distributed in the torus, and that the connection probability is a function of
the distance. Then, the terms in the sum of the r.h.s. in (14) are upper
bounded by

$\mathbb{E}_{\overline{h}}\left[\frac{\mathbb{E}_{\overline{x}}[p(h_{k_{1}},h_{j_{1}},x_{k_{1}},x_{j_{1}})]\mathbb{E}_{\overline{x}}[p(h_{j_{1}},h_{i_{1}},x_{j_{1}},x_{i_{1}})]\mathbb{E}_{\overline{x}}[p(h_{i_{1}},h_{j_{2}},x_{i_{1}},x_{j_{2}})]\mathbb{E}_{\overline{x}}[p(h_{j_{2}},h_{k_{2}},x_{j_{2}},x_{k_{2}})]}{h_{i_{1}}^{2}h_{j_{1}}h_{k_{1}}h_{j_{2}}h_{k_{2}}}\right]\\\
=\int_{[h_{0},\infty)^{5}}K_{1}^{5}h_{i_{1}}^{-\tau-2}(h_{j_{1}}h_{k_{1}}h_{j_{1}}h_{k_{2}})^{-\tau-1}\frac{h_{k_{1}}h_{j_{1}}^{2}h_{i_{1}}^{2}h_{j_{2}}^{2}h_{k_{2}}}{(n\mu)^{4}}\;dh_{i_{1}}\;dh_{j_{1}}\;dh_{k_{1}}\;dh_{j_{2}}\;dh_{k_{2}}=\frac{1}{n^{4}\mu^{2}}.$

where the first equality follows from (8). Then, the contribution to the
variance from triangles overlapping in one vertex is $O(n^{5}/n^{4})=O(n)$.

  3. (iii)

$(i_{1},j_{1},k_{1})$ and $(i_{2},j_{2},k_{2})$ do intersect in 2 vertices
(wlog $i_{1}=i_{2},j_{1}=j_{2}$).
In this case the number of possible choices for the vertices is $O(n^{4})$. We
may bound the term in the r.h.s. of (14) with

$\mathbb{E}_{h}\left[\frac{\mathbb{E}_{\overline{x}}[p(h_{k_{1}},h_{j_{1}},x_{k_{1}j_{1}})]\mathbb{E}_{\overline{x}}[p(h_{j_{1}},h_{i_{1}},x_{j_{1}i_{1}})]\mathbb{E}_{\overline{x}}[p(h_{i_{1}},h_{k_{2}},x_{i_{1}k_{2}})]}{h_{i_{1}}^{2}h_{j_{1}}^{2}h_{k_{1}}h_{k_{2}}}\right]\\\
=\int_{[h_{0},\infty)^{4}}K_{1}^{4}(h_{i_{1}}h_{j_{1}})^{-\tau-2}(h_{k_{1}}h_{k_{2}})^{-\tau-1}\frac{h_{k_{1}}h_{j_{1}}^{2}h_{i_{1}}^{2}h_{k_{2}}}{(n\mu)^{3}}\;dh_{i_{1}}\;dh_{j_{1}}\;dh_{k_{1}}\;dh_{k_{2}}=\frac{1}{n^{3}\mu^{3}},$

where the first equality follows from (8). Then, the contribution to the
variance from triangles overlapping in two vertices is $O(n^{4}/n^{3})=O(n)$.

  4. (iv)

$(i_{1},j_{1},k_{1})$ and $(i_{2},j_{2},k_{2})$ intersect in 3 vertices
($i_{1}=i_{2},j_{1}=j_{2},k_{1}=k_{2}$).
There are $\binom{n}{3}$ ways to choose the vertices. We upper bound the term
in the r.h.s. of (14) with

$\mathbb{E}_{h}\left[\frac{\mathbb{E}_{\overline{x}}[p(h_{k_{1}},h_{j_{1}},x_{k_{1}j_{1}})]\mathbb{E}_{\overline{x}}[p(h_{j_{1}},h_{i_{1}},x_{j_{1}i_{1}})]}{h_{i_{1}}^{2}h_{j_{1}}^{2}h_{k_{1}}^{2}}\right]=\int_{[h_{0},\infty)^{3}}K_{1}^{3}(h_{i_{1}}h_{j_{1}}h_{k_{1}})^{-\tau-2}\frac{h_{i_{1}}h_{j_{1}}^{2}h_{k_{1}}}{(n\mu)^{2}}\;dh_{i_{1}}\;dh_{j_{1}}\;dh_{k_{1}}=\frac{1}{n^{2}}\left(\frac{\tau-2}{\tau
h_{0}^{2}}\right)^{2},$

where, again, the first equality follows from (8). Then, the contribution from
triangles completely overlapping is $O(n)$.

Hence, summing up all possible different cases, we see that the variance of
$W_{h}$ in GIRGs is $O(n)$. Since the degrees $d_{i}$ in the GIRG are
concentrated around their means $h_{i}$, we conclude that
$\operatorname{Var}(W)=O(n)$.

##  Appendix E Concentration of $W$

Here we show that $W$ concentrates around its expected value both in IRGs and
in GIRGs.

In Appendix B we proved that $\mathbb{E}[W]=O(1)$, in IRGs. Then,

$W=O(1),\quad\text{with high probability}$ (15)

in IRG, as consequence of the Markov’s inequality.

On the other hand, we proved that $\mathbb{E}[W]=\Omega(n)$ and
$\operatorname{Var}(W)=O(n)$ in GIRGs (Appendices C-D). By Chebyshev’s
inequality,

$\mathbb{P}\left(\left|\frac{W}{\mathbb{E}[W]}-1\right|>\delta\right)\leq\frac{\operatorname{Var}(W)}{\delta^{2}\mathbb{E}[W]^{2}}=o(1),$
(16)

for all $\delta>0$. In particular, from Equation (16) follows that, in GIRGs,
for all $\varepsilon>0$, there exist $\overline{\delta}>0$, $n_{0}>0$ such
that $\mathbb{P}\left(W<\overline{\delta}n\right)<\varepsilon$, for all
$n>n_{0}$. That is,

$W=\Omega(n),\quad\text{with high probability}.$ (17)

##  Appendix F 2-type inhomogeneous model

Consider an inhomogeneous random graph where

$h_{i}=\begin{cases}2,&\text{with probability }1-1/(\sqrt{\mu n}),\\\
\sqrt{\mu n},&\text{with probability }1/(\sqrt{\mu n}).\end{cases}$

We can approximate the weighted triangles $W$ by

$W_{h}=\sum_{i,j,k}\triangle_{i,j,k}\big{(}h_{i}h_{j}h_{k}\big{)}^{-1}.$

As well, can approximate the average clustering coefficient $\overline{C}$ by

$n\overline{C}_{h}=\sum_{i,j,k}\triangle_{i,j,k}\big{(}h_{i}^{-2}+h_{j}^{-2}+h_{k}^{-2}\big{)}.$

In this graph, a triangle falls into one of the four categories:

  1. (I)

The triangle has vertices with $h_{i}=h_{j}=h_{k}=2$.
Each one of these triangles contributes

$h_{i}^{-2}+h_{j}^{-2}+h_{k}^{-2}=3/4$

to $\overline{C}$, and

$(h_{i}h_{j}h_{k})^{-1}=1/8$

to $W_{h}$.
There are $O(n^{3})$ sets containing 3 vertices of weight 2, and they form a
triangle with probability

$\begin{split}&p(h_{i},h_{j})p(h_{i},h_{k})p(h_{j},h_{k})\\\ &\hskip
28.45274pt=\left(\frac{4}{n\mu}\wedge 1\right)\left(\frac{4}{n\mu}\wedge
1\right)\left(\frac{4}{n\mu}\wedge 1\right)\\\ &\hskip
28.45274pt=O(1/n^{3}).\end{split}$

Thus, this triangle type contributes $O(1)$ to $n\overline{C}_{h}$, and $O(1)$
to $W_{h}$.

  2. (II)

The triangle has $h_{i}=h_{j}=2$, $h_{k}=\sqrt{\mu n}$.
Each one of these triangles contributes

$h_{i}^{-2}+h_{j}^{-2}+h_{k}^{-2}=\frac{1}{2}+\frac{1}{n\mu}\approx\frac{1}{2}$

to $\overline{C}$, and

$(h_{i}h_{j}h_{k})^{-1}=\frac{1}{4\sqrt{n\mu}}$

to $W_{h}$.
There are $\Theta(n^{5/2})$ sets containing 2 vertices of weight 2 and one
with weight $\sqrt{\mu n}$, and they form a triangle with probability

$\begin{split}&p(h_{i},h_{j})p(h_{i},h_{k})p(h_{j},h_{k})\\\ &\hskip
28.45274pt=\left(\frac{4}{n\mu}\wedge
1\right)\left(\frac{2}{\sqrt{n\mu}}\wedge
1\right)\left(\frac{2}{\sqrt{n\mu}}\wedge 1\right)\\\ &\hskip
28.45274pt=\Theta(n^{-2}).\end{split}$

Thus, this triangle type contributes $\Theta(\sqrt{n})$ to
$n\overline{C}_{h}$, and $O(1)$ to $W_{h}$.

  3. (III)

The triangle has $h_{i}=2$, $h_{j}=h_{k}=\sqrt{\mu n}$.
Each one of these triangles contributes

$h_{i}^{-2}+h_{j}^{-2}+h_{k}^{-2}=\frac{1}{4}+\frac{2}{n\mu}\approx\frac{1}{4}$

to $\overline{C}$, and

$(h_{i}h_{j}h_{k})^{-1}=\frac{1}{2n\mu}$

to $W_{h}$.
There are $\Theta(n^{2})$ sets containing of one vertex of weight 2 and two
with weight $\sqrt{\mu n}$, and they form a triangle with probability

$\begin{split}&p(h_{i},h_{j})p(h_{i},h_{k})p(h_{j},h_{k})\\\ &\hskip
28.45274pt=\left(\frac{2}{\sqrt{n\mu}}\wedge
1\right)\left(\frac{2}{\sqrt{n\mu}}\wedge 1\right)\\\ &\hskip
28.45274pt=\Theta(n^{-1}).\end{split}$

Thus, this triangle type contributes $\Theta(n)$ to $n\overline{C}_{h}$, and
$O(1)$ to $W_{h}$.

  4. (IV)

The triangle has $h_{i}=h_{j}=h_{k}=\sqrt{\mu n}$.
Each one of these triangles contributes

$h_{i}^{-2}+h_{j}^{-2}+h_{k}^{-2}=\frac{3}{n\mu}$

to $\overline{C}$, and

$(h_{i}h_{j}h_{k})^{-1}=\frac{1}{(n\mu)^{3}/2}$

to $W_{h}$.
There are $\Theta(n^{3/2})$ sets containing three vertices with weight
$\sqrt{\mu n}$, and they form a triangle with probability

$\begin{split}p(h_{i},h_{j})p(h_{i},h_{k})p(h_{j},h_{k})=1.\end{split}$

Thus, this triangle type contributes $\Theta(\sqrt{n})$ to
$n\overline{C}_{h}$, and $O(1)$ to $W_{h}$.

Thus the total contributions to $n\overline{C}$ are:

  * •

$O(1)$, from type (I) triangles;

  * •

$\Theta(\sqrt{n})$, from type (II) triangles;

  * •

$\Theta(n)$, from type (III) triangles;

  * •

$\Theta(\sqrt{n})$, from type (IV) triangles.

Hence, $n\overline{C}_{h}=\Theta(n)$.

On the other hand, the total contributions to $W$ are:

  * •

$O(1)$, from type (I) triangles;

  * •

$\Theta(1)$, from type (II) triangles;

  * •

$\Theta(1)$, from type (III) triangles;

  * •

$\Theta(1)$, from type (IV) triangles.

Hence, $W_{h}=\Theta(1)$.

## References

  * Boguñá  _et al._ [2021] M. Boguñá, I. Bonamassa, M. D. Domenico, S. Havlin, D. Krioukov, and M. Á. Serrano, Network geometry, Nature Reviews Physics 3, 114 (2021).
  * Krioukov  _et al._ [2010] D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguná, Hyperbolic geometry of complex networks, Phys. Rev. E 82, 036106 (2010).
  * Bringmann  _et al._ [2018] K. Bringmann, R. Keusch, and J. Lengler, Average distance in a general class of scale-free networks with underlying geometry, arXiv preprint arXiv:1602.05712 (2018).
  * Deijfen  _et al._ [2013] M. Deijfen, R. Van der Hofstad, and G. Hooghiemstra, Scale-free percolation, in  _Annales de l’IHP Probabilités et statistiques_ , Vol. 49 (2013) pp. 817–838.
  * Serrano  _et al._ [2008] M. A. Serrano, D. Krioukov, and M. Boguñá, Self-similarity of complex networks and hidden metric spaces, Phys. Rev. Lett. 100, 078701 (2008).
  * Penrose  _et al._ [2003] M. Penrose _et al._ ,  _Random geometric graphs_ , Vol. 5 (Oxford university press, 2003).
  * Dall and Christensen [2002] J. Dall and M. Christensen, Random geometric graphs, Physical review E 66, 016121 (2002).
  * Bläsius  _et al._ [2018a] T. Bläsius, C. Freiberger, T. Friedrich, M. Katzmann, F. Montenegro-Retana, and M. Thieffry, Efficient shortest paths in scale-free networks with underlying hyperbolic geometry, in  _International Colloquium on Automata, Languages, and Programming (ICALP)_ , Vol. 107 (2018) pp. 20:1–20:14.
  * Kleinberg [2007] R. Kleinberg, Geographic routing using hyperbolic space, in  _IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications_ (IEEE, 2007).
  * Faqeeh  _et al._ [2018] A. Faqeeh, S. Osat, and F. Radicchi, Characterizing the analogy between hyperbolic embedding and community structure of complex networks, Phys. Rev. Lett. 121, 098301 (2018).
  * Smith  _et al._ [2019] A. L. Smith, D. M. Asta, and C. A. Calder, The geometry of continuous latent space models for network data, Statistical science: a review journal of the Institute of Mathematical Statistics 34, 428 (2019).
  * Krioukov [2016] D. Krioukov, Clustering implies geometry in networks, Phys. Rev. Lett. 116, 208302 (2016).
  * Devroye  _et al._ [2011] L. Devroye, A. György, G. Lugosi, and F. Udina, High-Dimensional Random Geometric Graphs and their Clique Number, Electronic Journal of Probability 16, 2481 (2011).
  * Gao and Lafferty [2017] C. Gao and J. Lafferty, Testing for global network structure using small subgraph statistics, arXiv preprint arXiv:1710.00862 (2017).
  * Bubeck  _et al._ [2016] S. Bubeck, J. Ding, R. Eldan, and M. Z. Rácz, Testing for high-dimensional geometry in random graphs, Random Structures & Algorithms 49, 503 (2016).
  * van der Kolk  _et al._ [2022] J. van der Kolk, M. Ángeles Serrano, and M. Boguñá, A geometry-induced topological phase transition in random graphs, arXiv preprint arXiv:2106.08030v2 (2022).
  * Michielan and Stegehuis [2022] R. Michielan and C. Stegehuis, Cliques in geometric inhomogeneous random graphs, Journal of Complex Networks 10 (2022).
  * Bringmann  _et al._ [2019] K. Bringmann, R. Keusch, and J. Lengler, Geometric inhomogeneous random graphs, Theoretical Computer Science 760, 35 (2019).
  * Komjáthy and Lodewijks [2020] J. Komjáthy and B. Lodewijks, Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs, Stochastic Processes and their Applications 130, 1309 (2020).
  * Bollobás  _et al._ [2007] B. Bollobás, S. Janson, and O. Riordan, The phase transition in inhomogeneous random graphs, Random Structures & Algorithms 31, 3 (2007).
  * Hofstad  _et al._ [2021] R. Hofstad, P. van der Hoorn, and N. Maitra, Local limits of spatial inhomogeneous random graphs, arXiv preprint arXiv:2107.08733 (2021).
  * Stegehuis  _et al._ [2019] C. Stegehuis, R. van der Hofstad, and J. S. van Leeuwaarden, Variational principle for scale-free network motifs, Scientific reports 9, 1 (2019).
  * van der Hofstad  _et al._ [2021] R. van der Hofstad, J. S. H. van Leeuwaarden, and C. Stegehuis, Optimal subgraph structures in scale-free configuration models, The Annals of Applied Probability 31, 501 (2021).
  * Bläsius  _et al._ [2018b] T. Bläsius, T. Friedrich, and A. Krohmer, Cliques in hyperbolic random graphs, Algorithmica 80, 2324 (2018b).
  * Fountoulakis  _et al._ [2021] N. Fountoulakis, P. Van Der Hoorn, T. Müller, and M. Schepers, Clustering in a hyperbolic model of complex networks, Electronic Journal of Probability 26 (2021).
  * Colomer-de Simon and Boguñá [2012] P. Colomer-de Simon and M. Boguñá, Clustering of random scale-free networks, Phys. Rev. E 86, 026120 (2012).
  * van der Hofstad  _et al._ [2017] R. van der Hofstad, A. J. E. M. Janssen, J. S. H. van Leeuwaarden, and C. Stegehuis, Local clustering in scale-free networks with hidden variables, Phys. Rev. E 95, 10.1103/PhysRevE.95.022307 (2017).
  * Newman [2001] M. E. Newman, The structure of scientific collaboration networks, Proceedings of the National Academy of Sciences of the United States of America 98, 404 (2001).
  * [29] The CAIDA AS Relationships Dataset (January 2004 to November 2007) .
  * Matei  _et al._ [2002] R. Matei, A. Iamnitchi, and P. Foster, Mapping the gnutella network, IEEE Internet Computing 6, 50 (2002).