# Preferential attachment and vertex arrival times

Benjamin<EMAIL_ADDRESS>[ Peter
<EMAIL_ADDRESS>[ University of Oxford and Columbia
University  Department of Statistics
24–29 St. Giles’
Oxford OX1 3LB, UK
Department of Statistics
1255 Amsterdam Avenue
New York, NY 10027, USA

###### Abstract

We study preferential attachment mechanisms in random graphs that are
parameterized by (i) a constant bias affecting the degree-biased distribution
on the vertex set and (ii) the distribution of times at which new vertices are
created by the model. The class of random graphs so defined admits a
representation theorem reminiscent of residual allocation, or “stick-breaking”
schemes. We characterize how the vertex arrival times affect the asymptotic
degree distribution, and relate the latter to neutral-to-the-left processes.
Our random graphs generate edges “one end at a time”, which sets up a one-to-
one correspondence between random graphs and random partitions of natural
numbers; via this map, our representation induces a result on (not necessarily
exchangeable) random partitions that generalizes a theorem of Griffiths and
Spanó. A number of examples clarify how the class intersects with several
known random graph models.

authorprefix copyrighttext

and

The term _preferential attachment_ describes generative mechanisms for random
graph models that select the terminal vertices of a new edge with probability
biased by the vertex degrees. These models come in many shapes and guises
[e.g. 4, 5, 24, 32], and are often motivated by their ability to generate (and
hence explain) power law distributions. Degree-biased selection is a form of
size bias [3], and this interplay between size-biasing and power laws is not
confined to random graph models, but also encountered in random partitions,
which are used in population genetics, machine learning, and other fields
[e.g. 36, 16, 10]. In partition models, power laws arise as heavy-tailed
distributions of block sizes. Size-biased sampling as such, however, need not
result in a power laws: The most basic form of size-biased sampling from a
countable number of categories is a type of Pólya urn with an unbounded number
of colors, or, equivalently, the one-parameter Chinese restaurant process
[36]. It does not generate a power law. To obtain power laws, plain size-
biased sampling can be modified in two ways:

  1. (i)

By biasing the size-biased probability of each category downward.

  2. (ii)

By forcing new categories to arrive at a faster rate than that induced by
plain size-biased sampling.

An example is the two-parameter Chinese restaurant process with parameter
$(\alpha,\theta)$, which modifies the Chinese restaurant process with a single
parameter $\theta$—a model that corresponds to plain size-biased sampling—by
effectively (i) damping the size bias by a constant offset $\alpha$, and (ii)
increasing the rate at which new categories arrive. An example of (ii) is the
Barabási–Albert random graph model, in which vertices arrive at fixed,
constant time intervals; if these times were instead determined at random by
size-biased sampling, intervals would grow over time.

The premise of this work is to study preferential attachment mechanisms in
random graph models by explicitly controlling these two effects:

  1. (i)

The attachment probability, proportional to the degree $\deg_{k}$ of each
vertex $k$, is biased by a constant offset as ${\deg_{k}-\,\alpha}$.

  2. (ii)

Vertex arrival times are taken into account, by explicitly conditioning the
generation process on a (random or non-random) sequence of given times.

The result is a class of random graphs parametrized by the offset $\alpha$ and
a sequence $t$ of vertex arrival times. Each such $(\alpha,t)$-graph can be
generalized by randomizing the arrival times, i.e. to an $(\alpha,T)$-graph
for a random sequence $T$. Preferential attachment models that constantly bias
the attachment probability have been thoroughly studied [30, 24]. We consider
the range ${\alpha\in(-\infty,1)}$, and the case ${\alpha\in[0,1)}$ turns out
to be of particular interest. The effects (i) and (ii) are not independent,
and in models with a suitable exchangeability property, the effect of $\alpha$
can equivalently be induced by controlling the law of the arrival times. In
this sense, (ii) can provide more control over the model than (i).

Section 1 characterizes $(\alpha,T)$-graphs by a representation in terms of
independent beta random variables, reminiscent of stick-breaking constructions
of random partitions.

Section 2 considers implications for random partitions and urns.
${(\alpha,T)}$-graphs generate edges “one end at a time”, updating the vertex
degrees after each step. Although such a scheme differs from the usual
preferential attachment model, it is similar to so-called “sequential”
versions considered by [5, 32]. This sets up a one-to-one correspondence
between multigraphs and partitions of natural numbers: There is a bijection
$\Phi$ such that

$\Phi(\text{partition})=\text{graph}\;,$

which translates our results on graphs into statements about partitions. If
$G$ is an $(\alpha,T)$-graph, the random partition $\Phi^{-1}(G)$ may or may
not be exchangeable. The subclass of such partitions that are exchangeable are
precisely the exchangeable Gibbs partitions [21, 36]. Arrival times in such
partitions, known as _record indices_ , have been studied by Griffiths and
Spanò [23]. Broadly speaking, our results recover those of Griffiths and Spanò
if $\Phi^{-1}(G)$ is exchangeable, but show there is a larger class of random
partitions—either of Gibbs type, or not exchangeable—for which similar results
hold. Non-exchangeable examples include partitions defined by the Yule–Simon
process [42, 39]. Additionally, our representation result for graphs yields an
analogous representation for this class of partitions; it also relates the
work of Griffiths and Spanò [23] to that of Berger, Borgs, Chayes, and Saberi
[5] on Benjamini–Schramm limits of certain random preferential attachment
graphs.

Section 3 studies degree asymptotics of $(\alpha,T)$-graphs. Properly scaled
degree sequences of such graphs converge. The limiting degrees are neutral-to-
the-left sequences of random variables that satisfy a number of distributional
identities. We characterize cases in which power laws emerge, and relate the
behavior of the degree distribution to sparsity. The range of power laws
achievable is constrained by whether or not the average degree is bounded.

Section 4 discusses examples, and shows how the class of $(\alpha,T)$-graphs
overlaps with several known models, such as the Barabási–Albert model [4],
edge exchangeable graphs [14, 11, 28], and the preferential attachment model
of Aiello, Chung, and Lu [1, 2]. We obtain new results for some of these
submodels. For preferential attachment graphs, for example, limiting degree
sequences are known to satisfy various distributional identities [32, 25, 26].
These results assume fixed intervals between vertex arrival times. We show
similar results hold if arrival times are random. Perhaps most closely related
is the work of Peköz, Röllin, and Ross [33] on random immigration times in a
two-color Pólya urn, which corresponds to a certain $(\alpha,T)$-model with
i.i.d. interarrival times. We use this correspondence to answer a question
posed in [33] about interarrival times with geometric distribution.

##  1 Preferential attachment and arrival times

Consider an undirected multigraph $g$, possibly with self-loops, with a
countably infinite number of edges. The graph models considered in the
following insert edges into the graph one at a time. It is hence convenient to
represent $g$ as a sequence of edges

$g=\bigl{(}(l_{1},l_{2}),(l_{3},l_{4}),\ldots\bigr{)}\qquad\text{ where
}l_{j}\in\mathbb{N}\text{ for all }j\in\mathbb{N}\;.$ (1)

Each pair ${(l_{2n-1},l_{2n})}$ represents an undirected edge connecting the
vertices $l_{2n-1}$ and $l_{2n}$. The vertex set of $g$ is
${\mathbf{V}(g):={\\{l^{*}_{1},l^{*}_{2},\ldots\\}}}$, the set of all distinct
values occurring in the sequence. We assume vertices are enumerated in order
of appearance, to wit

$l_{1}=1\qquad\text{ and }\qquad
l_{j+1}\leq\max{\\{l_{1},\ldots,l_{j}\\}}+1\quad\text{ for all
}j\in\mathbb{N}\;.$ (2)

Consequently, $\mathbf{V}(g)$ is either a consecutive finite set
${\\{1,\ldots,m\\}}$, or the entire set $\mathbb{N}$. Let $\mathbb{G}$ be the
set of multigraphs so defined, equipped with the topology inherited from the
product space $\mathbb{N}^{\infty}$, which makes it a standard Borel space.
For our purposes, a random graph is a random element

$G=\bigl{(}(L_{1},L_{2}),(L_{3},L_{4}),\ldots)$

of $\mathbb{G}$, for $\mathbb{N}$-valued random variables $L_{n}$. Note that
the same setup can be used to model directed multigraphs.

For a graph $g$, let ${g_{n}:=(l_{j})_{j\leq 2n}}$ denote the subgraph given
by the first $n$ edges, and $\deg_{k}(n)$ the degree of vertex $k$ in $g_{n}$.
The arrival time of vertex $k$ is

$t_{k}:=\min{\\{j\in\mathbb{N}\,|\,l_{j}=k\\}}\;,$

with ${t_{k}=\infty}$ if $g$ has fewer than $k$ vertices. The set of possible
arrival time sequences is
${\mathbb{T}:={\\{(1=t_{1}<t_{2}<\ldots\leq\infty)\\}}}$. Arrival times in
${\mathcal{T}_{\text{\tiny\rm 2}}:={\\{t\in\mathbb{T}\,|\,t_{k}\text{ even for
}k>1\\}}}$ is a sufficient, though not necessary, condition for $g$ to be a
connected graph; it is necessary and sufficient for each $g_{n}$ to be
connected. If ${T=(T_{1},T_{2},\ldots)}$ is a random sequence of arrival
times, the interarrival times

$\Delta_{k}:=T_{k}-T_{k-1}\qquad\text{ where }T_{0}:=0$

are random variables with values in ${\mathbb{N}\cup{\\{\infty\\}}}$.

###  1.1 Degree-biased random graphs

The term preferential attachment describes a degree bias: Recall that the
degree-biased distribution on the vertices of a graph $g_{n}$ with $n$ edges
is ${P(k\,;g_{n}):=\deg_{k}(n)/2n}$. We embed $P$ into a one-parameter family
of laws

$P_{\alpha}(k\,;g_{n}):=\frac{\deg_{k}(n)-\alpha}{2n-\alpha|\mathbf{V}(g_{n})|}\qquad\text{
for }\alpha\in(-\infty,1)\;,$

the $\alpha$-degree biased distributions. Both $P$ and $P_{\alpha}$ are
defined on a graph $g_{n}$, in which each edge is either completely present or
completely absent. To permit edges to be generated “one end at a time”, we
observe $P_{\alpha}$ can be rewritten as

$P_{\alpha}(k\,;l_{1},\ldots,l_{j})=\frac{|{\\{i\leq
j|l_{j}=k\\}}|-\alpha}{j-\alpha\max{\\{l_{1},\ldots,l_{j}\\}}}\qquad\text{ for
}k\leq\max{\\{l_{1},\ldots,l_{j}\\}}\;,$ (3)

which is well-defined even if $j$ is odd.

######  ${(\alpha,t)}$-graph.

Given are ${\alpha\in(-\infty,1)}$ and ${t\in\mathbb{T}}$. Generate
${L_{1},L_{2},\ldots}$ as

$L_{n}:=k\quad\text{ if }n=T_{k}\qquad\text{ and }\qquad L_{n}\sim
P_{\alpha}({\,\vbox{\hbox{\tiny$\bullet$}}\,}\,;L_{1},\ldots,L_{n-1})\quad\text{
otherwise}\;.$

Then ${G:=((L_{1},L_{2}),(L_{3},L_{4}),\ldots)}$ is a random graph, whose law
we denote ${\text{\rm DB}(\alpha,t)}$. The sequence $t$ may additionally be
randomized: We call $G$ an $(\alpha,T)$-graph if its law is $\text{\rm
DB}(\alpha,T)$, for some random element $T$ of $\mathbb{T}$. Examples of
multigraphs generated using different distributions for $T$ are shown in Fig.
1.

As a consequence of the family of laws (3), the finite-dimensional
distributions of $(\alpha,t)$-graphs have a simple product form.

######  Proposition 1.

Let $G_{n}$ be an $(\alpha,t)$-graph with $n/2$ edges and $k$ vertices. Then

$\displaystyle\mathbb{P}_{\alpha,t}[G_{n/2}$
$\displaystyle=((L_{1},L_{2}),\dotsc,(L_{n-1},L_{n}))]$
$\displaystyle=\frac{1}{\Gamma(n-k\alpha)}\prod_{j=1}^{k}\frac{\Gamma(T_{j}-j\alpha)\Gamma(\\#\\{L_{i}=k\mid
i\leq
n\\}-\alpha)}{\Gamma(T_{j}-1-(j-1)\alpha+\delta_{1}(j))\Gamma(1-\alpha)}\;.$
(4)

###  1.2 Representation result

Fix ${\alpha\in(-\infty,1)}$ and ${t\in\mathbb{T}}$. Let
${\Psi_{1},\Psi_{2},\ldots}$ be independent random variables with
$\Psi_{1}=1$,

$\Psi_{j}\sim\text{Beta}\bigl{(}1-\alpha,t_{j}-1-(j-1)\alpha\bigr{)}\quad\text{for}\quad
j\geq 2\;,$ (5)

and define

$W_{j,k}:=\sum_{i=1}^{j}\Psi_{i}\prod_{\ell=i+1}^{k}(1-\Psi_{\ell})\quad\text{
and }\quad I_{j,k}:=[W_{j-1,k},W_{j,k})\text{ with }W_{0,k}=0\;.$ (6)

Note that $W_{j,k}=\prod_{\ell=j+1}^{k}(1-\Psi_{\ell})$ and $W_{k,k}=1$.
Hence, ${\cup_{j=1}^{k}I_{j,k}=[0,1)}$. Generate a random sequence
${U_{1},U_{2},\ldots\sim_{\mbox{\tiny iid}}\text{\rm Uniform}[0,1)}$. For each
$n$, let $t_{k(n)}$ be the preceding arrival time, i.e. the largest $t_{k}$
with ${t_{k}\leq n}$, and set

$L_{n}:=\begin{cases}k(n)&\text{ if }n=t_{k(n)}\\\ j\text{ such that }U_{n}\in
I_{j,k(n)}&\text{ otherwise}\end{cases}\;.$ (7)

Then ${H(\alpha,t):=((L_{1},L_{2}),\ldots)}$ is a random element of
$\mathbb{G}$.

######  Theorem 2.

A random graph $G$ is an $(\alpha,T)$-graph if and only if
${G\stackrel{{\scriptstyle\text{\rm\tiny d}}}{{=}}H(\alpha,T)}$ for some
${\alpha\in(-\infty,1)}$ and a random element $T$ of $\mathbb{T}$.

Products of the form (6), for the same sequence of beta variables $\Psi_{j}$,
previously have appeared in two separate contexts: Griffiths and Spanò [23]
identify $\Psi_{j}W_{j,\infty}$ as the limiting relative block sizes in
exchangeable Gibbs partitions, conditioned on the block arrival times. This
corresponds to the special case of Theorem 2 where the random variables
${(L_{1},L_{2},\ldots)}$ define an exchangeable Gibbs partition (see Sections
2 and 4.2). In work of Berger, Borgs, Chayes, and Saberi [5], a version of
(5)–(7) arises as the representation of the Benjamini–Schramm limit of certain
preferential attachment graphs (in which case all interarrival times are fixed
to a single constant).

That two problems so distinct lead to the same (and arguably not entirely
obvious) distribution raises the question whether (5) can be understood in a
more conceptual way. One such way is by regarding the graph as a recursive
sequence of Pólya urns: Conditionally on an edge attaching to one of the first
$k$ vertices, it attaches to vertex $k$ with probability $\Psi_{k}$ and one of
the first $k-1$ with probability $1-\Psi_{k}$, and so on for $k-1,\dotsc,2$. A
related interpretation is in terms of the special properties of beta and gamma
random variables. Let $\mathcal{G}_{a}$ and $\mathcal{B}_{a,b}$ generically
denote a gamma random variable with parameters $(a,1)$ and a beta variable
with parameters $(a,b)$. Beta and gamma random variables satisfy a set of
relationships sometimes referred to collectively as the _beta-gamma algebra_
[e.g. 38]. These relationships revolve around the fact that, if
$\mathcal{G}_{a}$ and $\mathcal{G}_{b}$ are independent, then

$\bigl{(}\mathcal{G}_{a+b},\mathcal{B}_{a,b}\bigr{)}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\Bigl{(}\mathcal{G}_{a}+\mathcal{G}_{b},\frac{\mathcal{G}_{a}}{\mathcal{G}_{a}+\mathcal{G}_{b}}\Bigr{)}\;,$
(8)

where the pair on the left is independent, and so is the pair on the right. In
the context of $(\alpha,T)$-graphs, conditionally on the sequence
${\Delta_{1},\Delta_{2},\ldots}$ of interarrival times, generate two sequences
of gamma variables

$\mathcal{G}^{(1)},\mathcal{G}^{(2)},\ldots\sim_{\mbox{\tiny iid}}\text{\rm
Gamma}(1-\alpha,1)\qquad\text{ and
}\qquad\mathcal{G}_{\Delta_{2}-1},\mathcal{G}_{\Delta_{3}-1},\ldots\;,$

all mutually independent given ${(\Delta_{k})}$. The variables $\Psi_{k}$ can
then be represented as

$\Psi_{j}\quad\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\quad\frac{\mathcal{G}^{(j)}}{\sum_{i\leq
j}\mathcal{G}^{(i)}+\sum_{i<j}\mathcal{G}_{\Delta_{i+1}-1}}\quad=:\quad\Psi_{j}^{\prime}\;.$
(9)

Such recursive fractions are not generally independent, but as a consequence
of (8), equality in law holds even jointly,
${(\Psi_{1},\Psi_{2},\ldots)\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}(\Psi_{1}^{\prime},\Psi_{2}^{\prime},\ldots)}$, recovering the
variables in Theorem 2. Identity (8) further implies
${\mathcal{B}_{a,b+c}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{B}_{a,b}\mathcal{B}_{a+b,c}}$, again with independence on
the right. Abbreviate

