# Clustering and Cliques in P.A random graphs with edge insertion

Caio Alves1 1 Oak Ridge National Lab, Tennessee, USA
e-mail<EMAIL_ADDRESS>,  Rodrigo Ribeiro2 2 University of Denver,
Colorado, USA
e-mail<EMAIL_ADDRESS>and  Rémy Sanchis3 3Departamento de Matemática,
Universidade Federal de Minas Gerais, Av. Antônio Carlos 6627 C.P. 702 CEP
30123-970 Belo Horizonte-MG, Brazil
e-mail<EMAIL_ADDRESS>
(Date:
1 Oak Ridge National Lab, USA
2 Mathematics Departament, University of Denver, USA.
3 Departamento de Matemática, Universidade Federal de Minas Gerais, Brazil. )

###### Abstract.

In this paper, we investigate the global clustering coefficient (a.k.a
transitivity) and clique number of graphs generated by a preferential
attachment random graph model with an additional feature of allowing edge
connections between existing vertices. Specifically, at each time step $t$,
either a new vertex is added with probability $f(t)$, or an edge is added
between two existing vertices with probability $1-f(t)$. We establish
concentration inequalities for the global clustering and clique number of the
resulting graphs under the assumption that $f(t)$ is a regularly varying
function at infinity with index of regular variation $-\gamma$, where
$\gamma\in[0,1)$. We also demonstrate an inverse relation between these two
statistics: the clique number is essentially the reciprocal of the global
clustering coefficient.

_Keywords_ : complex networks; cliques; preferential attachment; concentration
bounds; diameter; scale-free; small-world
MSC 2010 subject classifications. Primary 05C82; Secondary 60K40, 68R10

##  1\. Introduction

Analyzing graph observables is crucial to understanding the topology and
evolution of networks. These observable properties, including but not limited
to node degree distribution, clustering coefficient, and clique number,
provide invaluable insights into the network’s overall structure and
connectivity patterns. The global clustering coefficient captures the density
of triangles in the network and can reveal how nodes tend to form tightly-knit
clusters. Whereas, the clique number, which is the size of the largest
complete subgraph, can be thought of as a measure of how tightly connected the
vertices in the graph are.

The investigation and usage of the clustering coefficient and clique number
are an interdisciplinary field that have appeared in a wide range of
scientific papers. Articles from various fields have analyzed these properties
of networks due to the fact that they provide insights into the underlying
mechanisms governing network formation and evolution. In more theoretical
fields, the study of these properties has led to the development of new graph
theory concepts, see [16, 19] for a few examples of recent generalizations of
clustering coefficients. In the field of chemistry, in [21] the authors employ
cliques to describe chemicals within a chemical database that display a
notable level of similarity to a target structure. In sociology, the study of
these properties has helped to understand the formation of social networks and
the spread of information within them, see [17, 20]. Therefore, investigating
the clustering coefficient and clique number is a crucial step towards
developing a comprehensive understanding of network dynamics, and the
interdisciplinary nature of these quantities underscores their significance.

In the classical preferential attachment model where new arriving vertices
connect to $m$ neighbors [7], the clique number is at most $m$, and the
clustering coefficient tends to $0$ as the inverse of the number of vertices
in the graph [11]. In this paper, we focus on studying these two crucial
statistics in graphs generated by a variation of this model, where new edges
between existing vertices can be added at any time. We investigate the impact
of this modified rule on these statistics.

To facilitate our analysis and present our results clearly, we will first
introduce a formal definition of the model in the following subsection.

###  1.1. The model

Firstly, let us introduce a new notation. Given a finite connected
(multi)graph $G$, let $\pi_{G}$ be the following distribution over the
vertices of $G$ defined as follows

(1.1) $\pi_{G}(v):=\frac{{\rm degree}(u)}{\sum_{w\in G}{\rm degree}(w)}.$

Our model generates a sequence of (multi)graphs in an inductive way, that is,
we obtain the $t$-th graph by performing a graph operation on the $(t-1)$th
graph. In our settings, there exist two possible ways of modifying a given
graph $G$:

  * •

Vertex-operation. Add a new vertex $v$ to $G$ and connect it to a vertex $u\in
G$ selected accordingly to $\pi_{G}$;

  * •

Edge-operation. Add a new edge connecting two existing vertices of $G$, $u$
and $v$, both selected independently and accordingly to $\pi_{G}$.

We highlight that in edge-operation, $u$ and $v$ might be the same vertex, in
that case a loop is added to $v$, or they might be already connected in $G$,
in which case a multiple edge is created between then.

The parameter of the model is a real function $f:(0,\infty)\to[0,1]$. For a
fixed function $f$, we let $\\{Z_{t}\\}_{t\in\mathbb{N}}$ be an independent
sequence of random variables such that $Z_{t}\sim{\rm Ber}(f(t))$. We start
with an initial graph $G_{0}$ and then we generate the model inductively by
obtaining $G_{t+1}$ from $G_{t}$ as follows:

  * •

Vertex-step. If $Z_{t+1}=1$, we perform a vertex-operation on $G_{t}$ and set
the resulting graph to be $G_{t+1}$.

  * •

Edge-step. If $Z_{t+1}=0$, we perform an edge-operation instead.

In words, the model decides according to a coin, with a possibly time-
dependent bias, which operation it is going to perform on the current graph in
order to generate the next one.

The model here investigated was originally introduced in [2] and, by choosing
$f(t)\equiv 1$, one obtains the well-known Preferential Attachment (PA) random
graph proposed by A-L. Barabási and R. Albert in [7] with parameter $m=1$. The
case $f(t)\equiv p\in[0,1]$ is a particular case of the model introduced by C.
Cooper and A. Frieze in [14] and also investigated by F. Chung and L. Lu in
[13].

For the sake of readability and to avoid clutter we will make some choices
notation-wise. Throughout the paper, we will use letters $f,g$ and $h$ to
denote functions for which $G_{t}(f)$ makes sense, that is,
$f,g,h:(0,\infty)\to[0,1]$. We will also simply write $G_{t}$ for the $t$-th
graph generated by the above dynamics, whenever the function $f$ is fixed and
there is no risk of confusion. Alternatively, we will write $G_{t}(f)$ to
highlight the dependence on $f$ when needed.

We will also set $G_{0}$ to be the multigraph on one vertex and a self-loop
attached to it. The reader will notice that the initial graph plays no
important role in our results as long as it is finite. And we will write $|G|$
as a shorthand for the cardinality of the vertex set of $G$. In this paper we
investigate the aforementioned model when $f$ belongs to the family of
regularly varying functions. We say a function $f:(0,\infty)\to(0,\infty)$ is
a regularly varying function at infinity if there exists a real number
$\gamma$ such that for all $a>0$ the following identity is satisfied

(1.2) $\lim_{t\to\infty}\frac{f(at)}{f(t)}=a^{\gamma}.$

The constant $\gamma$ is called the index of regular variation. Sometimes,
when $\gamma=0$, we may call the function $f$ slowly varying.

###  1.2. Main results: Statements and Discussion

In this part we will state and discuss our main results. The results concern
concentration inequalities for the clique number and global clustering
coefficients. Our results are particularly interesting as they provide a
characterization of such statistics in terms of the index of regular variation
when $f$ is taken as a regularly varying function. We also prove a continuity
theorem, meaning that under a suitable notion of convergence for the function
$f$, we have convergence in total variation distance of the respective
processes.

####  1.2.1. Cliques

A complete subgraph is a subgraph in which every pair of vertices is adjacent
to each other. The clique number of a graph is the size of the largest
complete subgraph (clique) that can be found in the graph. Again for the sake
of readability, we will denote the clique number of $G_{t}(f)$ simply by
$\omega_{t}$ whenever $f$ is fixed or understood from the context.

The most straightforward problem about clique number concerns finding its
order of magnitude. In [9], K. Bogerd, R. M. Castro and R. van der Hofstad,
prove a concentration result for the clique number in rank-1 random graphs.
Another interesting problem is the one of detecting artificially planted
cliques, that is, by observing realizations of the model, decides whether it
contains a clique that has been artificially added to the graph. This type of
problem is investigated by K. Bogerd, R. M. Castro, R. van der Hofstad and N.
Verzelen in [10].

In our context, we establish two results involving the clique number of
$G_{t}(f)$. Firstly, we have proved a general lower bound for the clique
number of $G_{t}$ that holds under the mild assumption that $f$ decreases to
zero.

######  Theorem 1 (Existence of Large cliques).

If $f$ decreases to zero, then for every $\delta\in(0,1)$, there exist
positive constants $c_{1}$ and $c_{2}$ depending on $\delta$ and $f$ only such
that

${\mathbb{P}}\left(\omega_{t}\geq\frac{c_{2}{\mathbb{E}}\left[|G_{t^{(1-\delta)/2}}|\right]}{\log
t}\right)\geq 1-\frac{2}{\log
t}-\exp\left\\{-\frac{c_{2}{\mathbb{E}}\left[|G_{t^{(1-\delta)/2}\log
t}|\right]}{4\log t}\right\\},$

The above theorem yields an interesting result: for certain regimes of the
model, it states that $G_{t}(f)$ contains a clique of order approximately
$\sqrt{|G_{t}(f)|}$. For example, consider the case where $f(t)=t^{-\gamma}$
with $\gamma\in(0,1)$. This gives us
${\mathbb{E}}\left[|G_{t}(f)|\right]\approx t^{1-\gamma}$. Thus, by Theorem 1
we obtain, with high probability, a clique of order at least
$t^{(1-\gamma)(1-\delta)/2}$ which is approximately
$\left({\mathbb{E}}\left[|G_{t}(f)|\right]\right)^{(1-\delta)/2}$.

As our second main result, we have also provided a comprehensive
characterization of this statistic along with the global clustering
coefficient under the additional assumption of $f$ being regularly varying. In
other words, we establish that for the vast and important class of regularly
varying functions at infinity the lower bound given by Theorem 1 is sharp up
to factors of order $t^{\delta}$ for any $\delta$. This is our next result.

######  Theorem 2 (Clique number for RV functions).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, for every
$\delta\in(0,1)$, there exist positive constants $c_{1},c_{2}$ and $c_{3}$
depending on $\delta$ only such that

${\mathbb{P}}\left(c_{1}t^{(1-\gamma)(1-\delta)/2}\leq\omega_{t}\leq
c_{2}t^{(1-\gamma)(1+\delta)/2}\right)\geq 1-\frac{c_{3}}{\log t}.$

From a computational perspective, the problem of finding cliques in a graph
are not only too time-consuming, but some are NP-complete. In our case, as a
consequence of our approach, the clique given by Theorem 2 is likely to be
formed by the $t^{(1-\gamma)(1+\delta)/2}$ first vertices added by the
process.

By Theorem 2 and properties of the random sequence $\\{\omega_{t}\\}_{t\geq
0}$ we prove a convergence result

######  Corollary 1.3 (Convergence of clique number).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then,

$\lim_{t\to\infty}\frac{\log\omega_{t}}{\log
t}=\frac{1-\gamma}{2},\;\text{almost surely.}$

In [5] the authors prove the convergence of the clique in the $\log$ scale for
$f(t)\equiv p$, with $p\in[0,1]$. Their result states that

$\lim_{t\to\infty}\frac{\log\omega_{t}}{\log t}=\frac{1-p}{2-p},\;\text{almost
surely.}$

Then Corollary 1.3 can be seen as some sort of limit of the above convergence
when the parameter $p$ goes to zero. From this perspective, if the parameter
$p$ goes to zero as a slowly varying function, then one obtains the expected
$\frac{1}{2}$ as the limit. However, if $p$ goes too fast to zero, then a
limit smaller than $\frac{1}{2}$ is obtained.

####  1.2.2. Clustering coefficient

The global clustering coefficient is a statistic that measures the extent to
which vertices in a graph tend to cluster together. It is defined as the ratio
of the number of triangles (complete subgraphs of size three) in the graph to
the total number of connected triples of vertices (a.k.a cherries).

Due to the fact that in our settings $G_{t}(f)$ might be a multigraph with
multiple edges or self-loops, we will compute the global clustering for the
simplification of $G_{t}(f)$, that is, given $G_{t}(f)$, we obtain a simple
graph $\widehat{G}_{t}(f)$ obtained from $G_{t}(f)$ by removing multiple edges
and loops.

