{'fraction_non_alphanumeric': 0.04899777282850779, 'fraction_numerical': 0.015383021701973377, 'mean_word_length': 4.251019853141147, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Higher-order clustering in networks

A fundamental property of complex networks is the tendency for edges to cluster. The extent of the clustering is typically quantified by the clustering coefficient, which is the probability that a length-2 path is closed, i.e., induces a triangle in the network. However, higher-order structures beyond triangles are crucial to understanding complex networks, and the clustering behavior with respect to such higher-order patterns is not well understood. Here we introduce higher-order clustering coefficients that measure the closure probability of higher-order network structures and provide a more comprehensive view of how the edges of complex networks cluster. Our higher-order clustering coefficients are a natural generalization of the traditional clustering coefficient. We derive several properties about higher-order clustering coefficients and analyze them under common random graph models. Finally, we use higher-order clustering coefficients to gain new insights into the structure of real-world networks from several domains.

Networks are a fundamental tool for understanding and modeling complex physical, social, informational, and biological systems [1]. Although such networks are typically sparse, a recurring trait of networks throughout all of these domains is the tendency of edges to appear in small clusters or cliques [2,3]. In many cases, such clustering can be explained by local evolutionary processes. For example, in social networks, clusters appear due to the formation of triangles where two individuals who share a common friend are more likely to become friends themselves, a process known as triadic closure [2,4]. Similar triadic closures occur in other networks: in citation networks, two references appearing in the same publication are more likely to be on the same topic and hence more likely to cite each other [5] and in co-authorship networks, scientists with a mutual collaborator are more likely to collaborate in the future [6]. In other cases, local clustering arises from highly connected functional units operating within a larger system, e.g., metabolic networks are organized by densely connected modules [7].
The clustering coefficient quantifies the extent to which edges of a network cluster. The clustering coefficient is defined as the fraction of length-2 paths, or wedges, that are closed with a triangle [3,8] (Fig. 1, C 2 ). In other words, the clustering coefficient measures the probability of triadic closure in the network. However, the clustering coefficient is inherently restrictive as it measures the closure pattern of just one simple structure-the triangle. Higher-order structures such as larger cliques are crucial to the structure and function of complex networks [9,10]. For example, 4-cliques reveal community structure in word association and proteinprotein interaction networks [11] and cliques of size 5-7 are more frequent than triangles in many real-world networks with respect to certain null models [12]. However, the extent of clustering of such higher-order structures has not been well understood nor quantified.
Here we give an alternative interpretation of the clustering coefficient that will later allow us to generalize 1. Start with 2. Find an adjacent edge 3. Check for an an ℓ-clique to form an ℓ-wedge FIG. 1: Overview of higher-order clustering coefficients as clique expansion probabilities. The ℓth-order clustering coefficient C ℓ measures the probability that an ℓ-clique and an adjacent edge, i.e., an ℓ-wedge, is closed, meaning that the ℓ − 1 possible edges between the ℓ-clique and the outside node in the adjacent edge exist to form an (ℓ + 1)-clique.
it and quantify clustering of higher-order network structures. We view clustering as a tendency for lower-order structures, such as edges, to form higher-order structures, such as triangles (Fig. 1). As a specific example, first consider a 2-clique K in a graph G (that is, a single edge K). Now, expand the clique K by considering any edge e adjacent to K, i.e., e and K share exactly one node. This expanded subgraph forms a wedge (length-2 path). The global clustering coefficient C of G [8,13] can then be defined as the fraction of wedges that are closed, meaning that the 2-clique and adjacent edge induce a (2 + 1)-clique, or a triangle ( Fig. 1, C 2 ). Formally, where K 3 is the set of 3-cliques (triangles), W is the set of wedges, and the coefficient 6 comes from the fact that each 3-clique closes 6 wedges (the 6 ordered pairs of edges in the triangle). Given this novel interpretation of the global clustering coefficient, we can also reinterpret the local clustering coefficient [3]. Each wedge consists of a 2-clique and adjacent edge (Fig. 1), and we call the unique node in the intersection of the 2-clique and adjacent edge the center of the wedge. Under this view, the local clustering clustering coefficient of a node u can be defined as the fraction of wedges centered at u that are closed: where K 3 (u) is the set of 3-cliques containing u and W (u) is the set of wedges with center u (if |W (u)| = 0, we say that C(u) is undefined). The average clustering coeffi-cientC is the mean of the local clustering coefficients, where V is the set of nodes in the network where the local clustering coefficient is defined. Our alternative interpretation of the clustering coefficient, described above as a form of clique expansion, leads to a natural generalization to higher-order structures. Instead of expanding 2-cliques to 3-cliques, we expand ℓ-cliques to (ℓ + 1)-cliques ( Fig. 1, C 3 and C 4 ). Formally, we define an ℓ-wedge to consist of an ℓ-clique and an adjacent edge. Then we define the global ℓthorder clustering coefficient C ℓ as the fraction of ℓ-wedges that are closed, meaning that they induce an (ℓ+1)-clique in the network. We can write this as where K ℓ+1 is the set of (ℓ + 1)-cliques, W ℓ is the set of ℓ-wedges, and the coefficient ℓ+1 ℓ ℓ 1 comes from the fact that each (ℓ + 1)-clique closes that many wedges.
We also define higher-order local clustering coefficients: where K ℓ+1 (u) is the set of (ℓ + 1)-cliques containing u, W ℓ (u) is the set of ℓ-wedges with center u, and the coefficient ℓ ℓ−1 comes from the fact that each (ℓ + 1)clique containing u closes that many ℓ-wedges in W ℓ (u).
An important benefit of this generalization is that it carries a natural probabilistic interpretation. In particular, we can interpret C ℓ (u) as the probability that a wedge w chosen uniformly at random from all wedges centered at u is closed: The ℓth-order clustering coefficient of a node is defined for any node that is the center of at least one ℓ-wedge, and the average ℓth-order clustering coefficient is the mean of the local clustering coefficients: where V ℓ is the set of nodes that are the centers of at least one ℓ-wedge.
To further understand higher-order clustering coefficients and to derive an algorithm for computing them, we study the structure of the 1-hop neighborhood N u of a given node u. Here, N u has d u nodes, where d u is the degree of u in G, and edge set Any ℓ-clique in G containing node u corresponds to a unique (ℓ − 1)-clique in N u , and specifically for ℓ = 2, any edge (u, v) corresponds to a node v in N u . Therefore, each ℓ-wedge centered at u corresponds to an (ℓ − 1)-clique K and one of the d u − ℓ + 1 nodes outside K (i.e., in N u \K). Letting K ℓ (N u ) be the set of ℓ-cliques in N u , we obtain By combining Eqs. 5, 8, and 9, we obtain the formula for computing the local higher-order clustering coefficient: Eq. 11 leads to an algorithm for computing local higherorder clustering coefficients by enumerating all (ℓ + 1)cliques and ℓ-cliques. The computational complexity of the algorithm is thus bounded by the time to enumerate all (ℓ + 1)-and ℓ-cliques in G. For the global ℓth-order clustering coefficient, we can use the fact that |W ℓ | = u∈V |W ℓ (u)|, and it suffices to count the total number of (ℓ + 1)-cliques and enumerate all ℓ-cliques. We find that fast clique enumeration algorithms [14] work well in practice.
Eq. 10 also highlights another important probabilistic interpretation of the local ℓth-order clustering coefficient. If we uniformly at random select an (ℓ − 1)-clique K from N u and then also uniformly at random select a node v from N u outside of this clique, then C ℓ (u) is the probability that these ℓ nodes form an ℓ-clique (c.f. Eq. 6): Moreover, if we condition on observing an ℓ-clique, then the ℓ-clique itself is selected uniformly at random from all ℓ-cliques in N u . Therefore, C ℓ−1 (u)·C ℓ (u) is the probability that an (ℓ−1)-clique and two nodes selected uniformly at random from N u form an (ℓ + 1)-clique. Applying this recursively gives In other words, the product of the higher-order local clustering coefficients of node u up to order ℓ is the ℓ-clique density amongst u's neighbors. (We can also derive this formally by expanding Eq. 10.) Next we analyze the relationships between local higherorder clustering coefficients of different orders. For any ℓ ≥ 3, C ℓ (u) satisfies the bound The lower bound is tight, even if C 2 (u) is constant, when N u is (ℓ − 1)-partite (Fig. 2, middle). To derive the upper bound, consider the 1-hop neighborhood N u , and let δ ℓ (N u ) = |K ℓ (N u )|/ du ℓ denote the ℓ-clique density of N u . The Kruskal-Katona theorem [15,16] implies that Combining this with Eq. 10 gives (14) where the last equality uses the fact that C 2 (u) is the edge density of N u . The upper bound is tight if N u consists of a clique and isolated nodes (Fig. 2, right). Furthermore, by adjusting the ratio of the number of nodes in the clique to the number of isolated nodes in N u , we can construct a family of graphs such that C 2 (u) may take any value in [0, 1] and C 3 (u) = C 2 (u) as d u → ∞.
Next, we analyze higher-order clustering coefficients in two common random graph models: the classical Erdős-Rényi model with edge probability p (i.e., the G n,p model [17]) and the small-world model [3].
In the G n,p model, we first observe that any ℓ-wedge is closed if and only if the ℓ − 1 possible edges between the ℓ-clique and the outside node in the adjacent edge exist to form an (ℓ + 1)-clique. Each of the ℓ − 1 edges exist independently with probability p in the G n,p model, which means that the higher-order clustering coefficients for G n,p graphs satisfy E[C ℓ ] = p ℓ−1 . By the same argument, E[C ℓ (u)] = p ℓ−1 for any node u and E[C ℓ ] = p ℓ−1 . Furthermore, for G n,p graphs we also obtain relationship between clustering coefficients of different orders: as C 2 (u) measures the edge density of N u . Notice that even if the second-order clustering coefficient is large, the ℓth-order clustering coefficient will still decay exponentially in ℓ.
We also study higher-order clustering in the smallworld random graph model [3]. The model begins with a ring network where each node connects to its 2k nearest neighbors. Then, for each node u and each of the k edges (u, v) with v following u "clockwise" in the ring, the edge is "rewired" to (u, w) with probability p, where w is chosen uniformly at random.
With no rewiring (p = 0) and k ≪ n,C 2 ≈ 3/4 [3]. As p increases, the average clustering coefficientC 2 slightly decreases until a phase transition near p = 0.1, wherē C 2 decays to 0 [3] (also see Fig. 3). Here, we generalize these results for higher-order clustering coefficients. Specifically, when p = 0, we can analytically show that for any ℓ ≥ 2. Thus,C ℓ decreases as ℓ increases. Furthermore, we observe the same behavior as forC 2 when adjusting the rewiring probability p (Fig. 3). Regardless of ℓ, the phase transition happens near p = 0.1. To derive Eq. 16, we first label the 2k neighbors of u as 1, 2, . . . , 2k by their clockwise ordering in the ring. Next, we define the span of any ℓ-clique containing u as the difference between the largest and smallest label of the ℓ − 1 nodes in the clique other than u. Note that the span s of every ℓ-clique satisfies ℓ − 2 ≤ s ≤ k − 1, and we can find 2k − 1 − s pairs of labels (i, j) such that 1 ≤ i, j ≤ 2k and j − i = s. Finally, for every such pair (i, j), there are s−1 ℓ−3 choices of ℓ − 3 nodes between i  For the real-world networks, we also measure the clustering coefficientsC ℓ with respect to two null models: a Configuration Model (CM) that produces random graphs with the same degree distribution as in the real graph [20,21], and Maximally Random Clustered Networks (MRCN) that preserve the degree distribution as well asC2 [22,23]. For the random networks, we report the mean over 100 samples. An asterisk (*) denotes when the value in the original network is at least four standard deviations from the mean.
and j which will form an ℓ-clique together with nodes u, i, and j. Therefore, Eq. 16 then follows from Eq. 10. Lastly, we apply our framework to five synthetic and real-world networks to study their higher-order clustering: (1) an Erdős-Rényi graph with n = 1, 000 nodes and edge probability p = 0.2; (2) a small-world network with n = 20, 000 nodes, k = 10 edges per node, and rewiring probability p = 0.1; (3) the neural network of the nematode worm C. elegans [3], where we take the edges in this network to be undirected; (4) the friendships between Stanford students on Facebook from September 2005 [18]; and (5) a co-authorship network constructed from papers posted to the Astrophysics category on arXiv [19]. Table I lists the higher-order clustering coefficients for ℓ = 2 and 3. Eq. 15 and Fig. 3 say thatC 3 should be smaller thanC 2 for the Erdős-Rényi and small-world models and indeed this is the case. Moreover,C 3 <C 2 also holds for the three real-world networks. (Although not listed in Table I,C 4 <C 3 in all five networks as well.) Thus, when averaging over nodes, higher-order cliques are less likely to close in both the synthetic and real-world networks.
For the three real-world networks, we also measure the higher-order clustering coefficients with respect to two null models (Table I). First, we use the Configuration Model (CM) that samples uniformly at random from simple graphs with the same degree distribution [20,21]. In real-world networks,C 2 is much larger than expected with respect to the CM null model (Table I). We also find that the same holds forC 3 .
Second, we use a null model that samples graphs that preserve both the degree distribution andC 2 . Specifically, these are samples from an ensemble of exponential graphs where the Hamiltonian measures the absolute value of the difference inC 2 between the original network and the sampled network [22]. Such samples are referred to as Maximally Random Clustered Networks (MRCN) and are sampled with a simulated annealing procedure [23]. ComparingC 3 between the realworld and the null network, we observe different behavior in higher-order clustering. The C. elegans network has less than expected higher-order clustering in terms ofC 3 with respect to the MRCN null model (Table I). On the other hand, the Facebook friendship and co-authorship network exhibit higher than expectedC 3 . (We also observed the same patterns forC 4 .) Thus, while all three of the real-world networks exhibit clustering in the classical sense of triadic closure, only the friendship and coauthorship networks exhibit higher-order clustering.
The lack of higher-order clustering in the C. elegans network agrees with previous results that 4-cliques are under-expressed in parts of C. elegans, while open 3wedges related with cooperative information propagation are over-expressed [9,24,25]. This also provides credence for the "3-layer" model of C. elegans [25]. The observed clustering in the friendship network is consistent with prior work showing the relative infrequency of open ℓwedges in many Facebook network subgraphs with respect to a null model accounting for triadic closure [26]. Co-authorship networks are known to have large clustering in the traditional sense, which is partially attributed to papers with multiple authors that form cliques [27]. It is natural that these cliques contribute to higher-order clustering as well. Fig. 4 (top row) plots the joint distribution of C 2 (u) and C 3 (u). The lower trend line represents random behavior (i.e., the behavior of Erdős-Rényi in expectation; see Eq. 15) and the upper trend line denotes the maximum possible value of C 3 (u) given C 2 (u) (Eq. 13). For many nodes in the C. elegans network, local clustering is nearly random, i.e., resembles the Erdős-Rényi joint distribution. This provides further evidence that the C. elegans neural network lacks higher-order clustering. In the co-authorship network, there are many nodes u with a large value of C 2 (u) that have an even larger value of C 3 (u) near the upper bound of Eq. 13 (inset of Fig. 4, top row, fifth column). Thus, our bound is tight in practice. We emphasize that this does not imply that these nodes are simply members of large cliques (if the 1-hop neighborhood of u is a clique, then C 2 (u) = C 3 (u) = 1). Instead, some nodes appear in both cliques and also as the center of star-like patterns, as in Fig. 2 (right).
We also compute the higher-order clustering coefficient as a function of node degree (Fig. 4, bottom row). In the Erdős-Rényi, small-world, and C. elegans networks, there is a distinct gap between the average higher-order clustering coefficients for nodes of all degrees. Thus, the observed decrease in clustering as the order increases is independent of degree. In the Facebook friendship network, C 2 (u) is larger than C 3 (u) and C 4 (u) on average for nodes of all degrees, but C 3 (u) and C 4 (u) are roughly the same for nodes of all degrees, which means that 4-cliques and 5-cliques close at roughly the same rate, independent of degree, albeit at a smaller rate than traditional triadic closure. In the co-authorship network, nodes u have roughly the same C ℓ (u) for ℓ = 2, 3, 4, which means that ℓ-cliques close at about the same rate, independent of ℓ. We note that the global clustering coefficient C ℓ slightly increases with ℓ in this network (C 2 = 0.32, C 3 = 0.33, C 4 = 0.36), which means there are nodes participating in a large clique and also serving as the center of a star-like pattern (Fig. 2, right), which causes the global clustering coefficient to increase with the order.
To summarize, we have proposed a methodology for higher-order clustering coefficients to study higher-order closure patterns in networks, which generalizes the widely used clustering coefficient that measures triadic closure. Prior efforts in generalizing clustering coefficients have focused on shortest paths [28], cycle formation [29], and triangle frequency in k-hop neighborhoods [30,31], none of which capture the closure patterns of higher-order cliques. Our methodology gives new insights into the clustering behavior of both real-world networks and random graph models, and our theoretical analysis provides intuition for the way in which higher-order clustering coefficients describe local clustering in graphs. Overall, higher-order clustering coefficients are simple but effective measurements for strengthening our understanding of complex networks from both empirical and theoretical perspectives.