$\tau_{j}:=t_{j}-1+\alpha(j-1)\qquad\text{ such that \eqref{eq:sb:1} becomes
}\qquad\Psi_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{B}_{1-\alpha,\tau_{j}}\;.$

The recursion (9) then implies

$\mathcal{B}_{1-\alpha,\tau_{j}}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{B}_{1-\alpha+\tau_{j-1},\Delta_{j}-\alpha}\mathcal{B}_{1-\alpha,\tau_{j-1}}\quad\text{
hence }\quad\Psi_{j}|\Psi_{j-1}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\Psi_{j-1}\mathcal{B}_{1-\alpha+\tau_{j-1},\Delta_{j}-\alpha}\;,$

with independence on the right of both identities. Informally, one may think
of ${\mathcal{G}^{(k)}}$ as an (unnormalized) propensity of vertex $k$ to
attract edges, of those edges attaching to one of the first $k$ vertices. The
requisite normalization in (9) depends on propensities of previously created
vertices (represented by the variables
${\mathcal{G}^{(1)},\ldots,\mathcal{G}^{(k-1)}}$), and contributions of the
“head start” given to previously created vertices (represented by the
variables $\mathcal{G}_{\Delta_{j}-1}$).

##  2 Graphs and urns

Any graph in $\mathbb{G}$ defines a partition of $\mathbb{N}$, and vice versa.
This fact is used below to classify $\alpha$-degree biased graphs according to
the properties of the random partition they define. More precisely, a
partition of $\mathbb{N}$ is a sequence
${\pi=(b_{1},b_{2},\ldots)\subset\mathbb{N}}$ of subsets, called blocks, such
that each ${n\in\mathbb{N}}$ belongs to one and only one block. The set of all
partitions is denoted ${\mathcal{P}(\mathbb{N})}$, and inherits the topology
of ${\mathbb{N}^{\infty}}$. A partition can equivalently be represented as a
sequence ${\pi=(l_{1},l_{2},\ldots)}$ of block labels, where ${l_{j}=k}$ means
${j\in b_{k}}$. There is hence a bijective map

$\Phi:\mathcal{P}(\mathbb{N})\rightarrow\mathbb{G}\qquad\text{ given by
}\qquad(l_{1},l_{2},\ldots)\mapsto\bigl{(}(l_{1},l_{2}),(l_{3},l_{4}),\ldots\bigr{)}\;,$

which is a homeomorphism of $\mathcal{P}(\mathbb{N})$ and $\mathbb{G}$. It
identifies blocks of $\pi$ with vertices of ${g=\Phi(\pi)}$. In population
genetics, the smallest element of the $k$th block of a partition $\pi$ is
known as a _record index_ [23]. Thus, the $k$th arrival time in $g$ is
precisely the $k$th record index of $\pi$.

The generative process of a random partition $\Pi$ can be thought of as an
urn: Start with an empty urn, and add consecutively numbered balls one at a
time, each colored with a randomly chosen color. Colors may reoccur, and are
enumerated in order of first appearance. Let $B_{k}(n)$ be the set of all
balls sharing the $k$th color after $n$ balls have been added. For
${n\rightarrow\infty}$, one obtains a random partition
${\Pi=(B_{1},B_{2},\ldots)}$ of $\mathbb{N}$, with blocks
${B_{k}:=\cup_{n}B_{k}(n)}$. In analogy to the $(\alpha,t)$-graphs above, we
define:

######  ${(\alpha,t)}$-urn.

Given are ${\alpha\in(-\infty,1)}$ and ${t\in\mathbb{T}}$.

  * $\bullet$

If ${n=t_{k}}$ for some $k$, add a single ball of a new, distinct color to the
urn.

  * $\bullet$

Otherwise, add a ball of a color already present in the urn, where the $j$th
color is chosen with probability proportional to ${|B_{j}(n)|-\alpha}$.

A familiar special case of such an urn is the Pólya urn with $m$ colors,
obtained for ${\alpha=0}$ and ${t=(1,2,\ldots,m,\infty,\infty,\ldots)}$.
Another is the two-parameter Chinese restaurant process [36], also known as
the Blackwell–MacQueen urn [7, 34]: If $t$ is randomized by generating
${(T_{1}=1,T_{2},T_{3},\ldots)}$ according to

$\mathbb{P}[T_{k+1}=T_{k}+t\mid T_{k}]=(\theta+\alpha
k)\frac{\Gamma(\theta+T_{k})\Gamma(T_{k}+t-1-\alpha
k)}{\Gamma(\theta+T_{k}+t)\Gamma(T_{k}-\alpha k)}\;,$ (10)

for some ${\theta>-\alpha}$, the partition has law
${\text{CRP}(\alpha,\theta)}$.

In general, $(\alpha,t)$-urns define a class of random partitions $\Pi$ that
are _coherent_ , in the sense that

$\displaystyle\mathbb{P}(\Pi_{n-1}=\\{B_{1},\dotsc,B_{k}\\})=\sum_{j=1}^{k+1}\mathbb{P}(\Pi_{n}=\mathcal{A}_{n\to
j}(\Pi_{n-1}))\;,$

where $\mathcal{A}_{n\to j}(\Pi_{n-1})$ denotes the operation of appending $n$
to block $B_{j}$ in $\Pi_{n-1}$. Partitions for which these probabilities
depend only on the sizes of the blocks, and which are therefore invariant
under permutations of the elements, are exchangeable random partitions [36].
That is, there is an _exchangeable partition probability function_ (EPPF)
$p(\cdot)$, symmetric in its arguments, such that

$\displaystyle
p(|B_{1}|,\dotsc,|B_{k}|)=\mathbb{P}(\Pi_{n}=\\{B_{1},\dotsc,B_{k}\\})\;,$

which is invariant under the natural action of the symmetric group. A special
subclass are the exchangeable partitions of _Gibbs type_ , for which the EPPF
has the unique product form [21]

$\displaystyle
p(|B_{1}|,\dotsc,|B_{k}|)=V_{n,k}\prod_{j=1}^{k}\frac{\Gamma(|B_{j}|-\alpha)}{\Gamma(1-\alpha)}\;,$
(11)

for a suitable sequence of coefficients $V_{n,k}$ satisfying the recursion

$\displaystyle V_{n,k}=(n-\alpha k)V_{n+1,k}+V_{n+1,k+1}\;.$ (12)

The distribution of the arrival times can be deduced from (11) and (12) as

$\displaystyle\mathbb{P}[T_{k+1}=T_{k}+t\mid
T_{k}]=\frac{\Gamma(T_{k}+t-1-\alpha k)}{\Gamma(T_{k}-\alpha
k)}\frac{V_{T_{k}+t,k+1}}{V_{T_{k},k}}\;,$ (13)

of which (10) for the CRP is a special case. Denote the law of
$T_{1},\dotsc,T_{k}$ generated by (13) as $P_{\alpha,V}(T_{1},\dots,T_{k})$.

Alternatively, consider the $(\alpha,T)$-urn counterpart of the EPPF, given in
Proposition 1,

$\displaystyle p_{\alpha,T}(|B_{1}|,\dotsc,|B_{k}|;$ $\displaystyle\
T_{1},\dots,T_{k})=\mathbb{P}[\Pi_{n}=\\{B_{1},\dotsc,B_{k}\\}\mid
T_{1},\dots,T_{k}]$ (14)
$\displaystyle=\frac{1}{\Gamma(n-k\alpha)}\prod_{j=1}^{k}\frac{\Gamma(T_{j}-j\alpha)\Gamma(|B_{j}|-\alpha)}{\Gamma(T_{j}-1-(j-1)\alpha+\delta_{1}(j))\Gamma(1-\alpha)}\;.$

Define

$\displaystyle
V_{n,k}^{\alpha,T}:=\frac{1}{\Gamma(n-k\alpha)}\prod_{j=1}^{k}\frac{\Gamma(T_{j}-j\alpha)}{\Gamma(T_{j}-1-(j-1)\alpha+\delta_{1}(j))}\;,$
(15)

in which case (14) takes on the Gibbs-like form

$\displaystyle p_{\alpha,T}(|B_{1}|,\dotsc,|B_{k}|;$ $\displaystyle\
T_{1},\dots,T_{k})=V_{n,k}^{\alpha,T}\prod_{j=1}^{k}\frac{\Gamma(|B_{j}|-\alpha)}{\Gamma(1-\alpha)}\;.$

This general formula holds for all $(\alpha,T)$-urns. In the case that $\Pi$
is exchangeable, these relationships imply a further characterization of
exchangeable Gibbs partitions: (11) is obtained by marginalizing the arrival
times from (14) according to $P_{\alpha,V}$.

######  Proposition 3.

Let $\Pi$ be a random partition generated by an $(\alpha,T)$-urn, with finite-
dimensional conditional distributions given by (14). Then $\Pi$ is
exchangeable if and only if there exists some sequence of coefficients
$V=(V_{n,k})$ satisfying

$\displaystyle V_{n,k}$
$\displaystyle=\sum_{\begin{subarray}{c}T_{1},\dotsc,T_{k}\\\ T_{k}\leq
n\end{subarray}}\frac{P_{\alpha,V}(T_{1},\dots,T_{k})}{\Gamma(n-k\alpha)}\prod_{j=1}^{k}\frac{\Gamma(T_{j}-j\alpha)}{\Gamma(T_{j}-1-(j-1)\alpha+\delta_{1}(j))}=\mathbb{E}[V_{n,k}^{\alpha,T}]\;,$

for all $k\leq n$, in which case (11) holds and $\Pi$ is an exchangeable Gibbs
partition.

It is straightforward to verify that $\Phi(\Pi)$ is an $(\alpha,t)$-graph if
and only if $\Pi$ is an $(\alpha,t)$-urn. This correspondence is used in
Section 4 to classify some ${(\alpha,t)}$-graphs according to the urns they
define. It also allows us to translate properties of random graphs into
properties of random partitions, and vice versa. Theorem 2 implies the
following result on partitions, which gives a representation of exchangeable
Gibbs partitions.

######  Corollary 4.

A random partition $\Pi$ is an ${(\alpha,t)}$-urn if and only if it is
distributed as ${\Pi\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}(L_{1},L_{2},\ldots)}$, for variables $L_{n}$ generated according to
(5)–(7).

##  3 Degree asymptotics

Let $G$ be an $(\alpha,t)$-graph, and $G_{n}$ the subgraph given by its first
$n$ edges. The degree sequence of $G_{n}$ is the vector
$\mathbf{D}(n)=(\deg_{k}(n))_{k\geq 1}$, where vertices are ordered by
appearance. Denote by $m_{d}(n)$ the number of vertices in $G_{n}$ with degree
$d$. The empirical degree distribution

$\displaystyle(p_{d}(n))_{d\geq 1}:=|\mathbf{V}(g_{n})|^{-1}(m_{d}(n))_{d\geq
1}$

is the probability that a vertex sampled uniformly at random from $G_{n}$ has
degree $d$. The degree sequence and the degree distribution as $G_{n}$ grows
large are characterized by the scaling behavior induced by $\alpha$ and $t$,
which yields power laws and related properties.

###  3.1 Linear and sub-linear regimes

As will become clear in the next section, the scaling behavior of
$(\alpha,t)$-graphs is the result of products of the form

$\displaystyle W_{j,k}=\prod_{i=j+1}^{k}(1-\Psi_{i})\quad\text{as}\quad
k\to\infty\;,$ (16)

where $(\Psi_{j})_{j>1}$ are as in (5). In particular, two regimes of distinct
limiting behavior emerge. To which of the two regimes an $(\alpha,t)$-graph
belongs is determined by whether or not $W_{j,k}$ converges to a non-zero
value as $k\to\infty$.

We consider $(\alpha,t)$-graphs that satisfy the following assumption:

$\displaystyle|\mathbf{V}(G_{n})|/n^{\sigma}\xrightarrow[n\to\infty]{\text{\small
a.s.}}\mu_{\sigma}^{-\sigma}\quad\text{ for some }\quad 0<\sigma\leq
1\quad\text{ and }\quad 0<\mu_{\sigma}<\infty\;.$ (17)

Slower vertex arrival rates (e.g., logarithmic) result in graphs that are
almost surely dense (see Section 3.4), and as such exhibit less interesting
structural properties. For example, in order to generate power law
distributions in $(\alpha,t)$-graphs, the asymptotic arrival rate must be
super-logarithmic, which follows from work on exchangeable random partitions
and can be read from [36, Chapter 3].

For a growing graph sequence satisfying the assumption (17), consider the
limiting average degree,

$\displaystyle\lim_{n\to\infty}\bar{d}_{n}=\lim_{n\to\infty}\frac{2n}{\mu^{-\sigma}_{\sigma}n^{\sigma}}=\lim_{n\to\infty}\frac{2}{\mu^{-\sigma}_{\sigma}}n^{1-\sigma}\;.$

The average degree is almost surely bounded if $\sigma=1$, which we call the
linear regime; for $\sigma\in(0,1)$, the sub-linear regime, it diverges. This
is a consequence of Proposition 5 below: For a graph $G_{n}$ on $k(n)$
vertices, the probability that the end of edge $n+1$ is attached to vertex $j$
is equal to $\Psi_{j}W_{j,k(n)}$, which results in vertex $j$ participating in
a constant proportion of edges if and only if $W_{j,k(n)}$ is bounded away
from zero as $n$ grows large.

######  Proposition 5.

For fixed $\alpha\in(-\infty,1)$ and $t\in\mathbb{T}$ such that (17) is
satisfied for some $\sigma\in(0,1]$, let $W_{j,k}$ be as in (16). Then for
each $j\geq 1$, $W_{j,k}$ converges almost surely as $k\to\infty$ to some
random variable $W_{j,\infty}$, which is non-zero if and only if $\sigma<1$.

######  Remark 5.

For slower vertex arrivals (e.g.logarithmic) or when the limiting number of
vertices is finite, $W_{j,k(n)}$ also converges to a non-zero value.

###  3.2 Limiting joint distributions of degree sequences for given arrival
times

The previous section suggests that the limit of the scaled degrees should
depend on the random variables $(\Psi_{j})_{j>1}$. Indeed, for any
$(\alpha,t)$-graph $G$, it can be shown that for any $r\in\mathbb{N}_{+}$,

$\displaystyle\bigl{(}n^{-1}\deg_{j}(n)\bigr{)}_{1\leq j\leq
r}\xrightarrow[n\to\infty]{\text{\small a.s.}}\bigl{(}\xi_{j}\bigr{)}_{1\leq
j\leq r}\quad\text{where}\quad\xi_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\Psi_{j}\prod_{i=j+1}^{\infty}(1-\Psi_{i})\;,$ (18)

and $(\Psi_{j})_{j>1}$ are as in (5). Griffiths and Spanò [23] showed that
relative degrees with such a limit uniquely characterize exchangeable Gibbs
partitions among all exchangeable partitions; if the random partition
${\Phi^{-1}(G)}$ is exchangeable, that result applies to $G$ (see Section
4.2). For a general ${(\alpha,t)}$-graph, ${\Phi^{-1}(G)}$ need not be
exchangeable, and indeed there are examples for which ${n^{-1}\mathbf{D}(n)}$
converges to zero, in which case $W_{j,k(n)}$ does, as well. In such cases,
one may ask more generally whether a finite, non-zero limit

$\displaystyle\mathbf{D}_{\infty}:=\lim_{n\to\infty}n^{-1/\gamma}\mathbf{D}(n)\;,$

