2.1. Notation

Let $M=\sum_{i}\delta_{(\theta_{i},\vartheta_{i})}$ be a unit-rate Poisson random measure on $(0,+\infty)^{2}$ , and let $W\,:\,[0,+\infty)^{2}\rightarrow\lbrack0,1]$ be a symmetric measurable function such that $\lim_{x\to\infty} W(x,x)$ and $\lim_{x\to 0} W(x,x)$ both exist (by (3), this implies that $\lim_{x\to\infty} W(x,x)=0$ ) and

(3) \begin{equation}0<\overline W=\int_{\mathbb{R}_{+}^{2}}W(x,y)dxdy<\infty, \quad \int_{0}^{\infty}W(x,x)dx<\infty. \end{equation}

Let $(U_{ij})_{i,j\in\mathbb{N}^{2}}$ be a symmetric array of independent random variables, with $U_{ij}\sim U(0,1)$ if $i\leq j$ and $U_{ij}=U_{ji}$ for $i>j$ . Let $Z_{ij}=\mathbb{1}_{U_{ij}\leq W(\vartheta_{i},\vartheta_{j})}$ be a binary random variable indicating whether there is a link between i and j, where $\mathbb{1}_{A}$ denotes the indicator function.

Restrictions of the point process $\sum_{ij} Z_{ij}\delta_{(\theta_i,\theta_j)}$ to squares $[0,\alpha]^2$ then define a growing family of random graphs $(\mathcal G_\alpha)_{\alpha\geq 0}$ , called a graphex process, where $\mathcal G_\alpha=(\mathcal V_\alpha,\mathcal E_\alpha)$ denotes a graph of size $\alpha\geq 0$ with vertex set $\mathcal V_\alpha$ and edge set $\mathcal E_\alpha$ , defined by

(4) \begin{align}\mathcal V_\alpha &=\left \{ \theta_i \mid \theta_i\leq \alpha\text{ and }\exists \theta_k\leq \alpha\text{ s.t. }Z_{ik}=1\right \}, \end{align}

(5) \begin{align}\mathcal E_\alpha &=\left \{ \{\theta_i,\theta_j\} \mid \theta_i,\theta_j\leq \alpha\text{ and }Z_{ij}=1\right \}.\end{align}

The connection between the point process and graphex process is illustrated in Figure 3. The conditions (3) are sufficient (though not necessary) conditions for $|\mathcal E_\alpha|$ (hence $|\mathcal V_\alpha|$ ) to be almost surely finite, and for the graphex process to be well defined [Reference Veitch and Roy38, Theorem 4.9]. Note crucially that the graphs $\mathcal G_\alpha$ have no isolated vertices (that is, no vertices of degree 0), and that the number of nodes $|\mathcal V_\alpha|$ and the number of edges $|\mathcal E_\alpha|$ are both random variables.

Figure 3.

Illustration of the connection between the point process on the plane and the graphex process. (a) Point process $\sum_{ij} Z_{ij}\delta_{(\theta_i,\theta_j)}$ on the plane. (b–e) Associated graphs $\mathcal G_\alpha$ for (b) $\alpha\in [1,3)$ , (c) $\alpha\in[3,3.5)$ , (d) $\alpha\in [3.5,5)$ , and (e) $\alpha=5$ . Note that the graph is empty for $\alpha<1$ .

We now define a number of summary statistics of the graph $\mathcal G_\alpha$ . For $i\geq 1$ , let

\begin{equation*}D_{\alpha,i}=\sum_{k}Z_{ik}\mathbb{1}_{\theta_{k}\leq\alpha}.\end{equation*}

If $\theta_i\in \mathcal V_\alpha$ , then $D_{\alpha,i}\geq 1$ corresponds to the degree of the node $\theta_i$ in the graph $\mathcal G_\alpha$ of size $\alpha$ ; otherwise $D_{\alpha,i}=0$ . Let $N_{\alpha}=|\mathcal V_\alpha|$ and $N_{\alpha,j}$ be the number of nodes and the number of nodes of degree $j,\,j\ge 1$ , respectively,

(6) \begin{equation}N_{\alpha}=\sum_{i}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{D_{\alpha,i}\geq 1}, \quad N_{\alpha,j}=\sum_{i}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{D_{\alpha,i}=j}, \end{equation}

and $N^{(e)}_{\alpha}=|\mathcal E_\alpha|$ the number of edges

(7) \begin{equation}N^{(e)}_{\alpha}=\frac{1}{2}\sum_{i\neq j}Z_{ij} \mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{\theta_{j}\leq\alpha}+\sum_{i}Z_{ii}\mathbb{1}_{\theta_{i}\leq\alpha}.\end{equation}

For $i\geq 1$ , let

(8) \begin{equation}T_{\alpha, i}=\frac{1}{2}\sum_{j,k\mid j\neq k\neq i}Z_{ij}Z_{jk}Z_{ik}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{\theta_{j}\leq\alpha}\mathbb{1}_{\theta_{k}\leq\alpha}.\end{equation}

If $\theta_i\in \mathcal V_\alpha$ , $T_{\alpha, i}$ corresponds to the number of triangles containing node $\theta_i$ in the graph $\mathcal G_\alpha$ ; otherwise $T_{\alpha, i}=0$ . Let

(9) \begin{equation}T_{\alpha}=\frac{1}{3}\sum_{i}T_{\alpha,i}=\frac{1}{6}\sum_{i\neq j\neq k}Z_{ij}Z_{jk}Z_{ik}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{\theta_{j}\leq\alpha}\mathbb{1}_{\theta_{k}\leq\alpha}\end{equation}

denote the total number of triangles and

(10) \begin{align}A_{\alpha} =\sum_{i}\frac{D_{\alpha,i}(D_{\alpha,i}-1)}{2} =\frac{1}{2}\sum_{i\neq j\neq k}Z_{ij}Z_{jk}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{\theta_{j}\leq\alpha}\mathbb{1}_{\theta_{k}\leq\alpha}\end{align}

the total number of adjacent edges in the graph $\mathcal G_\alpha$ . The global clustering coefficient, also known as the transitivity coefficient, is defined as

(11) \begin{equation}C_{\alpha}^{(g)}=\frac{3T_{\alpha}}{A_{\alpha}}\end{equation}

if $A_{\alpha}\geq 1$ and 0 otherwise. The global clustering coefficient counts the proportion of closed connected triplets over all the connected triplets, or equivalently the fraction of pairs of nodes connected to the same node that are themselves connected, and is a standard measure of the transitivity of a network [Reference Newman30, Section 7.9]. Another measure of the transitivity of the graph is the local clustering coefficient. For any degree $j\geq 2$ , define

(12) \begin{equation}C_{\alpha,j}^{(\ell)}=\frac{2}{j(j-1)N_{\alpha,j}}\sum_{i}T_{\alpha,i}\mathbb{1}_{D_{\alpha,i}=j}\end{equation}

if $N_{\alpha,j}\geq 1$ and 0 otherwise. Then $C_{\alpha,j}^{(\ell)}$ corresponds to the proportion of pairs of neighbours of nodes of degree j that are connected. The average local clustering coefficient is obtained by

(13) \begin{equation}\overline{C}_{\alpha}^{(\ell)}=\frac{1}{N_{\alpha}-N_{\alpha,1}}\sum_{j\geq2}N_{\alpha,j}C_{\alpha,j}^{(\ell)}\end{equation}

if $N_{\alpha}-N_{\alpha,1}\geq 1$ and $\overline{C}_{\alpha}^{(\ell)}=0$ otherwise.

2.2. Assumptions

We will make use of the following three assumptions. Assumption 1 characterises the behaviour of the small-degree nodes. Assumption 2 is a technical assumption to obtain the almost sure results. Assumption 3 characterises the behaviour of large-degree nodes.

A central quantity of interest in the analysis of the asymptotic properties of graphex processes is the marginal generalised graphon function $\mu\,:\,(0,\infty)\to\mathbb R_+$ , defined for $x>0$ by

(14) \begin{equation}\mu(x)=\int_0^\infty W(x,y)dy.\end{equation}

The integrability of the generalised graphon W implies that $\mu$ is integrable. Ignoring loops (self-edges), the expected number of connections of a node with parameter $\vartheta$ is proportional to $\mu(\vartheta)$ . Therefore, assuming $\mu$ is monotone decreasing, its behaviour at infinity controls the small-degree nodes, while its behaviour at zero controls the large-degree nodes.

For mathematical convenience, it will be easier to work with the generalised inverse $\mu^{-1}$ of $\mu$ . The behaviour at zero of $\mu^{-1}$ then controls the small-degree nodes, while the behaviour of $\mu^{-1}$ at infinity controls large-degree nodes.

The following assumption characterises the behaviour of $\mu$ at infinity or, equivalently, of $\mu^{-1}$ at zero. We require $\mu^{-1}$ to behave approximately as a power function $x^{-\sigma}$ around zero, for some $\sigma\in[0,1]$ . This behaviour, known as regular variation, has been extensively studied (see, e.g., [Reference Bingham, Goldie and Teugels6]) and we provide some background on it in Appendix C.

Assumption 1. Assume $\mu$ is non-increasing, with generalised inverse $\mu^{-1}(x)=\inf\{ y>0 \mid \mu(y)\leq x\}$ , such that

(15) \begin{equation}\mu^{-1}(x)\sim\ell(1/x)x^{-\sigma}\ as\ x\rightarrow0,\end{equation}

where $\sigma\in\lbrack0,1]$ and $\ell$ is a slowly varying function at infinity: for all $c>0$ , $\lim_{t\rightarrow\infty}\ell(ct)/\ell(t)=1.$

Examples of slowly varying functions $\ell$ include functions converging to a strictly positive constant, and powers of logarithms. Note that Assumption 1 implies that, for $\sigma\in(0,1)$ , $\mu(t)\sim \overline \ell(t)t^{-1/\sigma}\text{ as }t\rightarrow\infty$ for some slowly varying function $\overline \ell$ . We can differentiate four cases, as will be formally derived in Corollary 1:

1. (i) Dense case: $\sigma=0$ and $\lim_{t\rightarrow\infty}\ell(t)<\infty$ . In this case, $\lim_{x\rightarrow 0}\mu^{-1}(x)<\infty$ , and hence $\mu$ has bounded support. The other three cases are all sparse cases.

2. (ii) Almost dense case: $\sigma=0$ and $\lim_{t\rightarrow\infty}\ell(t)=\infty$ . In this case $\mu$ has full support and super-polynomially decaying tails.

3. (iii) Sparse case with power law: $\sigma\in(0,1)$ . In this case $\mu$ has full support and polynomially decaying tails (up to a slowly varying function).

4. (iv) Very sparse case: $\sigma=1$ . In this case $\mu$ has full support and very light tails. In order for $\mu^{-1}$ (and hence W) to be integrable, we need $\ell$ to go to zero sufficiently fast.

Now define, for $x,y>0$ ,

(16) \begin{equation}\nu(x,y)=\int_0^\infty W(x,z)W(y,z)dz.\end{equation}

The expected number of common neighbours of nodes with parameters $(\vartheta_1,\vartheta_2)$ is proportional to $\nu(\vartheta_1,\vartheta_2)$ .

The following assumption is a technical assumption needed in order to obtain the almost sure results on the number of nodes and degrees. The paper [Reference Veitch and Roy38] made a similar assumption to obtain results in probability; see the discussion section for further details.

Assumption 2. Assume that there exist $C_1,a >0$ and $x_0\geq 0$ such that for all $x,y>x_0$ ,

