{'fraction_non_alphanumeric': 0.05121432240076308, 'fraction_numerical': 0.01814757746961137, 'mean_word_length': 3.6932966023875116, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 53, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The iterated local transitivity model for hypergraphs

Complex networks are pervasive in the real world, capturing dyadic interactions between pairs of vertices, and a large corpus has emerged on their mining and modeling. However, many phenomena are comprised of polyadic interactions between more than two vertices. Such complex hypergraphs range from emails among groups of individuals, scholarly collaboration, or joint interactions of proteins in living cells. A key generative principle within social and other complex networks is transitivity, where friends of friends are more likely friends. The previously proposed Iterated Local Transitivity (ILT) model incorporated transitivity as an evolutionary mechanism. The ILT model provably satisfies many observed properties of social networks, such as densification, low average distances, and high clustering coefficients. We propose a new, generative model for complex hypergraphs based on transitivity, called the Iterated Local Transitivity Hypergraph (or ILTH) model. In ILTH, we iteratively apply the principle of transitivity to form new hypergraphs. The resulting model generates hypergraphs simulating properties observed in real-world complex hypergraphs, such as densification and low average distances. We consider properties unique to hypergraphs not captured by their 2-section. We show that certain motifs, which are specified subhypergraphs of small order, have faster growth rates in ILTH hypergraphs than in random hypergraphs with the same order and expected average degree. We show that the graphs admitting a homomorphism into the 2-section of the initial hypergraph appear as induced subgraphs in the 2-section of ILTH hypergraphs. We consider new and existing hypergraph clustering coefficients, and show that these coefficients have larger values in ILTH hypergraphs than in comparable random hypergraphs.


Introduction
Complex networks are an effective paradigm for pairwise interactions between objects in realworld systems. Such networks capture dyadic interactions in many phenomena, ranging from friendship ties in Facebook, to Bitcoin transactions, to interactions between proteins in living cells. Complex networks evolve via a number of mechanisms such as preferential attachment or copying that predict how links between vertices are formed over time. Structural balance theory cites mechanisms to complete triads (that is, subgraphs consisting of three vertices) in social and other complex networks [16,19]. A central mechanism in balance theory is transitivity: if x is a friend of y, and y is a friend of z, then x is a friend of z; see, for example, [24].
The Iterated Local Transitivity (ILT ) model introduced in [11,12] and further studied in [8,9,25], simulates structural properties in complex networks emerging from transitivity. Transitivity gives rise to the notion of cloning, where an introduced vertex x is adjacent to all of the neighbors of some pre-existing vertex y. Note that in the ILT model, the vertices have local influence within their neighbor sets. Although graphs generated by the model evolve over time, there is a memory of the initial graph hidden in the structure. The ILT model simulates many properties of social networks. For example, as shown in [11], graphs generated by the model densify over time and exhibit bad spectral expansion. In addition, the ILT model generates graphs with the small-world property, which requires graphs to have low diameter and high clustering coefficient compared to random graphs with the same number of vertices and expected average degree.
Dyadic relationships do not always fully capture the dynamics of interactions between larger groups of vertices. For example, interactions among groups of vertices occur in scholarly collaborations, tags attached to the same web post, or metabolic interactions between more than two reactants. In these examples, a polyadic view of interactions is more accurate, giving rise to hypergraphs. A hypergraph is a discrete structure with vertices and hyperedges, which consists of sets of vertices. Graphs are special cases of hypergraphs, where each hyperedge has cardinality two. While hypergraph theory is less developed than graph theory, it is an emerging topic in the study of complex, real-world systems; see, for example, [2,4,15,17,18,21,27]. For a recent article discussing the important role of hypergraphs and other higher-order methods for studying complex networks, see [3].
In the present paper, we consider a deterministic model for complex hypergraph networks based on transitivity. The model is analogous to the ILT model, although it has its own unusual features. While every hypergraph can be reduced to its 2-section graph, replacing each hyperedge by a clique, not all hypergraph properties are captured by the 2-section. As we demonstrate, the ILT hypergraph model we introduce has properties not evident in its 2-section. Further, the model simulates several properties, such as clustering and motif evolution, more robustly when compared to random hypergraphs with analogous characteristics. For simplicity, we consider throughout k-uniform hypergraphs, where each hyperedge has cardinality k for a fixed positive integer k ≥ 2.
The Iterated Local Transitivity Hypergraph (ILTH ) model is defined formally as follows. The model is deterministic and generates k-uniform hypergraphs over discrete time-steps. The sole parameter of the model is the initial k-uniform hypergraph H = H 0 . For a nonnegative integer t, the hypergraph H t represents the hypergraph at time-step t. To form H t+1 , for each x ∈ V (H t ), add a new vertex x ′ called the clone of x. We refer to x as the parent of x ′ , and x ′ as the child of x. For every hyperedge e of H t containing x, we add the hyperedge e ′ to H t+1 formed by replacing x with x ′ . Observe that e ′ = (e ∖ {x}) ∪ {x ′ }; we simply write e ′ = e − x + x ′ . Note that all existing hyperedges in H t are also included in H t+1 . See Figure 1. We refer to H t as an ILTH hypergraph, and we sometimes write H t =ILTH t (H) to emphasize the initial hypergraph H. Note that ILTH t (H) is k-uniform for all t ≥ 0. We sometimes refer to the formation of the hypergraphs H t as the ILTH process.
The clones form an independent set in H t+1 , resulting in a doubling of the order of H t . Unlike in the ILT model, a clone and its parent are not in a hyperedge. For a vertex x in H t , we will sometimes use the notation x * to mean any descendant of x; that is, x * is either x or x ′ in H t+1 . Similarly, if e is a hyperedge in H t , then e * represents one of the descendant hyperedges e or e − x + x ′ in H t+1 .
As we will demonstrate, the ILTH model simulates many properties observed in complex hypergraphs, including the small-world property and motif counts. In Section 2, we derive a densification power law for ILTH hypergraphs, and show that distance and spectral properties follow by properties of the 2-section. We then consider subhypergraphs and motifs in Section 3. Motifs are certain hypergraphs with a small number of vertices and hyperedges. In [21], it was shown that several real-world, complex hypergraphs have motif counts dramatically higher than comparable random hypergraphs. We show that for certain motifs arising in k-uniform x y z x' y' z' hypergraphs from the list in [21] of 26 motifs formed from three hyperedges, ILTH has a provably higher count than in a random hypergraph with the same average degree. We prove that the 2-section contains isomorphic copies of all graphs admitting a homomorphism to the 2-section of H 0 in Theorem 3 and contains only such graphs; as a consequence, certain motifs will be excluded in the ILTH process unless they appear in H 0 . In Section 4, we provide a rigorous analysis of various clustering coefficients for ILTH hypergraphs. Our study of clustering coefficients further validates the small-world property of ILTH hypergraphs, and leads to interesting combinatorial analysis. We consider two clustering coefficients HC 1 and HC 2 and their asymptotic order in ILTH. The clustering coefficient HC 1 was first studied in [17]. We introduce the new parameter HC 2 that is a variant of one that first appeared in [27], although we argue it is more natural and amenable to analysis. In the case of HC 1 , we show that these clustering coefficients provide higher clustering than is expected in random hypergraphs with the same average degrees. We show an analogous result for HC 2 in a variation of the ILTH model, where clones and parents are adjacent. We finish with a summary of our results along with open problems on the ILTH model.
Throughout the paper, we consider finite, simple, undirected graphs and hypergraphs. For a general reference on graph theory, see [26]. For a reference on hypergraphs, see [5,6]. For background on social and complex networks, see [7,13,14]. We define terms and notation for hypergraphs when they first appear throughout the article.

Densification, eigenvalues, and distances
Many examples of complex networks densify in the sense that the ratio of their number of edges to vertices tends to infinity over time; see [22]. In this section, we show that the ILTH model always generates hypergraphs that densify, and we give a precise statement below of its densification power law.
Let n(t) be the number of vertices in H t and let e(t) be the number of hyperedges in H t , respectively. We establish elementary though important recursive formulas for these parameters.
Theorem 1. For a nonnegative integer t, we have the following.
Proof. For item (1), for each vertex v in H t , there are two vertices v and v ′ in H t+1 . Hence, n(t + 1) = 2n(t). For item (2), notice that for each hyperedge e in H t , we add to H t+1 the hyperedge e and each of the k hyperedges e − x + x ′ where x is a vertex in e. We then have that e(t + 1) = (k + 1)e(t) for all t. The result follows.
As a consequence, the average vertex degree of ILTH t (H) is given by which increases exponentially with t. Hence, we have a densification power law for ILTH hypergraphs. We next turn to the 2-section of ILTH hypergraphs. For this, we consider a variant on the ILT model for graphs, which we call ILT ′ . Given a graph G = G 0 , iteratively construct ILT ′ t (G), where t ≥ 1 as follows. Suppose that we have ILT ′ t (G). For each v ∈ V (ILT ′ t (G)), the vertices v and v ′ are included in ILT ′ t+1 (G). For each uv ∈ E(ILT ′ t (G)), the edges uv, uv ′ and u ′ v are included in ILT ′ t+1 (G). We have the following lemma, whose proof is immediate. Lemma 2. For a nonnegative integer t, we have that ILT ′ t (G) is the 2-section of ILTH t (H). We use the notation n t and e t for the order and size of ILT ′ t (G). Observe that n t = 2 t n 0 and e t = 3 t e 0 edges. An implication of Lemma 2 is that any hypergraph property that depends solely on the 2-section behaves the same way for the hypergraph model ILTH as it does for the graph model ILT ′ . Such properties are not truly exploiting the hypergraph structures evident in ILTH. We briefly discuss some of these properties, including the adjacency matrix, the diameter, and the average distance.
The adjacency matrix A(H) for a hypergraph H has rows and columns indexed by the vertices of H and entry 1 if u ≠ v and there is some hyperedge of H containing both u and v, and 0 otherwise. It is evident that this is the same as the adjacency matrix of the 2-section of H. In particular, to analyse the adjacency matrix of ILTH t (H) we need only consider the adjacency matrix of ILT ′ t (G), where G is the 2-section of H. If ILT ′ t (G) has n × n adjacency matrix A, then ILT ′ t+1 (G) has 2n × 2n adjacency matrix where 0 is the n × n all-zeros matrix. It is straightforward to verify that if A has eigenvalue ρ with associated eigenvector v, then ( A A A 0 ) has eigenvalues 1± √ 5 2 ρ with associated eigenvectors In particular, given the eigenvalues for the graph G, one can calculate the eigenvalues for ILT ′ t (G). We next consider distance in ILTH hypergraphs. A walk of length k connecting two vertices u and v in a hypergraph is a sequence of hyperedges e 1 , e 2 , . . . , e k such that u ∈ e 1 , v ∈ e k and e i ∩e i+1 ≠ ∅, for all 1 ≤ i < k. We say that the distance between two vertices u, v, written d(u, v), is the minimum length of a walk connecting u and v. This is the same as the distance between two vertices u and v in the 2-section of the hypergraph. In particular, to analyze distances within ILTH t (H) we could only consider distances in ILT ′ t (G), where G is the 2-section of H, but it is equally convenient to analyse ILTH directly.
Consider vertices u, v in H t with u ≠ v. Let d = d(u, v) and let e 1 , e 2 , . . . , e d be a minimum length walk connecting them. We then have that in H t+1 , (1) d(u, v) = d, using the walk e 1 , e 2 , . . . , e d ; (2) d(u, v ′ ) = d, using the walk e 1 , e 2 , . . . , e d − v + v ′ ; (3) d(u ′ , v) = d, using the walk e 1 − u + u ′ , e 2 , . . . , e d ; Note that in the case of the final item, there is no walk of length one as there is no hyperedge containing two clones. In the other cases, there can be no walks of length less than d else the predecessors of these edges would form a walk from u to v in H t of length less than d.
The diameter of a hypergraph is the maximum distance between any pair of vertices. We find immediately that the diameter of H t+1 is the maximum of 2 and the diameter of H t , and, iterating this, is the maximum of 2 and the diameter of H 0 . In either case, the diameter is a constant, independent of t.
To end this section, we determine the average distance between any pair of vertices in H t . Let W (t) be the sum of the distances in H t or Wiener index, written Assuming that H 0 has no isolated vertices and so H t has no isolated vertices for all t ≥ 1, by our calculations pertaining to distances above, we obtain that: Solving this recurrence gives that Thus, the average distance is given by as t tends to infinity. We therefore have that ILTH hypergraphs exhibit a constant average distance, as is found in many real-world hypergraphs; see [15].

Subhypergraphs and motifs
We next consider subhypergraphs of the ILTH model, and our first approach is to consider the induced subgraphs of the 2-section. In Theorem 3, it is shown that a graph appears in the 2-section of an ILTH hypergraph exactly when it admits a homomorphism to the 2-section of H 0 . The theorem guarantees the absence of many kinds of induced subhypergraphs; for example, no hypergraph clique appears in an ILTH hypergraph with larger order than H 0 . We then turn to counting certain small order subhypergraphs, or motifs. Motifs are important in complex networks, as they are one measure of similarity for graphs. For example, the counts of 3− and 4−vertex subgraphs gives a similarity measure for distinct graphs; see [10,23] for implementations of this approach using machine learning. Hypergraph motifs were studied by several authors; see for example, [1,4,21]. In [21], motif counts were analyzed across various real-world complex hypergraphs and compared to random hypergraphs. We show in this section that in ILTH hypergraphs, the growth rate for certain motifs is higher than in comparable random hypergraphs.
3.1. Induced subgraphs of the 2-section. For all t ≥ 0, H t is an induced subhypergraph of H t+1 . There exists a homomorphism f t from H t+1 to H t by mapping each clone to its parent, and fixing all other vertices. Note that As a result, the clique and chromatic numbers of H t are bounded above by those of H 0 . This observation puts limitations on the kinds of subgraphs that H t contains. For additional background on graph homomorphisms, the reader is directed to [20].
The age of a hypergraph is its set of isomorphism types of induced subhypergraphs. As each F t is a homomorphism, we have that no H t contains k-uniform cliques larger than those in H 0 . In particular, the set of ages of an ILTH hypergraph does not contain all hypergraphs. This contrasts with the ILT model, where all graphs occur in the set of ages of ILT-graphs; see [8].
Characterizing the ages of ILTH hypergraphs remains an open problem. The next result solves the analogous problem for the ages of 2-sections of ILTH hypergraphs. For a fixed graph G and family of graphs G, we say that G is G-hom-universal if the set of ages of G consists of all finite graphs admitting a homomorphism to G.
Proof. The reverse direction follows since for an induced subgraph G of G(H t ), the inclusion map is a homomorphism from G to G(H t ). Composing with F t gives a homomorphism from G to G(H 0 ).
For the forward direction, suppose that G admits a homomorphism f to is the clone of the vertex f (u). We then note that the number of vertices in the codomain of f ′ is one larger than the number of vertices in the codomain of f . We may repeat this procedure until we find an injective homomorphism f i from G to G(H i ), for some i ≥ 0.
Suppose that there are two vertices u, v in G which are not neighbors but such that , as this edge does not exist in f i+1 (G). We can repeat this procedure to construct an injective homomorphism f j from G to G(H j ) for some j, with the property that for all

3.2.
Motifs. We now turn to counting motifs, which are certain types of subhypergraphs. In [21], 26 distinct motifs were studied for three interacting hyperedges e 1 , e 2 , and e 3 . Motif counts may be viewed as a similarity measure for hypergraphs, such as when we are comparing real-world hypergraphs and synthetic ones derived from models.
The different types of motifs emerge by considering which of the following seven regions are nonempty: We may compactly reference motifs by a binary sequence so that for all j, i j = 1 exactly when there is at least one element in the corresponding region. We refer to the different motifs as motif types. See Figure 2 for an example. We may generalize On the left, we represent this motif via a Venn diagram, where the vertex in a region implies it is nonempty. On the right, we have an example of a 3-uniform hypergraph realizing this motif. this notation to a tuple of nonnegative integers, quantifying the number of elements in each region. The cardinality vector of a motif composed of the three hyperedges e 1 , e 2 , e 3 is defined as the 7-tuple: Note that a motif contains a+b+c+d+e+f +g vertices. Further, we have that e 1 = a+d+f +g = k, e 2 = b + d + e + g = k, and e 3 = c + e + f + g = k.
In general hypergraphs, there are 26 non-isomorphic motif types; however, we note that only 11 motif types occur in k-regular hypergraphs. With numbering taken from [21], these motif types are: (1) Motif type 2: 1110001, We keep the numbering from [21] for brevity; for example, we refer to motif 11 rather than 1011101. We focus on these motif types since they always occur in the ILTH model and have higher counts when compared to random hypergraphs, as we describe below. Interestingly, motifs 11 and 12 are more prevalent in the co-authorship hypergraphs compared to random hypergraphs, as shown in [21]. The same conclusion holds for motif 16 for tag hypergraphs. These observations lend credence to the view that ILTH hypergraphs simulate properties observed in real-world, complex hypergraphs.
Let α i be the maximum number of vertices that can occur in a motif of type i in a kuniform hypergraph. Each value of α i can be calculated explicitly, and each calculation is straightforward. For example, we may calculate α 14 as follows. Suppose that the motif in question has cardinality vector (a, 0, 0, d, e, f, g). Without loss of generality we have that as each hyperedge contains k vertices. It therefore immediately follows that d = f . The total number of vertices is which is maximized when d = f = g = 1 (as d, g, f > 0 in a motif of type 14), yielding α 14 = 2k −2.
As the remaining calculations are similar to the above, we omit them, and present the results in Table 1.   i 2  6  11  12  13  14  15  16  24  25 26 Table 1. The maximum number of vertices α i in a motif of type i possible in a k-uniform hypergraph.
Proof. For a motif in H t of type i with cardinality vector (a, b, c, d, e, f, g) formed by the hyperedges e 1 , e 2 , e 3 , we choose a set S of up to three vertices contained in the motif to clone such that each hyperedge of the motif contains at most one cloned vertex. Consider the motif in H t+1 formed by the hyperedges e ′ 1 , e ′ 2 , e ′ 3 , where e ′ i is the hyperedge obtained from e i by replacing each vertex that is also in S with its clone and leaving other vertices unchanged. This motif is of type i and has cardinality vector (a, b, c, d, e, f, g). Each motif developed in this way is unique. We must therefore find how many ways there are of choosing S, which is g + (c + 1)d + (b + 1)f + (a + 1)e + (a + 1)(b + 1)(c + 1), and the proof follows.
We have the following theorem.
Theorem 5. If the initial hypergraph contains at least one hyperedge, then the number of motifs of type 11 in the ILTH model is Ω(k 2t ).
Proof. A motif of type 11 has cardinality vector (a, 0, c, d, e, 0, g), where a + d + g = d + e + g = c + e + g = k, which yields a = e and c = d. For each motif of type 11 in H t , there will be g + (c + 1)d + (a + 1)e + (a + 1)(c + 1) = g + 2a + 2c + c 2 + a 2 + ac + 1 = (k − g) 2 − ac + 2k − g + 1, motifs of type 11 in H t+1 , which is maximized when g = 1 and either a = 1 or c = 1 (as a, c, g > 0) yielding a maximum value k 2 − k + 3. Let e 1 be a hyperedge in H 0 . For some u ∈ e 1 , there is a hyperedge We can also perform a similar analysis of the other motif types that grow rapidly. Theorem 6. If the initial hypergraph contains at least one hyperedge, then the number of each motif of types 2, 6, 12, 16, and 26 in the ILTH model is Ω(k 3t ).
Proof. It is straightforward to verify that H 3k contains a motif of type i containing α i vertices, for i ∈ {2, 6, 11, 12, 16}. Suppose that the motif in question has cardinality vector (a, b, c, d, e, f, g), and so α i = a + b + c + d + e + f + g. As α i = Ω(k 3 ) for these values of i, by Lemma 4, there are at least (α i )-times more of this motif type and cardinality vector in each iteration of the ILTH process. Hence, there are at least (α i ) t−3k = Ω(k 3t ) of this motif type in H t , and the result follows.
Our analysis so far does not apply to motif types 13, 14, 15, 24, and 25, as each of these motif types will not be generated in the ILTH process on one hyperedge. However, if one of these motif types occurs within the starting hypergraph, then we will have exponential growth of these, as shown in the following theorem. Proof. The proof follows by Lemma 4.
We contrast the motif counts for ILTH with comparable random hypergraphs. Let G(n, k, p) be the random hypergraph where each possible k-set is included as a hyperedge with probability p. If we fix two vertices u and w, then the expected number of hyperedges e containing both u and w is n−2 k−2 p. We consider the k-uniform hypergraph with n = n(t) = 2 t n(0) = Θ (2 t ) vertices and We expect Θ(n α i p 3 ) motifs of type i with α i vertices. To see this, give each vertex in a motif with α i vertices a label between 1 and α i , and define three k-sets with these labels e 1 , e 2 , and e 3 from the three hyperedges in the motif with these labels. We select α i vertices from the set of n vertices in the k-uniform random hypergraph, labeling the ith choice by the label i. There are n! (n−α i )! ∼ n α i possible ways to make these choices. The sets of vertices e 1 , e 2 , and e 3 are hyperedges in the k-uniform random hypergraph with probability p 3 . There is systematic double counting of occurrences of the motif but this only changes the expectation by a multiple of some function of k, which is a constant. The motifs of type i with fewer than α i vertices will occur o(n α i p 3 ) times, so the total number of motifs of type i that have any number of vertices is Θ(n α i p 3 ).
Therefore, we expect Θ(n α i p 3 ) = Θ 2 α i −3(k−log 2 (k+1)) t many occurrences of motif i. If α i < 3 (k − log 2 (k + 1)) , then the expected number of motifs of type i will tend to 0 exponentially fast, and if α i > 3 (k − log 2 k + 1) , then the expected number of motifs of type i grows exponentially. In particular, it will be useful to note that if α i ≤ 2k − 1 and k ≥ 9, then the expected number of motifs of type i will tend to 0 exponentially fast, and if α i = 3k −c with c ∈ {2, 3, 4, 5}, then the expected number of motifs of type i grows exponentially fast.
As a consequence, we expect motifs 2, 6, 12, 16, and 26 to occur an exponential number of times each in a random hypergraph. We expect that other motifs will rarely occur, with the probability that we see any diminishing when k ≥ 9 and t increases. As a consequence of Theorems 5 and 6, the growth rates of the motif types 2, 6, 11, 12, 16, and 26 is faster in ILTH than in a comparable random k-uniform hypergraph.
We finish the section with precise motif counts for ILTH with initial hypergraph a single hyperedge. We ran the ILTH model on a computer, starting with a single hyperedge of cardinality k, for 3 ≤ k ≤ 6 and 1 ≤ t ≤ 10 − k.
See Tables 2 to 5 below for the motif counts of these ILTH hypergraphs.

Hypergraph clustering coefficients
The small-world property in complex networks demands low average distance and high clustering coefficients, relative to random graphs with the same expected average degree; see [7] for a discussion. An analogous definition holds for small-world hypergraphs, comparing their properties to a random hypergraph G(n, k, p) with the same order n and p chosen so that they have the same expected average degree. As we demonstrated in Section 2, ILTH hypergraphs have constant average distance. Hence, a natural next step in our investigation is to consider clustering coefficients of ILTH hypergraphs.
There are a variety of hypergraph clustering coefficients we may consider; see [18] for nine distinct coefficients. We focus on a clustering coefficient introduced in [17], along with a new one that is a variant of the one studied in [27]. We discuss these clustering coefficients by considering graphs. For a graph G, the global clustering coefficient is 6 × (number of triangles in G) number of paths of length two in G .

Note that C(G) is a rational number in the interval
There are several different ways to generalize the definition of clustering coefficient to hypergraphs. We discuss three of these in the context of the ILTH model.
We define a path of length two in a hypergraph to be a 5-tuple (u, e 1 , v, e 2 , w) where u, v, w are distinct vertices, e 1 , e 2 are distinct hyperedges, and u, v ∈ e 1 , v, w ∈ e 2 . Similarly, we define a hypertriangle to be a 6-tuple (u, e 1 , v, e 2 , w, e 3 ) where u, v, w are distinct vertices, e 1 , e 2 , e 3 are distinct hyperedges, and u, v ∈ e 1 , v, w ∈ e 2 , w, u ∈ e 3 . We have the following generalization of the clustering coefficient to hypergraphs, appearing first in [17]: The reason for this difference with the graph case is because a given path of length two (u, e 1 , v, e 2 , w) can be extended to a hypertriangle in many different ways. The hyperedge e 3 can be any hyperedge so long as it includes u and w. The clustering coefficient HC 1 counts the average number of hypertriangles that are extensions of a path of length two.
We prove the following theorem on HC 1 in Subsection 4.1.
Theorem 8. For a nonnegative integer t, we have that We can show that H t has a higher value of HC 1 than the random k-uniform hypergraph with the same number of vertices and the same expected average degree. See the discussion at the end of Subsection 4.1.
There are other ways to express the clustering coefficient on graphs that lead to different generalisations to hypergraphs. One such equivalent definition is that C is the probability that given a path of length two, the end vertices are adjacent: C(G) = P (uv is an edge ∶ (u, e 1 , w, e 2 , v) a path of length two) .
We say two vertices u, v in a hypergraph are adjacent, written u ∼ v, if there is some hyperedge e containing both. There is then a natural way to generalize this definition of C to hypergraphs, which we think we are, surprisingly, the first to propose.

v) a path of length two in H)
= number of paths (u, e 1 , w, e 2 , v), where u ∼ v number of paths of length two .
Note that since HC 2 is a probability, this clustering coefficient is bounded between 0 and 1. Further, HC 2 matches the clustering coefficient C on graphs. A different generalization of the clustering coefficient to hypergraphs, due to [27], also retains the property that the clustering coefficient is between 0 and 1, and is closely related to HC 2 . Let I be the set of pairs of intersecting edges in H. For a (e, f ) ∈ I, define The extra overlap attempts to capture the number of connections between vertices u ∈ e 1 − e 2 and w ∈ e 2 − e 1 . It is evident that 0 ≤ EO(e 1 , e 2 ) ≤ 1. The following clustering coefficient from [27] is the average extra overlap over all intersecting pairs of edges: The goals of the authors in [27] were to define a clustering coefficient on hypergraphs that i) took values in [0, 1], ii) matches the normal clustering coefficient when applied to graphs, and iii) reflects the extent of connectivity among neighbors of v due to hyperedges other than ones connecting v with those neighbors. These three goals are satisfied by HC 3 , but they are also all satisfied by HC 2 , which we believe to be a more natural definition given that it can be simply expressed as a probability without recourse to the notion of extra overlap. For these reasons, we focus on the new clustering coefficient parameter HC 2 .
We prove the following theorem on HC 2 in Subsection 4.2.
Theorem 9. For a nonnegative integer t, we have that We show that H t has a lower value of HC 2 than the random k-uniform hypergraph with the same number of vertices and the same expected average degree, and so by this measure, it has less clustering. This is in contrast to the clustering coefficient HC 1 , and we include a discussion of this phenomenon at the end of the section. We introduce a modified version of ILTH where clones and their parents are in certain hyperedges. For the modified ILTH model, HC 2 has higher values than in random hypergraphs.
The following lemma will prove useful in our study of hypergraph clustering coefficients.
Let v * ∈ V (H t ) be a descendant of v and e * ∈ E(H t ) be a descendant of e. We then have that v * ∈ e * .
Proof. Take some v ∈ V (H t−1 ) and e ∈ E(H t−1 ) with v ∈ e. The descendants of e are e and e − x + x ′ for each x ∈ e. Since v ∈ e, it is evident that v and v ′ are not contained in any of the descendants of e.
Lemma 10 is more useful for our purpose in its contrapositive form.
and e ∈ E(H t−1 ) are their respective predecessors, then v ∈ e.
4.1. The clustering coefficient HC 1 . This subsection is devoted to proving Theorem 8. To that end, we prove two combinatorial lemmas finding the asymptotic order of the number of paths of length two and the number of hypertriangles in H t , respectively.
Lemma 12. The number of paths of length two in H t is Θ (k 2 + 1) t .
Proof. Let P ′ (t) = {(e 1 , v, e 2 ) ∶ v ∈ V (H t ), e 1 , e 2 ∈ E(H t ), v ∈ e 1 ∩ e 2 }. Note that, while closely related, this is not the same as the set of paths of length two as we do not include endpoints.
We include the degenerate case where e 1 = e 2 . We find an exact value for P ′ (t) in terms of t and P ′ (0) , which will enable us to bound the number of paths of length two. Fix some (e 1 , v, e 2 ) ∈ P ′ (t − 1). We wish to count the number of descendants (e * 1 , v * , e * 2 ) this has in P ′ (t).
For 0 ≤ i ≤ k, let P i (t) be the set of ordered pairs (e 1 , e 2 ) of hyperedges with e 1 ∩ e 2 = i. Note that P k (t) = e(t). We then have that P This gives that For a lower bound, we count the number of 6-tuples where e 1 , e 2 and e 3 are not distinct. If e 1 = e 2 ≠ e 3 , then u and w are distinct elements in e 1 ∩ e 3 = e 2 ∩ e 3 and v ∈ e 1 − u − w. Recalling that P i (t) is the number of pairs of edges intersecting in i vertices, we find that there are ∑ with e 2 = e 3 ≠ e 1 and with e 3 = e 1 ≠ e 2 .
Finally, note that when e 1 = e 2 = e 3 then we just have u, v, w distinct vertices in e 1 and so there are k(k − 1)(k − 2)e(t) 6-tuples in T ′ (t) with e 1 = e 2 = e 3 . Putting these together gives as calculated in the proof of Lemma 12. In particular, we have that We next have that which completes the proof.
As an immediate consequence of Lemmas 12 and 13, we obtain Theorem 8 on the value of the HC 1 clustering coefficient on ILTH hypergraphs. To contextualize the result of Theorem 8, we compare HC 1 (H t ) to HC 1 for other k-uniform hypergraphs. For the complete k-uniform hypergraph K (k) n it is straightforward to derive by counting choices of u, v, w and the edges containing them that When n = n(t) = 2 t n(0), this gives HC 1 (K (k) n ) = Θ (2 (k−2)t ), which is larger than HC 1 (H t ), as expected.
We consider the expected value of HC 1 in the random hypergraph G(n, k, p). Here, given a path (u, e 1 , v, e 2 , w) of length two, the expected number of hypertriangles of the form (u, e 1 , v, e 2 , w, e) is n−2 k−2 p . This gives Let n = n(t) = 2 t n(0) and p = (k+1) t e(0) n k . We then have that E (HC 1 (G(n, k, p))) = n−2 As k+1 4 < (k−1) 3 +3(k−1) , the clustering coefficient HC 1 for H t grows faster than that for the random hypergraph of the same expected average degree.