exists for an appropriate scaling exponent $\gamma$. Theorem 6 establishes
that this is true for $(\alpha,t)$-graphs.

######  Theorem 6.

Let $G$ be an $(\alpha,t)$-graph for some $\alpha\in(-\infty,1)$ and
$t\in\mathbb{T}$. Then (18) holds. If $t$ is such that (17) holds with
$\sigma=1$, assume

$\displaystyle\lim_{j\to\infty}\frac{t_{j}}{j}=\mu\in(1,\infty)\;.$

Then for every $r\in\mathbb{N}_{+}$, there exists a positive, finite constant
$M_{r}(t)$, and positive random variables $\zeta_{1},\dotsc,\zeta_{r}$ such
that

$\displaystyle
M_{r}(t)n^{-r/\gamma}\deg_{1}(n)\dotsm\deg_{r}(n)\xrightarrow[n\to\infty]{\text{\small
a.s.}}\zeta_{1}\dotsm\zeta_{r}\quad\text{where}\quad\gamma=\frac{\mu-\alpha}{\mu-1}\;.$

The mixed moments also converge: For any $p_{1},\dotsc,p_{r}>-(1-\alpha)/2$
with $\bar{p}=\sum_{j=1}^{r}p_{j}$, there exists some
$M_{\bar{p}}(t)\in(0,\infty)$ such that

$\displaystyle
M_{\bar{p}}(t)\mathbb{E}\bigl{[}\lim_{n\to\infty}n^{-\bar{p}/\gamma}\deg_{1}(n)^{p_{1}}\dotsm\deg_{r}(n)^{p_{r}}\bigr{]}=\mathbb{E}\bigl{[}\zeta_{1}^{p_{1}}\dotsm\zeta_{r}^{p_{r}}\bigr{]}\;.$
(19)

Furthermore,

$\displaystyle\bigl{(}\zeta_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq j\leq
r}\;,$ (20)

where $\Psi_{1}=1$ and $(\Psi_{j})_{j>1}$ are as in (5).

In the sub-linear regime, (18) agrees with and generalizes the result of [23]
for exchangeable Gibbs partitions (though the proof uses different methods).
In the linear regime, the mixed moments of the scaled degrees also converge to
those of products of independent beta random variables. However, the result
does _not_ completely describe the joint distributions, due to the presence of
the unknown scaling terms $M_{\bar{p}}(t)$. These terms depend on the moments
$p_{1},\dotsc,p_{r},$ and on $t$, and express the randomness remaining, for
large $k(n)$, in $W_{j,k(n)}$ after the part that scales with $n$ is removed;
in particular, they result from early fluctuations of the process. Section 4
provides stronger results in several cases for which these terms are well-
behaved.

###  3.3 Neutrality

It was noted in Section 2 that the map $\Phi^{-1}$ from graphs to partitions
translates results on graphs into results on partitions. Conversely, one can
transfer properties from partitions to graphs. A sequence
${(X_{1},X_{2},\ldots)}$ of random variables is neutral-to-the-left (NTL) if
the relative increments

$\displaystyle
X_{1},\frac{X_{2}}{X_{1}+X_{2}},\ldots,\frac{X_{j}}{\sum_{i=1}^{j}X_{i}},\ldots$

are independent random variables in (0,1) [17, 23]. If $\Pi$ is an
exchangeable partition, Griffiths and Spanò [23] show that the limiting
relative block sizes of $\Pi$ are NTL if and only if $\Pi$ is an exchangeable
Gibbs partition. If so, the random graph ${\Phi(\Pi)}$ has a limiting degree
sequence $\mathbf{D}_{\infty}$ that is NTL. Due to the representation in
Theorem 2, this property generalizes beyond the exchangeable case:

######  Corollary 7.

The limiting degree sequence $\mathbf{D}_{\infty}$ of an $(\alpha,t)$-graph is
NTL.

###  3.4 Sparsity and power law degrees

Suppose $G_{n}$ is the subgraph of an $(\alpha,T)$-graph $G$, given by the
first $n$ edges. Since $G_{n}$ is finite, one can sample a vertex uniformly at
random from its vertex set and report its degree $D_{n}$. One can then ask
whether the sequence of random degrees $D_{n}$ converges in distribution to
some limiting variable $D$. We show in this section that that is indeed the
case for $(\alpha,T)$-graphs, under some regularity conditions. We also show
how the degree distribution is related to the sparsity, or, equivalently, the
edge density, of $(G_{n})$.

The sequence ${(G_{n})}$ is defined to be $\varepsilon$-dense if

$\displaystyle\underset{n\to\infty}{\lim\sup}\frac{n}{|\mathbf{V}(G_{n})|^{\varepsilon}}=c_{\varepsilon}>0\quad\text{for
some}\quad\varepsilon\geq 1\;.$ (21)

If $\varepsilon<2$, the graph sequence is typically called _sparse_ ; when
$\varepsilon\geq 2$, the sequence is _dense_. Note that ${\varepsilon>2}$ is
only possible for multigraphs. The level of sparsity follows from $\sigma$:
Graph models in the linear regime correspond to $\varepsilon=1$ [9, 5, 2];
graph models in the sub-linear regime with $\sigma>\frac{1}{2}$ have appeared
in the literature [12, 41, 14, 11], with $1<\varepsilon<2$. See Section 4 for
examples.

For functions $a$ and $b$, we use the notation

$\displaystyle
a(n)\overset{\scriptscriptstyle{n\uparrow\infty}}{\mathrel{\scalebox{1.25}[1.0]{$\sim$}}}b(n)\quad:\Leftrightarrow\quad\lim_{n\to\infty}a(n)/b(n)\to
1\;.$

The sequence $(G_{n})$ has power law degree distribution with exponent
$\eta>1$ if

$\displaystyle
p_{d}(n)=\frac{m_{d}(n)}{|\mathbf{V}(G_{n})|}\xrightarrow[n\to\infty]{}p_{d}\overset{\scriptscriptstyle{d\uparrow\infty}}{\mathrel{\scalebox{1.25}[1.0]{$\sim$}}}L(d)d^{-\eta}\quad\text{for
all large $d$}\;,$ (22)

for some slowly varying function $L(d)$, that is,
${\lim_{x\to\infty}L(rx)/L(x)=1}$ for all ${r>0}$ [6, 20].

In the sub-linear regime, the degree distribution follows from results due to
Pitman and Hansen [36, Lemma 3.11], see also [22], on the limiting block sizes
of exchangeable random partitions (see Section 4.2 for more details). In
particular, if (17) is satisfied by an $(\alpha,t)$-graph
$G^{\alpha}=\Phi(\Pi^{\alpha})$ for $\sigma=\alpha\in(0,1)$, then there exist
an exchangeable random partition $\Pi$ and a positive, finite random variable
$S$ such that
${|\mathbf{V}(\Phi(\Pi_{2n}))|/n^{\alpha}\xrightarrow[n\to\infty]{\text{\small
a.s.}}S}$, $\Pi=\Pi^{\alpha}$ and $S=\mu_{\alpha}$. The limiting degree
distribution is

$p^{\alpha}_{d}\quad=\quad\alpha\frac{\Gamma(d-\alpha)}{\Gamma(d+1)\Gamma(1-\alpha)}\quad\overset{\scriptscriptstyle{d\uparrow\infty}}{\mathrel{\scalebox{1.25}[1.0]{$\sim$}}}\quad\frac{\alpha}{\Gamma(1-\alpha)}d^{-(1+\alpha)}\;.$
(23)

In the linear regime, $\sigma=1$, with limiting mean interarrival time
$\mu_{1}$. We show (see Section A.4) that the resulting limiting degree
distribution is a generalization of the classical Yule–Simon distribution
(which corresponds to $\alpha=0$) [42, 39, 19],

$p^{\gamma}_{d}\quad=\quad\gamma\frac{\Gamma(d-\alpha)\Gamma(1-\alpha+\gamma)}{\Gamma(d+1-\alpha+\gamma)\Gamma(1-\alpha)}\quad\overset{\scriptscriptstyle{d\uparrow\infty}}{\mathrel{\scalebox{1.25}[1.0]{$\sim$}}}\quad\gamma\frac{\Gamma(1-\alpha+\gamma)}{\Gamma(1-\alpha)}d^{-(1+\gamma)}\;,$
(24)

where ${\gamma:=\frac{\mu_{1}-\alpha}{\mu_{1}-1}}$, as in (19).

The tail behavior of the two distributions (23), (24) partition the range of
possible values of the power law exponent, as summarized by the following
theorem.

######  Theorem 8.

Let $G$ be a random $(\alpha,T)$-graph for some $\alpha\in(-\infty,1)$ and
$T\in\mathbb{T}$. If

$\displaystyle T_{j}j^{-1/\sigma}\xrightarrow[j\to\infty]{\text{\small
a.s.}}\mu_{\sigma}\quad\text{ for some }\quad\sigma\in(0,1]\quad\text{ and
}\quad 1<\mu_{\sigma}<\infty\;,$

then $G$ has $\varepsilon$-density with $\varepsilon=1/\sigma$. If $\sigma=1$,
assume that $\mathbb{E}[\Delta_{j}]=\mu_{1}$,
${\text{Var}(\Delta_{j})<\infty}$ for all $j\in\mathbb{N}_{+}$, and
$\lvert\text{Cov}(\Delta_{i},\Delta_{j})\rvert\leq C^{2}_{\Delta}\lvert
i-j\rvert^{-\ell_{\Delta}}$ for all $i,j>1$, some $C^{2}_{\Delta}\geq 0$, and
some $\ell_{\Delta}>0$. Then the degree distribution converges asymptotically,

$\displaystyle\frac{m_{d}(n)}{|\mathbf{V}(G_{n})|}\xrightarrow[n\to\infty]{\text{\small
p}}\begin{cases}p^{\alpha}_{d}&\text{ if }\sigma=\alpha\in(0,1)\\\
p^{\gamma}_{d}&\text{ if }\sigma=1\end{cases}\;,$

which for large $d$ follows a power law with exponent

$\displaystyle\eta=\begin{cases}1+\alpha&\in(1,2)\quad\;\;\text{ if
}\sigma=\alpha\in(0,1)\\\ 1+\gamma&\in(2,\infty)\quad\text{ if
}\sigma=1\end{cases}\;.$

The distributions (23), (24) have the following representation, which is
useful for generating realizations from those distributions.

######  Corollary 9.

Let $G$ be a random $(\alpha,T)$-graph for some $\alpha\in(-\infty,1)$ and
$T\in\mathbb{T}$ satisfying the conditions of Theorem 8. Then the degree
$D_{n}$ of a vertex sampled uniformly at random from $G_{n}$ converges in
distribution to $D^{\prime}$, where $D^{\prime}$ is sampled as

$\displaystyle D^{\prime}\sim\text{\rm Geom}(\mathcal{B})\quad\text{ for
}\quad\mathcal{B}\sim\begin{cases}\text{\rm Beta}(\alpha,1-\alpha)&\text{ if
}\sigma=\alpha\in(0,1)\\\ \text{\rm Beta}(\gamma,1-\alpha)&\text{ if
}\sigma=1\end{cases}\;.$

This representation can be refined further: The proof of Theorem 8 shows, by
extending techniques introduced by Berger, Borgs, Chayes, and Saberi [5], that
the neighborhood of a random vertex can be coupled to a Poisson point process
on the unit interval. That yields the following representation:

######  Corollary 10.

Let $G$ be a random $(\alpha,T)$-graph for some $\alpha\in(-\infty,1)$ and
$T\in\mathbb{T}$ satisfying the conditions of Theorem 8. Then the degree
$D_{n}$ of a vertex sampled uniformly at random from $G_{n}$ converges in
distribution to $D^{\prime}$, where $D^{\prime}$ is sampled as

$D^{\prime}\sim\text{\rm Poisson}\left(\frac{1-\mathcal{B}}{\mathcal{B}}\
\mathcal{G}_{1-\alpha}\right)\quad\text{ for
}\quad\mathcal{B}\sim\begin{cases}\text{\rm Beta}(\alpha,1)&\text{ if
}\sigma=\alpha\in(0,1)\\\ \text{\rm Beta}(\gamma,1)&\text{ if
}\sigma=1\end{cases}\;.$

######  Remark 10.

Based on the fact that $(1-\mathcal{B})/\mathcal{B}$ is distributed as a so-
called beta prime random variable, additional distributional identities may be
deduced. To give one, let $\mathcal{G}_{1}$, $\mathcal{G}_{\alpha}$, and
$\mathcal{G}_{\gamma}$ be independent Gamma random variables. Then one can
replace $(1-\mathcal{B})/\mathcal{B}$ above by
$\mathcal{G}_{1}/\mathcal{G}_{\alpha}$ (for ${\sigma=\alpha<1}$) or
$\mathcal{G}_{1}/\mathcal{G}_{\gamma}$ (for ${\sigma=1}$).

###  3.5 A note on almost surely connected graphs

Suppose one requires each graph in the evolving sequence $(G_{n})$ drawn from
an $(\alpha,T)$-graph to be almost surely connected. That holds if and only if
${T\in\mathcal{T}_{\text{\tiny\rm 2}}}$, i.e. if each arrival time after
${T_{1}=1}$ is even. A simple way to generate $T\in\mathcal{T}_{\text{\tiny\rm
2}}$ is to sample $\Delta_{2},\Delta_{3},\dotsc$ as in the generation of
general $T\in\mathbb{T}$, and to set

$\displaystyle T_{2}=2\Delta_{2},\quad
T_{k}=T_{k-1}+2\Delta_{k}\quad\text{for}\quad k>2\;.$ (25)

In the sub-linear regime, doubling the interarrival times does not affect the
degree asymptotics. In the linear regime, the change has noticeable affect.
For example, suppose the variables $\Delta_{k}$ above are drawn i.i.d. from
some probability distribution on $\mathbb{N}_{+}$ with mean $\mu$. Then by
Theorem 8, the limiting degree distribution has power law exponent
$\eta_{\text{\tiny\rm 2}}=1+\frac{2\mu-\alpha}{2\mu-1}$. For
${T\not\in\mathcal{T}_{\text{\tiny\rm 2}}}$, the upper limit of $\eta$ is
$\infty$, no matter the value of $\alpha$; for
$T\in\mathcal{T}_{\text{\tiny\rm 2}}$, one has ${\eta_{\text{\tiny\rm
2}}<3-\alpha}$. Hence, if $\alpha>0$, then $\eta_{\text{\tiny\rm 2}}\in(2,3)$,
implying that the limiting degree distribution has finite mean, but unbounded
variance for any $\mu$.

##  4 Examples

Figure 1: Examples of ${(\alpha,T)}$-graphs generated using different arrival
time distributions. Each graph has $500$ edges. Left: arrival times generated
by $\text{\rm CRP}(\alpha,\theta)$, with $\alpha=0.1$, $\theta=5$. Middle:
interarrival times are i.i.d. $\text{\rm Poisson}_{+}(2)$, with $\alpha=0.1$.
Right: interarrival times are i.i.d. $\text{\rm Geom}(0.25)$, with
$\alpha=0.5$.

We next discuss several subclasses of $(\alpha,T)$-graphs. One is obtained by
fixing all interarrival times to the same, constant value (Section 4.1). This
includes the Barabási–Albert random tree as a special case. Other subclasses
can be obtained by imposing exchangeability assumptions. One is that the
vertex assignment variables $L_{n}$ form an exchangeable sequence, and hence
that the induced random partition ${\Phi^{-1}(G)}$ is exchangeable (Section
4.2). This subclass overlaps with the class of “edge exchangeable” graphs [14,
11, 28]. If the interarrival times ${\Delta_{k}}$ are exchangeable (Section
4.3), the induced partition is not exchangeable. This case includes a version
of the random graph model of [1, 2, 13].

###  4.1 Barabási–Albert trees and graphs with constant interarrival time

The basic preferential attachment model popularized by [4] generates a random
graph as follows: With parameter ${d\in\mathbb{N}_{+}}$, start with any finite
connected graph. At each step, select $d$ vertices in the current graph
independently from $P_{0}$ in (3), add a new vertex, and connect it to the $d$
selected vertices (multiple connections are allowed).

The Barabási–Albert model can be expressed in terms of a sequence
$(L_{1},L_{2},\ldots)$ with given arrival times as follows: Start, say, with a
graph consisting of a single vertex and $d$ self-loops. Thus, ${t_{k}=1}$ and
${L_{1}=\ldots=L_{2d}=1}$. Each new vertex requires $2d$ stubs, so
${t_{k+1}=t_{k}+2d}$. At time ${t_{k+1}-1=(2d)k}$, just before the
${(k+1)}$-st vertex arrives, the graph ${G_{kd}=(L_{n})_{n\leq 2kd}}$ has $k$
vertices and $kd$ edges. For ${t_{k}\leq n<t_{k+1}}$, we then set