(17) \begin{equation} \nu(x,y)\leq C_1 \mu(x)^a\mu(y)^a, \quad \mu(x_0)>0, \quad \left \{\begin{array}{l@{\quad}l} a>\max\left(\frac{1}{2},\sigma\right) & \text{if }\sigma\in[0,1), \\[4pt] a=1 & \text{if }\sigma=1.\end{array}\right .\end{equation}

Remark 1. Assumption 2 is trivially satisfied when the function W is separable, $W(x,y)= \mu(x)\mu(y)/\overline W.$ Assumptions 1 and 2 are also satisfied if

(18) \begin{equation}\quad W(x,y)= 1-e^{-f(x)f(y)/\overline f}\end{equation}

for some positive, non-increasing, measurable function f with $\overline f=\int_0^\infty f(x)dx<\infty$ and generalised inverse $f^{-1}$ satisfying $f^{-1}(x)\sim\ell(1/x)x^{-\sigma}\text{ as }x$ tends to 0. In this case, $\mu$ is monotone non-increasing. We have

\begin{align*}\mu\{f^{-1}(x)\}&=\int_0^\infty \big\{1-e^{-x f(y)/\bar f}\big\}dy=x\int_0^\infty e^{-xu/\bar f} f^{-1}(u)/\bar fdu\sim x\end{align*}

as x tends to 0 by dominated convergence. Hence $f\{\mu^{-1}(x)\}\sim x$ as x tends to 0 and $f^{-1}[f\{\mu^{-1}(x)\}]\sim \ell(1/x)x^{-\sigma}$ . Assumption 2 follows from the inequality $W(x,y)\leq f(x)f(y)/\overline f$ . Other examples are considered in Section 6.

The following assumption is used to characterise the asymptotic behaviour of both small- and large-degree nodes.

Assumption 3. Assume $\mu^{-1}(t)=\int_t^\infty f(x)dx$ where f is continuous on $(0, \infty)$ and the following hold:

\begin{align*}(a) \qquad f(x) &\sim \tau x^{-\tau-1}\ell_2(x)\ as \ x\to\infty,\\(b) \qquad f(x) &\sim x^{-\tilde{\sigma}-1}\tilde{\ell}_2(1/x)\ as \ x\to 0,\end{align*}

where $\tau>0$ , $\tilde{\sigma} \leq 1$ , and $\ell_{2}, \tilde{\ell}_2$ are slowly varying functions.

Note that Assumption 3 implies that $\mu^{-1}(x)\sim x^{-\tau}\ell_2(x)\text{ as }x\to\infty$ , and $\mu(t)\sim \overline \ell_2(t)t^{-1/\tau}$ as $t\rightarrow 0$ , for some slowly varying function $\overline \ell_2$ . Assumption 3 also implies Assumption 1 with $\sigma = \max( \tilde \sigma , 0)$ , $\ell(x)=\frac{1}{\sigma} \tilde{\ell}_2(x)$ if $\tilde \sigma\neq 0$ , and $\ell(x)=o(\tilde{\ell}_2(x))$ if $\tilde \sigma= 0$ .

Finally, we state an assumption on $\nu(x, y)$ , the quantity proportional to the expected number of common neighbours of two nodes with parameters x and y, defined in Equation (16). This technical assumption is used to prove a result on the asymptotic behaviour of the variance of the number of nodes (Proposition 3) and the central limit theorem for sparse graphs enunciated in Section 4.3.

Assumption 4. Assume that there exist $0<C_{0}\leq C_1$ and $x_{0}\geq0$ such that for all $x,y>x_{0}$ ,

\begin{equation*}C_{0}\mu(x)\mu(y)\leq\nu(x,y)\leq C_1\mu(x)\mu(y).\end{equation*}

Assumption 4 holds when W is separable, as well as in the model of [Reference Caron and Fox12] under some moment conditions (see Section 6.5). Obviously, Assumption 4 implies that Assumption 2 is satisfied with $a=1$ .

3.1. Asymptotic behaviour of the number of edges, number of nodes, and degree distribution

In this section we characterise the almost sure and expected behaviour of the number of nodes $N_\alpha$ , number of edges ${N_{\alpha}^{(e)}}$ , and number of nodes with j edges $N_{\alpha,j}$ . These results allow us to provide precise statements about the sparsity of the graph and the asymptotic power-law properties of its degree distribution.

We first recall existing results on the asymptotic growth of the number of edges. The growth of the mean number of edges has been shown by [Reference Veitch and Roy38], and the almost sure convergence follows from [Reference Borgs, Chayes, Cohn and Holden9, Proposition 56].

Proposition 1. (Number of edges [Reference Borgs, Chayes, Cohn and Holden9, Reference Veitch and Roy38].) As $\alpha $ goes to infinity, almost surely

(19) \begin{equation}{N_{\alpha}^{(e)}} \sim E({N_{\alpha}^{(e)}})\sim \alpha^{2}\overline W/2.\end{equation}

The following two theorems provide a description of the asymptotic behaviour of the terms $N_\alpha, N_{\alpha,j}$ in expectation and almost surely.

Theorem 1. For $\sigma\in[0,1]$ , let $\ell_\sigma$ be slowly varying functions defined as

(20) \begin{align}\ell_1(t)=\int_t^\infty y^{-1} \ell(y)dy \qquad and \quad \ell_\sigma(t) = \ell(t) \Gamma(1-\sigma)\text{ for }\sigma \in[0,1).\end{align}

Under Assumption 1, for all $\sigma \in [0,1]$ ,

(21) \begin{equation} E(N_{\alpha})\sim\alpha^{1+\sigma}\ell_\sigma(\alpha).\end{equation}

If $\sigma = 0$ then for $j\geq 1$

\begin{equation*} E\big(N_{\alpha,j}\big)=o\{\alpha\ell(\alpha)\}.\end{equation*}

If $\sigma\in(0,1)$ then for $j\geq 1$

\begin{equation*} E\big(N_{\alpha,j}\big)\sim\frac{\sigma\Gamma(j-\sigma)}{j!}\alpha^{1+\sigma}\ell(\alpha). \end{equation*}

Finally, if $\sigma= 1$ , then

\begin{equation*}E\big(N_{\alpha,j}\big)\sim \left \{\begin{array}{l@{\quad}l} \alpha^{2}\ell_1(\alpha), & j=1, \\[5pt] \frac{\alpha^{2}}{j(j-1)}\ell(\alpha), & j\geq 2.\end{array}\right .\end{equation*}

Theorem 1 follows rather directly from asymptotic properties of regularly varying functions [Reference Gnedin, Hansen and Pitman17], recalled in Lemmas B.2 and B.3 in the appendix. Details of the proof are given in Appendix A.1. Note that $\ell(\alpha)=o(\ell_1(\alpha))$ ; hence, for $\sigma=1$ , $E\big(N_{\alpha,j}\big)=o\{E(N_{\alpha,1})\}$ for all $j\geq 2$ .

The paper [Reference Veitch and Roy38] shows that, under Assumption 2 with $a=1$ , we have, in probability,

\begin{equation*} N_{\alpha}\sim E(N_{\alpha}),\quad \sum_{k\geq j} N_{\alpha,k}\sim E\left (\sum_{k\geq j} N_{\alpha,k}\right)\,\,\text{for }j\geq 1.\end{equation*}

The next theorem shows that the asymptotic equivalence holds almost surely under Assumptions 1 and 2. Additionally, combining these results with Theorem 1 allows us to characterise the almost sure asymptotic behaviour of the number of nodes and the number of nodes of a given degree. The proof of Theorem 2 is given in Section 3.2.

Theorem 2. Under Assumptions 1 and 2, we have almost surely as $\alpha$ tends to infinity

(22) \begin{equation} N_{\alpha}\sim E(N_{\alpha}),\quad \sum_{k\geq j} N_{\alpha,k}\sim E\left (\sum_{k\geq j} N_{\alpha,k}\right)\,\, for\ j\geq 1. \end{equation}

Combining this with Theorem 1, we obtain that, for all $\sigma\in[0,1]$ ,

\begin{equation*} N_{\alpha}\sim\alpha^{1+\sigma}\ell_\sigma(\alpha).\end{equation*}

Moreover, for $j\geq 1$ , if $\sigma = 0$ then $N_{\alpha,j}=o\{\alpha\ell(\alpha)\} $ , while if $0< \sigma < 1$ then

\begin{equation*} N_{\alpha,j}\sim\frac{\sigma\Gamma(j-\sigma)}{j!}\alpha^{1+\sigma}\ell(\alpha). \end{equation*}

If $\sigma = 1$ , then $N_{\alpha,1}\sim \alpha^{2}\ell_1(\alpha)$ and for all $j \geq 2$ we also have $N_{\alpha,j}=o\{\alpha^{2}\ell_1(\alpha)\}.$

The following result is a corollary of Theorem 2 which shows how the parameter $\sigma$ relates to the sparsity and power-law properties of the graphs. We denote by $\ell^\#$ the de Bruijn conjugate (see Definition C.2 in the appendix) of the slowly varying function $\ell$ .

Corollary 1. (Sparsity and power-law degree distribution.) Assume Assumptions 1 and 2. For $\sigma\in[0,1]$ , almost surely as $\alpha$ tends to infinity,

\begin{equation*}{N_{\alpha}^{(e)}}\sim \frac{\overline W }{2} N_\alpha^{2/(1+\sigma)}\ell_\sigma^*(N_\alpha), \quad \ell_\sigma^*(y)=\left [\left \{\ell_\sigma^{1/(1+\sigma)}(y^{1/1+\sigma})\right \}^\#\right ]^2.\end{equation*}

The function $\ell_\sigma^*(y)$ is slowly varying and the graph is dense if $\sigma=0$ and $\lim_{t\rightarrow\infty} \ell(t)=C<\infty$ , as ${N_{\alpha}^{(e)}}/N_{\alpha}^2\rightarrow C^2\overline W/2$ almost surely. Otherwise, if $\sigma>0$ or $\sigma=0$ and $\lim_t \ell(t)=\infty$ , the graph is sparse, as ${N_{\alpha}^{(e)}}/N_{\alpha}^2\rightarrow 0$ . Additionally, for $\sigma\in [0,1)$ , for any $j=1,2,\ldots$ ,

(23) \begin{align}\frac{N_{\alpha,j}}{N_\alpha}\rightarrow \frac{\sigma \Gamma(j-\sigma)}{j!\Gamma(1-\sigma)}\end{align}

almost surely. If $\sigma>0$ , this corresponds to a degree distribution with power-law behaviour, as, for j large,

\begin{equation*}\frac{\sigma \Gamma(j-\sigma)}{j!\Gamma(1-\sigma)}\sim \frac{\sigma}{\Gamma(1-\sigma)j^{1+\sigma}}.\end{equation*}

For $\sigma=1$ , $N_{\alpha,1}/N_\alpha\rightarrow 1$ and $N_{\alpha,j}/N_\alpha\rightarrow 0$ for $j \geq 2$ ; hence the nodes of degree 1 dominate in the graph.

The above results are important in terms of modelling aspects, since they allow a precise description of the degrees and number of edges as a function of the number of nodes. They can also be used to conduct inference on the parameters of the statistical network model, since the behaviour of most estimators will depend heavily on the behaviour of $N_\alpha$ , $N_{\alpha}^{(e)} $ , and possibly $N_{\alpha,j}$ . For instance the naive estimator of $\sigma$ given by

(24) \begin{equation}\hat \sigma = \frac{ 2 \log N_\alpha}{ \log N_\alpha^{(e)} } - 1\end{equation}

is almost surely consistent. Note that, following an earlier version of the present paper, [Reference Naulet, Sharma, Veitch and Roy29] proposed an alternative estimator for $\sigma$ , with better statistical properties. Indeed, under Assumptions 1 and 2, using Theorems 1 and 2, we have almost surely $N_\alpha^2\sim\alpha^{2+2\sigma}\ell_\sigma(\alpha)^2$ and $N_\alpha^{(e)}\sim \alpha^2\overline W/2$ . Hence

\begin{equation*}\log\frac{N_\alpha^2}{N_\alpha^{(e)}}\sim 2\sigma\log\!(\alpha)+\log\!\left(\ell_\sigma(\alpha)^2 2/\overline W\right)\end{equation*}

and the result follows as $\log\ell_\sigma(\alpha)/\log\alpha\rightarrow 0$ .

All of the above results concern the behaviour of small-degree nodes, where the degree j is fixed as the size of the graph goes to infinity. It is also of interest to look at the number of nodes of degree j as both $\alpha$ and j tend to $\infty$ . We show in the next proposition that this is controlled by the behaviour of the function f, introduced in Assumption 3, at 0 or $\infty$ .

Proposition 2. (Power law for high-degree nodes.) Assume that Assumption 3 holds. Then when $j \rightarrow \infty$ , $\log \alpha = o(j)$ , and $j/\alpha \rightarrow c_0 \in [0, \infty]$ , we have

\begin{equation*}E\big(N_{\alpha,j}\big) \sim f(j/\alpha). \end{equation*}

Note that Proposition 2 implies that when $j/\alpha\to\infty$ ,

\begin{equation*} E\big(N_{\alpha,j}\big)\sim\frac{\tau\alpha^{1+\tau}\ell_{2}(j/\alpha)}{j^{1+\tau}},\end{equation*}

which corresponds to power-law behaviour with exponent $1+\tau$ . If $j/\alpha\to 0$ then

\begin{equation*} E\big(N_{\alpha,j}\big)\sim\frac{\alpha^{1+\tilde{\sigma}}\tilde{\ell}_{2}(\alpha/j)}{j^{1+\tilde{\sigma}}}.\end{equation*}

This is similar to the asymptotic results for j fixed, stated in Theorem 1, noting that

\begin{equation*}\frac{\Gamma(j-\sigma)}{j!}\sim j^{-1-\sigma}\end{equation*}

as $j\to\infty$ . Finally, if $j/\alpha \rightarrow c_0 \in (0,\infty)$ , then $ E\big(N_{\alpha,j}\big) \sim f(c_0) \in (0,\infty)$ .

Proof. Under Assumption 3, we have $\mu^{-1}(t)=\int_t^\infty f(x)dx$ with

\begin{equation*}f(x)\sim \tau x^{-\tau-1}\ell_2(x)\text{ as }x\to\infty, \quad f(x)\sim \tau x^{-\sigma-1}\tilde{\ell}_2(x)\text{ as }x\to 0.\end{equation*}

From [Reference Veitch and Roy38, Theorem 5.5] we have, assuming that $W(x,x)=0$ for the sake of simplicity,

\begin{align*}E\big(N_{\alpha,j}\big)&=\alpha\int_0^\infty e^{-\alpha\mu(\vartheta)}\frac{(\alpha\mu(\vartheta))^{j}}{j!}d\vartheta \\&=\alpha\int_0^\infty e^{-\alpha x}\frac{(\alpha x)^{j}}{j!}f(x)dx \\ &= E[ f((j+1) X_j /\alpha) ],\end{align*}

where $X_j$ is a gamma random variable with rate $j+1$ and inverse scale $j+1$ . We split the above expectation into $X_j < 1/2$ , $X_j \in [1/2, 3/2]$ , and $X_j>3/2 $ . The idea is that the third and the first expectations are small because $X_j$ concentrates fast to 1, while the middle expectation ( $X_j \in [1/2, 3/2]$ ) uses the fact that $f((j+1)X_j/\alpha) \approx f((j+1)/\alpha) $ . More precisely, using Stirling’s approximation, for every $\epsilon>0$ there exists $c>0$ such that

\begin{align*}E[ f((j+1) X_j /\alpha) \mathbb{1}_{X_j<1/2}] & = \frac{ (j+1)^{j+1} }{\Gamma(j+1)} \int_0^{1/2} f((j+1)x/\alpha) x^j e^{-(j+1)x}dx \\&\lesssim \sqrt{j} \int_0^{1/2}\left( 1 + \left(\frac{ (j+1)x}{\alpha}\right)^{-1-\tilde{\sigma} -\epsilon } \right) e^{-j(x-\log x -1) } dx \\& \lesssim e^{- c j} \left( 1 + \left(\frac{ j }{ \alpha }\right)^{-1-\tilde{\sigma } -\epsilon } \right) = o(1),\end{align*}

since $\alpha/j = o(e^{cj }) $ for any $c>0$ . The expectation over $X_j >3/2$ is treated similarly. We now study the expectation over $[1/2, 3/2]$ . We have that if $j/\alpha \rightarrow \infty $ , then uniformly in $x \in [1/2, 3/2]$ , under Assumption 3,

\begin{equation*} \left | \frac{ f( (j+1) x/\alpha) }{ f( (j+1) /\alpha) } - x^{-1-\tau} \right| = o(1), \end{equation*}

and similarly when $j/\alpha \rightarrow 0$ , with $\tau $ replaced by $\tilde \sigma$ ; if $j/\alpha \rightarrow c_0 \in (0,\infty)$ , then uniformly in $x \in [1/2, 3/2]$ ,

\begin{equation*} \left | \frac{ f( (j+1) x/\alpha) }{ f( (j+1) /\alpha) } - \frac{f(c_0 x)}{f(c_0)} \right| = o(1). \end{equation*}

Moreover, since $X_j $ converges almost surely to 1, we finally obtain that

\begin{equation*}E\left[ \frac{ f((j+1) X_j /\alpha) }{ f((j+1) /\alpha) } \mathbb{1}_{X_j\in [1/2,3/2]} \right] \to 1, \end{equation*}

which terminates the proof.

3.2. Proof of Theorem 2

The proof follows similarly to that of [Reference Veitch and Roy38, Theorem 6.1], by bounding the variance. The paper [Reference Veitch and Roy38] showed that $\textrm{var}(N_{\alpha})=o(E(N_{\alpha})^2)$ and $\textrm{var}\big(N_{\alpha,j}\big)=o(E\big(N_{\alpha,j}\big)^2)$ and used this result to prove that (22) holds in probability; we need a slightly tighter bound on the variances to obtain the almost sure convergence. This is stated in the next two propositions.

Proposition 3. Let $N_\alpha$ be the number of nodes. We have

(25) \begin{align}\textrm{var}(N_{\alpha}) & =E(N_{\alpha})+2\alpha^{2}\int_{\mathbb{R}_{+}}\mu(x)\{1-W(x,x)\}e^{-\alpha\mu(x)}dx\nonumber\\& \quad +\alpha^{2}\int_{\mathbb{R}_{+}^{2}}\{1-W(x,y)\}\{1-W(x,x)\}\{1-W(y,y)\}\nonumber\\&\qquad \left\{ e^{\alpha \nu(x,y)} -1 +W(x,y) \right\} e^{-\alpha\mu(x)-\alpha\mu(y)}dxdy.\end{align}

Under Assumptions 1 and 2, with $\sigma\in[0,1]$ , slowly varying function $\ell$ , and positive scalar a satisfying (17), we have

(26) \begin{equation}\textrm{var}(N_{\alpha})=O\big\{\alpha^{3+2\sigma-2a}\ell_\sigma(\alpha)^2\big\},\end{equation}

where the slowly varying functions $\ell_\sigma$ are defined in Equation (20). Additionally, under Assumptions 1 and 4, we have, for any $\sigma\in[0,1]$ and any slowly varying function $\ell$ ,

(27) \begin{equation}\textrm{var}(N_{\alpha})\asymp\alpha^{1+2\sigma}\ell_\sigma^{2}(\alpha).\end{equation}

Sketch of the proof. We give here the ideas behind the proof, deferring its completion to Section A.1 of the supplementary material [Reference Caron, Panero and Rousseau13]. Equation (25) is immediately obtained using the Slivnyak–Mecke and Campbell theorems. Applying the inequality $e^{x}-1\le xe^x$ and Lemmas B.2 and B.6 to the right-hand side of Equation (25), we obtain the upper bound of Equation (26). Finally, if Assumption 4 holds, then Assumption 2 holds as well with $a=1$ . Combining this with Assumption 1, we can therefore specialise the upper bound of Equation (26) to the case $a=1\,:\, O(\alpha^{1+2\sigma}\ell^2_\sigma(\alpha))$ . The lower bound with the same order is found using the inequality $e^x-1\ge x$ and Lemmas B.2 and B.3.

Proposition 3 and Theorem 1 imply in particular that, under Assumptions 1 and 2,

\begin{equation*}\textrm{var}(N_{\alpha})=O\big\{E(N_\alpha)^2 \alpha^{-\kappa}\big\}\end{equation*}

for some $\kappa>0$ . Here $N_\alpha$ is a positive, monotone increasing stochastic process. Using Lemma B.1 in the appendix, we obtain that $N_\alpha\sim E(N_\alpha)$ almost surely as $\alpha$ tends to $\infty$ .

Proposition 4. Let $N_{\alpha,j}$ be the number of nodes of degree j. Then, under Assumptions 1 and 2, with $\sigma\in[0,1]$ , slowly varying function $\ell$ , and positive scalar a satisfying (17), we have

\begin{equation*}\textrm{var}\big(N_{\alpha,j}\big)=O\big\{\alpha^{3+2\sigma-2a}\ell_\sigma(\alpha)^2\big\}.\end{equation*}

where the slowly varying functions $\ell_\sigma$ are defined in Equation (20). In the case $\sigma=0$ and $a=1$ , we have the stronger result

\begin{equation*}\textrm{var}\big(N_{\alpha,j}\big)=o\big\{\alpha\ell(\alpha)^2\big\}.\end{equation*}

Sketch of the proof. While the complete proof of Proposition 4 is given in Section A.2 in the supplementary material [Reference Caron, Panero and Rousseau13], we explain here its main passages. We start by evaluating the expectation of $N_{\alpha, j}^2$ and $N_{\alpha, j}$ conditional on the unit-rate Poisson random measure $M=\sum_{i}\delta_{(\theta_{i},\vartheta_{i})}$ :

\begin{align*}& E\big(N_{\alpha,j}^{2}\mid M\big)-E\big(N_{\alpha,j}\mid M\big)\nonumber\\&= \sum_{i_{1}\neq i_{2}}\mathbb{1}_{\theta_{i_{1}}\leq\alpha}\mathbb{1}_{\theta_{i_{2}}\leq\alpha}\mathbb{P}\left\{ \sum_{k}\mathbb{1}_{\theta_{k}\leq\alpha}Z_{i_{1}k}=j\text{ and } \sum_{k}\mathbb{1}_{\theta_{k}\leq\alpha}Z_{i_{2},k}=j\mid M\right\}\\&=\sum_{b\in\{0,1\}^3} \sum_{j_1=0}^j \sum_{i_{1}\neq i_{2}}\mathbb{1}_{\theta_{i_{1}}\leq\alpha}\mathbb{1}_{\theta_{i_{2}}\leq\alpha}\\&\quad \times\mathbb{P}\left\{ \sum_{k}\mathbb{1}_{\theta_{k}\leq\alpha}Z_{i_{1}k}=j\text{ and } \sum_{k}\mathbb{1}_{\theta_{k}\leq\alpha}Z_{i_{2},k}=j\text{ and } \sum_{k}\mathbb{1}_{\theta_{k}\leq\alpha}Z_{i_{1}k}Z_{i_{2}k}=j-j_1\right .\\&\quad \quad \quad \quad \left .\text{ and }Z_{i_1i_1}=b_{11},Z_{i_1i_2}=b_{12},Z_{i_2i_2}=b_{22} \mid M\right \},\end{align*}

where $b=(b_{11},b_{12},b_{22})\in\{0,1\}^3$ . We then use the Slivnyak–Mecke theorem to obtain $E(N_{\alpha,j}^{2})-E\big(N_{\alpha,j}\big)$ , which can be bounded by a sum of terms of the form

(28) \begin{equation}\alpha^2\int_{\mathbb{R}^2} [\alpha\mu(x)]^{k_1}[\alpha\mu(y)]^{k_2} (\alpha \nu(x,y))^{r} e^{ - \alpha \mu(x) -\alpha \mu(y) +\alpha \nu(x,y)}dxdy\end{equation}

for $k_1,k_2,r\in\{0,\ldots,j\}$ . For terms with $r\geq1$ , we use Lemma A.1 (enunciated and proved, using Lemmas B.2 and B.4, in Section A.2 of the supplementary material). The lemma states that, under Assumptions 1 and 2, the integral in (28) is in $O\big( \alpha^{r-2ar+2\sigma } \ell_\sigma^2(\alpha)\big)\big)=O\big( \alpha^{1-2a+2\sigma } \ell_\sigma^2(\alpha)\big)\big)$ for any $r\ge 1$ , $k_1,k_2\ge 0$ . For terms with $r=0$ in (28), we use the inequality $e^{x}\leq 1+xe^x$ , the Cauchy–Schwarz inequality, and Lemma B.4 to show that these terms are in $O\big\{\alpha^{3+2\sigma-2a}\ell_\sigma^2(\alpha)\big\}$ , which completes the proof.

Define $\widetilde{N}_{\alpha,j} =\sum_{k\geq j}N_{\alpha,k}$ , the number of nodes of degree at least j. Note that $\widetilde{N}_{\alpha,j}$ is a positive, monotone increasing stochastic process in $\alpha$ , with $ \widetilde{N}_{\alpha,j} = N_\alpha - \sum_{k = 1}^{j-1} N_{\alpha,k}$ . We then have, using the Cauchy–Schwarz and Jensen inequalities, that

\begin{equation*} E\big(\widetilde{N}_{\alpha,j}\big) = E(N_\alpha) - \sum_{k = 1}^{j-1} E( N_{\alpha,k}), \quad \textrm{var}\big(\widetilde{N}_{\alpha,j}\big) \leq j \left\{ \textrm{var}(N_\alpha) + \sum_{k = 1}^{j-1} \textrm{var}( N_{\alpha,k})\right\}.\end{equation*}

Consider first the case $\sigma\in[0,1)$ . Since Theorem 1 implies, for $j\geq 2$ , $\alpha^{1+\sigma}\ell(\alpha) \lesssim E\big(\widetilde{N}_{\alpha,j}\big)$ as $\alpha$ goes to infinity, using Propositions 3 and 4, we obtain $\textrm{var}\big(\widetilde N_{\alpha,j}\big) =O\{\alpha^{-\tau} E\big(\widetilde N_{\alpha,j}\big)^2 \}$ for some $\tau>0$ . Combining this with Lemma B.1 leads to $\widetilde N_{\alpha,j}\sim E\big(\widetilde N_{\alpha,j}\big)$ almost surely as $\alpha$ goes to infinity.

The almost sure results for $N_{\alpha,j}$ then follow from the fact that, for all $j\geq 2$ , $E\big(\widetilde N_{\alpha,j}\big)\asymp E(N_\alpha)$ if $\sigma\in(0,1)$ , $E\big(\widetilde N_{\alpha,j}\big)\sim E(N_\alpha)$ if $\sigma=0$ , and $E\big(\widetilde N_{\alpha,j}\big)=o\{E(N_\alpha)\}$ if $\sigma=1$ .

3.3. Asymptotic behaviour of the clustering coefficients

The following proposition is a direct corollary of [Reference Borgs, Chayes, Cohn and Holden9, Proposition 56], which showed the almost sure convergence of subgraph counts in graphex processes.

Proposition 5. (Global clustering coefficient [Reference Borgs, Chayes, Cohn and Holden9].) Assume $\int_{0}^{\infty}\mu(x)^{2}dx<\infty$ . Recall that $T_\alpha$ and $A_\alpha$ are respectively the number of triangles and the number of adjacent edges in the graph of size $\alpha$ . We have

\begin{align*}T_{\alpha} & \sim E(T_{\alpha})=\frac{\alpha^{3}}{6}\int_{\mathbb{R}_{+}^{3}}W(x,y)W(x,z)W(y,z)dxdydz,\\A_{\alpha} & \sim E(A_{\alpha})=\frac{\alpha^{3}}{2}\int_{0}^{\infty}\mu(x)^{2}dx\end{align*}

almost surely as $\alpha\rightarrow\infty$ . Therefore, if $\int_{0}^{\infty}\mu(x)^{2}dx>0$ , the global clustering coefficient defined in Equation (11) converges to a constant

\begin{equation*}C_{\alpha}^{(g)}\rightarrow\frac{\int_{\mathbb{R}_{+}^{3}}W(x,y)W(x,z)W(y,z)dxdydz}{\int_{0}^{\infty}\mu(x)^{2}dx} \quad { almost\ surely\ as }\ \alpha\rightarrow\infty.\end{equation*}

Note that if $\mu$ is monotone decreasing, as $\overline{W}<\infty$ , we necessarily have $\int_{a}^{\infty}\mu(x)^{2}dx<\infty$ for any $a>0$ . Hence the condition $\int_{0}^{\infty}\mu(x)^{2}dx<\infty$ in Proposition 5 requires additional assumptions on the behaviour of $\mu$ at 0 (or equivalently the behaviour of $\mu^{-1}$ at $\infty$ ), which drives the behaviour of large-degree nodes. If the graph is dense, $\mu$ is bounded and thus $\int_{0}^{\infty}\mu(x)^{2}dx<\infty$ .

Proposition 6. (Local clustering coefficient.) Assume Assumptions 1 and 2 hold with $\sigma\in(0,1)$ . Assume additionally that

(29) \begin{equation} \lim_{x\rightarrow\infty}\frac{\int_{\mathbb{R}_{+}^{2}}W(x,y)W(x,z)W(y,z)dydz}{\mu(x)^{2}}\rightarrow b\end{equation}

for some $b\in[0,1]$ . Then the local clustering coefficients converge in probabiltiy as $\alpha\rightarrow\infty$ :

\begin{align*}C_{\alpha,j}^{(\ell)} & \rightarrow b \quad \forall j\geq2.\end{align*}

If $b>0$ , the above result holds almost surely, and the average local clustering coefficient satisfies

\begin{align*}\lim_{\alpha \rightarrow \infty} \overline{C}_{\alpha}^{(\ell)} & \rightarrow b, \quad almost\ surely .\end{align*}

In general,

\begin{equation*}\lim_{x\rightarrow\infty}\frac{1}{\mu(x)^{2}}\int W(x,y)W(x,z)W(y,z)dydz\neq\frac{\int W(x,y)W(x,z)W(y,z)dxdydz}{\int\mu(x)^{2}dx},\end{equation*}

and the global clustering and local clustering coefficients converge to different limits. A notable exception is the separable case where $W(x,y)=\mu(x)\mu(y)/\overline{W}$ , since in this case

\begin{equation*} \int W(x,y)W(x,z)W(y,z)dydz = \overline{W}^{-3}\mu(x)^2\left(\int \mu(y)^2dy\right)^2 , \quad b = \frac{ \left(\int \mu(y)^2dy\right)^2 }{\overline{W}^{3} } \end{equation*}

and

\begin{equation*} \int W(x,y)W(x,z)W(y,z)dydzdx = \overline{W}^{-3}\left(\int \mu(y)^2dy\right)^3 .\end{equation*}

Sketch of the proof. Full details are given in Appendix A.2; here we give only a sketch of the proof, which is similar to that of Theorem 2. We have

\begin{equation*}C_{\alpha,j}^{(\ell)} = \frac{ 2 R_{\alpha,j} }{ j(j-1) N_{\alpha,j} }, \quad \text{where} \quad R_{\alpha,j} = \sum_i T_{\alpha,i} \mathbb{1}_{D_{\alpha,i}=j}. \end{equation*}

Here $R_{\alpha,j}$ corresponds to the number of triangles having a node of degree j as a vertex; triangles having $k\leq 3$ degree-j nodes as vertices are counted k times.

We obtain an asymptotic expression for $E\big(R_{\alpha,j}\big)$ , and show that $\textrm{var}\big( R_{\alpha,j} \big) = O\big(\alpha^{1 -2a} \big[E\big(R_{\alpha,j}\big)\big]^2 \big)$ . We then prove that $R_{\alpha,j}/E\big(R_{\alpha,j}\big) $ goes to 1 almost surely. The latter is obtained by proving that $ R_{\alpha,j}$ is nearly monotone increasing by constructing an increasing sequence $\alpha_n $ going to infinity such that $E\big(R_{\alpha_n,j}\big)/E\big(R_{\alpha_{n+1},j}\big)$ goes to 1 and such that for all $\alpha \in (\alpha_n, \alpha_{n+1})$ ,

\begin{equation*} R_{\alpha_n,j} - \tilde R_{n,j} \leq R_{\alpha,j}\leq R_{\alpha_{n+1},j} + \tilde R_{n,j}, \qquad \tilde R_{n,j}= o\big(E\big(R_{\alpha_n,j} \big)\big).\end{equation*}

Roughly speaking, $\tilde R_{n,j}$ (defined in Equation (60)) corresponds to the sum of the number of triangles $T_{\alpha_{n+1} i}$ , over the set of nodes i such that $D_{n,i}\leq j$ and i has at least one connection with some ${i^{\prime}}$ such that $\theta_{i^{\prime}} \in (\alpha_n, \alpha_{n+1})$ . The result for the local clustering coefficient then follows from Toeplitz’s lemma (see e.g. [Reference Loève27, p. 250]).

4.1. CLT for subgraph counts

4.1.1. Statement of the result

Let F be a given subgraph which has neither isolated vertices nor loops. Denote by $|F|$ the number of nodes, $\{1, \cdots, |F|\}$ the set of vertices, and e(F) the set of edges. Let $N^{(F)}_{\alpha}$ be the number of subgraphs F in the graph $\mathcal{G}_\alpha$ :

\begin{equation*} N^{(F)}_\alpha =k_{(F)}\sum_{(v_1,\cdots, v_{|F|})}^{\neq} \prod_{(i,j) \in e(F)} Z_{v_{i},v_{j}} \mathbb{1}_{\theta_{v_{i}}\le\alpha}\mathbb{1}_{\theta_{v_{j}}\le\alpha},\end{equation*}

where $k_{(F)}$ is a constant accounting for the multiple counts of F, which we can omit in the rest of the discussion since it does not depend on $\alpha$ . Note that this statistic covers the number of edges (excluding loops) if $|F|=2$ and the number of triangles if $|F|=3$ and $e(F)=\{(1,2),(1,3),(2,3)\}$ . It is known in the graph literature as the number of injective adjacency maps from the vertex set of F to the vertex set of $\mathcal{G}_\alpha$ ; see [Reference Borgs, Chayes, Cohn and Holden9, Section 2.5].

Proposition 7. Let F be a subgraph without loops or isolated vertices. Assume that $\int_0^\infty \mu(x)^{2|F|-2}dx<\infty$ . Then

(30) \begin{equation}\frac{ N^{(F)}_{\alpha} - E\big(N^{(F)}_{\alpha}\big) }{ \sqrt{\textrm{var}\big(N^{(F)}_{\alpha}\big) }} \to \mathcal N(0,1),\end{equation}

as $\alpha$ goes to infinity, where

(31) \begin{align}E\big(N^{(F)}_{\alpha}\big)& = k_{(F)}\alpha^{|F|} \int_{\mathbb R_+^{|F|}} \prod_{(i,j)\in e(F)} W(x_i,x_j)dx_1\cdots dx_{|F|}<\infty\end{align}

and

\begin{equation*}\textrm{var}\big(N^{(F)}_{\alpha}\big)\sim c_F \alpha^{2|F|-1} \end{equation*}

for some positive constant $c_F$ that depends only on F.

Remark 3. If the graph is dense, then $\mu$ is a bounded function with bounded support and therefore $\int_0^\infty \mu(x)^{p}dx<\infty$ for any p. In the sparse case, if $\mu$ is monotone, we necessarily have $\int_a^\infty \mu(x)^p dx<\infty$ for any $p>1$ . The condition $\int_0^\infty \mu(x)^{2|F|-2}dx<\infty$ therefore requires additional assumptions on the behaviour of $\mu$ at 0, which drives the behaviour of large-degree nodes.

4.1.2. Proof

Recall that $M=\sum_{i}\delta_{(\theta_{i},\vartheta_{i})}$ . The main idea of the proof is to use the decomposition

(32) \begin{equation} N^{(F)}_{\alpha} - E\big(N^{(F)}_{\alpha}\big) = E\big(N^{(F)}_{\alpha}|M\big) - E\big(N^{(F)}_{\alpha}\big) + N^{(F)}_{\alpha} - E\big(N^{(F)}_{\alpha}|M\big), \end{equation}

and to show that $E\big(N^{(F)}_{\alpha}|M\big)$ is a geometric U-statistic of a Poisson process, for which a CLT has been derived by [Reference Reitzner and Schulte35].

In this section, denote by $K=|F|\geq 2$ the number of nodes of the subgraph F. The subgraph counts are

\begin{align*}N^{(F)}_\alpha &=k_{(F)}\sum_{(v_1,\cdots, v_K)}^{\neq} \left ( \prod_{k=1}^K \mathbb{1}_{\theta_{v_{k}}\leq \alpha} \right ) \frac{1}{|\mathbb S_K|}\sum_{\pi\in \mathbb S_K} \prod_{(i,j) \in e(F)} Z_{v_{\pi_i},v_{\pi_j}},\end{align*}

where $\mathbb S_K$ denotes the set of permutations of $\{1,\ldots, K\}$ .

Using the extended Slivnyak–Mecke theorem, we have

(33) \begin{align}E\big(N^{(F)}_{\alpha}\big)& = k_{(F)}\alpha^K \int_{\mathbb R_+^K} \prod_{(i,j)\in e(F)} W(x_i,x_j)dx_1\cdots dx_K.\end{align}

As $\int_0^\infty \mu(x)^{K-1}dx<\infty$ , [Reference Borgs, Chayes, Cohn and Holden9, Lemma 62] implies that $E\big(N^{(F)}_{\alpha}\big)<\infty$ . For any $K\geq 2$ , define the symmetric function

\begin{equation*}f(x_1,\ldots,x_K)=\frac{1}{|\mathbb S_K|} \sum_{\pi\in \mathbb S_K} \prod_{(i,j)\in e(F)} W\big(x_{\pi_i},x_{\pi_j}\big);\end{equation*}

using the condition (3) and the fact that $\int_0^\infty \mu(x)^{K-1}dx<\infty$ , it satisfies $0 <\int_{\mathbb R_+^{K}} f(x_1,\ldots,x_K)dx_1\ldots dx_K<\infty.$

We state the following useful lemma.

Lemma 1. The function f satisfies, for all $x_K\geq 0$ ,

\begin{equation*}g(x_K)\,:\!=\,\int_{\mathbb R_+^{K-1}} f(x_1,\ldots,x_{K-1},x_K)dx_1\ldots dx_{K-1}\leq C_0\max\big(\mu(x_K),\mu(x_K)^{K-1}\big)\end{equation*}

for some constant $C_0$ .

Proof. Let $\pi\in\mathbb S_K$ and $r_K\in \{1,\ldots,K\}$ be such that $\pi_{r_K}=K$ . Denote by $S\subseteq \{1,\ldots,$ $K-1\}$ the set of indices i such that $(i,r_K)\in e(F)$ and i has no other connections in F. Then

\begin{align*}\int_{\mathbb R_+^{K-1}}& \prod_{(i,j)\in e(F)} W(x_{\pi_i},x_{\pi_j}) dx_1\ldots dx_{K-1}\leq C_1 \int_{\mathbb R_+^{|S|}} \left [\prod_{i\in S} W\big(x_{\pi_i},x_K\big)dx_i\right ]\\&= C_1 \mu(x_K)^{|S|} \leq C_1 \max\big(\mu(x_K),\mu(x_K)^{K-1}\big)\end{align*}

for some constant $C_1$ .

It follows from Lemma 1 and from the fact that $\int_0^\infty\mu(x)dx<\infty$ that, if $\int_0^\infty \mu(x)^{2K-2}$ $dx<\infty$ , then

\begin{align*}\int_0^\infty \left (\int_{\mathbb R_+^{K-1}} f(x_1,\ldots,x_{K-1},y)dx_1\ldots dx_{K-1} \right )^2dy<\infty.\end{align*}

We are now ready to derive the asymptotic expression for the variance of $N^{(F)}_\alpha$ . Using the extended Slivnyak–Mecke theorem again,

\begin{align*}&E\big(\big(N^{(F)}_\alpha\big)^2\big)=E\big(E\big((N^{(F)}_\alpha)^2 \mid M\big)\big)\\&=k_{(F)}^2 E\left(\sum_{\big(v_1,\cdots, v_K,v^{\prime}_1,\ldots,v^{\prime}_K\big)}^{\neq} f\big(\vartheta_{v_1},\ldots,\vartheta_{v_K}\big)f\big(\vartheta_{v^{\prime}_1},\ldots,\vartheta_{v^{\prime}_K}\big)\prod_{k=1}^{K}\mathbb{1}_{\theta_{v_k}\leq \alpha}\mathbb{1}_{\theta_{v^{\prime}_k}\leq \alpha} \right )\\&\quad + k_{(F)}^2 K^2 E\left(\sum_{\substack{\big(v_1,\cdots, v_K, \\v^{\prime}_1,\ldots,v_{K-1}^{\prime}\big)} }^{\neq} f\big(\vartheta_{v_1},\ldots,\vartheta_{v_K}\big)f\big(\vartheta_{v^{\prime}_1},\ldots,\vartheta_{v^{\prime}_{K-1}},\vartheta_{v_{K}} \big)\mathbb{1}_{\theta_{v_{K}}\leq\alpha}\prod_{k=1}^{K-1}\mathbb{1}_{\theta_{v_k}\leq \alpha}\mathbb{1}_{\theta_{v^{\prime}_k}\leq \alpha} \right )\\&+O\big(\alpha^{2K-2}\big)\\&= k_{(F)}^2 K^2 \alpha^{2K-1}\int_{\mathbb R_+^{2K-1}} f\big(x_1,\ldots,x_K\big)f\big(x^{\prime}_1,\ldots,x^{\prime}_{K-1},x_{K}\big)dx_1,\ldots dx_K dx^{\prime}_1\ldots dx^{\prime}_{K-1} \\&+E\big(N^{(F)}_\alpha\big)^2 +O\big(\alpha^{2K-2}\big).\end{align*}

It follows that

\begin{align*}\textrm{var}\big(N^{(F)}_\alpha\big)\sim k_{(F)}^2 K^2 \alpha^{2K-1} \sigma_F^2\end{align*}

as $\alpha$ tends to infinity, where

\begin{equation*}\sigma_F^2=\int_0^\infty \left(\int_{\mathbb R_+^{K-1}} f(x_1,\ldots,x_{K-1},y)dx_1\ldots dx_{K-1} \right )^2 dy<\infty.\end{equation*}

We now prove the CLT. The first term of the right-hand side of Equation (32) takes the form

(34) \begin{equation}E\big(N^{(F)}_{\alpha}|M\big) = k_{(F)} \sum_{(v_1,\cdots, v_K)}^{\neq} f\big(\vartheta_{v_1},\ldots,\vartheta_{v_K}\big)\prod_{i=1}^K \mathbb{1}_{\theta_{v_i}\leq \alpha}.\end{equation}

By the superposition property of Poisson random measures, we have

\begin{equation*}E\big(N^{(F)}_{\alpha}|M\big) \overset{d}{=}k_{(F)} \sum_{(v_1,\cdots, v_K)}^{\neq} f\big(\widetilde\vartheta_{v_1},\ldots,\widetilde\vartheta_{v_K}\big)\prod_{i=1}^K \mathbb{1}_{\widetilde\theta_{v_i}\leq 1},\end{equation*}

where the right-hand side is a geometric U-statistic [Reference Reitzner and Schulte35, Definition 5.1] of the Poisson point process $\big\{\big(\widetilde \theta_i,\widetilde \vartheta_i\big)_{i\geq 1}\big\}$ with mean measure $\alpha d\widetilde \theta d\widetilde\vartheta$ on $[0,1]\times\mathbb R_+$ . Theorem 5.2 in [Reference Reitzner and Schulte35] therefore implies that

(35) \begin{align}\frac{E\big(N_{\alpha}^{(F)}\mid M\big)-E\big(N_\alpha^{(F)}\big)}{\sqrt{\textrm{var}\big(E\big(N_{\alpha}^{(F)} \mid M\big)\big)}}\to\mathcal N(0,1),\end{align}

where $\textrm{var}\big(E\big(N_{\alpha}^{(F)} \mid M\big)\big)\sim \textrm{var}\big(N_{\alpha}^{(F)}\big)\sim k_{(F)}^2 |F|^2 \alpha^{2|F|-1} \sigma_F^2$ . One can show similarly (proof omitted) that $\textrm{var}\big(N_{\alpha}^{(F)}-E\big(N_{\alpha}^{(F)}\mid M\big)\big)=o\big(\alpha^{2|F|-1}\big)$ . It follows from Equations (32) and (35) and the Chebyshev inequality that

\begin{equation*}\frac{N_{\alpha}^{(F)}-E\big(N_{\alpha}^{(F)}\big)}{\sqrt{\textrm{var}\big(N_{\alpha}^{(F)}\big)}}\to \mathcal N(0,1)\end{equation*}

as $\alpha$ tends to infinity.

4.2. CLT for $N_\alpha$ (dense case)

4.2.1. Statement of the result

In the dense case, $\mu$ has bounded support. If it is monotone decreasing, then Assumption 1 is satisfied with $\sigma=0$ , and $\ell(t)=\sup\{x>0\mid\mu(x)>0\}$ is constant. In this case a CLT applies, as described in the following theorem.

Theorem 3. (Dense case.) Assume that Assumption 1 holds with $\sigma=0$ and $\ell(t)= C\in(0,\infty)$ , where $C=\sup\{x>0\mid\mu(x)>0\}$ (dense case). Also assume that Assumption 2 holds with $a=1$ . Then

(36) \begin{equation}\frac{N_{\alpha}-E(N_\alpha)}{\sqrt{\alpha C} } \rightarrow\mathcal{N}(0,1).\end{equation}

Moreover, $E(N_\alpha) = \alpha C -m_{\alpha,0}$ , where

(37) \begin{equation}m_{\alpha,0}=\alpha\int_{0}^{C}e^{-\alpha\mu(x)}(1-W(x,x)) dx=o(\alpha).\end{equation}

The quantity $m_{\alpha,0}$ can be interpreted as the expected number of degree-0 nodes, and is finite in the dense case. As shown in the following examples, $m_{\alpha,0}$ can either diverge or converge to a constant as $\alpha$ tends to infinity.

Example 1. Consider $\mu(x)=\mathbb{1}_{x\in\lbrack0,1]}$ , $\mu(x)=(1-x)^{2}\mathbb{1}_{x\in\lbrack0,1]}$ , and $\mu(x)=(1-x)^{3}\mathbb{1}_{x\in\lbrack0,1]}$ . We respectively have $m_{\alpha,0}\rightarrow0$ , $m_{\alpha,0}\sim\frac{\sqrt{\pi}}{2}\alpha^{1/2}$ , and $m_{\alpha,0}\sim\Gamma(4/3)\alpha^{2/3}$ .

