The simpliciality of higher-order networks — TEI-tagged view

Nicholas W. LandrypersName, Jean-Gabriel YoungpersName, Nicole EikmeierpersName (2024date). “The simpliciality of higher-order networks.” EPJ Data Sciencetitle·j.

Object of study — inclusionterm·key structure (simplicialityterm·mth) of empirical higher-order networksterm·dom and of generative hypergraphterm·dom models

Research question — how suitable hypergraphterm·dom and simplicial-complex representations are for empirically observed interactions

Contribution — the concept of simplicialityterm·mth with three global and local measures

Full text — tagged

The reference list is not part of the text we hold for this paper. Our copy was extracted from the publisher's page and the bibliography did not survive that extraction, so the article below ends before its references. Nothing has been removed by us.

The simplicialityterm·mth of higher-order networksterm·dom Abstract Higher-order networksterm·dom are widely used to describe complex systems in which interactions can involve more than two entities at once. In this paper, we focus on inclusionterm·key within higher-order networksterm·dom, referring to situations where specific entities participate in an interaction, and subsets of those entities also interact with each other. Traditional modeling approaches to higher-order networksterm·dom tend to either not consider inclusionterm·key at all (e.g., hypergraphterm·dom models) or explicitly assume perfect and complete inclusionterm·key (e.g., simplicial complexterm·dom models). To allow for a more nuanced assessment of inclusionterm·key in higher-order networksterm·dom, we introduce the concept of “simplicialityterm·mth” and several corresponding measures. Contrary to current modeling practice, we show that empirically observed systems rarely lie at either end of the simplicialityterm·mth spectrum. In addition, we show that generative modelsterm·key fitted to these datasets struggle to capture their inclusionterm·key structure. These findings suggest new modeling directions for the field of higher-order networkterm·dom science.

Introduction A wide range of complex systems are shaped by interactions involving several entities at once: social networks are driven by group behavior [ 1 ], emails often have multiple recipients [ 2 – 4 ], molecular pathways in cells involve multi-protein interactions [ 5 ], and scientific articles involve groups of co-authors [ 6 ]. Higher-order networksterm·dom are a natural extension to networks explicitly designed to model such multi-way relationships [ 7 ].

Two mathematical representations are most commonly used to model higher-order networksterm·dom: hypergraphsterm·dom and simplicial complexesterm·dom [ 8 ]. A hypergraphterm·dom is a collection of entities (nodes) connected by interactions (hyperedges) between any number of these entities. A simplicial complexterm·dom can be considered a hypergraphterm·dom with an additional requirement known as downward closureterm·dom , which states that when an interaction exists between m entities, every possible sub-interaction also exists. This mathematical construction originates in algebraic topology and is motivated by theoretical applications; for example, forming operators such as boundary matrices to identify cycles in a dataset or the Hodge Laplacian to describe dynamical processes in higher-order networksterm·dom [ 9 , 10 ].

Recent work has grappled with the problem and consequences of choosing the proper representation—simplicial complexterm·dom, hypergraphterm·dom, or other—for a given complex system. Ref. [ 11 ], for instance, shows that synchronization can differ drastically in systems modeled with simplicial complexesterm·dom and hypergraphsterm·dom due to synchrony driven by the included edges of simplicial complexesterm·dom, and three recent studies investigate the impact of inclusionsterm·key on contagion [ 12 – 14 ]. Additionally, Ref. [ 8 ] discusses how each representation corresponds to different modeling assumptions and, thus, different analysis pipelines.

Missing from these studies are analyses of the suitability of higher-order representations for describing empirically observed interactions. When a set of interactions is given to a data scientist or modeler, the choice of representation is essentially empirical. Do the data satisfy downward closureterm·dom? (In which case, a simplicial complexterm·dom may best represent it.) Or do the data violate downward closureterm·dom? (In which case, it should be modeled as a hypergraphterm·dom.) In this paper, we introduce the concept of simplicialityterm·mth to describe the extent to which a set of interactions satisfies the downward closureterm·dom requirement. We implement this concept with three measures of the overall simplicialityterm·mth of a dataset and describe how to define local versions of these global metrics. Using these measures, we investigate the simplicialityterm·mth of empirical datasets and show that commonly analyzed higher-order interaction datasets populate the full spectrum of simplicialityterm·mth. We find that there may be large variations in the simplicialityterm·mth depending on the chosen empirical dataset and the measure of simplicialityterm·mth. Additionally, we show that the level of simplicialityterm·mth displayed by existing models is typically not captured by existing generative modelsterm·key for higher-order networksterm·dom. Hence, this paper identifies an essential gap in the current set of higher-order measures and models.

