{'fraction_non_alphanumeric': 0.039863234111021724, 'fraction_numerical': 0.005993563958165728, 'mean_word_length': 4.153606965174129, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Cluster Model for Growth of Random Trees

We first consider the growth of trees by probabilistic attachment of new vertices to leaves. This leads to a growth model based on vertex clusters and probabilities assigned to clusters. This model turns out to be readily applicable to attachment at any depth of the tree, hence the paper evolves to a general study of tree growth by cluster-based attachment. Drawing inspiration from the concept of intrinsic vertex fitness due to Bianconi and Barab\'asi, we introduce vertex mass as an additive intrinsic vertex attribute. Unlike Bianconi and Barab\'asi who used fitness as a vertex degree multiplier in the context of growth by preferential attachment, we treat vertex mass as a fundamental probabilistic construct whose additivity plays a primary role. Notably, independent mass distributions induce a distribution on the sum of such masses through Laplace convolution. In this way, clusters of vertices inherit their mass distributions from vertices within the cluster. Our main contribution is a novel theorem for the joint distribution of cluster masses, conditioned on their respective distributions. As described by Ferguson and Kingman in the context of distributions on general measures, the choice of gamma conditioning distributions leads to the Dirichlet distribution. Beyond gamma conditioning distributions, our theorem allows other choices, such as the fat-tailed stable distributions with infinite mean. We discuss L\'evy conditioning distributions as a gamma alternative, the L\'evy distribution being a notable instance of the stable family. We conclude with a theorem giving the analytic marginals of the normalised distribution conditioned on the L\'evy distribution.


Introduction
In the first instance, we consider a tree that grows by attachment from the root (where a directed edge from one vertex to another represents attachment of the former to the latter). The tree has two vertex types: (i) a deep vertex with one or more incoming attachments (ii) a leaf (or shallow vertex) with no incoming attachments (the root is also taken to be a leaf at the start). We consider growth by attachment of a new vertex to a leaf and not to a deep vertex. Figure 1 is an illustrative sequence of 'snapshots' of a tree as it grows by leaf attachment (time increases to the right in each snapshot). The rules for growth by leaf attachment are as follows: Rule 1: Only new vertices may issue attachments, existing vertices are 'inactive'. Rule 2: For a tree, a new vertex issues exactly one attachment Rule 3: Leaf attachment: a new vertex may only attach to a leaf. Rule 4: A leaf can receive multiple attachments from different new vertices created in the same time step. Thereafter, the leaf becomes deep and may not receive further attachments at later times. Rule 5: New vertices select attachment targets from a probability distribution over leaves. There are two logically distinct steps at play. The first step is the creation of n i ≥ 0 new vertices in the i th time interval. We may take such vertex creation to follow a Poisson process, i.e. at each time step i, the number n i is drawn from a Poisson distribution with a given rate. The second step is the attachment of newly created vertices to leaves of the existing tree. It is the latter step that is of primary interest -choosing a leaf probability distribution from which new vertices select their attachment targets.
If we ignore the history of the tree altogether, then there is no reason to prefer one leaf over another. Hence the leaf distribution to be used for attachment may be taken to be uniform. However, we do wish to strike a probabilistic distinction amongst leaves based on how well-connected they are to the history of the tree. Broadly speaking, we want to encourage branching of the tree or, equivalently, clustering of vertices and discourage isolated chains of vertices. A local view of clustering is to consider attachments that leaves make to their immediate predecessors. The more leaves cluster by attaching to a common predecessor, the more they are to be favoured for attachment. Hence a cluster, i.e. a set of vertices that directly attach to a common vertex, is the object of primary interest. It thus makes sense to consider a probability distribution over such clusters of leaves rather than treating the leaves as isolated objects. Once a cluster is selected, a leaf within the cluster may then be selected on the basis that leaves within a cluster are equivalent, i.e. the leaf distribution is uniform within a cluster.  We may now reinterpret the example of Figure 1 in terms of clusters and attachments amongst them, as illustrated in Figure 2. There are clusters of deep vertices, clusters of leaves and hybrid clusters containing both.
An immediate observation at this point is that the cluster interpretation need not be restricted to leaf attachment. It is also applicable to growth by unrestricted attachment to an existing vertex at any depth of the tree. We shall refer to the latter as free attachment. In either case, for a given vertex v, let a cluster C v be the set of of vertices that attach to v (v itself belongs to a cluster that attaches to some earlier vertex, except for the root). If v is a leaf then C v is the empty set. Let |C v | be a quantitative property of C v . How we define |C v | is what is at the core of this paper, more so than whether we are dealing with leaf or free attachment. An obvious choice of |C v | is the number of vertices in C v , or the in-degree of v. We shall elaborate below on the more nuanced choice of |C v | taken here. The fundamental difference between leaf and free attachment lies in how we use C v .

Leaf Attachment
• A cluster C v is static, containing a fixed number of vertices in a single time interval that attach to v. • For any deep vertex v for which C v contains one or more leaves, a new vertex first selects C v and then selects a leaf within C v to attach to. A cluster with no leaves is at full capacity and is thus not available for selection. • The probabilistic selection of C v is based on its |C v | relative to other clusters containing at least one leaf.

Free Attachment
• A cluster C v is dynamic with no simple topology -C v evolves as new vertices attach to v.
• A new vertex directly selects an existing vertex v at any depth to attach to. Hence an existing vertex can receive an unlimited number of attachments. • The probabilistic selection of v is based on its |C v | relative to all existing vertices. If |C v | is the in-degree of v then leaves would be excluded since they would have |C v | = 0. A simple remedy is to introduce a global offset β > 0 so that The conceptual benefit of the leaf attachment problem is that it has prompted us to think in terms of clusters and attributes we might assign to clusters that are more general than vertex in-degree. Such thinking does not arise naturally in the free attachment case where clusters are topologically awkward. We have thus chosen to retain the thought process flowing from leaf attachment even though the probabilistic formulation of the paper is ultimately not restricted to leaf attachment.
Attachment based on vertex in-degree is known as preferential attachment. It is widely used in network science (Barabási [1], van der Hofstad [11], Newman [14], Coscia [7]). Price [15] referred to such attachment as cumulative advantage in his graphical model of citation networks (a generalisation of a tree to a directed graph where a new vertex may make multiple attachments to existing vertices). Preferential attachment is often referred to as a "rich get richer" scheme that rewards vertices that are already rich in attachments.
To construct a cluster distribution, we look beyond mere vertex count to consider an intrinsic vertex attribute that we refer to as vertex mass, which is positive and additive. Hence the mass of a cluster is a sum of the masses of the vertices in the cluster. The probabilistic model may thus be summarised as follows. We take vertex mass to be governed by an assigned probability distribution. We shall take the vertices to be independent. The mass of a cluster is thus the sum of the masses of the vertices in the cluster, whose distribution is induced by the distributions of the masses of the vertices on the cluster. Specifically, the distribution of a sum of independently distributed variables is a convolution of the distributions of the individual variables. This is a crucial consistency property that underpins our mass-based model -the mass distribution of a cluster is a convolution of the mass distributions of its constituent vertices.
This may beg the question of whether we can simply invent intrinsic attributes at will. We take the view that the justification for any model lies in its ability to generate specified behaviour, or reproduce observed behaviour if it is intended to be a model of the external world. It suffices that the model exhibit internal mathematical consistency which, in our case, is the probabilistic convolution structure imposed by additivity. For variables on the real line (−∞, ∞), such convolution is the familiar Fourier convolution. Restriction to the nonnegative half-line [0, ∞) gives Laplace convolution, which will be the workhorse of our model.
We do not claim originality for the notion of intrinsic vertex attributes. Intrinsic vertex mass is inspired by the concept of intrinsic vertex fitness due to Bianconi and Barabási [4]. The focus of [4] was growth of a graph by the degree-based scheme of preferential attachment. Hence the fitness distribution was used solely to generate a single sample per vertex that is in turn used as a degree multiplier to tune the degree distribution. Beyond the inspiration, we adopt a different modelling route from [4] based on vertex mass. In fact, it will emerge that a degree multiplier can arise in a rather different context for our probabilistic model.
The primary objective of preferential attachment is to explore asymptotic behaviour -whether or not the limiting degree distribution obeys scale-free (power law) behaviour (Barabási and Albert [2]). With fitness included, it is possible to generate "winner takes all" degree clustering reminiscent of Bose-Einstein condensation in physics (Bianconi and Barabási [3]). In pursuit of scale-free behaviour by an alternative route to preferential attachment, Caldarelli et al. [5] explored the fitness distribution in its own right instead of the degree distribution.
Point processes involve similar probabilistic constructs to those considered here. The conceptual difference is that while our clusters may visually resemble spatial cells, such clusters only come into being as a result of vertex attachment, they do not pre-exist like some partition of a spatial domain may do even before any random points are strewn across it. Nonetheless, graphs can usefully be modelled as point processes. In an approach inspired by the adjacency matrix, Caron and Fox [6] model a graph as a point process on R 2 + whose points are pairs of connected vertices. Each vertex has an associated positive sociability parameter which, in turn, is a point of a Poisson point process or a jump of a completely random measure. The intrinsic sociability of a vertex rather than its degree is the fundamental probabilistic attribute. The approach has much in common with other work on random measures (e.g. Ferguson [8,9], Sibisi and Skilling [16]).
Main Result: At the outset, we had the rather focussed objective of constructing a growth model for the leaf attachment problem. As our thinking evolved, it became clearer that we needed first to consider a problem of much broader scope.
Accordingly, our primary contribution is significantly more far-reaching than the paper's initial brief. It takes the form of Theorem 3, which gives the joint distribution of cluster masses, conditioned on their respective independent distributions. A sample from this distribution is itself a distribution that, in the original application context, we may use for attachment in our tree growth application.
To our awareness, Theorem 3 is novel, at least to the extent that it accommodates any set of conditioning distributions. The idea of such generality is contained in Kingman [12], despite the difference in approach. Choosing gamma conditioning distributions leads to the Dirichlet distribution, initially described by Ferguson [8]. He addressed the more general problem of a Dirichlet process, which may be described as a set of consistent Dirichlet distributions over different partitions of an interval or spatial domain.
We shall see that the mean of the Dirichlet distribution is the degree distribution. Hence we may interpret preferential attachment as probabilistic selection scheme based on the Dirichlet mean. However, a representative sample from the Dirichlet distribution can be very different from the mean, depending on the parameters of the conditioning gamma distributions.
Furthermore, the generality of Theorem 3 allows the choice of any conditioning distributions. An example is the family of fat-tailed stable distributions with infinite mean, such as the Lévy distribution. We conclude with a theorem giving the analytic form of the marginals of the normalised distribution conditioned on the Lévy distribution. This distribution is a novel alternative to the Dirichlet distribution induced by gamma conditioning distributions. We defer more detailed study to a separate paper.
Toward a more detailed discussion of the model, we start with some well-known preliminaries.

Preliminaries
We restrict attention to distributions defined on the nonnegative half-line [0, ∞) and take every distribution to be normalised and to have a density. Notation 1. A probability distribution F (x) and its density f (x) ≥ 0 with respect to dx are related as follows with normalisation F (∞) = 1.
A unit jump at x 0 in F corresponds to an atom at Convolution is associative: Hence the definition readily generalises to an arbitrary number of functions. Following Feller, we use the notation f n⋆ for the n-fold self-convolution of f . Theorem 1 is standard and so is the proof.
Proof of Theorem 1. Consider the Laplace transform of the convolution of 2 functions The generalisation (5) and particular case (6) follow from associativity of convolution. . . , f n } respectively. The distribution of the sum z = x 1 + · · · + x n is the Laplace convolution of the n individual distributions, i.e. the density of z is Pr(z|F 1 , . . . , F n ) ≡ Pr(z|f 1 , . . . , f n ) = (f 1 ⋆ · · · ⋆ f n )(z).
Note. To limit notational clutter, we shall often write Pr(z|f 1 , . . . , f n ) merely as Pr(z), where the conditioning information can be inferred from the context.
To our awareness, Theorem 3 is novel, at least as stated in general form with any {f 1 , . . . , f n }.
Theorem 3 is valid for any set of conditioning distributions {F 1 , . . . , F n } with respective densities {f 1 , . . . , f n }. It places no additional restriction on the distributions, such as the existence of means. Indeed, in Theorem 4 below, we will consider conditioning distributions with infinite means. We have implicitly assumed finite n. Whether (12) and (17) exist for n → ∞ will depend on {f 1 , . . . , f n }.
Corollary 3.1 enables evaluation of marginals without the need first to evaluate the joint distribution and then marginalise explicitly.
Adopting the convention of representing a distribution by its conditioning information, let P(F 1 , . . . , F n ) or P(f 1 , . . . , f n ) denote the distribution with density (12) of Theorem 3. By the foregoing discussion, to draw a sample from P(F 1 , . . . , F n ): • Draw n independent samples {x i ∼ F i : i = 1 . . . n} from the n distributions {F i } • Formẑ =x 1 + · · · +x n and {p i =x i /ẑ : i = 1 . . . n} • ThenP (n) = (p 1 , . . . ,p n ) is a sample point from P(F 1 , . . . , F n ).P (n) is a normalised distribution on an n-valued discrete variable that may then be used as appropriate (such as selecting the i th cluster given n clusters).
The key observation here is that we do not actually need P(F 1 , . . . , F n ) (or its marginals) to generate a sample from it. It suffices to generate independent samples from the conditioning distributions {F 1 , . . . , F n } and normalise. The benefit of Theorem 3 is that it shows how formally to obtain the density of P(F 1 , . . . , F n ) (and its marginals). If this can be done in closed form, then it facilitates an analytical study of the properties of P(F 1 , . . . , F n ). It also enables visual representation of P(F 1 , . . . , F n ), at least for small n, while the n marginals can be visualised individually in one-dimension for any n. In the absence of a closed form, the exercise becomes computational rather than analytical -we have to rely on many samples from P(F 1 , . . . , F n ) to approximate its properties, but without a theoretical handle on how many samples are needed for a "good" approximation.
It is logical then, at least in the first instance, to search for a set of conditioning distributions {F 1 , . . . , F n } for which Theorem 3 gives a closed form of the density of P(F 1 , . . . , F n ). To that end, we turn to the set of gamma conditioning distributions, for which it will emerge that Theorem 3 leads to the Dirichlet distribution, as introduced by Ferguson [8] in his seminal work on the Dirichlet process.
For integer shape parameter, G (n, λ) is also known as the Erlang distribution, named after Erlang who discovered it in his pioneering study of telephone networks.
The derivation of the Dirichlet distribution from G (α i , 1) dates back to Ferguson [8]. However, we have derived the Dirichlet distribution as a particular case of Theorem (3), which admits any choice of conditioning distributions {F i }.