The above CLT for $N_\alpha$ can be generalised to $\widetilde N_{\alpha,j}=\sum_{k\geq j} N_{\alpha,k}$ , the number of nodes of degree at least j.

Theorem 4. Assume that Assumption 1 holds with $\sigma=0$ and $\ell(t)= C\in(0,\infty)$ , where $C=\sup\{x>0\mid\mu(x)>0\}$ (dense case). Also assume that Assumption 2 holds with $a=1$ . Then for any $j\geq 1$ ,

(38) \begin{equation}\frac{\widetilde N_{\alpha,j}-E\big(\widetilde N_{\alpha,j}\big)}{\sqrt{\alpha C} } \rightarrow\mathcal{N}(0,1).\end{equation}

Moreover, $E\big(\widetilde N_{\alpha,1}\big)=E(N_\alpha)=\alpha C-m_{\alpha,0}$ , and for $j\geq 2$ , $E\big(\widetilde N_{\alpha,j}\big) = \alpha C -m_{\alpha,0}-\sum_{k=1}^{j-1}E\big(N_{\alpha,j}\big)$ , where $m_{\alpha,0}$ is defined in Equation (37) and $E\big(N_{\alpha,j}\big)$ is defined in Equation (53). Note that $m_{\alpha,0}=o(\alpha)$ , and for any $j\geq 1$ , $E\big(N_{\alpha,j}\big)=o(\alpha)$ .