These new simplicialityterm·mth measures complement other higher-order structural measures such as community structure [ 15 – 17 ], centrality [ 18 – 20 ], clustering [ 21 , 22 ], assortativity [ 23 , 24 ], and degree heterogeneity [ 25 ]. While these measures are helpful in understanding how higher-order data is organized, they do not address how hypergraphsterm·dom relate to simplicial complexesterm·dom. Closest to our work is the recent Ref. [ 13 ], in which the authors describe the encapsulation graph, a structural description of the inclusionterm·key patterns of any given dataset, as well as a dynamical process based on inclusionterm·key that spreads from included hyperedges to larger containing hyperedges. Also relevant is Ref. [ 26 ], which defines a global metric of inclusionsterm·key. There is a large body of literature surrounding the concept of nestednessterm·dom [ 27 ], which measures the inclusionterm·key structure of unipartite and bipartite networks, particularly in ecological contexts [ 28 ]. Measures of nestednessterm·dom, however, do not use simplicial complexesterm·dom as a reference point against which to compare. In contrast, our approach describes downward inclusionsterm·key succinctly with simple global measures, offering a new perspective on how higher-order data is organized.

Mathematical definitions We encode interactions as hypergraphsterm·dom , defined as a pair H = ( V , E ) where V is a set of N = | V | entities known as nodes, and where E is a set of subsets of V encoding relationship between nodes. We refer to a set e ∈ E as a “hyperedge” or just “edge,” and define the size of an edge as | e | . In general, E could be a multiset of multisets, but in this study, we solely consider simple hypergraphsterm·dom, where each edge is only present once (no multi-hyperedges), and each edge can only contain unique entities (no self-relations).

Our analysis will focus on the prevalence of inclusionsterm·key in interaction data, so we describe this relationship formally. We say that an edge f is included in e , or f ⊂ e , if every node of f is also a node of e . Drawing from the nomenclature of algebraic topology, we also say that f is a subface of e [ 29 ].

Inclusionsterm·key naturally lead to the concept of a maximal hyperedgeterm·dom , i.e., a hyperedge ẽ that is not included in any other hyperedge. We denote the set of all the maximal hyperedgesterm·dom of H as E ˜ ( H ) .

A simplex s is then a collection of hyperedges that contains a single maximal hyperedgeterm·dom ẽ and satisfies s ≡ P ( e ˜ ) , where P ( X ) is the power set of set X . In other words, a simplex is a maximal edge with an associated collection of subfaces in which every possible subface of the maximal edge exists. A collection of simplices is a simplicial complexterm·dom S = ( V , E ) , and we say that a hypergraphterm·dom where every maximal edge is a simplex satisfies downward closureterm·dom .

Finally, we will use the notion of an induced simplicial complexterm·mth , which is the simplicial complexterm·dom constructed from the maximal edges of a hypergraphterm·dom by adding all hyperedges needed to satisfy downward closureterm·dom.

Measuring simplicialityterm·mth This paper introduces the concept of simplicialityterm·mth . Simplicialityterm·mth, broadly defined, measures the inclusionterm·key structure of a hypergraphterm·dom and how similar a higher-order dataset is to the structure of a simplicial complexterm·dom; see Fig. 1 A. There are many ways to measure this, which we outline in Sect. 2.1 . Before we get there, however, we must first introduce relevant terminology. Figure 1 An illustration of simplicialityterm·mth. Simplicialityterm·mth captures the notion of inclusionterm·key in higher-order networksterm·dom. (A) Interaction data are fully simplicial, denoted σ = 1 , when all possible included interactions exist, e.g., an interaction between three nodes appears together with interactions between all three possible pairings of these nodes. Data are minimally simplicial, denoted σ = 0 , when no included interactions are present. (B-D) Three natural measures of simplicialityterm·mth which place higher-order datasets on the simplicial spectrum between σ = 0 and σ = 1 , as described in Sect. 2.1 Measures This section introduces measures of simplicialityterm·mth. We follow a few guiding principles to design these measures. One, a simplicial complexterm·dom must be maximally simplicial with respect to any measure of simplicialityterm·mth. Two, to facilitate easier comparison between datasets, measures of simplicialityterm·mth should be normalized so that they map a hypergraphterm·dom to a value between 0 and 1. Three, if a subface is added to a hypergraphterm·dom, the simplicialityterm·mth must increase. Four, as a dataset becomes qualitatively more like a simplicial complexterm·dom, the simplicialityterm·mth should increase. And five, we stipulate that the simplicialityterm·mth of an empty hypergraphterm·dom is undefined.