Given a simple graph $H$ we will let $\Delta(H)$ be the number of triangles in
$H$. Whereas, $\Lambda(H)$ denotes the number of cherries (paths of length
two) in $H$. In the case of a multigraph $G$, we will simply write $\Delta(G)$
and $\Lambda(G)$ meaning $\Delta(\widehat{G})$ and $\Lambda(\widehat{G})$,
respectively. That is, $\Delta(G)$ and $\Lambda(G)$ count the number of
triangles and cherries respectively without multiplicities. Then, we define
the global clustering coefficient of $G_{t}(f)$ as

$c^{\rm glob}_{t}=c^{\rm
glob}(G_{t}(f)):=3\times\frac{\Delta(G_{t}(f))}{\Lambda(G_{t}(f))}.$

B. Bollobás and O. Riordan studied the BA-model with $m\geq 2$ in [11]. In
this model, a new vertex with $m$ randomly chosen neighbors is added to the
graph at each step. The authors proved that $\mathbb{E}[c^{\rm glob}_{t}]$
decreases at the rate of $\log^{2}(t)/t$, and the expected number of triangles
at time $t$ is roughly $\log^{3}(t)$. N. Eggemann and S. D. Noble studied a
variation of this model, called the affine version, where vertices are
selected based on their degree and a constant of attractiveness $\delta$ in
[15]. They proved that, for any positive $\delta$, the expected number of
triangles is of order $\log^{2}(t)$, and $\mathbb{E}[c^{\rm glob}_{t}]$ decays
as $\log(t)/t$.

In [18], E. Jacob and P. Mörters investigated the global clustering for a
different model which also takes into account spatial proximity of vertices to
create connections. Their study found that $c^{\rm glob}_{t}$ converges in
probability to a constant whose positivity depends on the choice of
parameters. In [23], C. Stegehuis, R. van der Hofstad and J. Leeuwaarden, also
investigate clustering for random graph models with latent geometry.

In our study, we establish a concentration inequality result for $c^{\rm
glob}_{t}$ that shows that in our case, $c^{\rm glob}_{t}$ decays polynomialy
fast and the exponent depends on the index of regular variation of $f$.
Additionaly, we show an almost surely convergence of $c^{\rm glob}_{t}$ in the
right scale.

######  Theorem 3 (Clustering coefficient for RV functions).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, for every
$\delta\in(0,1)$, there exist positive constants $c_{1}$ and $c_{2}$ depending
on $\delta$ only such that

${\mathbb{P}}\left(c_{1}t^{-(1-\gamma)(1+\delta)/2}\leq c^{\rm glob}_{t}\leq
c_{2}t^{-(1-\gamma)(1-\delta)/2}\right)\geq 1-\frac{1}{\log t}.$

The bounds and rates given by the above theorem are good enough to show the
convergence of the clustering coefficient at the $\log$ scale.

######  Corollary 1.4 (Convergence of clustering coefficient).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then,

$\lim_{t\to\infty}\frac{\log c^{\rm glob}_{t}}{\log
t}=-\frac{1-\gamma}{2},\;\text{almost surely.}$

In [5] the authors prove that for $f(t)\equiv p$, for $p\in[0,1]$, the
following limit holds

$\lim_{t\to\infty}\frac{\log c^{\rm glob}(G_{t}(f))}{\log
t}=\frac{3(1-p)}{2-p}-2+p,\;\text{almost surely.}$

Similarly to the case of the clique number, the case in which $f$ is a slowly
varying function that decreases to zero can be seen as the limit case when $p$
goes to zero.

Observe that Theorem 3 combined with Theorem 2 shows a surprisingly intriguing
reciprocal relation between global clustering and clique number. We state this
relation in the result below.

######  Corollary 1.5 (Inverse Relation).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, for every
$\delta\in(0,1)$, there exist positive constants $c_{1}$ and $c_{2}$ depending
on $\delta$ only such that

${\mathbb{P}}\left(\frac{c_{1}}{\omega(G_{t}(f))^{1+\delta}}\leq c^{\rm
glob}(G_{t}(f))\leq\frac{c_{2}}{\omega(G_{t}(f))^{1-\delta}}\right)\geq
1-\frac{1}{\log t}.$

####  1.2.3. Comparing $G_{t}(f)$ and $G_{t}(h)$

If two edge-step functions are “close” to each other in some sense, then one
should expect that the random processes they generate should be “close” as
well. In order to formalize this intuition, we have developed a grand coupling
mechanism that enables us to generate all processes $\\{G_{t}(f)\\}_{t}$, for
any $f$, from the same source of randomness. The coupling allows us to compare
the statistical properties of $G_{t}(f)$ and $G_{t}(h)$ by simply comparing
the functions $f$ and $h$. This can be seen as a Transfer Principle result
that allows us to transfer results for $G_{t}(f)$ to $G_{t}(h)$ under some
assumptions on the relation between $f$ and $h$.

The idea that $G_{t}(f)$ is close to $G_{t}(h)$ whenever $f$ and $h$ are close
is formalized in the theorem below, which is a consequence of our Grand
Coupling introduced at Section 2. In words, if $f$ and $h$ are close in the
$L_{1}(\mathbb{N})$-norm (denoted by $\|\cdot\|_{1}$), then
$\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq 1})$ is close to
$\mathrm{Law}(\\{G_{t}(h)\\}_{t\geq 1})$ in the total variation distance,
denoted by $\mathrm{dist}_{TV}(\cdot,\cdot)$.

######  Theorem 4.

Consider any two $f$ and $h$. We have

(1.6) $\mathrm{dist}_{TV}\left(\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq
1}),\mathrm{Law}(\\{G_{t}(h)\\}_{t\geq 1})\right)\leq\|f-h\|_{1}.$

In particular, the following implication holds

(1.7) $f_{n}\stackrel{{\scriptstyle
L_{1}(\mathbb{N})}}{{\longrightarrow}}f\implies\mathcal{L}((G_{t}(f_{n}))_{t\geq
1})\stackrel{{\scriptstyle\mathrm{dist}_{TV}}}{{\longrightarrow}}\mathcal{L}((G_{t}(f))_{t\geq
1}).$

The theorem presented above represents an interesting perturbative statement,
illuminating the ability to introduce a small amount of noise
$\epsilon=\epsilon(t)$ into the function $f$, while preserving the integrity
of the original process up to a maximum error of $|\epsilon|_{1}$ in total
variation distance. This result affirms the robustness of the process to
external perturbations.

One difficulty in our setup is the degree of generality we work with. Our case
replaces the parameter $p\in(0,1]$ in the models investigated in [1, 13, 14]
by any non-negative real function $f$ with $\|f\|_{\infty}\leq 1$. The
introduction of such function naturally increases the complexity of any
analytical argument one may expect to rely on and makes it harder to discover
threshold phenomena. On the other hand, the fact that we are working under
such large space of parameters is also one of the reasons why results like
Theorems 2 and 2 or even the Corollaries 1.3 and 1.4 are surprising, because
they depend on a simple functional of the parameter $f$: its index of regular
variation at infinity. Under such wide degree of freedom, there is no reason
to expect such simple characterizations of statistics to hold true.

###  1.3. Main technical ideas

In order to prove Theorem 1 and Theorem 4, we construct an auxiliary process
that we call the doubly-labeled random tree process,
$\\{\mathcal{T}_{t}\\}_{t\geq 1}$. In essence, this process is a realization
of the traditional BA-model (obtained in our settings choosing $f\equiv 1$)
where each vertex has two labels attached to it. We then show in Proposition
2.1 how to generate $G_{t}(f)$ from $\mathcal{T}_{t}$ using the information on
those labels. This procedure allows us to generate $G_{t}(f)$ and $G_{t}(h)$,
for two distinct functions $f$ and $h$, from exactly the same source of
randomness. The upshot is that the parameter function $f$ may be seen as a map
from the space of doubly-labeled trees to the space of (multi)graphs –
therefore it makes sense to use the notation $f(\mathcal{T}_{t})$.
Furthermore, this map has the crucial property of being monotonic (in a way we
make precise latter). Roughly speaking, if $f\leq h$, then certain monotonic
statistics respect this order, so if $\zeta$ is such an statistic, then
$\zeta(f(\mathcal{T}_{t}))\leq\zeta(h(\mathcal{T}_{t}))$. In Proposition 3.4
we give important examples of suitable monotonic statistics. The main
advantage of our machinery is that it allows us to transpose some results
about graphs generated for functions in a particular regime to another just by
comparing the functions themselves. This important feature of our approach
allows us, for instance, to use known results about cliques when $f$ is taken
to be a constant less than one to propagate this result down other regimes of
functions.

While the coupling approach offers a clear pathway for extending results of
one regime of $f$ to another, some statistics still demand further work. As
for an upper bound for the clique number, we obtain it by controlling the
number of triangles. In this approach, we investigate the simplification of
$G_{t}$ denoted by $\widehat{G}_{t}$. By providing a sharp upper bound on the
number of edges of $\widehat{G}_{t}$, we can use deterministic results to
bound the number of triangles, which by its turn can provide an upper bound
for the order of the largest clique. The upper bound on the number of edges in
$\widehat{G}_{t}$ requires a sharp upper bound for vertices degree and for the
number of edges between two vertices. The upper bound on the number of edges
between vertices is obtained using a method inspired by the martingale methods
used in the analysis of vertices’ degree in the literature of preferential
attachment random graphs.

##  2\. A Grand Coupling: The doubly-labeled random tree process

In this section we introduce a stochastic process
$\\{\mathcal{T}_{t}\\}_{t\geq 1}$ that provides a grand coupling between the
random graphs $\\{G_{t}(f)\\}_{t\geq 1}$ for every possible choice of $f$.

The process $\\{\mathcal{T}_{t}\\}_{t\geq 1}$ is essentially a realization of
the Barabási-Albert random tree with the distinction that each vertex has two
labels: an earlier vertex chosen according to the preferential attachment rule
and an independent uniform random variable. The label consisting in the
earlier vertex can be seen as a “ghost directed edge”, we later use these
random labels to collapse subsets of vertices into a single vertex in order to
obtain a graph with the same distribution as $G_{t}(f)$ for any prescribed
function $f$.

We begin our process with a graph $\mathcal{T}_{1}$ consisting as usual in a
single vertex and a single loop connecting said vertex to itself. We then
inductively construct the labeled graph $\mathcal{T}_{t+1}$ from
$\mathcal{T}_{t}$ in the following way:

Figure 1. A sample of the process $\\{\mathcal{T}_{t}\\}_{t\geq 1}$ up to time
$6$ without the uniform labels. The dashed lines indicate the label
$\ell(v_{j})$ taken by each vertex $v_{j}$.

  * (i)

We add to $\mathcal{T}_{t}$ a vertex $v_{t+1}$;

  * (ii)

We tag $v_{t+1}$ with a random label $\ell(v_{t+1})$ chosen from the set
$V(\mathcal{T}_{t})$ with the preferential attachment rule, that is, with
probability of choosing $u\in V(\mathcal{T}_{t})$ proportional to the degree
of $u$ in $\mathcal{T}_{t}$;

  * (iii)

Independently from the step above, we add an edge $\\{w,v_{t+1}\\}$ to
$E(\mathcal{T}_{t})$ where $w\in V(\mathcal{T}_{t})$ is also randomly chosen
according to the preferential attachment rule, see Figure 2.

We then finish the construction by tagging each vertex $v_{j}\in
V(\mathcal{T}_{t})$ with a second label consisting in an independent random
variable $U_{j}$ with uniform distribution on the interval $[0,1]$, as shown
in Figure 2. We note that only the actual edges contribute to the degree taken
in consideration in the preferential attachment rule, the tags are not
considered.

We now make precise the notation $f(\mathcal{T}_{t})$ which indicates that a
function $f$ may also be seen as a function that maps a doubly-labeled tree to
a (multi)graph. Our goal is to define this map in such way that
$f(\mathcal{T}_{t})\stackrel{{\scriptstyle d}}{{=}}G_{t}(f)$.