$L_{n}=k\quad\text{ if }n\text{ odd }\qquad\text{ and }\qquad L_{n}\sim
P_{0}({\,\vbox{\hbox{\tiny$\bullet$}}\,};G_{(k-1)d})\quad\text{ if }n\text{
even.}$

The single vertex with self-loops is chosen as a seed graph here only to keep
notation reasonable. More generally, any graph with $k$ vertices and $n$ edges
can be encoded in the variables ${L_{1},\ldots,L_{2n}}$ and the first $k$
arrival times.

When $d=1$, the result is a tree (with a loop at the root). When $d\geq 2$,
the above sampling scheme does not produce an $(\alpha,t)$-graph. However, the
following modified sampling scheme produces an $(\alpha,t)$-graph with
$\Delta_{j}=2d$ for all $j>1$. Start as before with a graph consisting of a
single vertex and $d$ self-loops. When the $k$-th vertex arrives at time
$t_{k}=2(k-1)d+1$, set $L_{t_{k}}=k$ and for $t_{k}+1\leq n<t_{k+1}$, set

$L_{n}\sim P_{\alpha}({\,\vbox{\hbox{\tiny$\bullet$}}\,};(L_{i})_{i<n})\;.$

The modified sampling scheme differs from the basic preferential attachment
model in that it updates the degrees after each step, allows loops, and does
not require that each vertex begin with $d$ edges. Although the connectivity
properties of the resulting graph may be substantially different from the
Barabási–Albert model, the degree properties are similar to modifications that
have been considered by [5, 32]. In this case, the results of Section 3.2 can
be strengthened, showing that the scaled degrees converge to random variables
that satisfy distributional relationships generalizing those of the beta-gamma
algebra (8), as discussed by Dufresne [18]. (See also [27].) These
relationships emerge due to the behavior of $W_{j,k}$ as $k\to\infty$, which
separates into two pieces: A deterministic scaling factor, and the random
variables that appear below.

######  Proposition 11.

Let $G$ be an $(\alpha,t)$-graph with $\alpha\in(-\infty,1)$ such that for
some $d\in\mathbb{N}_{+}$, $t_{j}=2d(j-1)+1$ for all $j\geq 1$. Then for every
$r\in\mathbb{N}_{+}$,

$\displaystyle\biggl{(}\frac{n}{2m}\biggr{)}^{-\frac{2d-1}{2d-\alpha}}(\deg_{j}(n))_{1\leq
j\leq r}\xrightarrow[n\to\infty]{\text{\small a.s.}}(\xi_{j})_{1\leq j\leq
r}\;.$

The vector of random variables $(\xi_{j})_{1\leq j\leq r}$ satisfies the
following distributional identities: Denote $\bar{\alpha}:=2d-\alpha$, and
define

$\displaystyle
Z_{r}=\prod_{i=1}^{2d-1}\mathcal{G}^{1/\bar{\alpha}}_{r+1-i/\bar{\alpha}}\quad\text{and}\quad
Z^{\prime}_{r}=\prod_{i=1}^{2d-1}\mathcal{G}^{1/\bar{\alpha}}_{1-i/\bar{\alpha}}\quad\text{and}\quad
Z^{\prime\prime}_{r}=Z^{\prime}_{r}\prod_{k=1}^{r-1}\mathcal{B}_{k\bar{\alpha},1-\alpha}\;,$

where all of the random variables are independent of each other and of
$(\xi_{j})_{j}$. Then with $\Psi_{1}=1$, and ${(\Psi_{j})_{j>1}\sim\text{\rm
Beta}(1-\alpha,(j-1)(2d-\alpha))}$, the following distributional identities
hold:

$\displaystyle Z_{r}\cdot\bigl{(}\xi_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{r\bar{\alpha}}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}$ (26) $\displaystyle
Z^{\prime}_{r}\cdot\bigl{(}\xi_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{r\bar{\alpha}}\prod_{k=1}^{r}\mathcal{B}_{k\bar{\alpha}-2d+1,2d-1}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}$ (27) $\displaystyle
Z^{\prime}_{r}\cdot\bigl{(}\xi_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{r\bar{\alpha}-2d+1}\prod_{k=1}^{r-1}\mathcal{B}_{k\bar{\alpha}-2d+1,2d-1}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}$ (28) $\displaystyle
Z^{\prime\prime}_{r}\cdot\bigl{(}\xi_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{1-\alpha}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}\;.$ (29)

######  Remark 11.

For a gamma random variable $\mathcal{G}_{a}$, $\mathcal{G}_{a}^{b}$ has so-
called generalized gamma distribution, denoted $\text{\rm GGa}(a/b,1/b)$.
Hence, $Z_{r}$ above is equal to the product of $\text{\rm
GGa}((r+1)\bar{\alpha}-i,\bar{\alpha})$ random variables, and similarly for
$Z^{\prime}_{r}$. Generalized gamma random variables also appear in the limits
of the preferential attachment models in [32, 37], and arise in a range of
other applications [31].

Results on power law degree distributions in preferential attachment models
are numerous [e.g. 4, 1, 2, 5]. It is well-known that the degree distribution
of the Barabási–Albert tree exhibits a power law with exponent $\eta=3$ [4,
8], which agrees with the following implication of Theorem 8.

######  Corollary 12.

For the constant interarrival time model considered above, the degree
distribution converges to (24) with $\gamma=(2d-\alpha)/(2d-1)$. In
particular, the $\alpha$-weighted Barabási–Albert tree has power law exponent
$\eta=3-\alpha$.

###  4.2 Graphs with exchangeable vertex assignments

Suppose $G$ is a random graph such that the random partition
${\Pi=\Phi^{-1}(G)}$ is exchangeable (see [36] for more on exchangeable
partitions). Equivalently, the vertex assignments ${L_{1},L_{2},\ldots}$ are
exchangeable, and there is hence a random probability measure $\mu$ on
$\mathbb{N}$ such that

$L_{1},L_{2},\ldots\mid\mu\sim_{\mbox{\tiny iid}}\mu\;.$ (30)

We first note an implication of Theorem 8. Recall that a random graph is
sparse if its density (21) is ${\varepsilon<2}$.

######  Corollary 13.

If a graph generated by an exchangeable partition is sparse and has a power
law degree distribution, then ${\sigma>1/2}$, and hence ${\eta\in(3/2,2)}$.

Recall from Section 2 that an exchangeable Gibbs partition is an exchangeable
random partition $\Pi$ such that the probability of any finite restriction
$\Pi_{n}$ can be written as

$\displaystyle\mathbb{P}(\Pi_{n}=\\{\deg_{1}(n),\dots,\deg_{k}(n)\\})=V_{n,k}\prod_{j=1}^{k}\frac{\Gamma(\deg_{j}(n)-\alpha)}{\Gamma(1-\alpha)}\;,$

for a suitable sequence of weights $V_{n,k}$. Griffiths and Spanò [23] studied
the block arrival times (called, in that context, the record indices) of
exchangeable Gibbs partitions. For the random graph induced by such
partitions, their results show that

$\displaystyle\frac{1}{n}\deg_{j}(n)\xrightarrow[n\to\infty]{\text{\small
a.s.}}P_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\Psi_{j}\prod_{i=j+1}^{\infty}(1-\Psi_{i})\;,$ (31)

where $\Psi_{j}$ is distributed as in (5). (This result is also contained in
Theorem 6.) They prove that an exchangeable random partition is of Gibbs form
if and only if the sequence $(P_{j})_{j\geq 1}$ is NTL conditioned on
$(T_{j})_{j\geq 1}$; this result has implications for some recent network
models.

Crane and Dempsey [14] and Cai, Campbell, and Broderick [11] call a random
graph ${((L_{1},L_{2}),\ldots)}$ _edge exchangeable_ if there is some random
probability measure $\nu$ on ${\mathbb{N}^{2}}$ such that

$(L_{1},L_{2}),(L_{3},L_{4}),\ldots\mid\nu\sim_{\mbox{\tiny iid}}\nu\;.$

Janson [28] refers to such a graph as being _rank one_ if
${\nu=\mu\otimes\mu}$ for some random probability measure on $\mathbb{N}$,
which is just (30). Thus, rank one edge exchangeable graphs are precisely
those corresponding to exchangeable random partitions via $\Phi$. The
intersection of edge exchangeable and $(\alpha,T)$-graphs are precisely those
$(\alpha,T)$-graphs that have exchangeable vertex assignments, in which case
$\Pi$ is an exchangeable Gibbs partition. That includes the case
${\Pi\sim\text{\rm CRP}(\alpha,\theta)}$ above, for which [14] call
$G=\Phi(\Pi)$ the _Hollywood model_.

######  Proposition 14.

Let $G$ be a rank one edge exchangeable graph, and let $\mathbf{D}_{\infty}$
be the limiting degree proportions $n^{-1}(\deg_{1}(n),\deg_{2}(n),\dotsc)$.
Then $\mathbf{D}_{\infty}$ is NTL if and only if $G$ is distributed as a
$(\alpha,T)$-graph, where $T$ distributed as in (13), in which case
$\mathbf{D}_{\infty}$ is distributed as in (31).

The results of Section 3.2 specialize for $G=\Phi(\Pi)$ where $\Pi$ has law
$\text{\rm CRP}(\alpha,\theta)$. In particular, consider conditioning on the
first $r$ arrival times, rather than all arrival times. As Proposition 15
shows, the scaled degrees have the same basic structure as in Section 3.2, but
$\mathbb{E}[W_{r,\infty}]$ is captured by a single beta random variable.

######  Proposition 15.

Let $G$ be an $(\alpha,T)$-graph for fixed $\alpha\in(0,1)$ such that $T$ are
the arrival times induced by a $\text{\rm CRP}(\alpha,\theta)$ partition
process (10). Then for every $r\in\mathbb{N}_{+}$, conditioned on
$T_{1},\dotsc,T_{r}$,

$\displaystyle n^{-1}(\deg_{j}(n))_{1\leq j\leq r}\mid
T_{1},\dotsc,T_{r}\xrightarrow[n\to\infty]{\text{\small
a.s.}}(\xi_{1},\dotsc,\xi_{r})\;,$

where

$\displaystyle\bigl{(}\xi_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{B}_{T_{r}-r\alpha,\theta+r\alpha}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}\;,$ (32)

with $\Psi_{1}=1$, $\Psi_{j}\sim\text{\rm Beta}(1-\alpha,T_{j}-1-(j-1)\alpha)$
and $\mathcal{B}_{T_{r}-r\alpha,\theta+r\alpha}$ mutually independent random
variables for $j\geq 1$. This implies the joint distributional identity

$\displaystyle\mathcal{G}_{T_{r}+\theta}\cdot\bigl{(}\xi_{j}\bigr{)}_{1\leq
j\leq r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{T_{r}-r\alpha}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}\;.$ (33)

and the marginal identities for all $j>1$

$\displaystyle\xi_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{B}_{1-\alpha,T_{j}-1+\theta+\alpha}$
$\displaystyle\xi_{j+1}\mid\xi_{j},\Delta_{j+1}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\xi_{j}\mathcal{B}_{T_{j}+\theta,\Delta_{j+1}}\;.$

The random variable $\xi_{j}$ is independent of $j$, given $T_{j}$. Among all
$(\alpha,T)$-graphs derived from exchangeable Gibbs partitions, this property
characterizes those derived from $\text{\rm CRP}(\alpha,\theta)$ partitions,
and stems from the arrival time distribution (see Section 4.4).

######  Proposition 16.

Let $G$ be an $(\alpha,T)$-graph such that $T$ are the arrival times induced
by an exchangeable Gibbs partition $\Pi$. For any $j\geq 1$, the marginal
distribution of $\xi_{j}$ conditioned on $j$th arrival time depends only on
$T_{j}$ if and only if $\Pi$ has law $\text{\rm CRP}(\alpha,\theta)$.

###  4.3 Graphs with exchangeable interarrival times

We next consider $(\alpha,T)$-graphs for which the interarrival times
${\Delta_{j}=T_{j}-T_{j-1}}$ are exchangeable. An immediate consequence of
exchangeability is that ${k^{-1}\sum_{j\leq k}\Delta_{j}\rightarrow\mu}$
almost surely for some constant ${\mu}$ in ${[1,\infty]}$. Theorem 6 implies:

######  Corollary 17.

If ${\mu}$ is finite, the limiting degrees scale as $n^{1/\gamma}$ in (19),
where ${\gamma=(\mu-\alpha)/(\mu-1)}$. If $\text{Var}(\Delta_{j})$ is finite
for all $j$, then the degree distribution converges to (24).

Stronger results hold when the interarrivals are i.i.d. geometric variables,
corresponding to the Yule–Simon model [42, 39]. Recall that a positive random
variable $\mathcal{M}_{\sigma}$ is said to have _Mittag–Leffler distribution_
with parameter $\sigma\in(0,1)$ if
$\mathcal{M}_{\sigma}=\mathcal{Z}_{\sigma}^{-\sigma}$, where
$\mathcal{Z}_{\sigma}$ is a positive $\sigma$-stable random variable,
characterized by the Laplace transform
$\mathbb{E}[e^{-\lambda\mathcal{Z}}]=e^{-\lambda^{\sigma}}$ and density
$f_{\sigma}(z)$. See [36, 25] for details. Define
$\mathcal{Z}_{\sigma,\theta}$ for $\theta>-\sigma$ as a random variable with
the polynomially tilted density ${f_{\sigma,\theta}\propto
z^{-\theta}f_{\sigma}(z)}$, and let
$\mathcal{M}_{\sigma,\theta}=\mathcal{Z}_{\sigma,\theta}^{-\sigma}$. We denote
the law of $\mathcal{M}_{\sigma,\theta}$ by $\text{\rm ML}(\sigma,\theta)$,
which is known as the generalized Mittag–Leffler distribution [35, 25].

######  Proposition 18.

Let $G$ be an $(\alpha,T)$-graph with $\alpha=0$, and $T$ constructed from
i.i.d. $\text{\rm Geom}(\beta)$ interarrival times, for $\beta\in(0,1)$. Then
for every $r\in\mathbb{N}_{+}$, conditioned on $T_{1},\dotsc,T_{r}$,

$\displaystyle n^{-(1-\beta)}(\deg_{j}(n))_{1\leq j\leq r}\mid
T_{1},\dotsc,T_{r}\quad\xrightarrow[n\to\infty]{\text{\small
a.s.}}\quad(\xi_{1},\dotsc,\xi_{r})\;,$

where

$\displaystyle\bigl{(}\xi_{j}\bigr{)}_{1\leq j\leq
r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{M}_{1-\beta,T_{r}-1}\mathcal{B}_{T_{r},(T_{r}-1)\frac{\beta}{1-\beta}}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}\;,$ (34)

with $M_{1-\beta,T_{r}-1}$,
$\mathcal{B}_{T_{r},(T_{r}-1)\frac{\beta}{1-\beta}}$, $\Psi_{1}=1$ and
$\Psi_{j}\sim\text{\rm Beta}(1,T_{j}-1)$ mutually independent random variables
for $j\geq 1$. This implies the joint distributional identity

$\displaystyle\mathcal{G}_{T_{r}}^{1-\beta}\cdot\bigl{(}\xi_{j}\bigr{)}_{1\leq
j\leq r}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{T_{r}}\cdot\bigl{(}\Psi_{j}\prod_{i=j+1}^{r}(1-\Psi_{i})\bigr{)}_{1\leq
j\leq r}\;,$

and the marginal identities for $j>1$

$\displaystyle\xi_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{M}_{1-\beta}\mathcal{B}_{1,T_{j}-1}^{1-\beta}$ (35)
$\displaystyle\xi_{j+1}\mid\xi_{j},\Delta_{j+1}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\xi_{j}\mathcal{B}^{1-\beta}_{T_{j},\Delta_{j+1}}$ (36)
$\displaystyle\xi_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{M}_{1-\beta,T_{j}-1}\mathcal{B}_{T_{j},(T_{j}-1)\frac{\beta}{1-\beta}}\Psi_{j}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{M}_{1-\beta,T_{j}-1}\mathcal{B}_{1,\frac{T_{j}-1}{1-\beta}}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{M}_{1-\beta,T_{j}}\mathcal{B}_{1,\frac{T_{j}-1+\beta}{1-\beta}}$
(37)
$\displaystyle\xi_{j+1}\mid\xi_{j},\Delta_{j+1}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\xi_{j}\mathcal{B}_{\frac{T_{j}}{1-\beta},\frac{\Delta_{j+1}}{1-\beta}}\prod_{i=1}^{\Delta_{j+1}}\mathcal{B}_{\frac{T_{j}-1+i-\beta}{1-\beta},\frac{\beta}{1-\beta}}$
(38)
$\displaystyle\xi_{j}\mathcal{G}_{T_{j}}^{1-\beta}\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\mathcal{G}_{1}\;.$ (39)