There are many ways to define a measure of simplicialityterm·mth while maintaining these guiding principles. To highlight different structural elements contributing to the inclusionterm·key structure, we define three measures: the simplicial fractionterm·mth, the edit simplicialityterm·mth, and the mean face simplicialityterm·mth. These measures are all illustrated in Fig. 1 B-D.

Simplicial fractionterm·mth In a simplicial complexterm·dom, every subface is itself a simplex, so when a hypergraphterm·dom is a simplicial complexterm·dom, it contains all subsets of each of its hyperedges. The simplicial fractionterm·mth (SFterm·mth) measures the degree to which this is true, defined as the fraction of hyperedges which are also simplices.

Formally, we let H = ( V , E ) be a hypergraphterm·dom and let S = { e ∈ E | P ( e ) ⊆ E } be the set of hyperedges which are also simplices. Then, the simplicial fractionterm·mth is defined as 1 σ SFterm·mth = | S | | E | and it takes values in the range σ SFterm·mth ∈ [ 0 , 1 ] ; see Fig. 1 B.

The simplicial fractionterm·mth directly measures the number of simplices in the dataset and is, therefore, highly interpretable. However, one potential downside is that edges which almost achieve downward closureterm·dom do not count at all toward the overall simplicialityterm·mth. Furthermore, this definition weighs smaller simplices heavily, as small simplices contribute to the simplicialityterm·mth of all hyperedges that include them.

Edit simplicialityterm·mth The edit simplicialityterm·mth (ESterm·mth) is defined as the minimal number (or fraction, in the normalized case) of additional edges needed to make a hypergraphterm·dom a simplicial complexterm·dom.

Our formal definition uses the notion of an induced simplicial complexterm·mth defined in Sect. 1.1 . Given a hypergraphterm·dom H = ( V , E ) for which we want to measure the ESterm·mth, we find its maximal edges Ẽ and construct the simplicial complexterm·dom S = ( V , C ) induced on H , with C = ⋃ e ∈ E ˜ P ( e ) . The edit simplicialityterm·mth is then 2 σ ESterm·mth = | E | − | E ˜ | | C | − | E ˜ | , again satisfying σ ESterm·mth ∈ [ 0 , 1 ] ; see Fig. 1 C. We subtract the number of maximal edges from the total number of edges so that the edit simplicialityterm·mth is zero in the case of a hypergraphterm·dom with no subfaces. (We note that one can use the induced simplicial complexterm·mth to define variants of the ESterm·mth, e.g., a simplicial edit distance d ESterm·mth = | C | − | E | or a normalized distance d NES = ( | C | − | E | ) / ( | C | − | E ˜ | ) = 1 − ( | E | − | E ˜ | ) / ( | C | − | E ˜ | ) = 1 − σ ESterm·mth .) The ESterm·mth answers a slightly different question than the SFterm·mth does—it counts missing hyperedges that would make the dataset into a simplicial complexterm·dom, rather than the edges that already satisfy downward closureterm·dom. It thus offers a complementary, equally interpretable measure of simplicialityterm·mth. However, the ESterm·mth has the disadvantage of being sensitive to outliers, as a handful of large hyperedges with few inclusionsterm·key will rapidly drive σ ESterm·mth towards 0. Indeed, a hyperedge of size m without any inclusionterm·key contributes one edge to | E | but 2 m edges to | C | in the denominator of Eq. ( 2 ).

Face edit simplicialityterm·mth Finally, building upon the idea of edit simplicialityterm·mth, we define a more localized notion of simplicialityterm·mth, using the number of subfaces that must be added to the hypergraphterm·dom to make a particular face a simplex.