In order to do so, let us fix such a function $f$. Given $v_{j}\in
V(\mathcal{T}_{t})$, we compare $U_{j}$ to $f(j)$. If $U_{j}\leq f(j)$, we do
nothing. Otherwise, we collapse $v_{j}$ onto its label $\ell(v_{j})$, that is,
we consider the set $\\{v_{j},\ell(v_{j})\\}$ to be a single vertex with the
same labels as $\ell(v_{j})$. We then update the label of all vertices $v$
such that $\ell(v)=v_{j}$ to $\\{v_{j},\ell(v_{j})\\}$. This procedure is
associative in the sense that the order of the vertices on which we perform
this operation does not affect the final resulting graph, as long as we
perform it for all the vertices of $\mathcal{T}_{t}$. We let then
$f(\mathcal{T}_{t})$ be the (multi)graph obtained when this procedure has run
over all the $t$ vertices of $\mathcal{T}_{t}$. We refer to Figure 2 as an
illustration of the final outcome.

In the next proposition we prove that $f(\mathcal{T}_{t})$ is indeed
distributed as $G_{t}(f)$.

Figure 2. On the left, the graph $\mathcal{T}_{6}$, where each vertex receives
an independent uniform random variable label. On the right, how one can sample
the distribution of $G_{6}(f)$ using the $\mathcal{T}_{6}$.

######  Proposition 2.1.

Let $\mathcal{T}_{t}$ be the doubly-labeled tree above defined. Then,

$f(\mathcal{T}_{t})\stackrel{{\scriptstyle d}}{{=}}G_{t}(f).$

###### Proof.

We first observe that the associativity of the collapsing operation and the
independence of the sequence $\\{U_{j}\\}_{j\geq 1}$ from the previous
operations imply that we can glue together the vertex $v_{t+1}$ to
$\ell(v_{t+1})$ whenever $U_{t+1}>f(t+1)$ right after we complete step (iii)
of the above construction by induction. The resulting graph has either a new
vertex $v_{t+1}$ with an edge $\\{w(v_{t+1}),v_{t+1}\\}$ or an edge
$\\{w(v_{t+1}),\ell(v_{t+1})\\}$ with the exact same probability distribution
as the $(t+1)$-th step in the construction of the graph $(G_{t}(f))_{t\geq
1}$. By induction, both random graphs have the same distribution.

##  3\. Applications of The Grand Coupling

In the light of the Section 2 and Proposition 2.1, throughout this section, we
will tacitly assume that all processes of the form $\\{G_{t}(f)\\}_{t\geq 1}$
for all possible functions $f$ are on the same probability space provided by
our previous results.

A straightforward consequence of Proposition 2.1 is Theorem 4 which roughly
speaking states that functions close to each other in the
$L_{1}(\mathbb{N})$-norm generate essentially the same processes. Once we have
the machinery provided by Proposition 2.1, the proof of this fact becomes a
simple application of the union bound.

###### Proof of Theorem 4.

Fixed two possible functions $f$ and $h$, by Proposition 2.1 we have that

(3.1) $\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq
1})=\mathrm{Law}(\\{f(\mathcal{T}_{t})\\}_{t\geq 1}).$

Thus

(3.2) $\begin{split}\mathrm{dist}_{TV}\left(\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq
1}),\mathrm{Law}(\\{G_{t}(h)\\}_{t\geq
1})\right)&\leq{\mathbb{P}}\left(\\{f(\mathcal{T}_{t})\\}_{t\geq
1}\neq\\{h(\mathcal{T}_{t})\\}_{t\geq 1}\right)\\\
&\leq\sum_{i=1}^{\infty}{\mathbb{P}}\left(U_{i}\in(f(i)\wedge h(i),f(i)\vee
h(i))\right)\\\ &=\sum_{i=1}^{\infty}|f(i)-g(i)|\\\ &=\|f-g\|_{1},\end{split}$

and the above equation immediately implies (1.7).

###  3.1. Monotone Statistics

The next step is to use the coupling provided by the doubly-labeled random
tree process to compare statistics of graphs generated by different functions.
This method will allow us to transport results we have obtained for a fixed
$f$ to other edge-step functions by comparing them with $f$. To do this we
introduce the notion of increasing (decreasing) graph observable.

######  Definition 1 (Monotone Statistics).

We say that a (multi)graph statistic $\zeta$ is increasing if, given two edge-
step functions $f$ and $h$, we have that

(3.3) $f(s)\leq h(s),\forall s\leq
t\implies\zeta(f(\mathcal{T}_{t}))\leq\zeta(h(\mathcal{T}_{t}))\;\textit{a.s.}$

When the second inequality in (3.3) holds with “$\geq$”, we say $\zeta$ is
decreasing.

A first example of an increasing statistic is the total number of vertices.
Indeed, since every vertex $v_{j}$ of $\mathcal{T}_{t}$ remain preserved under
$f$ whenever its $U_{j}$ label is less than $f(j)$, it follows that every
$f$-preserved $v_{j}$ is $h$-preserved as well.

The next proposition states that the maximum degree is a decreasing statistic
whereas the diameter is an increasing one.

######  Proposition 3.4.

Let $f$ and $h$ be two functions satisfying the relation $f(s)\leq h(s)$ for
all $s\in(1,\infty)$. Then,

  1. (a)

the maximum degree is a _decreasing_ graph statistic. More precisely, if we
let $D_{\textit{max}}(G)$ denote the maximum degree of a (multi)graph $G$,
then

${\mathbb{P}}\left(\forall t\in\mathbb{N},\;D_{\textit{max}}(G_{t}(f))\geq
D_{\textit{max}}(G_{t}(h))\right)=1;$

  2. (b)

the diameter is an _increasing_ graph statistic. More precisely,

${\mathbb{P}}\left(\forall
t\in\mathbb{N},\;\mathrm{diam}(G_{t}(f))\leq\mathrm{diam}(G_{t}(h))\right)=1$

###### Proof.

The proofs follow from an analysis of the action of $f$ over
$\mathcal{T}_{t}$.

Proof of part (a): Given a vertex $v\in f(\mathcal{T}_{t})$ we let
$\mathsf{solid}$-$\mathsf{neighbors}(v)$ be the set of its neighbors in
$\mathcal{T}_{t}$ (that is, vertices sharing a solid edge with it, which would
come from a vertex-step). We also define the set
$\mathsf{dashed}$-$\mathsf{neighbors}(v)$ as the vertices $v_{s}$ in
$\mathcal{T}_{t}$ with label $\ell$ pointing to $v$ and whose corresponding
uniform label $U_{s}$ is larger than $f(s)$. To find the degree $D_{t}(v)$ of
$v$ in $f(\mathcal{T}_{t})$, one performs the following computation:

  * •

initialize $D_{t}(v)$ as the cardinality of
$\mathsf{solid}$-$\mathsf{neighbors}(v)$ and the set
$\mathsf{to}$-$\mathsf{explore}$ as $\mathsf{dashed}$-$\mathsf{neighbors}(v)$;

  * •

sequentially in some arbitrary order, for every
$w\in\mathsf{to}$-$\mathsf{explore}$, sum the cardinality of
$\mathsf{solid}$-$\mathsf{neighbors}(w)$ to $D_{t}(v)$ and add the vertices of
$\mathsf{dashed}$-$\mathsf{neighbors}(w)$ to $\mathsf{to}$-$\mathsf{explore}$;

  * •

repeat the above until no more vertices are in
$\mathsf{to}$-$\mathsf{explore}$.

In other words, given the directed tree with $v$ as the root, and edges coming
from labels that become edge-steps after the action of $f$, we perform a
graph-search algorithm, like breadth-first search, and sum the
$\mathcal{T}_{t}$-degree of each queried vertex. Note that each vertex of
$\mathcal{T}_{t}$ can be accounted for multiple times in this procedure when
we sum the degree in $\mathcal{T}_{t}$. This algorithm does yield the degree
of vertex $v$, as there is a bijection between each half-edge incident to $v$
in $f(\mathcal{T}_{t})$ and the multiset of vertices of $\mathcal{T}_{t}$ in
$\mathsf{solid}$-$\mathsf{neighbors}(w)$ as we explore vertices
$w\in\mathsf{to}$-$\mathsf{explore}$.

Now we note that if $f(s)\leq h(s)$ for all $s$, the
$\mathsf{dashed}$-$\mathsf{neighbors}$-directed tree associated to the
algorithm that discovers the degree of a vertex $v$ in $f(\mathcal{T}_{t})$
contains the tree that discovers the degree of the same vertex in
$h(\mathcal{T}_{t})$. So if $v_{s}$ is the vertex with maximum degree in
$h(\mathcal{T}_{t})$, and its associated uniform is larger than $f(s)$, by
direct comparison we obtain the result. If not, then this means that $v_{s}$
will be collapsed into some vertex $w\in f(\mathcal{T}_{t})$, and the tree
from the degree-discovering algorithm for this vertex will contain the tree
associated to $v_{s}\in h(\mathcal{T}_{t})$. This finishes the proof of part
(a).

Proof of part (b): Observe that if $u$ and $w$ are vertices whose $U$-label is
less than $f$ and such that $u\leftrightarrow w$ in $G_{t}(f)$, then $u$ and
$w$ are possibly not connected by a single edge in $G_{t}(h)$, in other words,
if $\mathrm{dist}_{G_{t}(f)}(u,w)=1$ then $\mathrm{dist}_{G_{t}(h)}(u,w)\geq
1$. Therefore, if $v_{0}=u,v_{1},\cdots,v_{k}=w$ is a minimal path in
$G_{t}(f)$, by the previous observation, this path induces a path in
$G_{t}(h)$ whose length is equal to or greater than $k$.

On the other hand, if $u=v_{0},v_{1},\cdots,v_{k}=w$ is a path realizing the
minimal distance between $u$ and $w$, in $G_{t}(h)$ we have that this path
induces another path in $G_{t}(f)$ of same length or less. To see this, just
notice that, if $U_{j}>f(j)$ and $\ell(v_{j})$ points to a vertex outside the
path for some $j\in\\{2,3,\cdots,k-1\\}$, then, after identifying $v_{j}$ to
its $\ell$-label, this operation does not increase the path length. This is
enough to conclude the proof.

Having small diameter, typically $\log$ of the number of nodes, is a feature
shared by several real-life networks, as observed by S. Strogatz and D. J.
Watts in [24], where the coined the term ‘small-world’ networks. Thus
investigating the order of the diameter is vital for models whose purpose
might be modeling real-life networks.

In [4], the authors showed a characterization of the diameter of $G_{t}(f)$
for regularly varying function $f$ in terms of the index of regular variation.
The proposition below offers a universal upper bound that guarantees that
$G_{t}(f)$ is small-world for any choice of $f$.

######  Proposition 3.5 (Universal Upper bound for the Diameter).

There exists a universal constant $c$ such that

${\mathbb{P}}\left(\mathrm{diam}(G_{t}(f))\leq c\log t\right)=1-o(1).$

###### Proof.

The proof follows from item (b) of Proposition 3.4 and known results for the
classical preferential attachment model. Indeed, in [12], B. Bollobás and O.
Riordan proved that for $f\equiv 1$ the diameter of $G_{t}(f)$ is bounded from
above by $c\log t$ asymptotically almost surely. Since $f$ is bounded by $1$,
a combination of this result with item (b) of Proposition 3.4 proves the
result.

##  4\. Proof of Theorem 1: existence of large cliques

In this section we keep exploring the machinery developed in previous
sections. Here, we transfer the existence of large cliques using the function
itself, i.e., if $h$ is such that $G_{t}(h)$ has a clique of order $K$ and $f$
another function satisfying $f(s)\leq h(s)$ for all $s\in(1,\infty)$, then the
clique existence propagates to $G_{t}(f)$ too but with a possibly
$f$-dependent order.

We will let $G_{t}(p)$ be the graph generated by $f\equiv p\in(0,1)$ and we
will let $\omega_{t}(p)$ be the clique number of $G_{t}(p)$. And for the sake
of convenience, we state the result about $\omega_{t}(p)$.

######  Theorem 1 (Theorem $1$ from [1]).

For any $\varepsilon>0$ and every $p\in(0,1)$, it follows that

(4.1) ${\mathbb{P}}\left(\omega_{t}(p)\geq
t^{(1-\varepsilon)\frac{1-p}{2-p}}\right)=1-o(1).$