4.2.
The clustering coefficient HC 2 . In this subsection, we prove Theorem 9. We first introduce a useful set of 5-tuples: for some e 3 ∈ E(H t ) such that u ∈ e 1 ∩ e 3 , v ∈ e 1 ∩ e 2 , w ∈ e 2 ∩ e 3 .
One view of a 5-tuple in A(t) is as a (possibly degenerate) path of length 2 that can be completed to a (possibly degenerate) hypertriangle. We have the following lemma counting the elements of A(t), which will greatly assist in estimating HC 2 in ILTH hypergraphs.
this means that u * = u and w * = w, and we know there is a hyperedge e 3 containing both. Thus, there is one descendant We cannot have both u * = u ′ and w * = w ′ as there does not exist any hyperedge in E(H t ) containing both u ′ and w ′ . We can have u * = u ′ and w * = w, as the hyperedge e 3 − u + u ′ ∈ e(H t ) contains both. In this case, e * 1 must be e 1 − u + u ′ and e * 2 must be e 2 or e 2 − y + y ′ for some y ∈ e 2 − v − w, giving k − 1 descendants in A(t). Similarly, we can have u * = u and w * = w ′ , and there are a further k − 1 descendants in A(t) of this form.
Finally, we can have u * = u and w * = w as we know the hyperedge e 3 contains both. In this case e * 1 must be e 1 or e 1 − x + x ′ for some x ∈ e 1 − v − u and e * 2 must be e 2 or e 2 − y + y ′ for some y ∈ e 2 − v − w, giving (k − 1) 2 descendants in A(t) of this form. In total, each (u, e 1 , v, e 2 , w) ∈ A(t−1) has k 2 descendants (u * , e * 1 , v * , e * 2 , w * ) in A(t) giving A(t) ≥ k 2 A(t−1) . In the other direction, suppose we have some (u * , e * 1 , v * , e * 2 , w * ) in A(t). Let e * 3 be a hyperedge in H t containing both u * and w * . Consider their respective predecessors u, e 1 , v, e 2 , w and e 3 in H t−1 . We know that u, v, w must be distinct: if say u = v then either u * = v * , contradicting (u * , e * 1 , v * , e * 2 , w * ) ∈ A(t), or {u * , v * } = {v, v ′ }, contradicting that there is a hyperedge e * 1 containing both. An analogous argument shows that v ≠ w and w ≠ u. Applying Lemma 10 shows that u ∈ e 1 ∩ e 3 , v ∈ e 1 ∩ e 2 and w ∈ e 2 ∩ e 3 , so (u, e 1 , v, e 2 , w) ∈ A(t − 1). Hence, every 5-tuple in A(t) is a descendant of a 5-tuple in A(t − 1), and in particular, A(t) = k 2 A(t − 1) . Iterating this, we have that A(t) = (k 2 ) t A(0) .
We can now use Lemma 14 to prove Theorem 9.
Proof of Theorem 9. Recall that HC 2 (H) = number of paths (u, e 1 , w, e 2 , v), where u and v are in a hyperedge number of paths of length two .
Let Λ(t) be the number of paths (u, e 1 , v, e 2 , w), where u ∼ w. We then have that Λ(t) ⊆ A(t). Also, a 5-tuple (u, e 1 , v, e 2 , w) is in A(t) but not Λ(t) if and only if e 1 = e 2 , and there are k(k − 1)(k − 2)e(t) such 5-tuples. Thus, we have that Combining this with Lemma 12, we derive that HC 2 = Θ k 2 k 2 +1 t , as required.
We contextualize these results by comparing them to the random k-uniform hypergraph G(n, k, p) with the same expected average degree. We derive a lemma computing the expected value of HC 2 on random hypergraphs. Lemma 15. For a given k and p, we have that E (HC 2 (G(n, k, p))) = 1 − (1 − p) Proof. Suppose that we are given a path (u, e 1 , v, e 2 , w) and we wish to know the probability that the two vertices u, w lie in some hyperedge. There are n−2 k−2 k-sets containing both u and w and the probability that none of them is a hyperedge of G(n, k, p) is (1 − p) We compare H t to a random hypergraph with the same number of vertices and the same expected average degree. Set n = 2 t n(0) and choose p such that n k p = (k + 1) t e(0). We then have that where c depends only on k, n(0), and e(0). Hence, we conclude that E (HC 2 (G(n, k, p))) is at Measured by the clustering coefficient HC 1 , the hypergraph H t has higher clustering than in comparable hypergraphs, but this fails for HC 2 . The reason for the discrepancy is that the two clustering coefficients are counting different structures. Given a pair of intersecting edges e 1 , e 2 , the value of HC 2 counts how many pairs of vertices u ∈ e 1 − e 2 , w ∈ e 2 − e 1 there are that are contained in some hyperedge e 3 . As this is low for H t compared to random hypergraphs, fewer of those pairs are contained in any hyperedge than we might expect. The value of HC 1 roughly counts how many edges e 3 intersect both e 1 and e 2 to make a hypertriangle. As this is large for H t when compared to random hypergraphs, there are more of these edges than we might expect. Hence, relative to the random hypergraph, fewer pairs of vertices u ∈ e 1 − e 2 , w ∈ e 2 − e 1 are contained in a hyperedge, but those that are contained in an hyperedge must be contained in many hyperedges.