Peköz, Röllin, and Ross [33] consider the following two-color Pólya urn: Let
$\Delta_{1},\Delta_{2},\dotsc$ be drawn i.i.d. from some distribution
$P_{\Delta}$, and define $T_{j}=\sum_{i=1}^{j}\Delta_{j}$. Starting with $w$
white balls and $b$ black balls, at each step $n\neq T_{j}$, a ball is drawn
and replaced along with another of the same color. On steps $n=T_{j}$, a black
ball is added to the urn. Of interest is the distribution of the number of
white balls in the urn after $n$ steps.

In the language of $(\alpha,T)$-graphs, consider a seed graph $G_{w+b}$ with
$k_{w+b}<w+b$ vertices and $w+b$ edges arranged arbitrarily, the only
constraint being that there exists a bipartition
$\mathbf{V}_{w}\cup\mathbf{V}_{b}=\mathbf{V}(G_{w+b})$ so that the total
degree of the vertices in $\mathbf{V}_{w}$ is $D_{w}(w+b)=w$, and of those in
$\mathbf{V}_{b}$ is $D_{b}(w+b)=b$. For $T$ constructed from i.i.d.
interarrivals, $D_{w}(n)$ corresponds to the number of white balls after $n$
steps. For interarrivals drawn i.i.d. from the geometric distribution, the
following result characterizes the limiting distribution of $D_{w}(n)$, which
was left as an open question by Peköz, Röllin, and Ross [33].

######  Proposition 19.

Let $D_{w}(n)$ be the number of white balls in the Pólya urn with immigration
from [33] starting with $w$ white balls and $b$ black balls, where the
immigration times have i.i.d. $\text{\rm Geom}(\beta)$ distribution. Then

$\displaystyle
n^{-(1-\beta)}D_{w}(n)\quad\xrightarrow[n\to\infty]{\text{\small
a.s.}}\quad\xi_{w,w+b}\;\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\;\mathcal{B}_{w,b}\mathcal{B}_{w+b,(w+b-1)\frac{\beta}{1-\beta}}\mathcal{M}_{1-\beta,w+b-1}\;,$

which implies the distributional identities

$\displaystyle\xi_{w,w+b}\;\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\;\mathcal{B}_{w,\frac{(w-1)\beta+b}{1-\beta}}\mathcal{M}_{1-\beta,w+b-1}$
(40) $\displaystyle\xi_{w,w+b}\;\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\;\mathcal{B}_{w,\frac{w\beta+b}{1-\beta}}\mathcal{M}_{1-\beta,w+b}$
(41)
$\displaystyle\xi_{w,w+b}\mathcal{G}_{w+b}^{1-\beta}\;\stackrel{{\scriptstyle\text{\rm\tiny
d}}}{{=}}\;\mathcal{G}_{w}\;.$ (42)

${\mathbb{P}{\\{n+1\text{ is arrival time}|G_{n}\\}}}$ |  $\Phi^{-1}(G)$ is |  |  |
---|---|---|---|---
depends on |  $(\alpha,T)$-urn | $\mathcal{L}(\Phi^{-1}(G))$ | $\mathcal{L}(G)$ | $\mathcal{L}(\Delta_{k})$
$n$ | yes | $\text{\rm CRP}(\theta)$ | Hollywood model | (10)
$n,\\#\text{vertices in }G_{n}$ | yes | Gibbs partition |  $\subset$ rank one edge exch. | (13)
$n$, $\\#\text{vertices in }G_{n}$, degrees | no | exch. partition | rank one edge exch. | –
deterministic | yes | – | PA tree | $\delta_{2}$
independent | yes | Yule–Simon process | ACL [1, 2] | $\text{\rm Geom}(\beta)$
$n+1-T_{k(n)}$ | yes |  $(\alpha,T)$-urn |  $(\alpha,T)$-graph | i.i.d.

Table 1: Classification of different models according to which statistics of
$G_{n}$ determine the probability that a new vertex is observed at time $n+1$.

###  4.4 Classification by arrival time probabilities

De Blasi, Favaro, Lijoi, Mena, Prünster, and Ruggiero [16] classify
exchangeable partitions according to the quantities on which the probability
of observing a new block in draw ${n+1}$ depends [16, Proposition 1],
conditionally on the partition observed up to time $n$. This classification
can be translated to random graphs via the induced partition ${\Phi^{-1}(G)}$,
and can be extended further since partitions induced by $(\alpha,T)$-graphs
need not be exchangeable: See Table 1. One might also consider a sequence of
interarrival distributions indexed by the number of vertices, yielding a
bespoke generalization of the last row, where the probability of a new vertex
depends on $n+1-T_{k(n)}$ and the number of vertices.

## Acknowledgments

We are grateful to Nathan Ross for helpful comments on the manuscript. BBR is
supported by the European Research Council under the European Union’s Seventh
Framework Programme (FP7/2007–2013) / ERC grant agreement no. 617071. PO was
supported in part by grant FA9550-15-1-0074 of AFOSR.

## References

  * Aiello et al. [2001] W. Aiello, F. Chung, and L. Lu.  A random graph model for power law graphs.  _Experiment. Math._ , 10(1):53–66, 2001.
  * Aiello et al. [2002] W. Aiello, F. Chung, and L. Lu.  Random evolution in massive graphs.  In J. Abello, P. M. Pardalos, and M. G. C. Resende, editors, _Handbook of Massive Data Sets_ , volume II, pages 97–122, 2002.
  * Arratia et al. [2013] R. Arratia, L. Goldstein, and F. Kochman.  Size bias for one and all.  08 2013.  https://arxiv.org/abs/1308.2729.
  * Barabási and Albert [1999] A.-L. Barabási and R. Albert.  Emergence of scaling in random networks.  _Science_ , 186(5439):509–512, 1999.
  * Berger et al. [2014] N. Berger, C. Borgs, J. T. Chayes, and A. Saberi.  Asymptotic behavior and distributional limits of preferential attachment graphs.  _Ann. Probab._ , 42(1):1–40, 01 2014.
  * Bingham et al. [1989] N. H. Bingham, C. M. Goldie, and J. L. Teugels.  _Regular Variation_ , volume 27 of _Encyclopedia of Mathematics and its Applications_.  Cambridge University Press, 07 1989.
  * Blackwell and MacQueen [1973] D. Blackwell and J. B. MacQueen.  Ferguson distributions via pólya urn schemes.  _Ann. Statist._ , 1(2):353–355, 03 1973.
  * Bollobás et al. [2001] B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády.  The degree sequence of a scale-free random graph process.  _Random Structures & Algorithms_, 18(3):279–290, 2001.
  * Bollobás et al. [2007] B. Bollobás, S. Janson, and O. Riordan.  The phase transition in inhomogeneous random graphs.  _Random Structures & Algorithms_, 31(1):3–122, 2007.
  * Broderick et al. [2012] T. Broderick, M. I. Jordan, and J. Pitman.  Beta processes, stick-breaking and power laws.  _Bayesian Analysis_ , 7(2):439–476, 06 2012.
  * Cai et al. [2016] D. Cai, T. Campbell, and T. Broderick.  Edge-exchangeable graphs and sparsity.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems 29_ , pages 4242–4250. Curran Associates, Inc., 12 2016.
  * Caron and Fox [2017] F. Caron and E. B. Fox.  Sparse graphs using exchangeable random measures.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 79(5):1–44, 2017.
  * Chung and Lu [2006] F. Chung and L. Lu.  _Complex Graphs and Networks_.  (CBMS Regional Conference Series in Mathematics). American Mathematical Society, 2006.
  * Crane and Dempsey [2016] H. Crane and W. Dempsey.  Edge exchangeable models for network data.  03 2016.  URL https://arxiv.org/abs/1603.04571.
  * Daley and Vere-Jones [2008] D. J. Daley and D. Vere-Jones.  _An Introduction to the Theory of Point Processes_ , volume II of _Probability and its Applications_.  Springer-Verlag New York, 2008.
  * De Blasi et al. [2015] P. De Blasi, S. Favaro, A. Lijoi, R. H. Mena, I. Prünster, and M. Ruggiero.  Are Gibbs-type priors the most natural generalization of the Dirichlet process?  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 37(2):212–229, 02 2015.
  * Doksum [1974] K. Doksum.  Tailfree and neutral random probabilities and their posterior distributions.  _Ann. Probab._ , 2(2):183–201, 04 1974.
  * Dufresne [2010] D. Dufresne.  G distributions and the beta-gamma algebra.  _Electron. J. Probab._ , 15:2163–2199, 2010.
  * Durrett [2006] R. Durrett.  _Random Graph Dynamics_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York, NY, USA, 2006.
  * Feller [1971] W. Feller.  _An Introduction to Probability Theory and Its Applications_ , volume 2.  Wiley, 2nd edition, 1971.
  * Gnedin and Pitman [2006] A. Gnedin and J. Pitman.  Exchangeable Gibbs partitions and stirling triangles.  _Journal of Mathematical Sciences_ , 138(3):5674–5685, 2006.  ISSN 1573-8795.
  * Gnedin et al. [2007] A. Gnedin, B. Hansen, and J. Pitman.  Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws.  _Probab. Surveys_ , 4:146–171, 2007.
  * Griffiths and Spanò [2007] R. C. Griffiths and D. Spanò.  Record indices and age-ordered frequencies in exchangeable Gibbs partitions.  _Electron. J. Probab._ , 12:1101–1130, 2007.
  * Hofstad [2016] R. van der. Hofstad.  _Random Graphs and Complex Networks_ , volume 1 of _Cambridge Series in Statistical and Probabilistic Mathematics_.  Cambridge University Press, 2016.
  * James [2015] L. F. James.  Generalized Mittag–Leffler distributions arising as limits in preferential attachment models.  09 2015.  URL http://arxiv.org/abs/1509.07150.
  * Janson [2006] S. Janson.  Limit theorems for triangular urn schemes.  _Probability Theory and Related Fields_ , 134(3):417–452, 2006.
  * Janson [2010] S. Janson.  Moments of gamma type and the Brownian supremum process area.  _Probab. Surveys_ , 7:1–52, 2010.
  * Janson [2017] S. Janson.  On edge exchangeable random graphs.  02 2017.  URL https://arxiv.org/abs/1702.06396.
  * Kerov [2006] S. V. Kerov.  Coherent random allocations, and the Ewens–Pitman formula.  _Journal of Mathematical Sciences_ , 138(3):5699–5710, 2006.
  * Móri [2005] T. F. Móri.  The maximum degree of the Barabási–Albért random tree.  _Comb. Probab. Comput._ , 14(3):339–348, May 2005\.
  * Peköz et al. [2016] E. A. Peköz, A. Röllin, and N. Ross.  Generalized gamma approximation with rates for urns, walks and trees.  _Ann. Probab._ , 44(3):1776–1816, 05 2016.
  * Peköz et al. [2017] E. A. Peköz, A. Röllin, and N. Ross.  Joint degree distributions of preferential attachment random graphs.  _Advances in Applied Probability_ , 49(2):368–387, 2017.
  * Peköz et al. [forthcoming] E. A. Peköz, A. Röllin, and N. Ross.  Pólya urns with immigration at random times.  _Bernoulli_ , forthcoming.
  * Pitman [1996] J. Pitman.  _Some developments of the Blackwell-MacQueen urn scheme_ , volume Volume 30 of _Lecture Notes–Monograph Series_ , pages 245–267.  Institute of Mathematical Statistics, Hayward, CA, 1996.
  * Pitman [2003] J. Pitman.  _Poisson-Kingman partitions_ , volume Volume 40 of _Lecture Notes–Monograph Series_ , pages 1–34.  Institute of Mathematical Statistics, Beachwood, OH, 2003.
  * Pitman [2006] J. Pitman.  _Combinatorial Stochastic Processes_ , volume 1875 of _Ecole d’Eté de Probabilités de Saint-Flour_.  Springer-Verlag Berlin Heidelberg, 2006.
  * Pitman and Racz [2015] J. Pitman and M. Racz.  Beta-gamma tail asymptotics.  _Electron. Commun. Probab._ , 20:1–7, 2015.
  * Revuz and Yor [1999] D. Revuz and M. Yor.  _Continuous martingales and Brownian motion_.  Springer Science & Business Media, 3rd edition, 1999.
  * Simon [1955] H. A. Simon.  On a class of skew distribution functions.  _Biometrika_ , 42(3-4):425–440, 1955.
  * Tricomi and Erdélyi [1951] F. G. Tricomi and A. Erdélyi.  The asymptotic expansion of a ratio of gamma functions.  _Pacific J. Math._ , 1(1):133–142, 1951.
  * Veitch and Roy [2015] V. Veitch and D. M. Roy.  The class of random graphs arising from exchangeable random measures.  12 2015.  URL http://arxiv.org/abs/1512.03099.
  * Yule [1925] G. U. Yule.  A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F.R.S.  _Philosophical Transactions of the Royal Society of London B: Biological Sciences_ , 213(402-410):21–87, 1925.  ISSN 0264-3960.

##  Appendix A Proofs

###  A.1 Proof of Theorem 2

###### Proof.

Let $G(\alpha,T)=((L_{1},L_{2}),(L_{3},L_{4}),\dotsc)$ be an
$(\alpha,T)$-graph, and let $k_{n}$ denote the number of vertices after $n$
edge ends have been drawn. For notational convenience, let
$D_{j}(n):=\deg_{j}(n)$ be the degree of the $j$th vertex at step $n$. Then
from the sequence of laws $P_{\alpha}(k;l_{1},\dotsc,l_{j})$ in (3), the
probability of a particular sequence is

$\displaystyle\mathbb{P}[G_{n/2}(\alpha,T)\mid
T=t]=\frac{1}{\Gamma(n-k_{n}\alpha)}\prod_{j=1}^{k_{n}}\frac{\Gamma(t_{j}-j\alpha)\Gamma(D_{j}(n)-\alpha)}{\Gamma(t_{j}-1-(j-1)\alpha+\delta_{1}(j))\Gamma(1-\alpha)}\;.$

Now let $H_{n}(\alpha,T)$ denote the first $n$ elements of the sequence
$H(\alpha,T)$, so that

$\displaystyle\mathbb{P}[H_{n/2}(\alpha,T),(\Psi_{j})_{2\leq j\leq k_{n}}\mid
T=t]=\prod_{i=2}^{k_{n}}\frac{\Gamma(t_{j}-j\alpha)\Psi_{j}^{D_{j}(n)-\alpha-1}(1-\Psi_{j})^{\bar{D}_{j-1}(n)-(j-1)\alpha-1}}{\Gamma(1-\alpha)\Gamma(t_{j}-1-(j-1)\alpha)}\;.$

Hence, by marginalizing $(\Psi_{j})_{2\leq j\leq k_{n}}$, it follows that

$\displaystyle\mathbb{P}[H_{n/2}(\alpha,T)\mid T=t]$
$\displaystyle=\int_{[0,1]^{k_{n}}}\mathbb{P}[H_{n/2}(\alpha,T),(\Psi_{j})_{2\leq
j\leq k_{n}}\mid T=t]\;d\Psi_{2}\dotsm d\Psi_{k_{n}}$
$\displaystyle=\mathbb{P}[G_{n/2}(\alpha,T)\mid T=t]\;.$

The equality is true for all $n\in\mathbb{N}_{+}$, and $t\in\mathbb{T}$,
implying that ${\mathbb{P}[G(\alpha,T)]=\mathbb{P}[H(\alpha,T)]}$. ∎

###  A.2 Proof of Proposition 5

The proof will make repeated use of the expectation of $W_{j,k}$ as
$k\to\infty$. Observe that

$\displaystyle-\log\mathbb{E}[W_{j,k}]$
$\displaystyle=\sum_{i=j+1}^{k}\log\biggl{(}1+\frac{1-\alpha}{t_{i}-1-(i-1)\alpha}\biggr{)}=\sum_{i=j+1}^{k}\frac{1-\alpha}{t_{i}-1-(i-1)\alpha}+O(i^{-2})$

By assumption in the linear regime, $t_{i}-1-(i-1)\alpha$ is well-approximated
by $(i-1)(\mu_{1}-\alpha)$ for $i$ large enough, resulting in a finite error
$C_{j,k}$ that converges as $k\to\infty$. Hence,