We can now use the doubly-labeled tree together with the above results in
order to prove Theorem 1. In order to avoid clutter, let us introduce a new
notation for the expected number of vertices,

(4.2) $F(t):={\mathbb{E}}[|G_{t}(f)|]=1+\sum_{s=2}^{t}f(s).$

In order to formalize the strategy of transporting a clique in $G_{t}(p)$ down
to $G_{t}(f)$ it will be important to control the time the $j$-th vertex of
$G_{t}(p)$ is added. In our proof, we essentially condition on the existence
of a large clique in $G_{t}(p)$ and then using the independence of the
$U$-labels we pay a $f$-dependent price to guarantee that part of the cliques’
vertices are also a vertex in $G_{t}(f)$. However, if the vertices in the
clique took too long to be added, then the $f$-price we pay to force them to
be vertices in $G_{t}(f)$ as well is too expensive. This would result in a
much smaller clique in $G_{t}(f)$.

Consequently, it will be important to use the fact that for the process
$\\{G_{t}(p)\\}_{t\geq 0}$, does not take too much time between vertices
addition, since the time interval between the addition of any two vertices
follows a geometric distribution of parameter $p$. We can formalize this by
defining inductively the following sequence of stopping times, let
$\tau_{0}(p)\equiv 0$ and define $\tau_{k}(p)$ as below

$\tau_{k}(p):=\inf\\{n\geq\tau_{k-1}(p)\;:\;U_{n}\leq p\\}.$

Then, noticing that $\tau_{k}(p)-\tau_{k-1}(p)\sim Geo(p)$ for any $k>0$ we
have that

(4.3) ${\mathbb{P}}\left(\tau_{k}(p)-\tau_{k-1}(p)\geq\frac{10\log
t}{\log(1/(1-p))}\right)\leq t^{-10}.$

The above bound will give us control over the time vertices have been added by
the process $\\{G_{t}(p)\\}_{t\geq 0}$. With the discussed above we prove the
main result of this section.

###### Proof of Theorem 1.

Given $\delta>0$ sufficiently small, We begin by letting $\varepsilon$ be
small enough and setting $p=\delta/6$ so that

$\alpha=\alpha(p,\varepsilon):=\frac{1-p}{2-p}(1-\varepsilon)>\frac{1}{2}\left(1-\frac{\delta}{2}\right).$

In the proof of Theorem $1$ of [1] one uses Theorem $2$ of [1] to show that
for any $\varepsilon^{\prime}\in(0,\alpha)$ there exists a fixed integer
$m=m(\varepsilon,\varepsilon^{\prime},p)>0$ with the following property: if
one divides the set of vertices added by the process $\\{G_{t}(p)\\}_{t\geq
1}$ up to time $t$ into disjoint subsets of $m$ vertices born _consecutively_
, then with high probability (at least $1$ minus a polynomial function of $t$)
from the $t^{\varepsilon^{\prime}}$-th subset to the $t^{\alpha}/m$-th one, we
can select one vertex in each subset in such a way that the subgraph induced
by the set of chosen vertices is a complete subgraph of $G_{t}(p)$. These
vertices are the leaders of their block.

Let $\mathcal{K}$ be the random set formed by the leader vertices of the
$t^{\varepsilon^{\prime}}$-th to the $t^{\alpha}/m$-th blocks of $m$ vertices,
which form a clique in $G_{t}(p)$ w.h.p. Observe that in the event these
vertices do not form a clique or do not exist $t^{\alpha}/m$ blocks of $m$
vertices the random set $\mathcal{K}$ is empty.

Now, let $N$ be the following random variable

(4.4) $N:=\sum_{v_{j}\in\mathcal{K}}\mathbb{1}\left\\{U_{j}\leq
f(j)\right\\}.$

In words, $N$ counts how many leading vertices become a vertex of $G_{t}(f)$
as well. Here, we adopt the convention that a sum over an empty set of indexes
is zero.

To avoid clutter, let us write $k=t^{\alpha}/m$. Given a set of vertices
$S=\\{v_{t_{1}},\dots,v_{t_{k}}\\}$ in $G_{t}(p)$ the event
$\\{\mathcal{K}=S\\}$ then means the vertices $v_{t_{j}}$, for
$j\in\\{1,\dots,k\\}$ are all vertices of $G_{t}(p)$ and they are all
connected between themselves in $G_{t}(p)$. Thus, due to independent nature of
the $U$-label assignments in the doubly-labeled random tree process the
following identify holds

(4.5) ${\mathbb{P}}\left(U_{t_{j}}\leq
f(t_{j})\mid\mathcal{K}=S\right)=p^{-1}f(t_{j}).$

Additionally, we call $S$ good if

$v_{t_{j}}\in S\implies t_{j}\leq c_{1}j\cdot m\cdot\log t,$

where $c_{1}=10\log(1/(1-p))$. In words, a good set of vertices in $G_{t}(p)$
are those whose vertices did not take too much time to be added by the process
$\\{G_{t}(p)\\}_{t\geq 0}$. Observe that by (4.3) and union bound over the
number of vertices yields

(4.6) ${\mathbb{P}}\left(\exists S\subset G_{t}(p)\;:\;S\text{ is bad
}\right)\leq t^{-9}.$

Having the above in mind and letting $m$ be the auxiliary $m$ that appears in
proof of Theorem 1 of [1], define the following event

(4.7)
$A_{p,\varepsilon^{\prime},m,k}:=\left\\{\begin{array}[]{c}\exists\\{s_{1},\cdots,s_{k}\\}\subset\\{t^{\varepsilon^{\prime}},\dots,c_{1}m(t^{\alpha}+t^{\varepsilon^{\prime}})\log
t\\}\text{ such that }\\\ v_{s_{j}}\leftrightarrow v_{s_{i}}\text{ in
}G_{t}(p)\text{ for all }i,j\in[k]\end{array}\right\\}.$

In the context of the doubly labeled tree process, the event
$A_{p,\varepsilon^{\prime},m,k}$ says that we may find a subset of $k$
vertices of $\mathcal{T}_{t}$, all added between times
$t^{\varepsilon^{\prime}}$ and
$c_{1}m(t^{\alpha}+t^{\varepsilon^{\prime}})\log t$, with the property that
the $j$-th vertex $v_{t_{j}}$ of this subset has its $U_{t_{j}}$-label smaller
than $p$. Moreover, when we apply a constant function equals $p$ on
$\mathcal{T}_{t}$ in the event $A_{p,\varepsilon^{\prime},m,k}$, all these $k$
vertices form a complete graph in the resulting graph $G_{t}(p)$.

Theorem $1$ of [1] states that setting $k=t^{\alpha}/m$, the event
$A_{p,\varepsilon^{\prime},m,k}$ occurs with probability at least
$1-t^{-\eta}$, for some positive small $\eta$ depending on $p$, which, in our
case, is a function of $\delta$. Thus, for $t$ large enough, we may simply use
that

(4.8) ${\mathbb{P}}\left(A_{p,\varepsilon^{\prime},m,t^{\alpha}/m}\right)\geq
1-\frac{1}{\log t},$

this bound is good enough to prove Corollary 1.3. This is why we are
exchanging a polynomial decay by a $\log$ one, to get rid off the dependency
on $\delta$ and consequently simplify latter arguments.

Now, using identify (4.5), the definition of good set and the fact that $f$ is
decreasing, we have that

(4.9) $\begin{split}{\mathbb{E}}\left[N\;\middle|\;\mathcal{K}=S,S\text{ is
good }\right]&=p^{-1}\sum_{v_{t_{j}}\in S}f(t_{j})\geq
p^{-1}\sum_{j=t^{\varepsilon^{\prime}}}^{t^{\alpha}/m}f(c_{1}mj\log t)\\\
&\geq\frac{F(c_{1}t^{\alpha}\log t)-F(c_{1}mt^{\varepsilon^{\prime}}\log
t)}{pc_{1}m\log t}\\\ &\geq\frac{c_{2}F(c_{1}t^{\alpha}\log t)}{\log
t}.\end{split}$

For some positive constant $c_{2}$ depending on $\varepsilon^{\prime},\delta$
and $f$. Moreover, using that the $U$-labels are independent and Chernoff
bounds

(4.10) ${\mathbb{P}}\left(N\leq\frac{c_{2}F(c_{1}t^{\alpha}\log t)}{2\log
t}\,\middle|\,\mathcal{K}=S,S\text{ is good
}\right)\leq\exp\left\\{-\frac{c_{2}F(c_{1}t^{\alpha}\log t)}{4\log
t}\right\\}.$

And in order to simplify our writing, let $B$ be the following event

(4.11) $B:=\left\\{\nexists S\subset G_{t}(p),S\text{ is bad }\right\\}.$

In the event $B$, all vertices added by the process $\\{G_{t}(p)\\}_{t\geq 0}$
did not take too long to be added. That is, the $j$-th vertex added by the
process $\\{G_{t}(p)\\}_{t\geq 0}$ was added before time $c_{1}mj\log t$. Also
notice that by equation (4.3), ${\mathbb{P}}(B^{c})\leq t^{-9}$.

Furthermore, we have the following identity of events

(4.12) $A_{p,\varepsilon^{\prime},m,t^{\alpha}/m}\cap
B=\left\\{\mathcal{K}\neq\emptyset,\mathcal{K}\text{ is good }\right\\}$

and for each good $S\subset G_{t}(p)$ we use $\mathcal{K}(S)$ as a shorthand
for

$\mathcal{K}(S):=\left\\{\mathcal{K}=S,S\text{ is good }\right\\}.$

Then, using Equation (4.10) and summing over all possible good subsets $S$, we
have

$\begin{split}{\mathbb{P}}\left(N\leq\frac{c_{2}F(c_{1}t^{\alpha}\log
t)}{2\log
t},A_{p,\varepsilon^{\prime},m,t^{\alpha}/m},B\right)&=\sum_{S}{\mathbb{P}}\left(N\leq\frac{c_{2}F(c_{1}t^{\alpha}\log
t)}{2\log
t}\,\middle|\,\mathcal{K}(S)\right){\mathbb{P}}\left(\mathcal{K}(S)\right)\\\
&\leq\exp\left\\{-\frac{c_{2}F(c_{1}t^{\alpha}\log t)}{4\log
t}\right\\}{\mathbb{P}}\left(\mathcal{K}\neq\emptyset,\mathcal{K}\text{ is
good }\right).\end{split}$

We then obtain the following bound

(4.13) $\begin{split}{\mathbb{P}}\left(N\leq\frac{c_{2}F(c_{1}t^{\alpha}\log
t)}{2\log
t}\right)&\leq{\mathbb{P}}\left(N\leq\frac{c_{2}F(c_{1}t^{\alpha}\log
t)}{2\log
t},A_{p,\varepsilon^{\prime},m,t^{\alpha}/m},B\right)+{\mathbb{P}}\left(A^{c}_{p,\varepsilon^{\prime},m,t^{\alpha}/m}\cup
B^{c}\right)\\\ &\leq\exp\left\\{-\frac{c_{2}F(c_{1}t^{\alpha}\log t)}{4\log
t}\right\\}+\frac{2}{\log t},\end{split}$

which proves the theorem.

##  5\. Proof of Theorems 2 and 3: clique number and clustering

In this section we will prove our other two main theorems, which give sharp
bounds on the global clustering coefficient and the clique number. Recall that
the global clustering coefficient of $G_{t}(f)$ is defined as

(5.1) $c^{\rm glob}_{t}=c^{\rm
glob}(G_{t}(f))=3\times\frac{\Delta(G_{t}(f))}{\Lambda(G_{t}(f))}.$

For the proof of both theorems will need the bounds on $\Delta(G_{t}(f))$ and
$\Lambda(G_{t}(f))$ given by the results below.

######  Theorem 1 (Number of Triangles).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, for any
$\delta>0$ there exist positive constants $C,C^{\prime}$ and
$C^{\prime\prime}$ depending on $f$ and $\delta$, such that for all $t$

${\mathbb{P}}\left(C^{\prime}t^{\frac{3(1-\gamma)(1-\delta)}{2}}\leq\Delta(G_{t}(f))\leq
Ct^{\frac{3(1-\gamma)(1+\delta)}{2}}\right)\geq
1-\frac{C^{\prime\prime}}{\log(t)}.$