4.2.2. Proof

Given a point ( $\theta,\vartheta$ ) such that $\vartheta>C$ , its degree is necessarily equal to zero, as $\mu(\vartheta)=0$ . Write

\begin{equation*}N_{\alpha}=Q_{\alpha}-N_{\alpha,0}, \quad \text{where} \quad Q_{\alpha}=\sum_{i}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{\vartheta_{i}\leq C};\end{equation*}

$Q_{\alpha}$ is the total number of nodes i with $\theta_i\leq \alpha$ that could have a connection (hence such that $\mu(\vartheta_i)>0$ ), and

\begin{equation*}N_{\alpha,0}=\sum_{i}\mathbb{1}_{\theta_{i}\leq\alpha}\mathbb{1}_{\vartheta_{i}\leq C}\mathbb{1}_{D_{\alpha,i}=0}\end{equation*}

is the set of nodes i with degree 0, but for which $\theta_i\leq\alpha$ , $\mu(\vartheta_i)>0$ . In the dense regime, both $Q_{\alpha}$ and $N_{\alpha,0}$ are almost surely finite. Furthermore, $(Q_{\alpha})_{\alpha\geq 0}$ is a homogeneous Poisson process with rate C. By the law of large numbers, $Q_{\alpha}\sim\alpha C\sim N_{\alpha}$ almost surely as $\alpha$ tends to infinity. Using Campbell’s theorem, the Slivnyak–Mecke formula, and monotone convergence, we have $E(N_{\alpha,0})=\alpha\int_{0}^{C}(1-W(x,x))e^{-\alpha\mu(x)}dx=o(\alpha).$ We also have that