$\displaystyle-\log\mathbb{E}[W_{j,k}]$
$\displaystyle=C_{j,k}+\frac{1-\alpha}{\mu_{1}-\alpha}\sum_{i=j}^{k-1}i^{-1}+O(i^{-2})=C_{j,k}+\frac{1-\alpha}{\mu_{1}-\alpha}\log\biggl{(}\frac{k-1}{j}\biggr{)}+O(j^{-1})\;,$

and therefore for all $j>1$,

$\displaystyle\mathbb{E}[W_{j,k}]=A_{j}\biggl{(}\frac{j}{k-1}\biggr{)}^{\frac{1-\alpha}{\mu_{1}-\alpha}}\quad\text{as}\quad
k\to\infty\;.$ (43)

Clearly, this converges to zero for each $j$. Similarly, in the sub-linear
regime,

$\displaystyle-\log\mathbb{E}[W_{j,k}]$
$\displaystyle=C^{\prime}_{j,k}+\sum_{i=j}^{k-1}\frac{1-\alpha}{\mu_{\sigma}i^{1/\sigma}-i\alpha}+O(i^{-2})$
$\displaystyle=C^{\prime}_{j,k}+\frac{\sigma(1-\alpha)}{\alpha(1-\sigma)}\log\biggl{(}\frac{\mu_{\sigma}-\alpha(k-1)^{-\frac{1-\sigma}{\sigma}}}{\mu_{\sigma}-\alpha
j^{-\frac{1-\sigma}{\sigma}}}\biggr{)}+O(j^{-1})\;.$

Since $\frac{1-\sigma}{\sigma}>0$,

$\displaystyle\mathbb{E}[W_{j,k}]=A^{\prime}_{j}\biggl{(}1-\frac{\alpha}{\mu_{\sigma}j^{\frac{1-\sigma}{\sigma}}}\biggr{)}^{\frac{\sigma(1-\alpha)}{\alpha(1-\sigma)}}\biggl{(}1-\frac{\alpha}{\mu_{\sigma}(k-1)^{\frac{1-\sigma}{\sigma}}}\biggr{)}^{-\frac{\sigma(1-\alpha)}{\alpha(1-\sigma)}}\quad\text{as}\quad
k\to\infty\;.$ (44)

Clearly, this converges to something non-zero for each $j$.

###### Proof of Proposition 5.

Define $M_{j,k}:=W_{j,k}/\mathbb{E}[W_{j,k}]$. Since
${\mathbb{E}[M_{j,k+1}\mid M_{j,k}]=M_{j,k}}$ and $\mathbb{E}[M_{j,j+1}=1]$,
$M_{j,k}$ is a nonnegative martingale with mean 1 for $k>j$; it therefore
converges almost surely to a random variable $M_{j,\infty}$. Hence,

$\displaystyle
W_{j,\infty}:=\lim_{k\to\infty}W_{j,k}=M_{j,\infty}\lim_{k\to\infty}\mathbb{E}[W_{j,k}]\;.$

Simple calculations show that $\mathbb{E}[M^{2}_{j,k}]=1+O(k^{-1})$, and
therefore $M_{j,k}$ is bounded in $L_{2}$ and also in $L_{1}$. Hence,
$W_{j,\infty}$ exists if and only if $\lim_{k\to\infty}\mathbb{E}[W_{j,k}]$
exists. By (43) and (44), that is the case.

By Markov’s inequality, for any $\lambda>0$,

$\displaystyle\mathbb{P}[W_{j,k}\geq\lambda]\leq\frac{1}{\lambda}\mathbb{E}[W_{j,k}]\leq\begin{cases}O(k^{-\frac{1-\alpha}{\mu_{1}-\alpha}})\quad\text{for}\quad\sigma=1\\\
O(\lambda^{-1})\quad\text{for}\quad\sigma<1\end{cases}\;,$

indicating that $W_{j,\infty}=0$ in the linear case. On the other hand,

$\displaystyle\mathbb{P}[W_{j,k}\leq\lambda]$
$\displaystyle=\mathbb{P}[W_{j,k}^{-1}\geq\lambda^{-1}]\leq\lambda\mathbb{E}[W_{j,k}^{-1}]=\lambda\mathbb{E}[W_{j,k}]^{-1}\prod_{i=j+1}^{k}\frac{1-\frac{1}{t_{i}-i\alpha}}{1-\frac{1}{t_{i}-1-(i-1)\alpha}}$
$\displaystyle\leq\begin{cases}O(k^{\frac{1-\alpha}{\mu_{1}-\alpha}})\quad\text{for}\quad\sigma=1\\\
O(\lambda)\quad\text{for}\quad\sigma<1\end{cases}\;,$

indicating that $W_{j,\infty}>0$ in the sub-linear case. ∎

###  A.3 Proofs for Section 3.2

The proof of Theorem 6 uses martingale methods adapted and extended from those
used by Móri [30]. See also [24, 19]. For notational convenience, we let
$D_{j,n}=D_{j}(n)$. Fix $r\in\mathbb{N}_{+}$ and $p=(p_{1},p_{2},\dotsc)$ such
that $p_{j}>-(1-\alpha)$ for each $1\leq j\leq r$, and $p_{j}=0$ for $j>r$.
Let $\bar{p}_{j}=\sum_{i=1}^{j}p_{i}$, with $\bar{p}_{0}=0$ and
$\bar{p}_{j}=\bar{p}_{r}:=\bar{p}$ for $j>r$. For fixed $t\in\mathbb{T}$,
define

$\displaystyle Z_{n}(p,t):=$ (45)
$\displaystyle\frac{\Gamma(n-k_{n}\alpha)}{\Gamma(n-k_{n}\alpha+\bar{p}_{k_{n}})}\prod_{j=1}^{r}\frac{\Gamma(D_{j,n}-\alpha+p_{j})}{\Gamma(D_{j,n}-\alpha)}\prod_{k=r+1}^{k_{n}}\frac{\Gamma(t_{k}-1-(j-1)\alpha)\Gamma(t_{k}-j\alpha+\bar{p}_{k})}{\Gamma(t_{k}-1-(k-1)\alpha+\bar{p}_{k})\Gamma(t_{k}-k\alpha)}\;.$

The asymptotic behavior of $Z_{n}(p,t)$ is described by the following two
lemmas, from which Theorem 6 follows.

######  Lemma 20.

Let $Z_{n}(p,t)$ be as in (45), with $p_{j}>-(1-\alpha)$ for each $j\geq 1$.
Then $Z_{n}(p,t)$ is a nonnegative martingale with respect to
$(\mathcal{F}_{n})_{n\geq T_{r}}$, the filtration generated by the
$(\alpha,t)$ sampling process, for $n\geq T_{r}$, and therefore

$\displaystyle Z_{n}(p,t)\xrightarrow[n\to\infty]{\text{\small
a.s.}}\xi_{1}^{p_{1}}\dotsm\xi_{r}^{p_{r}}\;.$

Furthermore, if $p_{j}>-(1-\alpha)/2$ for each $j\geq 1$, then $Z_{n}(p,t)$
converges in $L_{2}$ and therefore also in $L_{1}$.

###### Proof.

$Z_{n}(p,t)$ is nonnegative by construction. Furthermore,

$\displaystyle\mathbb{E}\biggl{[}\frac{\Gamma(n+1-k_{n+1}\alpha)}{\Gamma(n+1-k_{n+1}\alpha+\bar{p}_{k_{n+1}})}\prod_{j=1}^{k_{n+1}}\frac{\Gamma(D_{j,n+1}-\alpha+p_{j})}{\Gamma(D_{j,n+1}-\alpha)}\mid\mathcal{F}_{n}\biggr{]}:=\mathbb{E}[R_{n+1}(p)\mid\mathcal{F}_{n}]$
$\displaystyle\;=R_{n}(p)\biggl{[}\mathds{1}\\{t_{k_{n}+1}>n+1\\}+\frac{\Gamma(n-k_{n}\alpha+\bar{p}_{k_{n}})\Gamma(n+1-(k_{n}+1)\alpha)}{\Gamma(n+1-(k_{n}+1)\alpha+\bar{p}_{k_{n}+1})\Gamma(n-k_{n}\alpha)}\mathds{1}\\{t_{k_{n}+1}=n+1\\}\biggr{]}\;,$

from which it follows that
$\mathbb{E}[Z_{n+1}(p,t)\mid\mathcal{F}_{n}]=Z_{n}(p,t)$ for all $n\geq
T_{r}$. Furthermore, $\mathbb{E}[Z_{n}(p,t)]<\infty$ and does not depend on
$n$. To bound $Z_{n}(p,t)$ in $L_{2}$, observe that by the properties of the
gamma function [40],

$\displaystyle
c_{\bar{p}}:=\frac{\Gamma(n-k_{n}\alpha)}{\Gamma(n-k_{n}\alpha+\bar{p}_{k_{n}})}=n^{-\bar{p}}(1+O(n^{-1}))\quad\text{as}\quad
n\to\infty\;,$ (46)

which implies that $c_{\bar{p}}^{2}/c_{2\bar{p}}\to 1$. Using the fact that
$x\mapsto\Gamma(x+y)/\Gamma(x)$ is increasing in $x$ for $y\geq 0$, it follows
that $Z_{n}(p,t)^{2}\leq Z_{n}(2p,t)$ (see [24, Section 8.7] for a similar
argument). Hence,
${\mathbb{E}[Z_{n}(p,t)^{2}]\leq\mathbb{E}[Z_{n}(2p,t)]<\infty}$ for
$p_{j}>-(1-\alpha)/2$. ∎

######  Lemma 21.

Let $Z_{n}(p,t)$ be as in (45), with $p_{j}>-(1-\alpha)$ for each $j\geq 1$.
Then there exists a constant $M_{\bar{p}}(t)$ such that

$\displaystyle
Z_{n}(p,t)=M_{\bar{p}}(t)n^{-\bar{p}/\gamma}\prod_{j=1}^{r}D_{j,n}^{p_{j}}(1+O(n^{-1}))\quad\text{as}\quad
n\to\infty\;.$

###### Proof.

The properties of the gamma function show that for each $j\leq r$,

$\displaystyle\frac{\Gamma(D_{j,n}-\alpha+p_{j})}{\Gamma(D_{j,n})}=D_{j,n}^{p_{j}}(1+O(n^{-1}))\quad\text{as}\quad
n\to\infty\;.$

Hence, it suffices to examine the behavior of the product

$\displaystyle M_{n}(p,t)$
$\displaystyle:=\frac{\Gamma(n-k_{n}\alpha)}{\Gamma(n-k_{n}\alpha+\bar{p}_{k_{n}})}\frac{\Gamma(1-\alpha+p_{1})}{\Gamma(1-\alpha)}\prod_{j=2}^{k_{n}}\frac{\Gamma(t_{j}-1-(j-1)\alpha)\Gamma(t_{j}-j\alpha+\bar{p}_{j})}{\Gamma(t_{j}-1-(j-1)\alpha+\bar{p}_{j})\Gamma(t_{j}-j\alpha)}$
$\displaystyle=\prod_{m=1}^{n-1}\frac{m-k_{m}\alpha}{m-k_{m}\alpha+\bar{p}_{k_{m}}\mathds{1}\\{t_{k_{m}+1}\neq
m+1\\}}$
$\displaystyle=\biggl{(}\prod_{m=1}^{n-1}\frac{m-k_{m}\alpha}{m-k_{m}\alpha+\bar{p}_{k_{m}}}\biggr{)}\biggl{(}\prod_{j=1}^{k_{n}-1}\frac{t_{j+1}-1-j\alpha+\bar{p}_{j}}{t_{j+1}-1-j\alpha}\biggr{)}:=M_{n}^{(1)}(p,t)M_{n}^{(2)}(p,t)\;.$

Taking the logarithm, the first term is

$\displaystyle\ln M_{n}^{(1)}(p,t)$
$\displaystyle=\sum_{m=1}^{n-1}\ln(m-k_{m}\alpha)-\ln(m-k_{m}\alpha+\bar{p}_{k_{m}})$
$\displaystyle=\sum_{m=1}^{n-1}\ln\bigl{(}1+\frac{\bar{p}_{k_{m}}}{m-k_{m}\alpha}\bigr{)}=C_{1}-\sum_{m=1}^{n-1}\frac{\bar{p}_{k_{m}}}{m-k_{m}\alpha}+O(m^{-2})\;,$

where $C_{1}$ captures the error in the approximation for terms where
$\bar{p}_{k_{m}}>m-k_{m}\alpha$, which is finite because $p_{j}=0$ for $j>r$.
By assumption when $\mu<\infty$, for any $\epsilon>0$ there exists some finite
$K$ such that for all $j\geq K$, $\lvert k_{m}-m/\mu\rvert\leq\epsilon$.
Therefore, absorbing the additional error into $C_{1}$,

$\displaystyle\ln M_{n}^{(1)}(p,t)$
$\displaystyle=C_{1}-\sum_{m=1}^{n-1}\frac{\bar{p}}{m(1-\alpha/\mu)}+O(m^{-2})=C_{1}-\frac{\bar{p}\mu}{\mu-\alpha}\ln
n+O(n^{-1})\;.$

In the sub-linear regime ($\mu=\infty$), the second term is $-\bar{p}\ln n$.
Similarly, for the second term of $M_{n}(p,t)$,

$\displaystyle\ln M_{n}^{(2)}(p,t)$
$\displaystyle=\sum_{j=1}^{k_{n}-1}\ln\bigl{(}1+\frac{\bar{p}_{j}}{t_{j+1}-1-j\alpha}\bigr{)}=C_{2}+\sum_{j=1}^{k_{n}-1}\frac{\bar{p}_{j}}{t_{j+1}-1-j\alpha}+O(j^{-2})$
$\displaystyle=C_{2}+\sum_{j=1}^{k_{n}-1}\frac{\bar{p}}{j(\mu-\alpha)}+O(j^{-2})=C_{2}+\frac{\bar{p}_{j}}{\mu-\alpha}\ln
n+O(n^{-1})\;.$

In the sub-linear regime, the second term is also $O(n^{-1})$. Hence, letting
$M_{\bar{p}}(t)=e^{C_{1}+C_{2}}$, the result follows. ∎

###### Proof of Theorem 6.

Equations (18) and (19) follow from Lemmas 20 and 21. To establish (20), let
$p\setminus p_{j}$ be $p$ with the $j$th element set to zero, observe that

$\displaystyle\mathbb{E}[\zeta_{1}^{p_{1}}\dotsm\zeta_{r}^{p_{r}}]=\mathbb{E}[Z_{t_{r}}(p,t)]$
$\displaystyle=\mathbb{E}[Z_{t_{r}-1}(p\setminus
p_{r},t)]\frac{\Gamma(1-\alpha+p_{r})\Gamma(t_{r}-r\alpha)\Gamma(t_{r}-1-(r-1)\alpha+\bar{p}_{r-1})}{\Gamma(1-\alpha)\Gamma(t_{r}-1-(r-1)\alpha)\Gamma(t_{r}-r\alpha+\bar{p}_{r})}$
$\displaystyle=\prod_{j=2}^{r}\frac{\Gamma(1-\alpha+p_{j})\Gamma(t_{j}-j\alpha)\Gamma(t_{j}-1-(j-1)\alpha+\bar{p}_{j-1})}{\Gamma(1-\alpha)\Gamma(t_{j}-1-(j-1)\alpha)\Gamma(t_{j}-j\alpha+\bar{p}_{j})}=\prod_{j=2}^{r}\mathbb{E}[\Psi_{j}^{p_{j}}(1-\Psi_{j})^{\bar{p}_{j-1}}]\;.$

∎

###  A.4 Proofs for Section 3.4

In the sub-linear regime, the degree distribution follows from results on
exchangeable random partitions and can be read from [36, Lemma 3.11]. The
proof of Theorem 8 in the linear case relies on the following lemma, which
says that for large enough $j$, $W_{j,k}$ is well-approximated by
$(j/k)^{1-1/\gamma}$ for all $k>j$, where $\gamma=(\mu-\alpha)/(\mu-1)$.

######  Lemma 22.

Let $G$ be a random $(\alpha,T)$ graph for some $\alpha\in(-\infty,1)$ and
$T\in\mathbb{T}$. Assume that $\text{Var}(\Delta_{j})<V^{2}_{\Delta}$ for all
$j\in\mathbb{N}_{+}$, that $\mathbb{E}[\Delta_{j}]=\mu$ for all $j>1$, and
that $\lvert\text{Cov}(\Delta_{i},\Delta_{j})\rvert=C^{2}_{\Delta}\lvert
i-j\rvert^{-\ell_{\Delta}}$ for all $i,j>1$, some $C^{2}_{\Delta}\geq 0$, and
some $\ell_{\Delta}>0$. Let $W_{j,k}$ be as in (6). Then for every
$\lambda\geq 0$, there exists some $K<\infty$ that does not depend on $n$ such
that for all $k\geq K$,