######  Theorem 2 (Number of Cherries).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, for any
$\delta>0$ there exist positive constants $C,C^{\prime}$ and
$C^{\prime\prime}$ depending on $f$ and $\delta$, such that for all $t$

${\mathbb{P}}\left(C^{\prime}t^{2(1-\gamma)(1-\delta)}\leq\Lambda(G_{t}(f))\leq
Ct^{2(1-\gamma)(1+\delta)}\right)\geq 1-\frac{C^{\prime\prime}}{\log(t)}.$

We will postpone their proofs to Section 6. For now, we will just focus on how
to use them to obtain our two main theorems.

###### Proof of Theorem 2 (Clique Number).

We will start by the lower bound.

Lower bound. Recall that we already have proven Theorem 1 which provides a
general lower bound for $\omega_{t}$ in terms of ${\mathbb{E}}[|G_{t}|]$ when
$f$ is decreasing to zero only. Thus, the lower bound part of Theorem 2 is a
particular case of Theorem 1 when $f$ is also regularly varying. Thus, this
part of the proof consists essentially of analytical arguments to obtain
estimates on ${\mathbb{E}}[|G_{t}|]$ itself.

With the above discussion in mind and given $\delta\in(0,1)$, set
$\delta^{\prime}=\delta+\varepsilon$ for some auxiliary $\varepsilon$ to be
adjusted later and small enough so $\delta^{\prime}\in(0,1)$. By Theorem 1, we
have that for every $\delta^{\prime}\in(0,1)$, there exist positive constants
$c_{1}$ and $c_{2}$ depending on $\delta^{\prime}$ and $f$ only such that

(5.2)
${\mathbb{P}}\left(\omega_{t}\geq\frac{c_{2}F(t^{(1-\delta^{\prime})/2})}{\log
t}\right)\geq 1-\frac{2}{\log
t}-\exp\left\\{-\frac{c_{2}F(c_{1}t^{(1-\delta^{\prime})/2}\log t)}{4\log
t}\right\\}.$

Since $f$ is a decreasing to zero, we also have that

(5.3) ${\mathbb{E}}[|G_{t}|]=F(t)=1+\sum_{s=2}^{t}f(s)\geq\int_{2}^{t}f(x){\rm
d}x.$

On the other hand, using that $f$ is a regularly varying function at infinity
with index $-\gamma$, where $\gamma\in[0,1)$, Theorem 1 gives us that $f(t)$
can be written as $f(t)=\frac{\ell(t)}{t^{\gamma}}$, where $\ell$ is a slowly
varying function. Thus, by Proposition A.2, we have that

$\lim_{t\to\infty}\frac{\int_{2}^{t}f(x){\rm
d}x}{t^{1-\gamma}\ell(t)}=\frac{1}{1-\gamma},$

which by its turn implies the existence of a positive and $f$-dependent
constant $C$ such that

(5.4) $\int_{2}^{t}f(x){\rm d}x\geq Ct^{1-\gamma}\ell(t),$

for all $t$. Plugging the above inequality into (5.3) yields

(5.5) $\frac{c_{2}F(t^{(1-\delta^{\prime})/2})}{\log
t}\geq\frac{C\ell(t^{(1-\delta^{\prime})/2})t^{(1-\delta^{\prime})(1-\gamma)/2}}{\log
t}.$

Notice then that, for any $\varepsilon>0$, Proposition A.1 allows us to
replace the slowly varying functions in the RHS of the above inequality by a
polynomial factor of $t$, at the expenses of a possibly different $C$, to
obtain a nicer lower bound as the one below

$\frac{C\ell(t^{(1-\delta^{\prime})/2})t^{(1-\delta^{\prime})(1-\gamma^{\prime})/2}}{\log
t}\geq
Ct^{(1-\delta^{\prime}-\varepsilon)(1-\gamma)/2}=Ct^{(1-\delta)(1-\gamma)/2}$

Returning to (5.2), we have that there exists a positive constant $c_{3}$
depending on $f,\delta$ and $\varepsilon$ such that

${\mathbb{P}}\left(\omega_{t}\geq
Ct^{(1-\delta)(1-\gamma)/2}\right)\geq{\mathbb{P}}\left(\omega_{t}\geq\frac{c_{2}F(t^{(1-\delta^{\prime})/2})}{\log
t}\right)\geq 1-\frac{c_{3}}{\log t},$

which is enough to conclude this part of the proof.

The proof will then be completed when we finish the upper bound.

Upper bound. Recall that by Theorem 1, it follows that for any $\delta>0$
there exist positive constants $C$ and $C^{\prime\prime}$ depending on $f$ and
$\delta$, such that for all $t$

(5.6) ${\mathbb{P}}\left(\Delta(G_{t}(f))\geq
Ct^{\frac{3(1-\gamma)(1+\delta)}{2}}\right)\leq\frac{C^{\prime\prime}}{\log(t)}.$

But notice that if $\omega_{t}\geq Ct^{\frac{(1-\gamma)(1+\delta)}{2}}$, then
$\Delta(G_{t}(f))\geq Ct^{\frac{3(1-\gamma)(1+\delta)}{2}}$ for some possibly
different constant $C$. This implies the following inclusion of events

$\left\\{\omega_{t}\geq
Ct^{\frac{(1-\gamma)(1+\delta)}{2}}\right\\}\subset\left\\{\Delta(G_{t}(f))\geq
Ct^{\frac{3(1-\gamma)(1+\delta)}{2}}\right\\},$

which combined to (5.6) gives us the desired upper bound w.h.p. and allows us
to conclude the proof of Theorem 2.

Now we move to the proof of our second main result of this section.

###### Proof of Theorem 3(Clustering Coefficient).

Notice that the proof is a straightforward consequence of Theorems 1 and 2
together with the definition of $c^{\rm glob}_{t}$.

By Theorem 1, for any fixed $\delta\in(0,1)$, we have that with probability at
least $1-C^{\prime}/\log t$, $\Delta(G_{t}(f))\leq
Ct^{3(1-\gamma)(1+\delta)/2}$. Whereas, by Theorem 2, $\omega_{t}\geq
Ct^{2(1-\gamma)(1-\delta)}$, with probability at least $1-C^{\prime}/\log t$.
These two results combined, gives us that

$c^{\rm glob}_{t}\leq
C\times\frac{t^{3(1-\gamma)(1+\delta)/2}}{t^{2(1-\gamma)(1-\delta)}},$

with probability at least $1-C^{\prime}/\log t$, for some constant
$C^{\prime}$ depending on $\delta$ and $f$. This gives the desired upper
bound. The lower bound is obtained similarly.

###  5.1. Convergence Theorems and the Inverse Relation

With the concentration inequalities for the clique number and global
clustering given by Theorems 2 and Theorem 3, respectively, we will show
almost surely convergence in the log scale of these statistics properly
normalized.

###### Proof of Corollary 1.3: Convergence of the clique number.

We would like to show that

(5.7) $\lim_{t\to\infty}\frac{\log(\omega_{t})}{\log
t}=\frac{1-\gamma}{2},\,\text{a.s.},$

when $f$ decreases to zero and is a regularly varying function at infinity
with index $-\gamma$, with $\gamma\in[0,1)$.

The proof will involve passing to a subsequence of $\\{\log(\omega_{t})/\log
t\\}_{t\in\mathbb{N}}$ and then using monotonicity of $\omega_{t}$ and $\log
t$. In order to do so, notice that by Theorem 2, for every $\delta\in(0,1)$,
there exist positive constants $c_{1},c_{2}$ and $c_{3}$ depending on $\delta$
only such that

${\mathbb{P}}\left(c_{1}t^{(1-\gamma)(1-\delta)/2}\leq\omega_{t}\leq
c_{2}t^{(1-\gamma)(1+\delta)/2}\right)\geq 1-\frac{c_{3}}{\log t}.$

The above result guarantees that for fixed $\delta$ and any $k\in\mathbb{N}$,
it follows that

(5.8) ${\mathbb{P}}\left(\frac{\log(\omega(G_{2^{k^{2}}}(f)))}{k^{2}\log
2}\leq\frac{(1-\gamma)(1-\delta)}{2}+\frac{\log c_{1}}{k^{2}\log
2}\right)\leq\frac{c_{3}}{k^{2}\log 2}.$

Similarly, we also have that

(5.9) ${\mathbb{P}}\left(\frac{\log(\omega(G_{2^{k^{2}}}(f)))}{k^{2}\log
2}\geq\frac{(1-\gamma)(1+\delta)}{2}+\frac{\log c_{2}}{k^{2}\log
2}\right)\leq\frac{c_{3}}{k^{2}\log 2}.$

Passing to the subsequence $\\{\log(\omega(G_{2^{k^{2}}}(f)))/k^{2}\log
2\\}_{k\in\mathbb{N}}$, we can combine (5.8) and (5.9) to Borel-Cantelli lemma
to obtain that

(5.10) $\lim_{k\to\infty}\frac{\log(\omega(G_{2^{k^{2}}}(f)))}{k^{2}\log
2}=\frac{1-\gamma}{2},\text{a.s.},$

since (5.8) and (5.9) hold for any $\delta\in(0,1)$ with possibly different
constants $c_{1},c_{2}$ and $c_{3}$.

Finally, using that both $\log t$ and $\omega_{t}$ are increasing on $t$, we
have that for any $t\in[2^{k^{2}},2^{(k+1)^{2}}]$, the following inequalities
hold

(5.11) $\frac{\omega(G_{2^{k^{2}}}(f))}{(k+1)^{2}\log
2}\leq\frac{\omega_{t}}{\log
t}\leq\frac{\omega(G_{2^{(k+1)^{2}}}(f))}{k^{2}\log 2}.$

With the above inequalities, (5.10) and the Squeeze Theorem, one can show that
the whole sequence $\\{\log(\omega_{t})/\log t\\}_{t\in\mathbb{N}}$ converges
to $\frac{1-\gamma}{2}$ almost surely.

We now prove similar result for the global clustering coefficient.

###### Proof of Corollary 1.4: Convergence of the Clustering Coefficient.

The proof of Corollary 1.4 is almost in line with the proof of Corollary 1.3,
for this reason we will just indicate how it follows from Corollary 1.3 proof.

From the definition of $c^{\rm glob}_{t}$ and properties of the $\log$, it
folows that

(5.12) $\frac{\log c^{\rm glob}_{t}}{\log t}=\frac{\log 3}{\log
t}+\frac{\log\Delta(G_{t}(f))}{\log t}-\frac{\log\Lambda(G_{t}(f))}{\log t}.$

Observe that both statistics $\Delta(G_{t}(f))$ and $\Lambda(G_{t}(f))$ are
increasing in time. Moreover, Theorems 1 and 2 provides bounds for the
probability of the same order as Theorem 2. Thus, the same argument of passing
to a subsequence and using Borel-Cantelli holds, which allow one to obtain
that

$\lim_{t\to\infty}\frac{\log\Delta(G_{t}(f))}{\log
t}=\frac{3(1-\gamma)}{2},\,\text{a.s.,}$

and that

$\lim_{t\to\infty}\frac{\log\Lambda(G_{t}(f))}{\log
t}=2(1-\gamma),\,\text{a.s.}$

Plugging the two above equality back into (5.12) is enough to conclude the
proof.

Finally, the proof of the inverse relation between clustering and clique
number.

###### Proof of Corollary 1.5.

Up to this point, with the results we have proven, the proof of Corollary 1.5
follows directly from Theorems 2 and 3. By Theorem 2, with probability at
least $1-c/\log(t)$ we have that

$c_{1}t^{(1-\gamma)(1-\delta)/2}\leq\omega_{t}\leq
c_{2}t^{(1-\gamma)(1+\delta)/2}$

and by Theorem 3, with probability at least $1-c/\log t$,

$c_{1}t^{-(1-\gamma)(1+\delta)/2}\leq c^{\rm glob}_{t}\leq
c_{2}t^{-(1-\gamma)(1-\delta)/2}.$

Adjusting the $\delta$’s properly and combining the above results finishes the
proof.

##  6\. Proof of Theorems 1 and 2: Number of Triangles and Cherries

In this section we will provide bounds on the number of triangles and cherries
both counted without multiplicities.

For the upper bound for both $\Delta(G)$ and $\Lambda(G)$ we will need the
result below regarding the number of edges in $\widehat{G}_{t}$.