Given a hyperedge e , the number of edges one must add to the hypergraphterm·dom to make e a simplex is d FESterm·mth ( e ) = | P ( e ) | − | c | , where c = { f ∈ E ∣ f ⊆ e } . We can think of this quantity as an edit distance, or face edit distance . We use this quantity to define an average d ¯ FESterm·mth = 1 | F | ∑ e ∈ F d FESterm·mth ( e ) , where F is a set of edges—most commonly, F = E ˜ or E . We exclusively use F = E ˜ in this study. These quantities are on the scale of counts, and to define quantities analogous to previous simplicialityterm·mth measures, we thus introduce a per-face normalization, either on a distance scale (meaning that the quantity grows as the dataset becomes less simplicial): d ¯ NFES = 1 | F | ∑ e ∈ F d FESterm·mth ( e ) | P ( e ) | − 1 , or, similarly to previous definitions, on a simplicialityterm·mth scale: 3 σ FESterm·mth = 1 | F | ∑ e ∈ F ( 1 − d FESterm·mth ( e ) | P ( e ) | − 1 ) . We call this last measure the face edit simplicialityterm·mth (FESterm·mth). We subtract one in the denominators of both expressions so that when an edge has no subfaces, its normalized face edit distance is one.

The FESterm·mth normalizes the face edit distance as a fraction of its maximal simplicialityterm·mth. This normalization removes the dominance of large edges in the calculation of σ ESterm·mth and, in fact, exponentially down-weights the contribution of these edges. In addition, because this metric is computed on faces, this is an averaged local metric.

Important considerations when measuring simplicialityterm·mth Before we turn to applications in Sect. 3 , let us discuss three design choices that may impact the conclusion we reach about the simplicialityterm·mth of a dataset.

First, we note that the formal definition of a simplicial complexterm·dom can be unnecessarily strict when used to represent perfect inclusionterm·key structures. By definition, a simplex always contains singletons (edges comprising a single node) and the empty set. Several datasets will not include such interactions by construction. One example is proximity datasets, where edges encode proximity events in which two or more nodes become in close contact during the observation period. Because of their spatial nature, these datasets are often very dense and contain many inclusionsterm·key [ 7 ]. Yet, according to the standard definition, these will never be simplicial complexesterm·dom due to the absence of singletons. Another example is email datasets, which also do not contain singletons unless one includes emails that individuals send to themselves. Because we define our notion of inclusionterm·key in terms of simplicial complexesterm·dom, our measures will label these datasets as having no inclusionterm·key structure whatsoever.

To circumvent this issue, we use a relaxed definition of downward closureterm·dom that excludes singletons wherever it makes sense. The relaxation uses the notion of a size-restricted power set P K ( X ) , where K is a set of integers, defined as 4 P K ( X ) = { x ∈ P ( X ) | | x | ∈ K } . For example, given an edge e of size n , P { 2 , … , n − 1 } ( e ) is the set of 2 | e | − | e | − 2 subfaces of e excluding the empty set, all singletons (sets of size one), and the edge e itself. Relaxed measures of simplicialityterm·mth follow by substituting P ( X ) for P K ( X ) in all the measures of Sect. 2.1 . Hence, for example, we obtain a relaxation of σ SFterm·mth by replacing the definition of S , the set of the hyperedges of H that are also simplices, by S = { e ⊆ E ∣ P K ( e ) ⊆ E } ), where K = { 2 , … , | e | } .

The results shown in Sect. 3 are all calculated using size restrictions to exclude singletons and the empty set. However, we note that this technique can be used more generally to exclude any interaction sizes deemed unimportant, anomalous, or problematic [ 30 ]; or, conversely, to be more strict and to include singletons (say, when analyzing academic co-authorship networks, where single-author papers can meaningfully impact the inclusionterm·key structure of the dataset).

Second, we observe that special hyperedges we call “minimal faces” may significantly skew the simplicialityterm·mth of a dataset. The minimal faces of a hypergraphterm·dom H are the edges of the minimal size, i.e., | e | = min ( K ) , where K is the set of sizes in the size-restricted powerset (In a traditional simplicial complexterm·dom, the minimal faces are singletons). With the size restrictions in place, the minimal faces of a hypergraphterm·dom are always simplices because, by definition, there are no smaller edges for these edges to include. We argue that when measuring the simplicialityterm·mth of a dataset, it is most meaningful to focus on the faces for which inclusionterm·key is possible , and so we exclude these minimal faces when counting potential simplices.

Note that this design choice operates differently from the size restriction imposed by the modified power set introduced in Eq. ( 4 ); in that context, we argued for ignoring edges that can prevent other edges from being simplices, while here we suggest that counting minimal faces as potential simplices will strongly affect the value of simplicialityterm·mth. Our strategy is as follows. For SFterm·mth, this means that both S and E exclude the minimal-sized edges. For ESterm·mth, we exclude maximal faces that are also minimal faces when constructing the minimal simplicial complexterm·dom. And for FESterm·mth, we only average over maximal edges that are not minimal faces.