Dirichlet Properties
The Dirichlet distribution inherits its behaviour from its conditioning gamma distributions. Hence the shape parameters have a crucial role, as discussed above for the gamma distribution. Shape parameters below 1 push the probability mass toward the axes, whilst tending to concentrate it away from the axes for shape parameters above 1. If all shape parameters are 1 then the distribution is uniform. For any n, if we choose {α i > 1} for all i, then we induce a D(α 1 , . . . , α n ) with probability concentrated away from the axes. The larger such {α i } are, the more sharply concentrated around its mean D(α 1 , . . . , α n ) will be. On the other hand, if {α i < 1} for some or all i, then then we induce D(α 1 , . . . , α n ) where some or all its probability is pushed to the axes, although the mean may still lie away from the axes. In the limit where we allow {α i = 0} for some but not all i, then a sampleP (n) = (p 1 , . . . ,p n ) from D(α 1 , . . . , α n ) will havep i = 0 for corresponding α i = 0, so thatP (n) is concentrated on thosep i corresponding to α i > 0. An equivalent way of stating this is that the density of the conditioning distribution G (α i = 0, 1) is an atom at zero. Yet the Dirichlet meanP (n) may remain quite smooth.
Visual representation would be of benefit but multivariate distributions are tricky to visualise. The beta-distributed marginals B(α i , α − α i ) are a useful way to get a sense of the behaviour of the Dirichlet distribution. It is also common to represent the Dirichlet distribution on an n − 1 dimensional simplex of n-dimensional space but this is not easy to visualise beyond n = 3.
The Dirichlet distribution often arises as a building block for a Dirichlet process -a family of consistent Dirichlet distributions for different n. The typical context involves progressive refinement of some spatial domain (often motivated through the metaphor of repeated breaking of pieces of a stick). In his paper, Ferguson [8] introduced arbitrary partitioning of a general space X : . He then defined a measure α on X : α i ≡ α(A i ) is the "size" of A i . Then defining a distribution G (α i , 1) on another measure F i ≡ F (A i ) and normalising using F (X ) gives a Dirichlet distribution D(α 1 , . . . , α n ) on any n-cell partition of X . Ferguson thus defined the Dirichlet process as a consistent family of such Dirichlet distributions for different n, which makes sense because the measure α is additive under cell combination (union of disjoint sets) and the conditioning gamma distributions are closed under addition of shape parameters. As Ferguson established, in the n → ∞ limit of an arbitrarily fine partition, the cell sizes approach zero so that samples from D(α 1 , . . . , α n ) will necessarily be concentrated on isolated cells, rather as described above for α i ≪ 1.
With the general probabilistic framework in place, we may turn to a discussion of our model.