######  Theorem 1 (Number of edges of $\widehat{G}$).

If $f$ decreases to zero and is a regularly varying function at infinity with
index $-\gamma$, with $\gamma\in[0,1)$, then, for every $\delta>0$ there
exists a positive constant $C$ depending on $\gamma$ and $\delta$ only such
that

${\mathbb{E}}\left[\mathcal{E}(\widehat{G}_{t})\right]\leq
Ct^{1-\gamma+\delta}.$

For the sake of readability, we will defer the proof of the above result to
Section 7. In the next two subsections, we will only focus on how to use
Theorem 1 to obtain bounds for the number of triangles and cherries.

###  6.1. Number of Triangles

In this section we provide bounds on the number of triangles. More
specifically, we will prove the following

###### Proof of Theorem 1.

We start by the lower bound.

Lower bound. It will follow from Theorem 2. Recall that if $f$ is a decreasing
regularly varying function with index $-\gamma$, we have that for large enough
$t$

$\frac{F(t)}{\log(t)}\geq Ct^{(1-\gamma)(1-\delta)}$

for some constant $C$ depending on $\gamma$, which implies that

$\frac{F(t^{(1-\delta)/2})}{\log(t)}\geq Ct^{(1-\gamma)(1-\delta)/2}.$

Thus, by Theorem 2, with probability at least $1-3/\log(t)$, there exists a
clique in $G_{t}(f)$ containing at least $Ct^{(1-\gamma)(1-\delta)/2}$
vertices. Consequently, with probability at least $1-3/\log(t)$ we have that

$\Delta(G_{t}(f))\geq Ct^{\frac{3(1-\gamma)(1-\delta)}{2}},$

which gives us the desired lower bound w.h.p.
Upper Bound. By Markov inequality, we have that

(6.1) ${\mathbb{P}}\left(\mathcal{E}(\widehat{G}_{t})\geq
Ct^{1-\gamma+2\delta}\right)\leq\frac{1}{t^{\delta}}.$

On the event inside the probability above, $\widehat{G}_{t}$ is a graph on at
most $t$ vertices and less than $Ct^{1-\gamma+2\delta}$ edges.

Now observe that, by Theorem 4 of [22], the number of triangles in
$\widehat{G}_{t}$ is deterministically bounded by the number of edges to the
power of $3/2$. Combining this to (6.1) gives us that

${\mathbb{P}}\left(\Delta(\widehat{G}_{t})\geq\left(Ct^{1-\gamma+2\delta}\right)^{3/2}\right)\leq\frac{1}{t^{\delta}},$

which is enough to conclude the proof, as $\delta$ is arbitrary.

###  6.2. Number of Cherries

In this section we will provide bounds for $\Lambda_{t}$. Before we start the
proof of Theorem 2, we will need some auxiliary results and notation.

We now let $i,j,k\in\mathbb{N}$ denote respectively the $i$-th, $j$-th, and
$k$-th vertices that are added to $G_{t}(f)$.

The lower bound will follow from a lower bound on some vertex’s degree, which
is proved in [3] but stated below for the reader’s convenience.

######  Lemma 6.1 (Theorem 1 of [3]).

Assume that $f$ goes to zero as $t$ goes to infinity. Then, for every
$N\in\mathbb{N}$, there exists $C_{f}>0$ depending on $f$ only such that

(6.2) $\begin{split}\mathbb{P}\left(\forall s\in\mathbb{N},\exists
i\in\\{1,2,\cdots,N\\}\text{ such that
}D_{s}(i)\geq\frac{\phi(s)}{\phi(N)}\right)&\geq
1-\exp\\{-C_{f}N\\},\end{split}$

where

(6.3)
$\phi(t)=\phi(t,f):=\prod_{s=1}^{t-1}\Big{(}1+\frac{1}{s}-\frac{f(s+1)}{2s}\Big{)}.$

We will need the following technical Lemma on the function $\xi:=\phi(t)/t$:

######  Lemma 6.2 (Lemma 2.2 of [3]).

Let

(6.4)
$\xi(t):=\frac{\phi(t)}{t}=\prod_{s=1}^{t-1}\frac{s}{s+1}\Bigg{(}1+\frac{1}{s}-\frac{f(s+1)}{2s}\Bigg{)}=\prod_{s=1}^{t-1}\Bigg{(}1-\frac{f(s+1)}{2(s+1)}\Bigg{)}$

Then, if $f$ decreases to $0$, $\xi$ is a decreasing slowly varying function
uniformly bounded from above by $1$.

The above lemma together with Proposition A.1 implies that for any $\delta>0$,
there exist a positive constant $C$ depending on $\delta$ and $f$, such that
for all $t\in\mathbb{N}$

(6.5) $Ct^{1-\delta}\leq\phi(t)\leq t.$

With the above discussion in mind, we can now move to the proof of Theorem 2.

###### Proof of Theorem 2.

We will obtain the upper bound first.

Upper Bound. For the upper bound, we use Theorem 1 again. The crucial
observation to be made is that, on the event
$\\{\mathcal{E}(\widehat{G}_{t})\leq C\log(t)t^{1-\gamma+\delta}\\}$, the
graph observable $\Lambda(\widehat{G}_{t})$ is bounded from above by
$\left(C\log^{5}(t)t^{1-\gamma}\right)^{2}$. Thus, by (6.1), it follows that

${\mathbb{P}}\left(\Lambda(\widehat{G}_{t})>\left(C\log(t)t^{1-\gamma+\delta}\right)^{2}\right)\leq\frac{1}{\log(t)},$

which is enough to conclude the proof of the upper bound.

Lower Bound. The main idea behind the proof of the lower bound is to show that
for any small enough $\delta$, with high probability, $G_{t}$ has a vertex
with at least $Ct^{1-\gamma-\delta}$ neighbors for some constant $C$. Then,
$\binom{Ct^{1-\gamma-\delta}}{2}$ is a lower bound for $\Lambda_{t}$.

In order to do so, for a fixed $t$ and small enough $\delta$, make
$N=10C_{f}^{-1}\log t$ on Lemma 6.1 to obtain

(6.6) $\mathbb{P}\left(\exists i\in\\{1,2,\cdots,N\\}\text{ such that
}D_{t}(i)\geq\frac{\phi(t)}{\phi(N)}\right)\geq 1-t^{-10}.$

Now let $v_{*}$ be the vertex of smallest index whose degree at time $t$ is
larger than $\phi(t)/\phi(N)$. Notice that by (6.5) and our choice of $N$ we
have that

(6.7) $\frac{\phi(t)}{\phi(N)}\geq\frac{Ct^{1-\delta/2}}{N}\geq
Ct^{1-\delta}.$

For any time $s\in\\{t,\dots,2t\\}$ denote by $A_{s}^{*}$ the following event

(6.8) $A_{s}^{*}:=\left\\{Z_{s}=1,v_{s}\text{ connects to }v_{*}\right\\}.$

In words, $A_{s}^{*}$ is the event in which at time $s$ a new vertex is added
and connected to the $v_{*}$. Then, let $Y_{t}$ be the following random
variable

(6.9) $Y_{t}:=\sum_{s=t}^{2t}\mathbb{1}_{A_{s}^{*}},$

which counts how many new neighbors $v_{*}$ gained from time $t$ to $2t$.
Also, let $\mathbb{P}_{*}$ be the following conditional measure

(6.10) $\mathbb{P}_{*}(\cdot):={\mathbb{P}}\left(\;\cdot\;\middle|\;\exists
i\in\\{1,2,\cdots,N\\}\text{ such that
}D_{t}(i)\geq\frac{\phi(t)}{\phi(N)}\right).$

Now, using that $f$ is decreasing, that vertices’ degree are increasing in
time and that $Z_{s}$ is independent of the whole past, we obtain

(6.11)
$\begin{split}\mathbb{P}_{*}\left(A_{s}^{*}\middle|\mathcal{F}_{s-1}\right)=f(s)\frac{D_{s-1}(v_{*})}{2s}\geq
f(2t)\frac{Ct^{1-\delta}}{4t}\geq Cf(2t)t^{-\delta}.\end{split}$

By the Representation Theorem (Theorem 1), $f(t)=\ell(t)t^{-\gamma}$, where
$\ell$ is a slowly varying function. And by Proposition A.1 we can then absorb
the slowly varying factor of $f$ into a polynomial factor in the last
inequality of (6.11) by increasing the value of $\delta$ and changing the
constant $C$. This allows us to obtain

(6.12)
$\mathbb{P}_{*}\left(A_{s}^{*}\middle|\mathcal{F}_{s-1}\right)\geq\frac{C}{t^{\gamma+\delta}}.$

Thus, under ${\mathbb{P}}_{*}$, $Y_{t}$ dominates a random variable $W$
distributed as ${\rm bin}(t,Ct^{-\gamma-\delta})$. This fact combined with
Chernoff bounds for $W$ yields

(6.13)
${\mathbb{P}}_{*}\left(Y_{t}\leq\frac{Ct^{1-\gamma-\delta}}{2}\right)\leq{\mathbb{P}}_{*}\left(W\leq\frac{Ct^{1-\gamma-\delta}}{2}\right)\leq\exp\\{-Ct^{1-\gamma-\delta}/8\\}.$

The above inequality tells us that conditioned on the event that at time $t$
there exists a vertex whose degree is at least $t^{1-\delta}$, then, with
probability at least $1-\exp\\{-Ct^{1-\gamma-\delta}/8\\}$, at time $2t$ this
vertex has at least $Ct^{1-\gamma-\delta}$ neighbors. Then, combining (6.13)
with (6.6) yields

(6.14) ${\mathbb{P}}\left(\nexists v_{*}\in G_{2t},v_{*}\text{ has at least
}Ct^{1-\gamma-\delta}\right)\leq\frac{2}{t^{10}},$

which allows us to conclude that with probability at least $1-2t^{-10}$,

$\Lambda_{2t}\geq\binom{Ct^{1-\gamma-\delta}}{2}$

and consequently to finish the proof of the theorem.

##  7\. Proof of Theorem 1: Number of edges in $\widehat{G}_{t}$

This section is devoted to prove Theorem 1, which is the last result left to
be proven. As usual, we will need a couple of technical estimates involving
the time of appearance of vertices, a tight upper bound for their degrees
together with estimates on the average number of edges between two vertices.
These are all technical estimates and their proof might be quite technical. In
a first reading, the reader might find instructive start from Section 7.3
which contains the proof of Theorem 1.

It is also important to highlight that throughout this entire section, $f$
will be a regularly varying function with index of variation at infinity
$\gamma\in[0,1)$, which decreases to $0$ monotonically.

Throughout this section we will make need new notation. Together with the
functions $\phi$ and $\xi$ defined in (6.3, 6.4), we will need the function
$F^{-1}:\mathbb{R}\to\mathbb{R}$ defined by

(7.1) $F(r):=\sum_{1\leq s\leq r}f(s);\quad\quad
F^{-1}(r):=\inf_{s\in\mathbb{R}}\\{F(s)\geq r\\}.$

Since we are assuming $f(s)$ to be strictly positive for all $s$, and since
$\|f\|_{\infty}\leq 1$, we have that

(7.2) $r\leq F(F^{-1}(r))\leq r+1,\quad\text{ and }\quad r\leq
F^{-1}(F(r))\leq r+1.$

We define $\tau_{i}$ to be the first time such that the cardinality of the
vertex set equals $i$, that is

(7.3) $\tau_{i}=\inf_{t\in\mathbb{N}}\big{\\{}t;\,|G_{t}(f)|=i\big{\\}},$

and in order to make notation less cumbersome, we further define

(7.4) $\psi(i)=\phi\left(F^{-1}(i)\right).$

###  7.1. Time of Appearance of Vertices

######  Lemma 7.1 (Time of Appearance of Vertices).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, there exists
a constant $C_{f}>0$ such that for $i\in\mathbb{N}$ and every $\delta>0$

(7.5)
$\mathbb{P}\left((1-\delta)F^{-1}(i)\leq\tau_{i}\leq(1+\delta)F^{-1}(i)\right)\geq
1-C_{f}^{-1}\exp\left\\{-C_{f}(1-\gamma)\delta i\right\\}.$

###### Proof.

We will prove that there exist a constant $C^{\prime}_{f}$ such that