\begin{align*}E\big(N_{\alpha,0}^{2}\big)-E(N_{\alpha,0})=\alpha^{2}\int_{0}^{C}\int_{0}^{C}&(1-W(x,x))(1-W(y,y))(1-W(x,y))\\& \times e^{-\alpha\mu(x)-\alpha\mu(y)+\alpha\nu(x,y)}dxdy.\end{align*}

Hence, using the inequality $e^{x}-1\leq xe^{x}$ , we obtain

\begin{align*}\textrm{var}(N_{\alpha,0}) & =\alpha^{2}\int_{0}^{C}\int_{0}^{C}(1-W(x,x))(1-W(y,y))(1-W(x,y))e^{-\alpha\mu(x)-\alpha\mu(y)+\alpha\nu(x,y)}dxdy\\& \quad -\alpha^{2}\left( \int_{0}^{C}(1-W(x,x))e^{-\alpha\mu(x)}dx\right) ^{2}+E(N_{\alpha,0})\\& \leq E(N_{\alpha,0})+\alpha^{3}\int_{0}^{C}\int_{0}^{C}\nu(x,y)e^{-\alpha\mu(x)-\alpha\mu(y)+\alpha\nu(x,y)}dxdy.\end{align*}

Using Lemma B.6 in the appendix and Assumption 2 with $a=1$ , we have

\begin{equation*}\int_{0}^{C}\int_{0}^{C}\nu(x,y)e^{-\alpha/2\mu(x)-\alpha/2\mu(y)}dxdy=o\big(\alpha^{-2}\big).\end{equation*}

It follows that $\textrm{var}(N_{\alpha,0})=o(\alpha)$ . This implies, by Chebyshev’s inequality, the CLT for Poisson processes, and Slutsky’s theorem, that

\begin{equation*}\frac{ N_\alpha - E(N_\alpha) }{ \sqrt{\alpha C} } =\frac{ Q_\alpha - \alpha C }{ \sqrt{\alpha C} } - \frac{ N_{\alpha,0} - E(N_{\alpha,0}) }{ \sqrt{\alpha C} } \rightarrow \mathcal N(0,1).\end{equation*}

This concludes the proof of Theorem 3. The proof of Theorem 4 follows similarly. Note that the case $j=1$ in Theorem 4 corresponds to Theorem 3. For any $j\geq 2$ , $\widetilde N_{\alpha,j}=Q_{\alpha}-N_{\alpha,0}-\sum_{k=1}^{j-1} N_{\alpha,k}.$ We have, using the Cauchy–Schwarz inequality and Proposition 4,

\begin{equation*}\textrm{var}\left (N_{\alpha,0}+\sum_{k=1}^{j-1} N_{\alpha,k}\right)\leq j\left (\textrm{var}(N_{\alpha,0})+\sum_{k=1}^{j-1} \textrm{var}(N_{\alpha,k})\right )=o(\alpha).\end{equation*}

This implies

\begin{equation*}\frac{ \widetilde N_{\alpha,j} - E\big(\widetilde N_{\alpha,j}\big) }{ \sqrt{\alpha C} } =\frac{ Q_\alpha - \alpha C }{ \sqrt{\alpha C} } -\frac{N_{\alpha,0}+\sum_{k=1}^{j-1} N_{\alpha,k}-E\big(N_{\alpha,0}+\sum_{k=1}^{j-1} N_{\alpha,k}\big)}{\sqrt{\alpha C}} \rightarrow \mathcal N(0,1).\end{equation*}

4.3. CLT for $N_\alpha$ (sparse case)

4.3.1. Statement of the result

We now assume that we are in the sparse regime; that is, $\mu$ has unbounded support. We make the following additional assumption in order to prove the asymptotic normality. This holds when W is separable, as well as in the model of [Reference Caron and Fox12] under some moment conditions (see Section 6.5).

Assumption 5. Assume that for any $j\leq 6$ and any $(x_1,\ldots,x_j)\in\mathbb R_+^j$ ,

\begin{equation*}\int_0^\infty \prod_{i=1}^j W(x_i,y)dy \leq \prod_{i=1}^j L(x_i)\mu(x_i),\end{equation*}

where L is a locally integrable, slowly varying function converging to a (strictly positive) constant, such that

\begin{equation*}\int_0^\infty L(x)\mu(x)dx<\infty.\end{equation*}

We now state the CLT for $N_\alpha$ under the sparse regime. Recall that in this case, when Assumption 1 holds, we have either $\sigma=0$ and $\ell(t)\to\infty$ or $\sigma\in(0,1]$ .

Theorem 5. (Sparse case.) Assume that $\mu$ has unbounded support (sparse regime). Under Assumptions 1, 4, and 5, we have

\begin{equation*}\frac{N_{\alpha}-E(N_{\alpha})}{\sqrt{\textrm{var}(N_{\alpha})}}\rightarrow\mathcal{N}(0,1).\end{equation*}

Remark 4. As detailed in Proposition 3, under Assumptions 1 and 4, for any $\sigma\in[0,1]$ and any slowly varying function $\ell$ we have $\textrm{var}(N_{\alpha})\asymp\alpha^{1+2\sigma}\ell_\sigma^{2}(\alpha),$ where the slowly varying function $\ell_\sigma$ is defined in Equation (20).

4.3.2. Proof

The proof uses the recent results of [Reference Last, Peccati and Schulte24] on normal approximations of nonlinear functions of a Poisson random measure. We have the decomposition

\begin{align*}N_{\alpha}-E(N_{\alpha}) & =(N_{\alpha}-E(N_{\alpha}\mid M))+(E(N_{\alpha}\mid M)-E(N_{\alpha}))\\& =(N_{\alpha}-E(N_{\alpha}\mid M))+(M(h_{\alpha})-E(N_{\alpha}))+f_{\alpha}(M),\end{align*}

where

\begin{equation*}f_{\alpha}(M)=\sum_{i}\mathbb{1}_{\theta_{i}\leq\alpha}\left[ (1-W(\vartheta_{i},\vartheta_{i}))e^{-\alpha\mu(\vartheta_{i})}-e^{-M\big(g_{\alpha,\vartheta_{i}}\big)}\right]\end{equation*}

is a nonlinear functional of the Poisson random measure M, and

\begin{equation*}M(h_{\alpha})=\sum_{i}\mathbb{1}_{\theta_{i}\leq\alpha}\left[ 1-(1-W(\vartheta_{i},\vartheta_{i}))e^{-\alpha\mu(\vartheta_{i})}\right]\end{equation*}

is a linear functional of M with $h_{\alpha}(\theta,\vartheta)=\mathbb{1}_{\theta\leq\alpha}\left[ 1-(1-W(\vartheta,\vartheta))e^{-\alpha\mu(\vartheta)}\right] $ . Theorem 5 is a direct consequence of the following three propositions and of Slutsky’s theorem.

Proposition 8. Under Assumptions 1 and 4, we have