Probabilistic Model
Let there be n clusters of interest, where cluster i has k i vertices (a cluster of interest will be determined by whether we are interested in leaf attachment or deep attachment, but that distinction is not of particular significance at this point). Let all vertices have independent identically distributed masses with distribution G (η, 1) for a chosen shape parameter η > 0. Hence, cluster i has mass distribution G (ηk i , 1). The corresponding normalised mass distribution is the Dirichlet distribution D(ηk 1 , . . . , ηk n ).
The next step is to generate a normalised sampleP (n) = (p 1 , . . . ,p n ) ∼ D(ηk 1 , . . . , ηk n ) as discussed in Section 3.P (n) is then a representative distribution over the n clusters that may be used for attachment. As discussed earlier, representative samples from D(ηk 1 , . . . , ηk n ) behave radically differently depending on whether {ηk i < 1} or {ηk i > 1}. In the former case, a small number of clusters can dominate the distribution of a representative distributionP (n) because of the concentration of probability near the axes. Thus, a small number of clusters (or vertices to which they attach) can attract the lion's share of the next wave of attachments.
How does this compare with common practice for growth by attachment? The popular approach of preferential attachment may be seen as a special case of what has been presented here.

Preferential Attachment
The mean of D(ηk 1 , . . . , ηk n ) is the discrete distributionP (n) = (µ 1 , . . . µ n ) where As previously noted, attachment based on such vertex in-degree (vertex count of attachments to a given vertex) is known as preferential attachment. The mean (28) is insensitive to η. Hence the flexibility that can be induced by a global η on a representative Dirichlet sampleP is not visible to the meanP used in preferential attachment.