(7.6)
$\mathbb{P}\left(\tau(i)\leq(1-\delta)F^{-1}(i)\right)\leq(C^{\prime}_{f})^{-1}\exp\left\\{-C^{\prime}_{f}(1-\gamma)\delta
i\right\\}.$

The upper bound for the probability of the event
$\\{\tau(i)\geq(1+\delta)F^{-1}(i)\\}$ will follow from the exactly same
argument.

By Theorem 1, we know that $f(t)=\ell(t)t^{-\gamma}$ with $\ell$ being a
slowly varying function. Proposition A.2 implies that as $r\to\infty$, using
the monotonicity of $f$ to approximate the integral by the sum,

(7.7)
$\begin{split}F((1-\delta)r)&=\sum_{s=1}^{\lfloor(1-\delta)r\rfloor}f(s)\\\
&=\sum_{s=1}^{\lfloor(1-\delta)r\rfloor}\ell(s)s^{-\gamma}\sim\frac{1}{1-\gamma}\ell((1-\delta)r)(1-\delta)^{1-\gamma}r^{1-\gamma}\\\
&\sim(1-\delta)^{1-\gamma}F(r),\end{split}$

where we also used the fact that $\ell$ is slowly varying to obtain
$\ell((1-\delta)r)\sim\ell(r)$. Letting $i_{*}=(1-\delta)F^{-1}(i)$ and
recalling that $|G_{r}(f)|$ is a sum of independent random variables, we may
use the above equation, (7.2), and an elementary Chernoff bound to obtain

(7.8)
$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle{\mathbb{P}}\left(\tau(i)\leq(1-\delta)F^{-1}(i)\right)$\mbox{}\hfil\quad\quad\\\
&={\mathbb{P}}\left(|G_{i_{*}}(f)|\geq i\right)\\\
&={\mathbb{P}}\left(|G_{i_{*}}(f)|\geq\left(1+\left(i\left(F\left((1-\delta)F^{-1}(i)\right)\right)^{-1}-1\right)\right){\mathbb{E}}\left[|G_{i_{*}}(f)|\right]\right)\\\
&\leq\exp\left\\{-\frac{1}{3}\left(i\left(F\left((1-\delta)F^{-1}(i)\right)\right)^{-1}-1\right)F\left((1-\delta)F^{-1}(i)\right)\right\\}\\\
&\leq\exp\left\\{-\frac{1}{3}\left((1-\delta)^{-(1-\gamma)}-1\right)(1-\delta)^{1-\gamma}\cdot
i\right\\}\\\ &\leq\exp\left\\{-C(1-\gamma)\delta i\right\\},\end{split}$

for sufficiently large $i$. By adjusting the constant we can then show (7.6)
for every $i\geq 1$, finishing the proof.

We will also need a suitable upper bound for the degree of the $i$-th vertex:

######  Lemma 7.2 (Upper bound on vertices degrees).

Assume that $f$ decreases to zero and it is a regularly varying function with
index of regular variation $-\gamma$, for $\gamma\in[0,1)$. Then, there exists
a constant $C_{f}>0$ such that, for every $\alpha>1$,

$\begin{split}\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}D_{s}(i)\geq\alpha\frac{\phi(s)}{\psi(i)}\right)&\leq
C_{f}^{-1}\left(\exp\left\\{-C_{f}\frac{\alpha-1}{\alpha}i\right\\}+\exp\left\\{-C_{f}\cdot\alpha\right\\}\right).\end{split}$

###### Proof.

Lemma $5$ of [6] implies

(7.9) $\begin{split}\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}D_{s}(i)\geq\alpha\frac{\phi(s)}{\phi(n)}\Bigg{|}\tau_{i}=n\right)&\leq
C_{f}^{-1}\exp\left\\{-C_{f}\cdot\alpha\right\\}.\end{split}$

We note that, for $r>0$ and $\delta\in(0,1)$,

(7.10)
$\frac{\phi\left(r\right)}{\phi\left((1-\delta)r\right)}=\prod_{s=(1-\delta)r}^{r-1}\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right)\leq\prod_{s=(1-\delta)r}^{r-1}\frac{s+1}{s}\leq\frac{1}{1-\delta}.$

Let $\delta=(\alpha-1)/(2\alpha)$, so that $\alpha(1-\delta)>1$ and
$\delta\in(0,1)$. We obtain, by the above equation, monotonicity, and the
union bound,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}\left(\exists
s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha\frac{\phi(s)}{\phi\left(F^{-1}(i)\right)}\right)\leq\mathbb{P}\left(\tau(i)\leq\left(1-\delta\right)F^{-1}(i)\right)$\mbox{}\hfil\\\
&\quad+\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha(1-\delta)\frac{\phi(s)}{\phi\left((1-\delta)F^{-1}(i)\right)}\middle|\tau(i)=(1-\delta)F^{-1}(i)\right),\end{split}$

The result then follows from Equation 7.9 and Lemma 7.1.

###  7.2. Average Number of Edges between two vertices

Our next step is to prove the following lemma, concerning the number of edges
between the $i$-th and $j$-th vertex in $G_{s}$, which we denote $e^{ij}_{s}$.

######  Lemma 7.3 (Average Number of Edges between two vertices).

There exist positive constants $C_{1}$ and $C_{2}$ depending on $f$ only, such
that, for all $1\leq s\leq t$ and $j>i>\log^{2}(t)$,

${\mathbb{E}}\left[e_{s}^{ij}\right]\leq
C_{1}s^{2}e^{-C_{2}\log^{2}(t)}+\frac{C_{3}\log^{2}(t)}{2\psi(i)}+\frac{\log^{4}(t)s}{\psi(i)\psi(j)}.$

###### Proof.

Throughout this proof we will need to define a new filtration which, at time
$r$, incorporates not only all the random choices made by the process until
that time, but also if time $r+1$ corresponded to a vertex or edge step:

(7.11) $\mathcal{F}_{r}^{+}=\sigma(\mathcal{F}_{r},Z_{r+1}).$

At the precise time in which vertex $j$ is added to the graph, the only way
for the the number of edges between $i$ and $j$ to increase is if $j$ connects
to $i$ in a vertex step. Therefore,

(7.12) ${\mathbb{E}}\left[\Delta
e_{t_{j}-1}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\middle|\mathcal{F}^{+}_{t_{j}-1}\right]=\frac{D_{t_{j}-1}(i)}{2(t_{j}-1)}\mathbb{1}\\{\tau_{j}=t_{j}\\}.$

For $r\geq t_{j}$, however, an edge step must occur in order for this random
variable to increase,

(7.13) ${\mathbb{E}}\left[\Delta
e_{r}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\middle|\mathcal{F}^{+}_{r}\right]=\frac{(1-Z_{r+1})D_{r}(i)D_{r}(j)}{2r^{2}}\mathbb{1}\\{\tau_{j}=t_{j}\\}.$

We define the event $B^{i}_{t}$, where the degree of vertex $i$ is well
behaved:

(7.14) $B^{i}_{t}=\left\\{\exists s\in\mathbb{N}\text{ such that
}D_{s}(i)\geq\log^{2}(t)\frac{\phi(s)}{\psi(i)}\right\\}.$

Lemma 7.2 implies ${\mathbb{P}}(B^{i}_{t})\leq C^{\prime}e^{-C\log^{2}(t)}$,
for some positive constants $C$ and $C^{\prime}$ depending on $f$.

Using that $D_{t_{j}-1}(i)\leq t_{j}$ deterministically, we obtain

(7.15) $\begin{split}{\mathbb{E}}\left[\Delta
e_{t_{j}-1}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\middle|\mathcal{F}^{+}_{t_{j}-1}\right]\mathbb{1}_{B_{t}^{i}}\leq\mathbb{1}_{B_{t}^{i}}\mathbb{1}\\{\tau_{j}=t_{j}\\},\end{split}$

which together with (7.12), implies

(7.16) ${\mathbb{E}}\left[\Delta
e_{t_{j}-1}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\right]\leq\frac{\log^{2}(t)\phi(t_{j}-1)}{2\psi(i)t_{j}}{\mathbb{P}}\left(\tau_{j}=t_{j}\right)+C^{\prime}e^{-C\log^{2}(t)};$

By the same reasoning for (7.13)

(7.17) ${\mathbb{E}}\left[\Delta
e_{r}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\right]\leq\frac{\log^{4}(t)\phi(r)^{2}}{2\psi(i)\psi(j)r^{2}}{\mathbb{P}}\left(\tau_{j}=t_{j}\right)+2C^{\prime}e^{-C\log^{2}(t)}.$

Since $\phi(r)\leq r$, it follows that

(7.18)
$\sum_{r=t_{j}-1}^{s}\frac{\log^{4}(t)\phi(r)^{2}}{2\psi(i)\psi(j)r^{2}}\leq\frac{\log^{4}(t)s}{\psi(i)\psi(j)}.$

Moreover, combining Lemma 7.1 with $\delta=1/2$ with the same bound on $\phi$,
we have that

(7.19)
$\begin{split}\sum_{t_{j}=j}^{F^{-1}(j)/2}\frac{\log^{2}(t)\phi(t_{j}-1)}{2\psi(i)t_{j}}{\mathbb{P}}\left(\tau_{j}=t_{j}\right)&=\frac{\log^{2}(t)}{2\psi(i)}\sum_{t_{j}=j}^{F^{-1}(j)/2}{\mathbb{P}}\left(\tau_{j}=t_{j}\right)\\\
&\leq(C^{\prime}_{f})^{-1}\frac{\log^{2}(t)}{2\psi(i)}e^{-C_{f}^{\prime}(1-\gamma)\log^{2}(t)/2}\\\
&\leq C^{\prime\prime}e^{-C\log^{2}(t)},\end{split}$

for two constants $C^{\prime\prime}$ and $C$ depending on $f$ only. The same
reasoning gives us similar bound for other two constants
$C_{2}^{\prime\prime}$ and $C_{2}$,

(7.20)
$\begin{split}\sum_{t_{j}=3F^{-1}(j)/2}^{t}\frac{\log^{2}(t)\phi(t_{j}-1)}{2\psi(i)t_{j}}{\mathbb{P}}\left(\tau_{j}=t_{j}\right)&\leq
C_{2}^{\prime\prime}e^{-C_{2}\log^{2}(t)}.\end{split}$

Using one more time the bound on $\phi$, we have

(7.21)
$\begin{split}\sum_{t_{j}=F^{-1}(j)/2}^{3F^{-1}(j)/2}\frac{\log^{2}(t)\phi(t_{j}-1)}{2\psi(i)t_{j}}{\mathbb{P}}\left(\tau_{j}=t_{j}\right)&\leq\frac{\log^{2}(t)}{2\psi(i)}.\end{split}$

Finally, combining (7.18), (7.19), (7.20) and (7.21), we obtain

(7.22)
$\begin{split}\sum_{t_{j}=j}^{t}{\mathbb{E}}&\left[e_{t}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\right]\\\
&=\sum_{t_{j}=j}^{s}\sum_{r=t_{j}-1}^{s}{\mathbb{E}}\left[\Delta
e_{r}^{ij}\mathbb{1}\\{\tau_{j}=t_{j}\\}\right]\\\ &\leq
3s^{2}C^{\prime}e^{-C\log^{2}(t)}+\sum_{t_{j}=j}^{s}\left[\frac{\log^{2}(t)\phi(t_{j}-1)}{2\psi(i)t_{j}}+\frac{\log^{4}(t)s\xi^{2}(s)}{\psi(i)\psi(j)}\right]{\mathbb{P}}\left(\tau_{j}=t_{j}\right)\\\
&\leq
C_{4}^{\prime}s^{2}e^{-C_{4}\log^{2}(t)}+\frac{\log^{2}(t)}{2\psi(i)}+\frac{\log^{4}(t)s}{\psi(i)\psi(j)},\end{split}$

for some positive constants $C_{4}^{\prime}$ and $C_{4}$ depending on $f$
only, which concludes the proof.

###  7.3. Proof of Theorem 1

Finally we can prove Theorem 1 which is the last result left to be proven.

###### Proof of Theorem 1.

We begin observing that the result is clearly true when $\gamma=0$, for this
reason, we will assume $\gamma\in(0,1)$. In this case, since $f(s)/s$ is
summable, by the definition of $\xi$ in 6.4, we we know that that there exists
$c_{f}>0$ such that