$\displaystyle\mathbb{P}\left[\sup_{k+1\leq m\leq n}\left\lvert
W_{j,m}\left(\frac{m}{k}\right)^{1-1/\gamma}-1\right\rvert\leq\lambda\right]\geq
1-\lambda\;.$

###### Proof.

Condition on $T=t$ and define for fixed $j$

$\displaystyle
M_{j,k}:=W_{j,k}\prod_{j=k+1}^{k}\frac{T_{j}-j\alpha}{T_{j}-1-(j-1)\alpha}\;,$

which is a martingale with mean 1 for $k\geq j+1$. By Doob’s maximal
inequality [e.g. 38, Chapter II], for any $c>0$ and $j\geq 1$,

$\displaystyle\mathbb{P}\bigl{[}\sup_{j+1\leq m\leq k}\lvert
M_{j,m}-1\rvert\geq c\mid
T\bigr{]}\leq\frac{1}{c^{2}}\mathbb{E}[(M_{j,k}-1)^{2}\mid T]\;.$ (47)

The right-hand side is

$\displaystyle\frac{1}{c^{2}}\mathbb{E}[(M_{j,k}-1)^{2}\mid T]$
$\displaystyle=\frac{1}{c^{2}}\biggl{(}\frac{\mathbb{E}[W_{j,k}^{2}\mid
T]}{\mathbb{E}[W_{j,k}\mid
T]^{2}}-1\biggr{)}\leq\frac{1}{c^{2}}\frac{1}{1-\alpha}\frac{1}{j}+O(j^{-2})\;.$
(48)

The product in $M_{j,k}$ is

$\displaystyle\exp\biggl{(}\sum_{i=j+1}^{k}\log\biggl{(}1+\frac{1-\alpha}{T_{i}-1-(i-1)\alpha}\biggr{)}\biggr{)}=\exp\biggl{(}\sum_{i=j+1}^{k}\frac{1-\alpha}{T_{i}-1-(i-1)\alpha}+O(i^{-2})\biggr{)}$
$\displaystyle=\biggl{(}\frac{k}{j}\biggr{)}^{1-1/\gamma}e^{-\epsilon_{j,k}}\bigl{(}1+O(j^{-1})\bigr{)}\quad\text{where}\quad\epsilon_{j,k}:=\sum_{i=j+1}^{k}\frac{(1-\alpha)}{(i-1)(\mu-\alpha)}-\frac{(1-\alpha)}{T_{i}-1-(i-1)\alpha}\;.$

Define $\bar{\epsilon}_{j,k}$ to be sum of the absolute values of the terms in
$\epsilon_{j,k}$. Because it is a running sum of nonnegative terms,
$\bar{\epsilon}_{j,k}$ is a nonnegative submartingale. Therefore, another
application of Doob’s maximal inequality followed by Jensen’s inequality shows
that

$\displaystyle\mathbb{P}[\sup_{j+1\leq m\leq k}\lvert\epsilon_{j,m}\rvert\geq
c_{\epsilon}]$ $\displaystyle\leq\mathbb{P}[\sup_{j+1\leq m\leq
k}\bar{\epsilon}_{j,m}\geq c_{\epsilon}]$
$\displaystyle\leq\frac{\mathbb{E}[\bar{\epsilon}_{j,k}]}{c_{\epsilon}}\leq\frac{1}{c_{\epsilon}(\mu-\alpha)}\sum_{i=j+1}^{k}\frac{1}{j^{2}}\mathbb{E}[\lvert
T_{j}-(j-1)\mu-1\rvert]$
$\displaystyle\leq\frac{1}{c_{\epsilon}(\mu-\alpha)}\sum_{i=j+1}^{k}\frac{1}{j^{2}}\biggl{(}\text{Var}\biggl{(}\sum_{i=2}^{j}(\Delta_{i}-\mu)\biggr{)}\biggr{)}^{1/2}$
$\displaystyle\leq\frac{1}{c_{\epsilon}(\mu-\alpha)}\sum_{i=j+1}^{k}\frac{1}{j^{2}}(V_{\Delta}^{2}(j+C_{\Delta}^{2}j^{2-\ell_{\Delta}}))^{1/2}$
$\displaystyle\leq\frac{\sqrt{V^{2}_{\Delta}+C^{2}_{\Delta}}}{c_{\epsilon}(\mu-\alpha)}\biggl{(}\frac{2/\ell_{+}}{j^{\ell_{+}/2}}-\frac{2/\ell_{+}}{k^{\ell_{+}/2}}+O(j^{-(1+\ell_{+}/2)})\biggr{)}\;,$

where $\ell_{+}:=\min\\{\ell_{\Delta},1\\}$. Let $A_{j,k}^{\delta}$ be the
event that $\lvert\epsilon_{j,m}\rvert<j^{-\delta}$ for each $j+1\leq m\leq k$
and some fixed $0<\delta<\ell_{+}/2$. Then

$\displaystyle\mathbb{P}[A_{j,k}^{\delta}]$
$\displaystyle=\mathbb{P}[\sup_{j+1\leq m\leq
k}\lvert\epsilon_{j,m}\rvert<j^{-\delta}]\geq\biggl{(}1-\frac{2\sqrt{V^{2}_{\Delta}+C^{2}_{\Delta}}}{\ell_{+}(\mu-\alpha)}\bigl{(}\frac{1}{j^{\ell_{+}/2-\delta}}+O(j^{-(1+\ell_{+}/2-\delta)})\bigr{)}\biggr{)}\;.$

Hence, the probability of $A_{j,k}^{\delta}\to 1$ as $j\to\infty$. Now, taking
expectation with respect to $T$ of the left-hand side of (47) yields

$\displaystyle\mathbb{E}_{T}\bigl{[}\mathbb{P}\bigl{[}\sup_{k+1\leq m\leq
k}\lvert
W_{j,k}\bigl{(}\frac{m}{j}\bigr{)}^{1-1/\gamma}(1+\epsilon_{j,m}+O(j^{-1}))-1\rvert\geq
c\mid T\bigr{]}\bigr{]}$ $\displaystyle\quad=\mathbb{P}\bigl{[}\sup_{j+1\leq
m\leq k}\lvert W_{j,k}\bigl{(}\frac{m}{j}\bigr{)}^{1-1/\gamma}-1\rvert\geq
c\bigr{]}\dotsb$
$\displaystyle\quad\quad\times\mathbb{E}_{T}\left[\mathds{1}_{A^{\delta}_{j,k}}\frac{\mathbb{P}\bigl{[}\sup_{j+1\leq
m\leq k}\lvert
W_{j,k}\bigl{(}\frac{m}{j}\bigr{)}^{1-1/\gamma}(1+\epsilon_{j,m}+O(j^{-1}))-1\rvert\geq
c\mid T\bigr{]}}{\mathbb{P}\bigl{[}\sup_{j+1\leq m\leq k}\lvert
W_{j,k}\bigl{(}\frac{m}{j}\bigr{)}^{1-1/\gamma}-1\rvert\geq
c\bigr{]}}\right]\dotsb$
$\displaystyle\quad\quad+\mathbb{E}_{T}\bigl{[}(1-\mathds{1}_{A^{\delta}_{j,k}})\mathbb{P}\bigl{[}\sup_{j+1\leq
m\leq k}\lvert
W_{j,k}\bigl{(}\frac{m}{j}\bigr{)}^{1-1/\gamma}(1+\epsilon_{j,m}+O(j^{-1}))-1\rvert\geq
c\mid T\bigr{]}\bigr{]}\;.$

Observe that as $j\to\infty$, the last term converges to zero by monotone
convergence, while the ratio inside the expectation converges to one on sets
where $A_{j,k}^{\delta}$ obtains, which have asymptotic measure equal to one.
The result follows by monotone convergence and comparison with (48). ∎

The following lemma gives an estimate based on the beta-gamma algebra, and
says that for large enough $j$, $\Psi_{j}$ can be approximated by
$\mathcal{G}_{1-\alpha}/((j-1)\mu-1-j\alpha)$.

######  Lemma 23.

For $j<k$, let $\Psi_{j}$ and $\Psi_{k}$ be independent beta random variables
as in (5), and let $\mathcal{G}^{(j)}$ and $\mathcal{G}^{(k)}$ be independent
$\text{\rm Gamma}(1-\alpha,1)$ random variables as in (9). Then there exists
some $J<\infty$ such that for every $j\geq J$ and $\lambda>0$,

$\displaystyle\mathbb{P}\left[\sup_{j\leq k\leq
n}\left\lvert\Psi_{j}\Psi_{k}-\frac{\mathcal{G}^{(j)}\mathcal{G}^{(k)}}{(j(\mu-\alpha)-(\mu-1))(k(\mu-\alpha)-(\mu-1))}\right\rvert<\lambda\right]\geq
1-\lambda\;.$

###### Proof.

Denote the quantity of interest as $\epsilon^{\Psi}_{j,k}$, and let
$\Sigma_{j}:=\sum_{i=1}^{j}\mathcal{G}^{(i)}+\sum_{i=1}^{j-1}\mathcal{G}_{\Delta_{i+1}-1}$.
Then using the distributional identity in (9),

$\displaystyle\lvert\epsilon^{\Psi}_{j,k}\rvert=\biggl{\lvert}\Psi_{j}\Psi_{k}\frac{(j(\mu-\alpha)-(\mu-1))(k(\mu-\alpha)-(\mu-1))-\Sigma_{j}\Sigma_{k}}{(j(\mu-\alpha)-(\mu-1))(k(\mu-\alpha)-(\mu-1))}\biggr{\rvert}$
$\displaystyle=\frac{\Psi_{j}\Psi_{k}}{(j(\mu-\alpha)-(\mu-1))(k(\mu-\alpha)-(\mu-1))}\dotsb$
$\displaystyle\quad\times\biggl{\lvert}\sum_{i=1}^{j}\sum_{m=1}^{k}\bigl{(}\mathcal{G}^{(i)}\mathcal{G}^{(m)}-(1-\alpha)^{2}\bigr{)}+\sum_{i=1}^{j}\sum_{m=1}^{k-1}\bigl{(}\mathcal{G}^{(i)}\mathcal{G}_{\Delta_{m+1}-1}-(1-\alpha)(\mu-1)\bigr{)}\biggr{.}\dotsb$
$\displaystyle\quad\biggl{.}+\sum_{i=1}^{j-1}\sum_{m=1}^{k}\bigl{(}\mathcal{G}_{\Delta_{j+1}-1}\mathcal{G}^{(m)}-(1-\alpha)(\mu-1)\bigr{)}+\sum_{i=1}^{j-1}\sum_{m=1}^{k-1}\bigl{(}\mathcal{G}_{\Delta_{j+1}-1}\mathcal{G}_{\Delta_{m+1}-1}-(\mu-1)^{2}\bigr{)}\biggr{\rvert}\;.$

Denote by $\bar{\epsilon}^{\Psi}_{j,k}$ the term-wise absolute value of
$\epsilon^{\Psi}_{j,k}$. As a cumulative sum of nonnegative terms,
$\bar{\epsilon}^{\Psi}_{j,k}$ is a nonnegative submartingale for $k>j$, and
hence by Doob’s maximal inequality, for any $c>0$,

$\displaystyle\mathbb{P}[\sup_{j\leq k\leq
n}\lvert\epsilon^{\Psi}_{j,k}\rvert\geq c]$
$\displaystyle\leq\mathbb{P}[\sup_{j\leq k\leq
n}\bar{\epsilon}^{\Psi}_{j,k}\geq
c]\leq\frac{1}{c}\mathbb{E}[\bar{\epsilon}^{\Psi}_{j,n}]\;.$

The independence properties of the beta and gamma random variables, along with
simple but tedious calculations yields

$\displaystyle\mathbb{E}[\bar{\epsilon}^{\Psi}_{j,n}]\leq\frac{C(\alpha,\mu,V^{2}_{\Delta})+O(j^{-1})}{(j(\mu-\alpha)-(\mu-1))(n(\mu-\alpha)-(\mu-1))}\;,$

where $C(\alpha,\mu,V^{2}_{\Delta})$ is a constant that depends only on the
model parameters. The result follows. ∎

Finally, the proof of Theorem 8 requires that for large enough $j$, the error
term

$\displaystyle\epsilon^{r}_{j,k}:=\sum_{r=j}^{k}\frac{1}{2r^{2-2/\gamma}}(\Delta_{r+1}-\mu)$

is small with high probability, which is established by the following lemma.

######  Lemma 24.

For any $c>0$,

$\displaystyle\mathbb{P}[\sup_{j\leq k\leq
n}\lvert\epsilon^{r}_{j,k}\rvert<c]\geq
1-\frac{V_{\Delta}}{c}\frac{1}{j^{1-2/\gamma}}(1+O(j^{-2-2/\gamma}))\;.$

###### Proof.

Denote by $\bar{\epsilon}^{r}_{j,k}$ the term-wise absolute value of
$\epsilon^{r}_{j,k}$. $\bar{\epsilon}^{r}_{j,k}$ is a nonnegative
submartingale for $k>j$, and an application of Doob’s maximal inequality
yields the result. ∎

###### Proof of Theorem 8.

Let $U_{0}$ be a $\text{\rm Uniform}[0,1]$ random variable, and define
$j_{0}=\lceil U_{0}k_{n}\rceil$ to be a vertex selected uniformly at random
from $G_{n}$, which has $k_{n}$ vertices. For simplicity, assume that either
all $T_{j}$ are even for $j>1$ (which is the case for graphs that are a.s.
connected for all $n$), or that $T_{j}$ has equal probability of being odd or
even for all $j>1$. (These assumptions are not necessary, but greatly simplify
notation. More general assumptions may be accommodated.) Conditioned on
$(\Psi_{j})_{j>1}$, the expected number of directed edges from vertex $j_{0}$
to any vertex $j\in\mathbb{N}_{+}$ is

$\displaystyle\mathbb{E}[N_{j_{0}\to j,n}]$ $\displaystyle=\sum_{r=j_{0}\vee
j}^{k_{n}}P_{j_{0}\to j,r}=\sum_{r=j_{0}\vee
j}^{k_{n}}\Psi_{j_{0}}W_{j_{0},r}\Psi_{j}W_{j,r}(\Delta_{r+1}/2-1)$ (49)
$\displaystyle\quad\quad+\mathds{1}\\{j_{0}\geq j,T_{j_{0}}\text{
odd}\\}\Psi_{j}W_{j,j_{0}}+\mathds{1}\\{j_{0}<j,T_{j}\text{
even}\\}\Psi_{j_{0}}W_{j_{0},j-1}\;.$

Define

$\displaystyle\hat{P}_{j_{0}\to
j,r}:=\frac{\mathcal{G}^{(j_{0})}\mathcal{G}^{(j)}(\mu/2-1)}{j_{0}j(\mu-\alpha)^{2}}\biggl{(}\frac{j_{0}}{r}\frac{j}{r}\biggr{)}^{1-1/\gamma}\;.$

By Lemmas 22, 23 and 24, for $n$ large enough, with probability at least
$1-2\lambda$,

$\displaystyle(1-\lambda)\sum_{r=j_{0}\vee j}^{k_{n}}\hat{P}_{j_{0}\to
j,r}\leq\sum_{r=j_{0}\vee j}^{k_{n}}P_{j_{0}\to
j,r}\leq(1+\lambda)\sum_{r=j_{0}\vee j}^{k_{n}}\hat{P}_{j_{0}\to j,r}\;.$

Similar approximations hold for the final two terms of (49). Let
$j_{+}=j_{0}\vee j$. Now summing over $r$ yields

$\displaystyle\mathbb{E}[\hat{N}_{j_{0}\to
j,n}]=\frac{\mathcal{G}^{(j_{0})}\mathcal{G}^{(j)}(\mu/2-1)}{(\mu-\alpha)^{2}(1-2/\gamma)}\frac{1}{k_{n}}\biggl{(}\frac{j_{0}}{k_{n}}\frac{j}{k_{n}}\biggr{)}^{-1/\gamma}\biggl{(}\biggl{(}\frac{k_{n}}{j_{+}}\biggr{)}^{1-2/\gamma}-1\biggr{)}\biggl{(}1+O(j_{+}^{-1})\biggr{)}\;.$