Third and finally, since the number of potential subfaces of a hyperedge grows exponentially with its size, computational issues prevent us from applying our measures to large hyperedges. For this reason, we select a maximum face size k (we use k = 11 throughout), again using the size restriction to define our metrics. This drops information about large hyperedges but speeds up computation drastically in practical applications.

Local simplicialityterm·mth Simplicialityterm·mth, up to this point a global metric, can also be localized on a smaller subset of the higher-order networkterm·dom to yield information about its local structure. The various face-centric measures used in our construction of the FESterm·mth provide this information at the level of faces. But for more flexibility, we also use subhypergraphs to define nodal simplicialityterm·mth measures of our global measures. More specifically, given a hypergraphterm·dom H = ( V , E ) and a node v ∈ V , we define the neighborhood of v as n ( v ) = { u ∈ V ∣ u , v ∈ e ∈ E } and the associated subsets V ˆ = v ∪ n ( v ) and E ˆ = { e ∈ E ∣ e ⊆ V ˆ } . Then the simplicialityterm·mth of node v is the simplicialityterm·mth defined on the subhypergraph H ˆ = ( V ˆ , E ˆ ) induced on the neighborhood of v . Note that when v is an isolated node or when Ê only contains minimal faces and we do not consider these potential simplices, the nodal simplicialityterm·mth will be undefined.

Results Empirical datasets As the first demonstration of the simplicialityterm·mth measures, we analyze empirical higher-order datasets from several general domains. All datasets are obtained from the xgi-data repository [ 31 ] and are openly available. Following the considerations highlighted in Sect. 2.2 , we preprocess these datasets to remove singletons, multiedges, and isolated nodes. In addition, for computational feasibility, we only consider hyperedges of size 11 (order, defined as the size minus one, of 10) and smaller. Basic structural properties of the pre-processed datasets are shown in Table 1 . Table 1 Properties of empirical datasets and their simplicialityterm·mth. | V | , | E | , 〈 k 〉 , 〈 s 〉 , σ SFterm·mth , σ ESterm·mth , and σ FESterm·mth denote the number of nodes, the number of hyperedges, the mean degree, the mean edge size, the simplicial fractionterm·mth (SFterm·mth), edit simplicialityterm·mth (ESterm·mth), and the face edit simplicialityterm·mth (FESterm·mth), respectively Dataset | V | | E | 〈 k 〉 〈 s 〉 σ SFterm·mth σ ESterm·mth σ FESterm·mth Proximity datasets contact-primary-school 242 12,704 52.50 2.42 0.85 0.88 0.94 contact-high-school 327 7,818 23.91 2.33 0.81 0.91 0.92 hospital-lyon 75 1,824 24.32 2.43 0.91 0.94 0.97 Email datasets email-enron 143 1,442 10.08 2.97 0.31 0.04 0.50 email-eu 967 23,729 24.54 3.12 0.32 0.04 0.52 Biological datasets diseasome 516 314 0.61 3.00 0.00 0.02 0.04 disgenenet 1,982 760 0.38 5.14 0.00 0.00 0.01 ndc-substances 2,740 4,754 1.74 5.16 0.02 0.00 0.07 Other congress-bills 1,715 58,788 34.28 4.95 0.03 0.00 0.10 tags-ask-ubuntu 3,021 145,053 48.01 3.43 0.15 0.11 0.46 Our sample of datasets contains various types of complex systems. We analyze three proximity datasets [ 1 , 2 , 31 – 33 ] (contact-primary-school, contact-high-school, and hospital-lyon), which are collected via proximity sensors with a range of roughly 1 meter. Nodes are individuals, and an edge is created from a proximity event, where two individuals are closer than 1 meter apart. To create a higher-order dataset, each maximal clique is converted into a hyperedge at each time step. Unique to proximity datasets are their geometrical constraints, and because of the proximity sensor range, 5-hyperedges are the largest edges present in these datasets. We also include two datasets of email interactions [ 2 – 4 , 34 ]: email-enron and email-eu. In both cases, the nodes are email addresses, and the hyperedges are emails, at the defunct company Enron in the former case and a large European research institution in the latter. Three datasets are loosely associated with biological processes [ 2 , 35 , 36 ]: diseasome, disgenenet, and ndc-substances. In these datasets, nodes are compounds, diseases, or genes, while hyperedges are interactions amongst these to represent pharmaceuticals, symptoms, and diseases. Finally, we include two miscellaneous datasets as well: tags-ask-ubuntu [ 2 ] higher-order dataset in which a node is a tag on Stack Overflow, and an edge is a question to which the tags are associated; and the congress-bills dataset [ 2 , 37 , 38 ] where nodes are congresspeople and edges represent the sponsoring and co-sponsoring congresspeople for a particular bill.