Bianconi-Barabási Fitness Scheme
As a variant of the foregoing, let cluster i have an assigned intrinsic shape parameter η i and let each vertex within the cluster have a mass distribution G (η i , 1). This leads to D(η 1 k 1 , . . . , η n k n ) and means This is the scheme of Bianconi and Barabási [4], where the degree multipliers {η i } are referred to as fitness parameters. We do not speak to the choice of the {η i }, which could be sampled from an assigned distribution on η.

Affine Preferential Attachment
Let the intrinsic vertex distribution G (η, 1) be complemented by an intrinsic cluster distribution G (β, 1) assigned to all clusters. The effective distribution of cluster i is G (ηk i , 1) ⋆ G (β, 1) = G (ηk i + β, 1). Alternatively, we can simply say that each cluster's shape parameter is displaced by β. This induces D(ηk 1 + β, . . . , ηk n + β), with means Using (30) for attachment is known as affine preferential attachment in the random graph literature. It has been used to model the growth of random trees (e.g. Garavaglia et al. [10], Marchand and Manolescu [13]).

Random Forest
For completeness, we note that the functional form of affine preferential attachment can be interpreted and used differently by writing it as: For 0 < δ < β, (31) may be used for the two distinct steps: Attachment: Free attachment to vertex i with probability ∝ ηk i + δ ensures that a leaf l, which has in-degree k l = 0, can also receive direct attachments with probability ∝ δ.

Conclusion
In presenting this paper, we have followed the thought process from an initial interest in the growth of random trees by leaf attachment to a general discussion of probabilistic attachment based on vertex clusters. Leaf attachment itself was inspired by distributed ledgers, which can be modelled as random trees that grow by leaf attachment, but the thought process quickly evolved from distributed ledgers to the growth of trees in general. Indeed, the very mention of distributed ledgers proved to be a distraction because of the many issues that come up that are not, in their nature, about probabilistic modelling.