(7.23) $c_{f}t\leq\phi(t)\leq t$

for all $t>0$. Now, recall that $|G_{t}|$ can be written as follows

$|G_{t}|=1+\sum_{s=1}^{t}Z_{s},$

where $Z_{s}\sim{\rm Ber}(f(s))$. Thus, by Chernoff bounds, there exist some
positive constant $C$ such that

(7.24) ${\mathbb{P}}\left(|G_{t}|>Ct^{1-\gamma}\right)\leq
C^{-1}\exp\left\\{Ct^{1-\gamma}\right\\}.$

Notice that $\mathcal{E}(\widehat{G}_{t})$ satisfies the following upper bound

(7.25) $\mathcal{E}(\widehat{G}_{t})=\sum_{\begin{subarray}{c}i,j\in G_{t},\\\
i<j\end{subarray}}\mathbb{1}\\{e^{ij}_{t}\geq
1\\}\leq\log^{4}(t)\;+\sum_{\begin{subarray}{c}i,j\in G_{t},\\\
\log^{2}(t)<i<j\end{subarray}}\mathbb{1}\\{e^{ij}_{t}\geq 1\\},$

almost surely. Since at time $t$ we have added $t$ edges, the second term on
the RHS of the above inequality can be bounded as follows

(7.26) $\sum_{\begin{subarray}{c}i,j\in G_{t},\\\
\log^{2}(t)<i<j\end{subarray}}\mathbb{1}\\{e^{ij}_{t}\geq
1\\}\leq\sum_{\begin{subarray}{c}i,j\in G_{t},\\\
\log^{2}(t)<i<j\end{subarray}}\mathbb{1}\\{e^{ij}_{t}\geq 1,|G_{t}|\leq
Ct^{1-\gamma}\\}+t\cdot\mathbb{1}\\{|G_{t}|\geq Ct^{1-\gamma}\\}$

Moreover, for a fixed $i\geq\log^{2}(t)$, we also have

(7.27) $\sum_{\begin{subarray}{c}j\in G_{t},\\\ j\geq
i\end{subarray}}\mathbb{1}\\{e^{ij}_{t}\geq 1,|G_{t}|\leq
Ct^{1-\gamma}\\}\leq\frac{t^{1-\gamma}}{i}+\sum_{j=t^{1-\gamma}/i}^{Ct^{1-\gamma}}e^{ij}_{t}.$

Plugging the above inequality back on (7.26) back and then on (7.25) yields

$\mathcal{E}(\widehat{G}_{t})\leq\log^{4}(t)+t\cdot\mathbb{1}\\{|G_{t}|\geq
Ct^{1-\gamma}\\}+\sum_{i=\log^{2}(t)}^{Ct^{1-\gamma}}\left[\frac{t^{1-\gamma}}{i}+\sum_{j=t^{1-\gamma}/i}^{Ct^{1-\gamma}}e^{ij}_{t}\right].$

Thus, taking the expectation on both sides of the above inequality and using
(7.24) gives us

(7.28)
${\mathbb{E}}\left[\mathcal{E}(\widehat{G}_{t})\right]\leq\log^{4}(t)+t\cdot
e^{-Ct^{1-\gamma}}+C\log(t)t^{1-\gamma}+\sum_{i=\log^{2}(t)}^{Ct^{1-\gamma}}\sum_{j=t^{1-\gamma}/i}^{Ct^{1-\gamma}}{\mathbb{E}}\left[e^{ij}_{t}\right].$

To bound the last term of the above inequality, we apply Theorem 7.3. We first
need, however, to better understand the behavior of the function
$\psi=\phi\circ F^{-1}$. Theorem 2 and elementary integration implies that
$F^{-1}$ is a regularly varying function with index of regularity
$1/(1-\gamma)$. Given $r\in\mathbb{N}$, we then have

(7.29) $\psi(r)=\phi(F^{-1}(r))\geq cF^{-1}(r)\geq
cr^{\frac{1}{1-\gamma}-\delta},$

for any $\delta>0$ and a positive constant $c$ depending on $\delta$. This
yields, together with Equation (7.28),

(7.30)
$\begin{split}\sum_{i=\log^{2}(t)}^{Ct^{1-\gamma}}\sum_{j=t^{1-\gamma}/i}^{Ct^{1-\gamma}}{\mathbb{E}}\left[e^{ij}_{t}\right]&\leq\sum_{i=\log^{2}(t)}^{Ct^{1-\gamma}}\sum_{j=t^{1-\gamma}/i}^{Ct^{1-\gamma}}C_{1}t^{2}e^{-C_{2}\log^{2}(t)}+\frac{C_{3}t^{\delta}}{i^{\frac{1}{1-\gamma}}}+\frac{C_{4}t^{1+\delta}}{(ij)^{\frac{1}{1-\gamma}}}\\\
&\leq
C_{1}t^{3}e^{-C_{2}\log^{2}(t)}+C_{3}t^{1-\gamma+\delta}+\sum_{i=\log^{2}(t)}^{Ct^{1-\gamma}}\frac{C_{4}t^{1+\delta}}{i^{\frac{1}{1-\gamma}}}\cdot\frac{i^{\frac{\gamma}{1-\gamma}}}{t^{\gamma}}\\\
&\leq
C_{1}t^{3}e^{-C_{2}\log^{2}(t)}+C_{3}t^{1-\gamma+\delta}+C_{4}t^{1-\gamma+\delta}\\\
&\leq Ct^{1-\gamma+\delta}.\end{split}$

By replacing the above bound on (7.28), we obtain the desired result.

##  Appendix A Important results for Regularly varying functions

In this appendix we gather important results from the Karamata’s theory. All
of them may be found in [8], but for the reader’s convenience we state them
here under our notation.

######  Proposition A.1 (Proposition 1.3.6 of [8]).

Let $\ell$ be a slowly varying function. Then, for any $a>0$ it follows that

$x^{a}\ell(x)\rightarrow\infty,\quad x^{-a}\ell(x)\rightarrow 0,\text{ as
}x\to\infty.$

######  Theorem 1 (Theorem 1.4.1 of [8]).

Let $f$ be a strictly positive regularly varying function with index $\beta$.
Then, there exists a slowly varying function $\ell$ such that

$f(x)=\ell(x)x^{\beta}.$

######  Proposition A.2 (Proposition 1.5.8 of [8]).

Let $\ell$ be a locally bounded slowly varying function. If $\alpha>-1$, then

$\frac{\int_{x_{0}}^{x}t^{\alpha}\ell(t)\mathrm{d}t}{x^{1+\alpha}\ell(x)}\longrightarrow\frac{1}{1+\alpha}\quad\text{as
}x\to\infty.$

######  Proposition A.3 (Proposition 1.5.9a of [8]).

Let $\ell$ be a locally bounded slowly varying function. Then, the function
$\widehat{\ell}$ defined as

$\widehat{\ell}(x):=\int_{X}^{x}\frac{\ell(t)\mathrm{d}t}{t}$

is a slowly varying function. Moreover,

$\frac{\widehat{\ell}(x)}{\ell(x)}\longrightarrow\infty\quad\text{as
}x\to\infty.$

######  Proposition A.4 (Proposition 1.5.10 of [8]).

Let $\ell$ be a slowly varying function. If $\alpha<-1$, then

$\frac{\int_{x}^{\infty}t^{\alpha}\ell(t)\mathrm{d}t}{x^{1+\alpha}\ell(x)}\longrightarrow\frac{1}{-1-\alpha}\quad\text{as
}x\to\infty.$

If $f$ a locally bounded function defined at $[x_{0},\infty)$ and tends to
$\infty$ as $x$ tends to $\infty$, then its generalized inverse

$f^{\leftarrow}(x):=\inf\\{y\in[x_{0},\infty):f(y)>x\\}$

is defined on $[f(x_{0}),\infty)$ and it increases monotonically to infinity.
The theorem below gives additional information on the generalized inverse when
$f$ is a regularly varying function.

######  Theorem 2 (Theorem 1.5.12 of [8]).

Let $f$ be a regularly varying function with index of regular varying
$\beta>0$. Then $f^{\leftarrow}$ is a regularly varying function with index
$1/\beta$.

## References

  * [1] C. Alves, R. Ribeiro, and R. Sanchis.  Large communities in a scale-free network.  Journal of Statistical Physics, 166(1):137–149, 2017.
  * [2] C. Alves, R. Ribeiro, and R. Sanchis.  Preferential Attachment Random Graphs with Edge-Step Functions.  Journal of Theoretical Probability, 34(1):438–476, 03 2021.
  * [3] Caio Alves and Rodrigo Ribeiro.  Spread of infection over pa random graphs with edge insertion.  ALEA, 19:1221–1239, 2022.
  * [4] Caio Alves, Rodrigo Ribeiro, and Rémy Sanchis.  Diameter of p.a. random graphs with edge-step functions.  Random Structures & Algorithms, 57(3):612–636, 2020.
  * [5] Caio Alves, Rodrigo Ribeiro, and Rémy Sanchis.  Clustering in preferential attachment random graphs with edge-step.  Journal of Applied Probability, 58(4):890–908, 2021.
  * [6] Caio Alves, Rodrigo Ribeiro, and Daniel Valesin.  Asymptotic results of a multiple-entry reinforcement process.  Stochastic Processes and their Applications, 2023.
  * [7] A-L. Barabási and R. Albert.  Emergence of scaling in random networks.  Science, 1999.
  * [8] N. H. Bingham, C. M. Goldie, and J. L. Teugels.  Regular variation, volume 27 of Encyclopedia of Mathematics and its Applications. CUP Cambridge, 1989.
  * [9] Kay Bogerd, Rui M. Castro, and Remco van der Hofstad.  Cliques in rank-1 random graphs: The role of inhomogeneity.  Bernoulli, 26(1):253 – 285, 2020.
  * [10] Kay Bogerd, Rui M. Castro, Remco van der Hofstad, and Nicolas Verzelen.  Detecting a planted community in an inhomogeneous random graph.  Bernoulli, 27(2):1159 – 1188, 2021.
  * [11] B. Bollobás and O. Riordan.  Mathematical results on scale-free random graphs. in handbook of graphs and networks: From the genome to the internet.  pages 1–34, 2003.
  * [12] B. Bollobás and O. Riordan.  The diameter of a scale-free random graph.  Combinatorica, 24(1):5–34, January 2004.
  * [13] F. Chung and L. Lu.  Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics).  American Mathematical Society, Boston, MA, USA, 2006.
  * [14] C. Cooper and A. Frieze.  A general model of web graphs.  Random Struct. Algorithms, 22(3):311–335, 2003.
  * [15] N. Eggemann and S.D. Noble.  The clustering coefficient of a scale-free random graph.  Discrete Applied Mathematics, 2011.
  * [16] Giorgio Fagiolo.  Clustering in complex directed networks.  Phys. Rev. E, 76:026107, Aug 2007.
  * [17] Leon Festinger.  The analysis of sociograms using matrix algebra.  Human Relations, 2(2):153–158, 1949.
  * [18] E. Jacob and P. Mörters.  Spatial preferential attachment networks: Power laws and clustering coefficients.  Ann. Appl. Probab., 25(2):632–662, 04 2015.
  * [19] Marcus Kaiser.  Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks.  New Journal of Physics, 10(8):083042, aug 2008.
  * [20] R. Duncan Luce and Albert D. Perry.  A method of matrix analysis of group structure.  Psychometrika, 14(2):95–116, 1949.
  * [21] Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar, and Christine Humblet.  Clip:similarity searching of 3d databases using clique detection.  Journal of Chemical Information and Computer Sciences, 43(2):443–448, 2003.  PMID: 12653507.
  * [22] I. Rivin.  Counting cycles and finite dimensional lp norms.  Advances in Applied Mathematics, 29(4):647 – 662, 2002.
  * [23] Clara Stegehuis, Remco Hofstad, and Johan Leeuwaarden.  Scale-free network clustering in hyperbolic and other random graphs.  Journal of Physics A: Mathematical and Theoretical, 52, 05 2019\.
  * [24] S.H Strogatz and D. J. Watts.  Tcollective dynamics of ’small-world’ networks.  Nature, 1998.