Numerical values of the simplicialityterm·mth measures are shown in Table 1 for all of these datasets. We find that values for simplicialityterm·mth fill the spectrum from 0 to 1, depending on the data. The proximity datasets have large simplicialityterm·mth for all three measures, while the biological datasets have low simplicialityterm·mth for all three measures. The email datasets have a very small ESterm·mth simplicialityterm·mth, with moderate simplicialityterm·mth for the other two measures. (And since we use size restrictions to exclude singletons, the lack or absence of emails sent to oneself does not affect this assessment.) Similarly, the tags-ask-ubuntu dataset has a range of simplicialityterm·mth values depending on which measure we consider. This shows that the measures we have defined in Sect. 2.1 capture different features of the inclusionterm·key structure.

While the measures give differing perspectives on the simplicialityterm·mth of each dataset, we verify that they broadly agree with a correlation analysis. The Pearson correlation coefficient is ρ = 0.97 between the SFterm·mth and ESterm·mth, ρ = 0.95 between the SFterm·mth and FESterm·mth, and ρ = 0.90 between the ESterm·mth and FESterm·mth (all significant at the p = 0.001 level). Hence, the values are closely and linearly related in our sample. They also order datasets similarly, from the least to most simplicial, since the Spearman rank-order correlation coefficient is ρ = 0.89 between SFterm·mth and ESterm·mth, ρ = 0.997 between SFterm·mth and FESterm·mth, and ρ = 0.90 between ESterm·mth and FESterm·mth (all significant at the same level).

Although our correlation analysis confirms that these measures roughly capture the same concepts, the datasets where they depart from one another highlight their key differences. In our experiments, these differences are due to features such as large edges with few included edges, many edges that are mostly closed downward, and different edge size distributions. Networks of organizational email messages are examples of the first case, where very large organization- or department-wide emails may be sent with no guarantee that emails are also sent between every possible subgroup of individuals. In this case, we would expect ESterm·mth to be extremely low while the SFterm·mth need not be low. Proximity networks are examples of the second case, i.e., dense downward-closed datasets. We see this by noting that the SFterm·mth is not 1, while both ESterm·mth and FESterm·mth are close to 1 due to the SFterm·mth penalizing almost-simplicial edges. Lastly, the edge size distribution has strong implications on all measures; for the same average edge size and number of edges, increasing both the number of small and large edges will affect the SFterm·mth and ESterm·mth measures. For ESterm·mth, the large edges will exponentially increase the number of subfaces needed to create a simplicial complexterm·dom, driving the simplicialityterm·mth to zero. In contrast, increasing the number of small edges can create more small simplices, increasing SFterm·mth.

Generative modelsterm·key of higher-order networksterm·dom To complement our analysis of empirical data, we also examine the simplicialityterm·mth of synthetic data generated with generative modelsterm·key for higher-order networksterm·dom.

We focus on models of hypergraphsterm·dom designed to describe and analyze arbitrary higher-order structures. There are several random hypergraphterm·dom models, including, among many classes of models, preferential attachment models [ 39 – 42 ], models with community structure [ 15 , 43 – 46 ], models with specified degree and size sequences [ 23 , 43 ], Erdös-Rényi models [ 47 , 48 ], models with latent nodal variables governing edge formation [ 49 ], and geometric models [ 42 , 50 , 51 ]. Higher-order random models that are commonly fit to empirical datasets include the configuration model [ 23 ], the bipartite Chung-Lu model [ 23 , 43 ], and the bipartite degree-corrected stochastic block modelterm·mth [ 52 ]. See Ref. [ 7 ] for an extensive overview. Overwhelmingly, generative hypergraphterm·dom models lack explicit control over the inclusionterm·key structure of hyperedges, so there are often relatively few simplices.

We focus our analysis on three models: the configuration model [ 23 ], the bipartite Chung-Lu model [ 43 ], and the bipartite degree-corrected stochastic block modelterm·mth (biSBMterm·mth) [ 52 ].