Defining for $u\in(0,1)$,
${\mathbb{E}[\hat{N}_{U_{0},n}(u)]:=\sum_{j=1}^{\lceil
k_{n}u\rceil}\mathbb{E}[\hat{N}_{j_{0}\to j,n}]}$, it follows from standard
results on convergence to Poisson processes [15] that $\hat{N}_{U_{0},n}(u)$
converges weakly to a Poisson point process with intensity

$\displaystyle\overrightarrow{\lambda}(u_{0},u)=\frac{\mathcal{G}_{1-\alpha}}{\mu-\alpha}\biggl{(}\frac{(1-\alpha)(\mu/2-1)}{(\mu-\alpha)(1-2/\gamma)}(u_{0}u)^{-1/\gamma}\frac{1-u_{+}^{1-2/\gamma}}{u_{+}^{1-2/\gamma}}+\frac{1}{2}u_{-}^{-1/\gamma}u_{+}^{-(1-1/\gamma)}\biggr{)}\;,$
(50)

where $u_{+}=u_{0}\vee u$ and $u_{-}=u_{0}\wedge u$. Similarly, for incoming
edges to $j_{0}$, the symmetry of the sampling process yields
$\overleftarrow{\lambda}(u_{0},u)=\overrightarrow{\lambda}(u_{0},u)$.

It follows that the degree of a randomly sampled vertex is a Poisson random
variable with mean parameter

$\displaystyle\Lambda(\mathcal{G}_{1-\alpha},U_{0})=\int_{0}^{1}\overleftarrow{\lambda}(U_{0},u)+\overrightarrow{\lambda}(U_{0},u)du=\mathcal{G}_{1-\alpha}(U_{0}^{-1/\gamma}-1)\;.$
(51)

Hence, by the conjugacy relationship between the Poisson and Gamma
distributions, the probability that the degree of a randomly sampled vertex,
conditioned on $U_{0}$, is equal to $d+1$ is

$\displaystyle\mathbb{P}[D=d+1\mid U_{0}]$
$\displaystyle=\mathbb{E}[e^{-\Lambda(\mathcal{G}_{1-\alpha},U_{0})}\Lambda(\mathcal{G}_{1-\alpha},U_{0})^{d}\mid
U_{0}]/d!$
$\displaystyle=\frac{\Gamma(d+1-\alpha)}{\Gamma(d+1)\Gamma(1-\alpha)}(1-U_{0}^{1/\gamma})^{d}U_{0}^{(1-\alpha)/\gamma}\;.$

Finally, taking the expectation with respect to the uniform random variable
$U_{0}$,

$\displaystyle\mathbb{P}[D=d+1]$
$\displaystyle=\frac{\Gamma(d+1-\alpha)}{\Gamma(d+1)\Gamma(1-\alpha)}\int_{0}^{1}(1-u^{1/\gamma})^{d}u^{(1-\alpha)/\gamma}du$
$\displaystyle=\frac{\Gamma(d+1-\alpha)}{\Gamma(d+1)\Gamma(1-\alpha)}\gamma\frac{\Gamma(d+1)\Gamma(1-\alpha+\gamma)}{\Gamma(d+1+1-\alpha+\gamma)}$
$\displaystyle=\gamma\frac{\Gamma(d+1-\alpha)\Gamma(1-\alpha+\gamma)}{\Gamma(d+1+1-\alpha+\gamma)\Gamma(1-\alpha)}\;,$

which is the stated result. Corollary 9 follows by checking moments. For
$\sigma=1$, Corollary 10 follows from (51) by observing that
$U_{0}^{1/\gamma}$ is distributed as $\text{\rm Beta}(\gamma,1)$; for
$\sigma\in(0,1)$, it follows from a similar integral identity. ∎

###  A.5 Proofs for Section 4

###### Proof of Proposition 11.

Let $\bar{m}:=2m-1$ and $\bar{\alpha}:=2m-\alpha$. When ${t_{j}=2m(j-1)+1}$,
(45) can be manipulated into the form

$\displaystyle Z_{n}(p,t)$
$\displaystyle=\frac{\Gamma(n-k_{n}\alpha)\Gamma(k_{n}\bar{\alpha}-\bar{m}+\bar{p})}{\Gamma(n-k_{n}\alpha+\bar{p})\Gamma(k_{n}\bar{\alpha}-\bar{m})}\prod_{i=1}^{\bar{m}}\frac{\Gamma(k_{n}-i/\bar{\alpha})\Gamma(r+1+(\bar{p}-i)/\bar{\alpha})}{\Gamma(k_{n}+(\bar{p}-i)/\bar{\alpha})\Gamma(r+1-i/\bar{\alpha})}\dotsm$
$\displaystyle\quad\quad\times\frac{\Gamma(r\bar{\alpha})}{\Gamma(r\bar{\alpha}+\bar{p})}\prod_{j=1}^{r}\frac{\Gamma(D_{j,n}-\alpha+p_{j})}{\Gamma(D_{j,n}-\alpha)}$
$\displaystyle=X_{n}(p,t)\frac{\Gamma(r\bar{\alpha})}{\Gamma(r\bar{\alpha}+\bar{p})}\prod_{i=1}^{\bar{m}}\frac{\Gamma(r+1+\frac{\bar{p}-i}{\bar{\alpha}})}{\Gamma(r+1-\frac{i}{\bar{\alpha}})}\;,$

where

$\displaystyle
X_{n}(p,t):=\biggl{(}\frac{n}{2m}\biggr{)}^{-\bar{p}\frac{\bar{m}}{\bar{\alpha}}}\prod_{j=1}^{r}D_{j,n}^{p_{j}}(1+O(n^{-1}))\;.$

Therefore, algebraic manipulations of $Z_{n}(p,t)$ show that for large $n$:

$\displaystyle
Z_{n}(p,t)=X_{n}(p,t)\mathbb{E}[\prod_{i=1}^{\bar{m}}\mathcal{G}_{r+1-\frac{i}{\bar{\alpha}}}^{\bar{p}/\bar{\alpha}}]/\mathbb{E}[\mathcal{G}_{r\bar{\alpha}}^{\bar{p}}]$
(52) $\displaystyle
Z_{n}(p,t)=X_{n}(p,t)\mathbb{E}[\prod_{i=1}^{\bar{m}}\mathcal{G}_{1-\frac{i}{\bar{\alpha}}}^{\bar{p}/\bar{\alpha}}]/\mathbb{E}[\mathcal{G}_{r\bar{\alpha}}^{\bar{p}}\prod_{j=1}^{r}\mathcal{B}^{\bar{p}}_{j\bar{\alpha}-\bar{m},\bar{m}}]$
(53) $\displaystyle
Z_{n}(p,t)=X_{n}(p,t)\mathbb{E}[\prod_{i=1}^{\bar{m}}\mathcal{G}_{1-\frac{i}{\bar{\alpha}}}^{\bar{p}/\bar{\alpha}}]/\mathbb{E}[\mathcal{G}_{r\bar{\alpha}-\bar{m}}^{\bar{p}}\prod_{j=1}^{r-1}\mathcal{B}^{\bar{p}}_{j\bar{\alpha}-\bar{m},\bar{m}}]$
(54) $\displaystyle
Z_{n}(p,t)=X_{n}(p,t)\mathbb{E}[\prod_{i=1}^{\bar{m}}\mathcal{G}_{1-\frac{i}{\bar{\alpha}}}^{\bar{p}/\bar{\alpha}}]\mathbb{E}[\prod_{j=2}^{r}\mathcal{B}^{\bar{p}}_{(j-1)\bar{\alpha},1-\alpha}]/\mathbb{E}[\mathcal{G}_{1-\alpha}^{\bar{p}}]\;.$
(55)

On the other hand, Lemma 20 establishes that $Z_{n}(p,t)$ converges almost
surely to the product of random variables
$\xi_{1}^{p_{1}}\dotsm\xi_{r}^{p_{r}}$. Now, letting $p\setminus p_{j}$ denote
$p$ with the $j$th element set to zero,

$\displaystyle\mathbb{E}[\xi_{1}^{p_{1}}\dotsm\xi_{r}^{p_{r}}]=\mathbb{E}[\lim_{n\to\infty}Z_{n}(p,t)]=\mathbb{E}[Z_{t_{r}}(p,t)]$
$\displaystyle=\mathbb{E}[Z_{t_{r}-1}(p\setminus
p_{r},t)]\frac{\Gamma(1-\alpha+\bar{p})\Gamma(r\bar{\alpha}-\bar{m})\Gamma((r-1)\bar{\alpha}+\bar{p}_{r-1})}{\Gamma(1-\alpha)\Gamma(r\bar{\alpha}-\bar{m}+\bar{p}_{r})\Gamma((r-1)\bar{\alpha})}$
$\displaystyle=\prod_{j=2}^{r}\frac{\Gamma(1-\alpha+p_{j})\Gamma(j\bar{\alpha}-\bar{m})\Gamma((j-1)\bar{\alpha}+\bar{p}_{j-1})}{\Gamma(1-\alpha)\Gamma((j-1)\bar{\alpha})\Gamma(j\bar{\alpha}-\bar{m}+\bar{p}_{j})}=\mathbb{E}[\prod_{j=2}^{r}\Psi_{j}^{p_{j}}(1-\Psi_{j})^{\bar{p}_{j-1}}]\;.$

By equating (52)–(55) to $\mathbb{E}[Z_{t_{r}}(p,t)]$, the results follow. ∎

###### Proof of Proposition 15.

Define $T_{1:r}:=(T_{1},T_{2},\dotsc,T_{r})$ and

$\displaystyle Z_{n}^{\alpha,\theta}(p,T_{1:r})$
$\displaystyle:=\frac{\Gamma(n+\theta)}{\Gamma(n+\theta+\bar{p})}\prod_{j=1}^{r}\frac{\Gamma(D_{j,n}-\alpha+p_{j})}{\Gamma(D_{j,n}-\alpha)}$
(56)
$\displaystyle=n^{-\bar{p}}\prod_{j=1}^{r}D_{j,n}^{p_{j}}(1+O(n^{-1}))\;.$
(57)

The fact that
${\mathbb{E}[Z_{n+1}^{\alpha,\theta}(p,T_{1:r})\mid\mathcal{F}_{n}]=Z_{n}^{\alpha,\theta}(p,T_{1:r})}$
shows that $Z_{n}^{\alpha,\theta}(p,T_{1:r})$ is a nonnegative martingale for
$n\geq T_{r}$. $Z_{n}^{\alpha,\theta}(p,T_{1:r})$ can be bounded in $L_{2}$
following an argument similar to that given in the proof of Lemma 20, and
hence it converges almost surely to $\xi_{1}^{p_{1}}\dotsm\xi_{r}^{p_{r}}$.
Therefore,

$\displaystyle\mathbb{E}[\lim_{n\to\infty}n^{-\bar{p}}\prod_{j=1}^{r}D_{j,n}^{p_{j}}\mid
T_{1:r}]=\mathbb{E}[\xi_{1}^{p_{1}}\dotsm\xi_{r}^{p_{r}}\mid T_{1:r}]$
$\displaystyle=\frac{\Gamma(1-\alpha+p_{r})\Gamma(T_{r}+\theta)\Gamma(T_{r}-1-(r-1)\alpha+\bar{p}_{r-1})}{\Gamma(1-\alpha)\Gamma(T_{r}+\theta+p_{1})\Gamma(T_{r}-1-(r-1)\alpha)}\dots$
$\displaystyle\quad\times\prod_{j=2}^{r-1}\frac{\Gamma(1-\alpha+p_{j})\Gamma(T_{j}-j\alpha)\Gamma(T_{j}-1-(j-1)\alpha+\bar{p}_{j-1})}{\Gamma(1-\alpha)\Gamma(T_{j}-j\alpha+\bar{p}_{j})\Gamma(T_{j}-1-(j-1)\alpha)}$
$\displaystyle=\mathbb{E}[\mathcal{B}_{T_{r}-r\alpha,\theta+r\alpha}^{\bar{p}}\cdot\prod_{j=2}^{r}\Psi_{j}^{p_{j}}(1-\Psi_{j})^{\bar{p}_{j-1}}]\;,$

from which the result follows. ∎

###### Proof of Proposition 16.

For an exchangeable Gibbs partition with $\alpha\in(0,1)$ and a sequence of
coefficients $v_{n,k}$, one may construct a martingale similar to that in
(56). It is then straightforward to show that the scaled degrees converge
almost surely to random variables $(\xi_{j})_{1\leq j\leq r}$, conditionally
on $T_{1},\dotsc,T_{r}$. Conditioned on $T_{j}$, $\xi_{j}$ has marginal
moments

$\displaystyle\mathbb{E}[\xi_{j}^{p}\mid
T_{j}]=\frac{\Gamma(1-\alpha+p)}{\Gamma(1-\alpha)}\bigl{(}1+p\frac{V_{T_{j}+1,j}}{V_{T_{j},j}}\bigr{)}^{-1}\;.$

Kerov [29] showed that the only exchangeable Gibbs partitions with
coefficients that can be represented as a ratio $V_{n,k}=v_{k}/c_{n}$ are
those of the $\text{\rm CRP}(\alpha,\theta)$, in which case the product in the
previous equation becomes independent of $j$. See also [23, Lemma 4.1], which
also implies the result. ∎

###### Proof of Proposition 18.

Define for $p>-1$,

$\displaystyle Z_{n}^{\beta}(p,T_{1:r})$
$\displaystyle:=\frac{\Gamma(n)}{\Gamma(n+\bar{p}(1-\beta))}\prod_{j=1}^{r}\frac{\Gamma(D_{j,n}+p_{j})}{\Gamma(D_{j,n})}$
$\displaystyle=n^{-\bar{p}(1-\beta)}\prod_{j=1}^{r}D_{j,n}^{p_{j}}(1+O(n^{-1}))\;,$

which is by construction a nonnegative martingale, bounded in $L_{2}$, for
$n\geq T_{r}$. Therefore,

$\displaystyle\mathbb{E}[\lim_{n\to\infty}n^{-\bar{p}(1-\beta)}\prod_{j=1}^{r}D_{j,n}^{p_{j}}]=\mathbb{E}[\xi_{1}^{p_{1}}\dotsm\xi_{r}^{p_{r}}]$
$\displaystyle=\frac{\Gamma(T_{r}+\bar{p})}{\Gamma(T_{r}+\bar{p}(1-\beta))}\prod_{j=2}^{r}\frac{\Gamma(1+p_{j})\Gamma(T_{j})\Gamma(T_{j}-1+\bar{p}_{j-1})}{\Gamma(T_{j}-1)\Gamma(T_{j}+\bar{p}_{j})}$
$\displaystyle=\mathbb{E}[\mathcal{M}_{1-\beta,T_{r}-1}^{-\bar{p}(1-\beta)}]\mathbb{E}[\mathcal{B}^{\bar{p}}_{T_{r},(T_{r}-1)\frac{\beta}{1-\beta}}]\mathbb{E}[\prod_{j=2}^{r}\Psi_{j}^{p_{j}}(1-\Psi_{j})^{\bar{p}_{j-1}}]\;,$

from which the result follows. The marginal identities result from altering
the above martingale to contain only $D_{j,n}$, which is also a martingale.
Similar treatment of the moments, along with the beta-gamma algebra and the
identity (1.3) in James [25] yields the rest of the identities. ∎

###### Proof of Proposition 19.

In analogy to the previous proof, for every $p>-1$,

$\displaystyle Z_{n}^{\beta}(p,w+b)$
$\displaystyle=\frac{\Gamma(n)}{\Gamma(n+p(1-\beta))}\frac{\Gamma(D_{w,n}+p)}{\Gamma(D_{w,n})}$
$\displaystyle=n^{-p(1-\beta)}D_{w,n}^{p}(1+O(n^{-1}))$

is a nonnegative martingale, bounded in $L_{2}$, for $n\geq w+b$. Therefore,
it converges almost surely to a random variable $\xi_{w,w+b}^{p}$, where

$\displaystyle\mathbb{E}[\xi_{w,w+b}^{p}]$
$\displaystyle=\frac{\Gamma(w+b)\Gamma(w+p)}{\Gamma(w+b+p(1-\beta))\Gamma(w)}$
$\displaystyle=\mathbb{E}[\mathcal{G}_{w}^{p}]/\mathbb{E}[\mathcal{G}_{w+b}^{p(1-\beta)}]=\mathbb{E}[\mathcal{B}_{w,b}^{p}\mathcal{B}_{w+b,(w+b-1)\frac{\beta}{1-\beta}}^{p}\mathcal{M}_{1-\beta,w+b-1}^{p}]\;.$

The other identities can be verified by checking moments; they also follow
from the beta-gamma algebra and from [25]. ∎