\begin{equation*}N_{\alpha}-E(N_{\alpha}\mid M)=\left \{\begin{array}{l@{\quad}l} O\big(\alpha^{1/2+\sigma/2}\ell^{1/2}_\sigma(\alpha)\big) & if \ \sigma\in[0,1),\\[4pt] o\big(\alpha^{1/2}\ell^{1/2}(\alpha)\big) & if\ \sigma=0,\end{array}\right.\quad { in\ probability;}\end{equation*}

hence

\begin{equation*}\frac{N_{\alpha}-E(N_{\alpha}\mid M)}{\sqrt{\textrm{var}(N_{\alpha})}}\rightarrow0\ { in\ probability}.\end{equation*}

Proposition 9. Under Assumptions 1 and 4, we have

\begin{equation*}M(h_{\alpha})-E(N_{\alpha})=O\big(\alpha^{1/2+\sigma/2}\ell^{1/2}(\alpha)\big)\ { in\ probability;}\end{equation*}

hence, if $\mu$ has unbounded support,

\begin{equation*}\frac{M(h_{\alpha})-E(N_{\alpha})}{\sqrt{\textrm{var}(N_{\alpha})}}\rightarrow0\ { in\ probability}.\end{equation*}

The above two propositions are proved in Section B of the supplementary material [Reference Caron, Panero and Rousseau13].

Proposition 10. Assume $\mu$ has unbounded support. Under Assumptions 1, 4, and 5, we have

\begin{equation*}\frac{f_{\alpha}(M)}{\sqrt{\textrm{var}(N_{\alpha})}}\rightarrow\mathcal{N}(0,1).\end{equation*}

Sketch of the proof. To prove Proposition 10 we resort to [Reference Last, Peccati and Schulte24, Theorem 1.1] on the normal approximation of nonlinear functionals of Poisson random measures. Define

(39) \begin{equation}F_\alpha=\frac{f_{\alpha}(M)}{\sqrt{v_{\alpha}}},\end{equation}

where $v_{\alpha}= \textrm{var}(f_{\alpha}(M))\sim \textrm{var}(N_{\alpha} )\asymp\alpha^{1+2\sigma}\ell_\sigma^{2}(\alpha)$ . Note that $E(F_\alpha)=0$ and $\textrm{var}(F_\alpha)=1$ . Consider the difference operator $D_{z}F_\alpha$ defined by

\begin{equation*}D_{z}F_\alpha=\frac{1}{\sqrt{v_\alpha}}( f_\alpha(M+\delta_{z})-f_\alpha(M)),\end{equation*}

and also

\begin{align*}D_{z_1,z_2}^{2}F_\alpha & =D_{z_2}(D_{z_1}F_\alpha)=D_{z_2}\left(\frac{1}{\sqrt{v_\alpha}} (f_\alpha(M+\delta_{z_1})-f_\alpha(M))\right )\\& =\frac{1}{\sqrt{v_\alpha}}\left( f_\alpha(M+\delta_{z_1}+\delta_{z_2})- f_\alpha(M+\delta_{z_1})- f_\alpha(M+\delta_{z_2})+ f_\alpha(M)\right ).\end{align*}

Define

\begin{align*}\gamma_{\alpha,1} & \,:\!=\,2\left( \int_{\mathbb{R}_{+}^{6}}\sqrt{\mathbb{E}\big(D_{z_{1}}F_\alpha\big)^{2}\big(D_{z_{2}}F_\alpha\big)^{2}}\sqrt{\mathbb{E}\big(D_{z_{1},z_{3}}^{2}F_\alpha\big)^{2}\big(D_{z_{2},z_{3}}^{2}F_\alpha\big)^{2}}dz_{1}dz_{2}dz_{3}\right) ^{1/2},\\\gamma_{\alpha,2} & \,:\!=\,\left( \int_{\mathbb{R}_{+}^{6}}\mathbb{E}\left [\big(D_{z_{1},z_{3}}^{2}F_\alpha\big)^{2}\big(D_{z_{2},z_{3}}^{2}F_\alpha\big)^{2}\right ]dz_{1}dz_{2}dz_{3}\right)^{1/2},\\\gamma_{\alpha,3} & \,:\!=\,\int_{\mathbb{R}_{+}^{2}}\mathbb{E}|D_{z}F_\alpha|^{3}dz.\end{align*}

In Section B.3 of the supplementary material [Reference Caron, Panero and Rousseau13], we prove that under Assumptions 1, 4, and 5, we have $\gamma_{\alpha,1},\gamma_{\alpha,2},\gamma_{\alpha,3}\rightarrow0$ . The proof is rather lengthy, and makes repeated use of Hölder’s inequality and of properties of integrals involving regularly varying functions (in particular Lemma B.5). An application of [Reference Last, Peccati and Schulte24, Theorem 1.1] then implies that $F_\alpha\to\mathcal N(0,1)$ .

6.1. Dense graph

Let us consider the graphon function

\begin{equation*}W(x,y)=(1-x)(1-y)\,\mathbb{1}_{x\leq1}\,\mathbb{1}_{y\leq1}\end{equation*}

which has bounded support. The corresponding marginal graphon function $\mu(x)= \mathbb{1}_{x\leq1} (1-x)/2$ has inverse $\mu^{-1}(x)=\ell(1/x)$ , where $\ell(1/x)=(1-2x)\mathbb{1}_{x\leq1/2}$ is slowly varying since $\ell(1/x)\rightarrow 1$ . Assumptions 1 and 2 are satisfied, so by Theorem 2 and Corollary 1,

\begin{equation*}N_\alpha\sim \alpha,\qquad {N_{\alpha}^{(e)}}\sim \alpha^2/8, \qquad {N_{\alpha}^{(e)}}\sim N_\alpha^2/8,\qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow 0, \quad j \geq 1,\end{equation*}

almost surely as $\alpha\rightarrow\infty$ . The function W is separable and $C_\alpha^{(g)}\to 4/9$ .

6.2. Sparse, almost dense graph without power-law behaviour

Consider the graphon function

\begin{equation*}W(x,y)=e^{-x-y},\end{equation*}

considered by [Reference Veitch and Roy38], which has full support. The corresponding function $\mu(x)=e^{-x}$ has inverse $\mu^{-1}(x)=\ell(1/x)=\log\!(1/x)\mathbb{1}_{0<x<1}$ , which is a slowly varying function. We have $\ell_0^*(x)=1/\log\!(x)^2$ . Assumptions 1 and 2 are satisfied, and

\begin{align*}N_\alpha\sim \alpha\log (\alpha), \qquad {N_{\alpha}^{(e)}}\sim \alpha^2/2, \qquad {N_{\alpha}^{(e)}}\sim \frac{N_\alpha^2}{2\log\!(N_\alpha)^2}, \qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow 0\text{ for all }j=1,2,\ldots.\end{align*}

The function W is separable, and $C_\alpha^{(g)}\to 1/4$ .

6.3. Sparse graphs with power-law behaviour

We consider two examples here, one separable and one non-separable. Interestingly, while the degree distributions in the two examples have similar power-law behaviours, the clustering properties are very different. In the first example, the local clustering coefficient converges to a strictly positive constant, while in the second example it converges to 0.

Separable example. First, consider the function

\begin{equation*}W(x,y)=(x+1)^{-1/\sigma}(y+1)^{-1/\sigma}\end{equation*}

with $\sigma\in(0,1)$ . We have $\mu(x)=\sigma (x+1)^{-1/\sigma}/(1-\sigma)$ , $\mu^{-1}(x)=x^{-\sigma}(1/\sigma-1)^{-\sigma}-1$ , $\ell(t)\sim (1/\sigma-1)^{-\sigma}$ , and $\ell_\sigma^*(t)\sim \left \{(1/\sigma-1)^{-\sigma}\Gamma(1-\sigma) \right \}^{-2/(1+\sigma)}$ . Assumptions 1 and 2 are satisfied. We have $N_\alpha\sim \alpha^{1+\sigma}\Gamma(1-\sigma)(1/\sigma-1)^{-\sigma}$ , ${N_{\alpha}^{(e)}}\sim \alpha^2 \sigma^2/\{2(1-\sigma)^2\}$ , and

\begin{align*}{N_{\alpha}^{(e)}}&\sim \frac{\sigma^2\left \{\Gamma(1-\sigma)\big(\frac{1}{\sigma}-1\big)^{-\sigma} \right \}^{-\frac{2}{1+\sigma}}}{2(1-\sigma)^2} N_\alpha^{2/(1+\sigma)}, \qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow \frac{\sigma \Gamma(j-\sigma)}{j!\Gamma(1-\sigma)}, \quad j\geq 1.\end{align*}

The function is separable, and for $\sigma\in(0,1)$ we obtain

\begin{align*}\lim_{\alpha\to\infty} C_\alpha^{(g)}=\left (\frac{1-\sigma}{2-\sigma}\right )^2\text{ and }\lim_{\alpha\to\infty} C_{\alpha,j}^{(\ell)}=\left (\frac{1-\sigma}{2-\sigma}\right )^2\text{ almost surely}.\end{align*}

Non-separable example. Consider now the non-separable function

(40) \begin{equation}W(x,y)=(x+y+1)^{-1/\sigma-1}\end{equation}

where $\sigma\in(0,1)$ . We have $\mu(x)=\sigma (x+1)^{-1/\sigma}$ , $\mu^{-1}(x)=\sigma^{\sigma} x^{-\sigma}-1$ , $\ell(t)\sim \sigma^{\sigma}$ , and $\ell_\sigma^*(t)\sim \left \{\sigma^\sigma\Gamma(1-\sigma) \right \}^{-2/(1+\sigma)}$ . Assumptions 1 and 2 are satisfied as for all $(x,y)\in\mathbb R_+^2$ ,

\begin{align*}W(x,y)&\leq (x+1)^{-1/(2\sigma)-1/2}(y+1)^{-1/(2\sigma)-1/2}=\sigma^{-1-\sigma} \mu(x)^{\frac{1+\sigma}{2}}\mu(y)^{\frac{1+\sigma}{2}}.\end{align*}

We have $N_\alpha\sim \alpha^{1+\sigma}\Gamma(1-\sigma)\sigma^\sigma$ , ${N_{\alpha}^{(e)}}\sim \alpha^2 \sigma^2/\{2(1-\sigma)\}$ , and

\begin{align*}{N_{\alpha}^{(e)}}&\sim \frac{\sigma^2\left [\Gamma(1-\sigma)\sigma^{\sigma} \right ]^{-\frac{2}{1+\sigma}}}{2(1-\sigma)} N_\alpha^{2/(1+\sigma)}, \qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow \frac{\sigma \Gamma(j-\sigma)}{j!\Gamma(1-\sigma)} , \quad j \geq 1.\end{align*}

We have $\int \mu(x)^2dx=\frac{\sigma^3}{2-\sigma}$ . There is no analytical expression for $\int W(x,y)W(y,z)$ $W(x,z)dxdydz$ , but this quantity can be evaluated numerically, and is non-zero, so the global clustering coefficient converges almost surely to a non-zero constant for any $\sigma\in(0,1)$ . For the local clustering coefficient, we have $\mu(x)^2\sim \sigma^2x^{-2/\sigma}$ as $x\to\infty$ and

\begin{align*}\int W(x,y)W(x,z)W(y,z)dydz\leq x^{-2/\sigma -2}\int (y+z+1)dydz =o\big(\mu(x)^2\big).\end{align*}

Hence the local clustering coefficients $C_{\alpha,j}^{(\ell)}$ converge in probability to 0 for all j.

6.4. Almost extremely sparse graph

Consider the function

\begin{equation*}W(x,y)=\frac{1}{(x+1)(1+\log\!(1+x))^2}\frac{1}{(y+1)(1+\log\!(1+y))^2}.\end{equation*}

We have $\overline W=1$ , $\mu(x)=(x+1)^{-1}(1+\log\!(1+x))^{-2}$ , and, using properties of inverses of regularly varying functions, $\mu^{-1}(x)\sim x^{-1}\ell(1/x)$ as $x\rightarrow 0$ , where $\ell(t)=\log\!(t)^{-2}$ is a slowly varying function. For $t>1$ we have $\ell_1(t)=\int_t^\infty x^{-1}\ell(x)dx=1/\log\!(t)$ and $\ell_1^*(t)\sim \log\!(t)/2.$ Assumptions 1 and 2 are satisfied, and almost surely

\begin{align*}{N_{\alpha}^{(e)}}\sim \alpha^2/2, \qquad N_\alpha\sim \frac{\alpha^2}{\log\!(\alpha)}, \qquad {N_{\alpha}^{(e)}}\sim \frac{1}{4} N_\alpha \log\!(N_\alpha),\\\frac{N_{\alpha,1}}{N_\alpha}\rightarrow 1, \qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow 0\text{ for all }j\geq 2.\end{align*}

We have $\int\mu(x)^2dx=\frac{1}{6}(2+e\text{Ei}({-}1))\simeq 0.24$ , where Ei is the exponential integral; hence $C_\alpha^{(g)}\to 0.0576$ almost surely.

6.5. Model of [Reference Caron and Fox12]

The paper [Reference Caron and Fox12] studied a particular subclass of non-separable graphon models. This class is very flexible and allows one to span the whole range of sparsity and power-law behaviours described in Section 3. As shown by [Reference Caron and Fox12], efficient Monte Carlo algorithms can be developed for estimating the parameters of this class of models. Additionally, [Reference Borgs, Chayes, Dhara and Sen11, Corollary 1.3] recently showed that this class is the limit of some sparse configuration models, providing further motivation for the study of their mathematical properties.

Let $\rho$ be a Lévy measure on $(0,+\infty)$ and $\overline{\rho}(x)=\int_{x}^{\infty}\rho(dw)$ the corresponding tail Lévy intensity with generalised inverse $\overline{\rho}^{-1}(x)=\inf\{u>0|\overline{\rho}(u)<x\}$ . The paper [Reference Caron and Fox12] introduced the model defined by

(41) \begin{align}W(x,y)=\left\{\begin{array}{l@{\quad}l}1-e^{-2\overline{\rho}^{-1}(x)\overline{\rho}^{-1}(y)}, & x\neq y,\\[4pt]1-e^{-\{\overline{\rho}^{-1}(x)\}^{2}}, & x=y.\end{array}\right.\end{align}

The quantity $w=\overline \rho^{-1}(x)$ can be interpreted as the sociability of a node with parameter x. The larger this value, the more likely the node is to connect to other nodes. The tail Lévy intensity $\overline \rho$ is a monotone decreasing function; its behaviour at zero will control the behaviour of low-degree nodes, while its behaviour at infinity will control the behaviour of high-degree nodes.

The following proposition formalises this and shows how the results of Sections 3 and 4 apply to this model. Its proof is given in Section 6.6.

Proposition 11. Consider the graphon function W defined by Equation (41) with Lévy measure $\rho$ and tail Lévy intensity $\overline\rho$ . Assume $m=\int_0^\infty w\rho(dw)<\infty$ and

(42) \begin{equation}\overline{\rho}(x)\sim x^{-\sigma}\widetilde\ell(1/x) as\ x\to 0\end{equation}

for some $\sigma\in [0,1]$ and some slowly varying function $\widetilde\ell$ . Then Equation (3) and Assumptions 1 and 2 hold, with $a=1$ and $\ell(x)=(2m)^\sigma \widetilde \ell(x).$ Proposition 1, Theorems 1 and 2, and Corollary 1 therefore hold. If $\int_0^\infty \psi(2w)^2\rho(dw)<\infty$ , where $\psi(t)=\int(1-e^{-wt})\rho(dw)$ is the Laplace exponent, then the global clustering coefficient converges almost surely,

\begin{equation*}\lim_{\alpha\to\infty}C_\alpha^{(g)}= \frac{\int_{\mathbb R_+^3} \big(1-e^{-2xy}\big)\big(1-e^{-2xz}\big)\big(1-e^{-2yz}\big)\rho(dx)\rho(dy)\rho(dz)}{\int_0^\infty \psi(2w)^2\rho(dw)},\end{equation*}

and when $\sigma\in(0,1)$ , Proposition 6 holds and for any $j\geq 2$ we have

\begin{align*}\lim_{\alpha\to\infty}C_{\alpha, j}^{(\ell)}=\lim_{\alpha\to\infty}\overline C_{\alpha}^{(\ell)}= &\ 1-\frac{\int_{\mathbb R_+^2} yze^{-2yz}\rho(dy)\rho(dz)}{m^2}\end{align*}

almost surely. For a given subgraph F, the CLT for the number of such subgraphs (Proposition 7) holds if $\int \psi\big(2\overline\rho^{-1}(x)\big)^{2|F|-2}dx<\infty$ . Under Assumption 1, this condition always holds if $\sigma=0$ ; for $\sigma\in(0,1]$ , it holds if $\overline \rho(x)=O\big(x^{-(2|F|-2)\sigma-\epsilon}\big)$ as $x\to\infty$ for some $\epsilon>0$ . In this case, we have

(43) \begin{equation}\frac{N_{\alpha}^{(F)}-E\big(N_\alpha^{(F)}\big)}{\sqrt{\textrm{var}\big(N_\alpha^{(F)}\big)} } \rightarrow\mathcal{N}(0,1).\end{equation}

Moreover, if $\int w^6\rho(dw)<\infty$ , then Assumptions 4 and 5 also hold. It follows that Theorems 3, 4, and 5 apply, and for any $\sigma\in[0,1]$ and any $\ell$ ,

(44) \begin{equation}\frac{N_{\alpha}-E(N_\alpha)}{\sqrt{\textrm{var}(N_\alpha)} } \rightarrow\mathcal{N}(0,1).\end{equation}

Finally, assume $\sigma\in(0,1)$ and $\widetilde\ell(t)=c>0$ . If additionally

(45) \begin{equation}\overline \rho(x)\sim c_0 x^{-\sigma\tau}\ as\ x\to\infty\end{equation}

for some $\tau>0$ , $c_0>0$ , then Assumption 3 is also satisfied with $\tau>0$ , $\ell_2(x)=\frac{c_0}{2^{\sigma\tau}c^\tau\Gamma(1-\sigma)^\tau}$ , and Proposition 2 applies; that is, for fixed $\alpha$ ,

\begin{equation*}E\big(N_{\alpha,j}\big)\sim\frac{\alpha^{1+\tau}\tau\ell_{2}(j)}{j^{1+\tau}}\ as\ j\rightarrow\infty.\end{equation*}

We consider below two specific choices of mean measures $\rho$ . The two measures have similar properties for large graph size $\alpha$ , but different properties for large degrees j.

Generalised gamma measure. Let $\rho$ be the generalised gamma measure

(46) \begin{equation}\rho(dw)=1/\Gamma(1-\sigma_0)w^{-1-\sigma_0}e^{-\tau_0 w}dw\end{equation}

with $\tau_0>0$ and $\sigma_0\in({-}\infty,1)$ . The tail Lévy intensity satisfies

\begin{align*}\overline\rho(x)\sim \left \{\begin{array}{l@{\quad}l} \frac{1}{\Gamma(1-\sigma_0)\sigma_0}x^{-\sigma_0}, & \sigma_0>0, \\[8pt] \log\!(1/x), & \sigma_0= 0, \\[8pt] -\frac{\tau_0^{\sigma_0}}{\sigma_0}, & \sigma_0<0,\end{array}\right .\end{align*}

as $x\to 0$ . Then for $\sigma_0\in(0,1)$ (sparse with power law),

\begin{align*}{N_{\alpha}^{(e)}}\asymp N_\alpha^{2/(1+\sigma_0)}, \qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow \frac{\sigma_0 \Gamma(j-\sigma_0)}{j!\Gamma(1-\sigma_0)}, \quad j \geq 1.\end{align*}

For $\sigma_0=0$ (sparse, almost dense), we have ${N_{\alpha}^{(e)}}\asymp N^2_\alpha/\log\!(N_\alpha)^2$ and $N_{\alpha,j}/N_\alpha\rightarrow 0$ for $j \geq 1;$ for $\sigma_0<0$ (dense), we have ${N_{\alpha}^{(e)}}\asymp N^2_\alpha$ and $N_{\alpha,j}/N_\alpha\rightarrow 0$ for $j \geq 1$ , almost surely, as $\alpha$ tends to infinity. The constants in the asymptotic results are omitted for simplicity of exposition, but they can also be obtained from the results of Section 3. We have $\int w^p\rho(dw)<\infty$ for all $p\geq 1$ ; hence the global clustering coefficient converges, and the CLT applies for the number of subgraphs and the number of nodes. Note that Equation (45) is not satisfied, as the Lévy measure has exponentially decaying tails, and Proposition 2 does not apply. The asymptotic properties of this model are illustrated in Figure 2 for $\sigma_0=0.2$ and $\tau_0=2$ (sparse, power-law regime).

Generalised gamma-Pareto measure. Consider the generalised gamma-Pareto measure, introduced by [Reference Ayed, Lee and Caron2, Reference Ayed, Lee and Caron3]:

\begin{equation*}\rho(dw)= \frac{1}{\Gamma(1-\sigma)}w^{-1-\sigma\tau}\gamma(\sigma(\tau-1),\beta w)dw,\end{equation*}

where $\gamma(s,x)=\int_0^x u^{s-1}e^{-u}du$ is the lower incomplete gamma function, $c>0$ , $\tau>1$ , $\sigma\in(0, 1)$ . The tail Lévy intensity satisfies

\begin{align*}\overline\rho(x)&\sim cx^{-\sigma}\text{ as }x\to 0,\\\overline\rho(x)&\sim c_0x^{-\sigma\tau}\text{ as }x\to \infty,\end{align*}

where

\begin{equation*}c=\frac{\beta^{\sigma(\tau-1)}}{\sigma^2(\tau-1)\Gamma(1-\sigma)}, \qquad c_0=\frac{\Gamma(\sigma(\tau-1))}{\sigma\tau\Gamma(1-\sigma)}.\end{equation*}

It is regularly varying at both zero and infinity, and it satisfies (42) and (45). We therefore have, almost surely,

\begin{align*}{N_{\alpha}^{(e)}}\asymp N_\alpha^{2/(1+\sigma)}, \qquad \frac{N_{\alpha,j}}{N_\alpha}\rightarrow \frac{\sigma_0 \Gamma(j-\sigma)}{j!\Gamma(1-\sigma)}, \quad j \geq 1.\end{align*}

Proposition 2 applies, and for large-degree nodes,

\begin{equation*}E\big(N_{\alpha,j}\big)\sim\frac{\tau\alpha^{1+\tau}c_0}{2^{\sigma\tau }c^\tau\Gamma(1-\sigma)^\tau} \frac{1}{j^{1+\tau}}\ as\ j\rightarrow\infty.\end{equation*}

The global clustering coefficient converges if $\tau>2$ ; the CLT applies for the number of subgraphs F if $\tau>2|F|-2$ , and for the number of nodes if $\sigma\tau>6$ .

6.6. Proof of Proposition 11

The marginal graphon function is given by $\mu(x)=\psi(2\overline \rho^{-1}(x))$ where $\psi(t)=\int_0^\infty (1-e^{-wt})\rho(dw)$ is the Laplace exponent. Its generalised inverse is given by $\mu^{-1}(x)=\overline\rho(\psi^{-1}(x)/2).$ The Laplace exponent satisfies $\psi(t)\sim m t$ as $t\to 0$ . It therefore follows that $\mu^{-1}$ satisfies Assumption 1 with $\ell(x)=(2m)^\sigma \widetilde \ell(x).$ Ignoring loops, the model is of the form given by Equation (18) with $f(x)=2m \overline{\rho}^{-1}(x)$ . Assumption 2 is therefore satisfied. Regarding the global clustering coefficient, $\int \psi(2w)^2\rho(dw)\leq 4\int w^2\rho(dw)<\infty$ , so its limit is finite. For the local clustering coefficient, using dominated convergence and the inequality $\frac{1-e^{-2\overline{\rho}^{-1}(x)y}}{2\overline{\rho}^{-1}(x)}\leq y$ , we obtain

\begin{align*}\int W(x,y)W(y,z)W(x,z)dydz & =\int\big(1-e^{-2\overline{\rho}^{-1}(x)y}\big)\big(1-e^{-2\overline{\rho}^{-1}(x)z}\big)\big(1-e^{-2yz}\big)\rho(dy)\rho(dz)\\& \sim4\overline{\rho}^{-1}(x)^{2}\int yz\big(1-e^{-2yz}\big)\rho(dy)\rho(dz).\end{align*}

Using the fact that $\mu(x)=\psi(2\overline \rho^{-1}(x))\sim 2m\overline \rho^{-1}(x)$ as $x\to\infty$ , we obtain the result. Finally, if $\overline\rho$ satisfies (42), then $\psi(t)\sim \Gamma(1-\sigma)\widetilde \ell(t)t^\sigma$ as $t\to\infty$ . Using [Reference Bingham, Goldie and Teugels6, Proposition 1.5.15], we have

\begin{equation*}\psi^{-1}(t)\sim \Gamma(1-\sigma)^{-1/\sigma}\widetilde\ell^{\#1/\sigma}\big(t^{1/\sigma}\big)t^{1/\sigma}\end{equation*}

as $t\to\infty$ , where $\widetilde{\ell}^{\#}$ is the de Bruijn conjugate of $\widetilde{\ell}$ . We obtain $\psi^{-1}(t)=\ell_3\big(t^{1/\sigma}\big)t^{\frac{1}{\sigma}},$ where $\ell_3$ is a slowly varying function with $\ell_3\big(t^{1/\sigma}\big)\sim\widetilde{\ell}^{\#1/\sigma}\big(t^{1/\sigma}\big)\Gamma(1-\sigma)^{-1/\sigma}\text{ as }t\rightarrow\infty.$ We therefore have $ \mu^{-1}(t) \sim c_0 2^{-\tau\sigma}\ell_3\big(t^{1/\sigma}\big)^{\sigma\tau} t^{\tau}\text{ as }t\to\infty.$ If $\widetilde\ell(t)=c$ , then $\ell_3(t)=(c\Gamma(1-\sigma))^{-1/\sigma}$ .

For the CLT for the number of subgraphs F to hold, we need $\int_0^\infty \mu(x)^{2|F|-2}dx<\infty$ . As $\mu$ is monotone decreasing and integrable, we only need $\mu(x)^{2|F|-2}=\psi\big(2\overline\rho^{-1}(x)\big)^{2|F|-2}$ to be integrable in a neighbourhood of 0. In the dense case, $\psi(t)$ is bounded, and the condition holds. If $\overline\rho$ satisfies (42), then $\psi(t)\sim \Gamma(1-\sigma)\widetilde \ell(t)t^\sigma$ as $t\to\infty$ . For $\sigma\in(0,1]$ (sparse regime), the condition holds if $\overline\rho(x)=O\big(x^{-(2|F|-2)\sigma-\epsilon}\big)$ as $x\to\infty$ for some $\epsilon>0$ .

We now check the assumptions for the CLT for the number of nodes. Noting again that $\mu(x)\sim 2m\overline\rho^{-1}(x)$ as $x\to\infty$ , we have, using the inequality $1-e^{-x}\leq x$ ,

\begin{align*}\nu(x,y)&=\int \big(1-e^{-2\overline\rho^{-1}(x)w}\big)\big(1-e^{-2\overline\rho^{-1}(y)w}\big)\rho(dw)\\&\leq L(x)L(y)\mu(x)\mu(y),\end{align*}

where

\begin{equation*}L(x)=2 \frac{\overline\rho^{-1}(x)}{\mu(x)}\sqrt{\int w^2\rho(dw)}\to \sqrt{\int w^2\rho(dw)}/m\end{equation*}

as $x\to\infty$ . Using now the inequality $1-e^{-x}\geq xe^{-x}$ , we have

\begin{align*}\nu(x,y)&\geq 4\overline\rho^{-1}(x)\overline\rho^{-1}(y)\int w^2e^{-2(\overline\rho^{-1}(x)+\overline\rho^{-1}(y))w}\rho(dw).\end{align*}

As

\begin{equation*}\int w^2e^{-2(\overline\rho^{-1}(x)+\overline\rho^{-1}(y))w}\rho(dw)\to\int w^2\rho(dw) \end{equation*}

as $\min(x,y)\to\infty$ , there exist $C_0=2\int w^2\rho(dw)$ and $x_0$ such that for all $x,y>x_0$ , $\nu(x,y)\geq C_0\mu(x)\mu(y)$ .

More generally, if $\int w^6\rho(dw)<\infty$ , then for any $j\leq 6$ ,

\begin{align*}\int_0^\infty \prod_{i=1}^j W(x_i,y)dy &\leq \prod_{i=1}^j L(x_i)\mu(x_i),\end{align*}

where

\begin{equation*}L(x)=2 \frac{\overline\rho^{-1}(x)}{\mu(x)}\max\left (1, \max_{j=1,\ldots,6}\int w^j \rho(dw)\right )\to \max\left (1, \max_{j=1,\ldots,6}\int w^j \rho(dw)\right )/m\end{equation*}

as $x\to\infty$ . Note also that

\begin{equation*}\int L(x)\mu(x)dx= 2\max\left (1, \max_{j=1,\ldots,6}\int w^j \rho(dw)\right ) \int w\rho(dw)<\infty.\end{equation*}

7.1. Statement of the results

By Kallenberg’s representation theorem, any exchangeable point process can be represented by Equation (2). However, it may be more suitable to use a different formulation where the function W is defined on a general space, not necessarily $\mathbb R_+^2$ , as discussed by [Reference Borgs, Chayes, Cohn and Holden9]. Such a construction may lead to more interpretable parameters and easier inference methods. Indeed, a few sparse vertex-exchangeable models, such as the models of [Reference Herlau, Schmidt and Mørup18] or [Reference Todeschini, Miscouridou and Caron37], are written in such a way that it is not straightforward to express them in the form given by (2).

In this section we show that the above results easily extend to models expressed in the following way. Let F be a probability space. Writing $\vartheta = (u,v)\in \mathbb R_+\times F$ , let $\xi(d\vartheta)=du G(dv)$ where G is some probability distribution on F. Consider models expressed as in (1) with

(47) \begin{align}Z_{ij}\mid (\theta_k,\vartheta_k)_{k=1,2,\ldots}\sim \text{Bernoulli}\{ W\ ( \vartheta_i, \vartheta_j)\}, \quad W \,:\, (\mathbb R_+\times F)^2 \rightarrow[0,1], \end{align}

where $(\theta_k,\vartheta_k)_{k=1,2,\infty}$ are the points of a Poisson point process with mean measure $d\theta\xi(d \vartheta)$ on $\mathbb R_+\times (\mathbb R_+ \times F)$ . Let us assume additionally that the function W factors in the following way:

(48) \begin{equation}W((u_i,v_i),(u_j,v_j))=\omega(v_i,v_j)\eta(u_i,u_j), \end{equation}

where $\omega\,:\,F\times F\rightarrow [0,1]$ and the function $\eta\,:\,\mathbb R_+\times\mathbb R_+\rightarrow [0,1]$ is integrable. In this model, $\omega$ can capture the local structure, as in the classical dense graphon, and $\eta$ the sparsity behaviour of the graph. Let $\mu_\eta(u)=\int_0^\infty \eta(u,u^{\prime})du^{\prime}$ , $\mu_\omega (v) = \int_F\omega(v,v^{\prime})G(dv^{\prime})$ , and $\nu_\eta(x,y)=\int_{\mathbb R_+^2} \eta(x,z)\eta(y,z)dz$ . The results presented in Section 3 remain valid when $\mu_\eta$ and $\nu_\eta$ satisfy Assumptions 1 and 2. The proof of Proposition 12 is given in Section 7.2.

Proposition 12. Consider the model defined by Equations (47) and (48) and assume that the functions $\mu_\eta$ and $\nu_\eta$ satisfy Assumptions 1 and 2. Then the conclusions of Proposition 1 hold, and so do the conclusions of Theorems 1 and 2, with $\ell(\alpha)$ and $\ell_1(\alpha)$ replaced respectively by

\begin{equation*} \tilde \ell(\alpha ) = \ell(\alpha) \int_F \mu_\omega(v)^\sigma G(dv) , \qquad \tilde \ell_1(\alpha) = \ell_1(\alpha) \int_F \mu_\omega(v)^\sigma G(dv).\end{equation*}

Consider for example the following class of models for dense and sparse stochastic block-models.

Example 2. (Dense and sparse stochastic block-models.) Consider $F=[0,1]$ and G the uniform distribution on [0, 1]. We choose for $\omega$ the graphon function associated to a (dense) stochastic block-model. For some partition $A_1,\ldots,A_p$ of [0, 1] and any $v,v^{\prime}\in[0,1]$ , let

(49) \begin{equation}\omega(v,v^{\prime})= B_{k,\ell}\end{equation}

with $v\in A_k$ , $v^{\prime}\in A_\ell$ , and B a $p\times p$ matrix where $B_{k,\ell}\in[0,1]$ denotes the probability that a node in community k forms a link with a node in community $\ell$ . Then $\omega$ defines the community structure of the graph, and $\eta$ will tune its sparsity properties. Choosing $\eta(x,y)=\mathbb{1}_{x\leq 1}\mathbb{1}_{y\leq 1}$ yields the dense, standard stochastic block-model; choosing $\eta(x,y)=\exp({-}x-y)$ yields a sparse stochastic block-model without power-law behaviour; and so on. Figure 4 gives an illustration of the use of this model to obtain sparse stochastic block-models with power-law behaviour, generalising the model of Section 6.3. The function $\omega$ is defined by

\begin{align*}A_1&=[0,0.5), \quad A_2=[0.5,0.8), \quad A_3=[0.8,1],\\B_{11}&=0.7, \quad B_{22}=0.5, \quad B_{33}=0.9, \quad B_{12}=B_{13}=0.1, \quad B_{23}=0.05,\end{align*}

and $\eta(x,y)=(1+x)^{-1/\sigma}(1+y)^{-1/\sigma}$ , with $\sigma=0.8$ .

Figure 4.

Illustration of a sparse stochastic block-model with three communities. (a) The function $\omega$ , which controls the local community structure. A darker colour represents a higher value. (b) The function $\eta$ , which controls the sparsity. (c) Graph sampled from the sparse stochastic block-model using $\alpha=50$ . The size of each node is proportional to its degree. (d) Empirical degree distribution of the sampled graph.

More generally, one can build on the large literature on (dense) graphon/exchangeable graph models, and combine these models with a function $\eta$ satisfying Assumptions 1 and 2, such as those described in the previous section, in order to sparsify a dense graphon and control its sparsity/power-law properties.

Remark 5. We can also obtain asymptotic results for those functions W that do not satisfy the separability condition (48). Let $\mu(u,v)=\int_{\mathbb R_+\times F} W((u,v),(u^{\prime},v^{\prime}))du^{\prime}dv^{\prime}$ . Assume that for each fixed v there exists $u_0(v)>0$ such that, for $u>u_0$ ,

(50) \begin{equation}C_3\tilde\mu_\eta(u)\tilde\mu_\omega(v)\leq \mu(u,v)\leq C_4\tilde\mu_\eta(u)\tilde\mu_\omega(v), \end{equation}

where $\tilde\mu_\omega\,:\,F\rightarrow \mathbb R_+$ , $\tilde\mu_\eta\,:\,\mathbb R_+ \rightarrow \mathbb R_+$ with $\tilde\mu_\eta(u)=\int_0^\infty \tilde\eta(u,u^{\prime})du^{\prime}$ for some positive function $\tilde\eta$ , and $C_3>0$ and $C_4>0$ . Assume that $\tilde\mu_\eta$ and $\tilde\nu_\eta$ satisfy Assumptions 1 and 2. Then the results of Theorems 1 and 2 and Corollary 1 hold up to a constant. For example, for $\sigma\in[0,1]$ we have ${N_{\alpha}^{(e)}}\asymp N_\alpha^{2/(1+\sigma)}\ell_\sigma^*(N_\alpha)$ almost surely as $\alpha$ tends to infinity. In particular, the inequality from (50) is satisfied if

(51) \begin{equation}W((u_i,v_i),(u_j,v_j))=1-e^{-\tilde \omega(v_i,v_j)\tilde\eta(u_i,u_j)}.\end{equation}

The models developed by [Reference Herlau, Schmidt and Mørup18, Reference Todeschini, Miscouridou and Caron37] for capturing (overlapping) communities fit into this framework. Ignoring loops, both models can be written in the form given by Equation (51) with $\tilde\eta(u,u^{\prime})=2\overline\rho^{-1}(u)\overline\rho^{-1}(u^{\prime})$ , where $\rho$ is a Lévy measure on $(0,+\infty)$ and $\overline{\rho}(x)=\int_{x}^{\infty}\rho(dw)$ is the tail Lévy intensity with generalised inverse $\overline{\rho}^{-1}(x)$ . When $\tilde \omega$ is given by Equation (49), it corresponds to the (dense) stochastic block-model graphon of [Reference Herlau, Schmidt and Mørup18], and when $\tilde \omega(v_i,v_j)=v_i^{T}v_j$ with $v_i\in \mathbb R_+^p$ , it corresponds to the model of [Reference Todeschini, Miscouridou and Caron37]. For instance, let $\rho$ be the mean measure from Equation (46) with parameters $\tau_0>0$ and $\sigma_0\in({-}\infty,1)$ . Then for $\sigma_0\in(0,1)$ , the corresponding sparse regime with power law for this graph is given by

\begin{align*}{N_{\alpha}^{(e)}}\asymp N_\alpha^{2/(1+\sigma_0)}, \qquad \frac{C_3}{C_4}\frac{\sigma_0 \Gamma(j-\sigma_0)}{j!\Gamma(1-\sigma_0)}\leq \lim_{\alpha\rightarrow\infty}\frac{N_{\alpha,j}}{N_\alpha}\leq \frac{C_4}{C_3}\frac{\sigma_0 \Gamma(j-\sigma_0)}{j!\Gamma(1-\sigma_0)}, \quad j \geq 1\end{align*}

For $\sigma_0=0$ (sparse, almost dense regime), ${N_{\alpha}^{(e)}}\asymp N^2_\alpha/\log\!(N_\alpha)^2$ and $N_{\alpha,j}/N_\alpha\rightarrow 0$ for $j\geq 1$ ; for $\sigma_0<0$ (dense regime), ${N_{\alpha}^{(e)}}\asymp N^2_\alpha$ and $N_{\alpha,j}/N_\alpha\rightarrow 0$ for $j \geq 1$ , almost surely, as $\alpha$ tends to infinity.

7.2. Proof of Proposition 12

The proofs of Proposition 1 and Theorems 1 and 2 hold with x replaced by $(u,v) \in \mathbb R_+ \times F$ , $dx = du G(dv)$ , and $\mu(x) = \mu_\eta(u)\mu_\omega(v)$ . We thus need only prove that if $\eta$ satisfies Assumptions 1 and 2, then Lemmas B.2, B.3, and B.4 in the appendix hold. Recall that $\mu(x) = \mu_\eta (u) \mu_\omega(v) $ , for $x=(u,v)$ . Then, for all v such that $\mu_\omega(v) >0$ , we apply Lemma B.2 to get

\begin{equation*}g_0(t) = \int_0^\infty (1 - e^{-t \mu_\eta(u)})du, \qquad g_r(t) = \int_0^\infty \mu_\eta(u)^r e^{-t \mu_\eta(u)}du, \qquad t = \alpha \mu_\omega(v).\end{equation*}

For all v such that $\mu_\omega(v) >0$ , this leads to

\begin{equation*}\begin{split}\int_0^\infty (1 - e^{-\alpha \mu_\omega(v) \mu_\eta(u)})du &= \Gamma(1-\sigma) \alpha^\sigma \ell(\alpha) \mu_\omega(v)^\sigma\frac{ \ell\{\alpha \mu_\omega(v) \} }{ \ell(\alpha) } \{1 + o(1) \} \\& = \Gamma(1-\sigma) \alpha^\sigma \ell(\alpha) \mu_\omega(v)^\sigma \{ 1 + o(1)\}.\end{split}\end{equation*}

To prove that there is convergence in $L_1(G)$ , note that if $\mu_\omega(v) >0$ , since $\mu_\omega \leq 1$ , we have

\begin{equation*}\begin{split}\int_0^\infty \big(1 - e^{-\alpha \mu_\omega(v) \mu_\eta(u)}\big)du& = \int_0^\infty \mu_\eta^{-1}\left\{\frac{ z}{ \alpha \mu_\omega(v) }\right\}e^{-z} dz \leq \int_0^\infty \mu_\eta^{-1}\left(\frac{ z}{ \alpha }\right)e^{-z}dz.\end{split}\end{equation*}

Moreover,

\begin{equation*}\sup_{\alpha \geq 1} \frac{1}{\alpha^{\sigma}\ell(\alpha)} \int_0^\infty \mu_\eta^{-1}\left(\frac{ z}{ \alpha }\right)e^{-z}dz < +\infty; \end{equation*}

thus the Lebesgue dominated convergence theorem implies

\begin{equation*}\int_F \int_0^\infty \big(1 - e^{-\alpha \mu_\omega(v) \mu_\eta(u)}\big)duG(dv) \sim \Gamma(1-\sigma) \alpha^\sigma \ell(\alpha) \int_F\mu_\omega(v)^\sigma G(dv)\end{equation*}

when $\sigma <1$ , while when $\sigma=1$ ,

\begin{equation*}\int_F \int_0^\infty (1 - e^{-\alpha \mu_\omega(v) \mu_\eta(u)})duG(dv) \sim \alpha\ell_1(\alpha) \int_F\mu_\omega(v) G(dv). \end{equation*}

The same reasoning is applied to the integrals

\begin{equation*}\int_F \mu_\omega(v)^r \int_0^\infty \mu_\eta(u)^re^{-\alpha \mu_\omega(v) \mu_\eta(u)}duG(dv).\end{equation*}

To verify Lemma B.3, note that

\begin{equation*}\begin{split}h_0(\alpha) &= \int_F \omega(v,v) \int_0^\infty \eta(u,u)\big( 1 - e^{-\alpha \mu_\omega(v)\mu_\eta(u) }\big)du G(dv), \\ h_r(\alpha) &= \int_F \omega(v,v)\mu_\omega(v)^r \int_0^\infty \eta(u,u)\mu_\eta(u)^r e^{-\alpha \mu_\omega(v)\mu_\eta(u) }du G(dv), \end{split}\end{equation*}

so that the Lebesgue dominated convergence theorem also leads to

\begin{equation*}h_0(\alpha ) \sim \int_F \omega(v,v) \int_0^\infty \eta(u,u)du G(dv), \qquad h_r(\alpha ) = o(\alpha^{-r} )\end{equation*}

and the control of the integrals $\int_{\mathbb R_+\times F} \{t\mu(u,v)\}e^{-t \mu(u,v)}duG(dv )$ as in Lemma B.4.