We fit each model to the empirical datasets of Table 1 , use the fitted models to generate a distribution of higher-order networksterm·dom (the posterior predictive distribution in Bayesian parlance), and analyze the resulting distribution of simplicialityterm·mth values.

In all cases, when sampling synthetic higher-order networksterm·dom from the three generative modelsterm·key, we generate 10 3 realizations of each model for each empirical dataset. We use the double edge-swap algorithm presented in Ref. [ 23 ] to sample from the configuration model and performed 10 × | E | edge swaps, roughly in accordance with [ 53 ]. For the bipartite Chung-Lu model [ 43 ], we extract the degree and edge size sequences and then use a bipartite variation of the algorithm introduced in Ref. [ 54 ] and available in XGI [ 55 ] to sample from this model. Lastly, when sampling from the biSBMterm·mth, we used a Markov chain Monte Carlo method with a bipartite prior using the algorithm described in Ref. [ 52 ].

All results are reported in Fig. 2 . Overwhelmingly, we see that the generative modelsterm·key cannot accurately capture the simplicialityterm·mth of datasets when they have a non-trivial inclusionterm·key structure. While it does not reproduce the correct values, the hypergraphterm·dom configuration model consistently captures the inclusionterm·key structure better than the biSBMterm·mth and the bipartite Chung-Lu model, irrespective of the simplicialityterm·mth measure used. This may be due to the exact specification of the degree and edge size sequences; the Chung-Lu model and biSBMterm·mth only match these sequences in expectation. Figure 2 The simplicialityterm·mth of empirical datasets and their fitted generative modelsterm·key. The simplicialityterm·mth of empirical datasets compared with samples from three higher-order generative modelsterm·key: the hypergraphterm·dom configuration model [ 23 ], the bipartite Chung-Lu model [ 43 ], and the bipartite degree-corrected stochastic block modelterm·mth [ 52 ]. The violin plots indicate the simplicialityterm·mth of samples drawn from the fitted generative modelsterm·key, and the solid vertical lines indicate the mean of the distributions. Empirical results are shown with a solid circle Local measures of simplicialityterm·mth As a final demonstration, we apply our local measures of simplicialityterm·mth to the dataset of emails sent by Enron employees (142 nodes and 1126 hyperedges, filtered to include interactions of sizes 2 and 3). Results are shown in Fig. 3 . Figure 3 The local simplicialityterm·mth of an empirical dataset. The local (A) simplicial fractionterm·mth, (B) edit simplicialityterm·mth, and (C) face edit simplicialityterm·mth of the email-enron dataset filtered to include interactions of sizes 2 and 3. The colors of the histogram bars match the node colors on their corresponding network visualization. Nodes for which the local simplicialityterm·mth is undefined are colored in grey Focusing on the histograms first, we find that the SFterm·mth has the most variability and that the FESterm·mth covers a similarly large range. In contrast, the ESterm·mth tells us that nearly every neighborhood is strongly simplicial. This is expected behavior because the ESterm·mth relies on a simplicial complexterm·dom induced on the ego-hypergraph; the size of the largest hyperedges in this ego-hypergraph can be substantially smaller than that of the largest hyperedges in the whole hypergraphterm·dom. As a result, the denominator of Eq. ( 2 ) is reduced, increasing the local ESterm·mth systematically. In contrast, when we take a subset of nodes to form an ego-hypergraph, it is easy to omit a small subface shared by many hyperedges, thus leading to a very small SFterm·mth (and, similarly, to a small FESterm·mth).

Turning to the spatial distribution of simplicialityterm·mth shown in the insets, we see that the SFterm·mth and FESterm·mth find a region of high simplicialityterm·mth at the network’s core with regions of low simplicialityterm·mth on its edges. In fact, these two measures are largely in agreement, with a Pearson correlation coefficient of ρ = 0.84 between the local SFterm·mth and FESterm·mth. (The correlation drops to ρ = 0.6 when comparing the SFterm·mth and ESterm·mth). We also observe several nodes for which simplicialityterm·mth is undefined. These nodes are only connected via minimal faces in their ego-hypergraphs, and these faces are excluded when calculating both potential and actual simplices.