4.3.
A variant of ILTH with large HC 2 values. To remedy the situation with ILTH having lower HC 2 values than random hypergraphs, we consider a variant of the model where clones and their parents are in certain hyperedges. Such a variant is a natural one, as we may expect newly formed hyperedges to include both parent and child vertices.
Let H (2) 0 be a fixed k-uniform hypergraph and we iteratively construct H (2) t , where t ≥ 1 as follows. Suppose that we have H   original ILT model. While the models are distinct, ILTH 2 hypergraphs share properties with the ILTH hypergraphs such as densification and low distances. One key difference between ILTH and ILTH 2 is the clustering coefficient HC 2 . We have the following theorem, whose proof is analogous to the one of Theorem 9 and so is omitted.
Theorem 16. For nonnegative integers t, we have that We compare H (2) t to the random hypergraph with the same number of vertices and the same expected averaged degree. Set n = k t n(0) and choose p such that the expected number of edges n k p is e(t). In particular, we have that Applying Lemma 15, we have that E (HC 2 (G(n, k, p))) = Θ For all k ≥ 2, we find that so the clustering coefficient HC 2 is larger for H (2) t than in random hypergraphs.

Further directions
We introduced the new ILTH model for complex hypergraphs. We found that ILTH hypergraphs densify over time and have low average distances. We considered motifs and found that for those occurring in the ILTH model, their counts grow faster than in random hypergraphs with the same expected average degree. The 2-sections of ILTH hypergraphs were shown to contain isomorphic copies of all graphs admitting a homomorphism to the 2-section of H 0 in Theorem 3. We finished with an analysis of clustering coefficients, and it was shown that HC 1 was larger in ILTH hypergraphs than in random hypergraphs. A similar result was proven for HC 2 applied to a variant of ILTH, where parents are adjacent to their clones.
Several questions remain surrounding ILTH hypergraphs. We may consider variants of the model, and study properties of hypergraphs generated by the model. For example, we may allow hyperedges that are non-uniform orders, or randomize the model by adding random hyperedges to sets of clones. An open problem is to determine the age of ILTH hypergraphs; that is, what are the induced subhypergraphs of ILTH hypergraphs?
Another direction is to consider other notions of clustering in ILTH hypergraphs. Several hypergraph clustering coefficients were investigated in [17], for example, and it would be interesting to consider their values in the ILTH model.