Finally, inspecting Fig. 3 , we notice that, in this case, nodes of similar simplicialityterm·mth tend to be connected to one another. To quantify this observation, we define the simplicial assortativityterm·mth as the Pearson correlation coefficient of the simplicialityterm·mth of pairs of nodes connected by at least one hyperedge. More formally, we use the unweighted adjacency matrix of the hypergraphterm·dom, A , defined as A i j = { 1 , [ BB T ] i j > 0 and i ≠ j , 0 , otherwise, where B is the incidence matrix of the hypergraphterm·dom, such that B i j = 1 if node edge j is incident on node i . The simplicial assortativityterm·mth, ρ , can then be defined as 5 ρ = ∑ i , j A i j ( σ i − E [ σ ] ) ( σ i − E [ σ ] ) Var [ σ ] , where σ i is the local simplicialityterm·mth of node i according to one of our measures. The simplicial assortativityterm·mth for SFterm·mth, ESterm·mth, and FESterm·mth are denoted ρ SFterm·mth , ρ ESterm·mth , and ρ FESterm·mth respectively. This coefficient is equivalent to the assortativity coefficient [ 56 ] of the local simplicialityterm·mth on the unweighted pairwise projection of the hypergraphterm·dom.

One should expect local simplicialityterm·mth to be assortative as any given subface contributes to the simplicialityterm·mth of all their nodes. Table 2 shows that the situation is a bit more nuanced. For tags-ask-ubuntu, FESterm·mth is weakly assortative, SFterm·mth is weakly disassortative, and ESterm·mth is strongly disassortative. It is particularly striking that despite the hospital-lyon dataset being highly simplicial (as seen in Fig. 2 ), it is also weakly disassortative. Table 2 The simplicial assortativityterm·mth of each dataset filtered to only include interactions of sizes two and three for computational tractability Dataset ρ SFterm·mth ρ ESterm·mth ρ FESterm·mth Proximity datasets contact-primary-school 0.15 0.17 0.14 contact-high-school 0.22 0.37 0.24 hospital-lyon −0.02 −0.01 −0.01 Email datasets email-enron 0.29 0.29 0.24 email-eu 0.19 0.16 0.16 Biological datasets ndc-substances 0.56 0.54 0.69 diseasome N/A 0.28 0.68 disgenenet N/A 0.28 0.78 Other congress-bills 0.78 0.33 0.75 tags-ask-ubuntu −0.03 −0.24 0.04 Conclusion In this paper, we have introduced measures to summarize the inclusionterm·key structure—the simplicialityterm·mth—of hypergraphsterm·dom. We have presented three measures of simplicialityterm·mth but recognize that other definitions of simplicialityterm·mth may also prove useful. We have discussed how the simplicialityterm·mth of higher-order datasets depends on many factors, including, but not limited to, the manner in which the dataset was collected, its domain, and the measure of simplicialityterm·mth. When fitting common generative modelsterm·key to several empirical higher-order networksterm·dom, we found that the simplicialityterm·mth of the original dataset is often much higher than the simplicialityterm·mth of the posterior predictive distribution of fitted models by any measure of simplicialityterm·mth. Measuring the simplicial assortativityterm·mth indicates that the simplicialityterm·mth displays different levels of localization.

We hope this study will serve as a starting point for network scientists aiming to characterize higher-order networkterm·dom datasets and look forward to future work developing these methods along a number of dimensions of interest.

First, we presented global- and node-level definitions of simplicialityterm·mth, but other scales of interaction may yield further insights into the inclusionterm·key structure of the data [ 27 ]. Future work could explore mesoscale measures of simplicialityterm·mth that describe how, for example, simplicialityterm·mth varies between communities. One could also obtain the largest simplicial component or the set of simplicial components in a hypergraphterm·dom. In addition, we have restricted ourselves to unweighted simplicial complexesterm·dom, but one might consider extending these notions to weighted simplicial complexesterm·dom [ 57 ].

Second, our approach complements the existing literature on nestednessterm·dom in bipartite networks [ 27 ], which shows that nestednessterm·dom exists for a wide variety of unipartite and bipartite networks [ 58 ]. Existing work shows that nestednessterm·dom is important for the function of networks in many domains [ 28 , 59 – 61 ], and comparing these findings from the perspective of simplicialityterm·mth could offer additional insights from both a structural and mechanistic perspective.

Finally, we have shown a disparity between the simplicialityterm·mth of artificial datasets and observed ones. Our findings should thus inform new higher-order networkterm·dom models that specify the inclusionterm·key structure of the network and can be fit to empirical higher-order datasets.