The simpliciality of higher-order networks

We encode interactions as hypergraphs, defined as a pair \(\mathbf{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\in 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 hypergraphs, 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 inclusions in interaction data, so we describe this relationship formally. We say that an edge f is included in e, or \(f \subset 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].

Inclusions naturally lead to the concept of a maximal hyperedge, i.e., a hyperedge ẽ that is not included in any other hyperedge. We denote the set of all the maximal hyperedges of H as \(\widetilde{E}(\mathbf{H})\).

A simplex s is then a collection of hyperedges that contains a single maximal hyperedge ẽ and satisfies \(s \equiv \mathcal{P}(\widetilde{e})\), where \(\mathcal{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 complex \(\mathbf{S}=(V, E)\), and we say that a hypergraph where every maximal edge is a simplex satisfies downward closure.

This section introduces measures of simpliciality. We follow a few guiding principles to design these measures. One, a simplicial complex must be maximally simplicial with respect to any measure of simpliciality. Two, to facilitate easier comparison between datasets, measures of simpliciality should be normalized so that they map a hypergraph to a value between 0 and 1. Three, if a subface is added to a hypergraph, the simpliciality must increase. Four, as a dataset becomes qualitatively more like a simplicial complex, the simpliciality should increase. And five, we stipulate that the simpliciality of an empty hypergraph is undefined.

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

Before we turn to applications in Sect. 3, let us discuss three design choices that may impact the conclusion we reach about the simpliciality of a dataset.

First, we note that the formal definition of a simplicial complex can be unnecessarily strict when used to represent perfect inclusion 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 inclusions [7]. Yet, according to the standard definition, these will never be simplicial complexes 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 inclusion in terms of simplicial complexes, our measures will label these datasets as having no inclusion structure whatsoever.

To circumvent this issue, we use a relaxed definition of downward closure that excludes singletons wherever it makes sense. The relaxation uses the notion of a size-restricted power set \(\mathcal{P}_{K}(X)\), where K is a set of integers, defined as For example, given an edge e of size n, \(\mathcal{P}_{\{2,\dots ,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 simpliciality follow by substituting \(\mathcal{P}(X)\) for \(\mathcal{P}_{K}(X)\) in all the measures of Sect. 2.1. Hence, for example, we obtain a relaxation of \(\sigma _{\mathrm{SF}}\) by replacing the definition of S, the set of the hyperedges of H that are also simplices, by \(S = \{e\subseteq E\mid \mathcal{P}_{K}(e)\subseteq E\} \)), where \(K= \{2,\ldots,|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 inclusion structure of the dataset).

Second, we observe that special hyperedges we call “minimal faces” may significantly skew the simpliciality of a dataset. The minimal faces of a hypergraph 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 complex, the minimal faces are singletons). With the size restrictions in place, the minimal faces of a hypergraph are always simplices because, by definition, there are no smaller edges for these edges to include. We argue that when measuring the simpliciality of a dataset, it is most meaningful to focus on the faces for which inclusion 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 simpliciality. Our strategy is as follows. For SF, this means that both S and E exclude the minimal-sized edges. For ES, we exclude maximal faces that are also minimal faces when constructing the minimal simplicial complex. And for FES, 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.

Simpliciality, up to this point a global metric, can also be localized on a smaller subset of the higher-order network to yield information about its local structure. The various face-centric measures used in our construction of the FES provide this information at the level of faces. But for more flexibility, we also use subhypergraphs to define nodal simpliciality measures of our global measures. More specifically, given a hypergraph \(\mathbf{H}= (V,E)\) and a node \(v\in V\), we define the neighborhood of v as \(n(v) = \{u \in V \mid u, v \in e\in E\}\) and the associated subsets \(\widehat{V}=v\,\cup \, n(v)\) and \(\widehat{E} = \{e \in E \mid e\subseteq \widehat{V}\}\). Then the simpliciality of node v is the simpliciality defined on the subhypergraph \(\widehat{\mathbf{H}} =(\widehat{V}, \widehat{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 simpliciality will be undefined.

As the first demonstration of the simpliciality 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.

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 simpliciality measures are shown in Table 1 for all of these datasets. We find that values for simpliciality fill the spectrum from 0 to 1, depending on the data. The proximity datasets have large simpliciality for all three measures, while the biological datasets have low simpliciality for all three measures. The email datasets have a very small ES simpliciality, with moderate simpliciality 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 simpliciality values depending on which measure we consider. This shows that the measures we have defined in Sect. 2.1 capture different features of the inclusion structure.

While the measures give differing perspectives on the simpliciality of each dataset, we verify that they broadly agree with a correlation analysis. The Pearson correlation coefficient is \(\rho =0.97\) between the SF and ES, \(\rho =0.95\) between the SF and FES, and \(\rho =0.90\) between the ES and FES (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 \(\rho =0.89\) between SF and ES, \(\rho =0.997\) between SF and FES, and \(\rho =0.90\) between ES and FES (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 ES to be extremely low while the SF 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 SF is not 1, while both ES and FES are close to 1 due to the SF 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 SF and ES measures. For ES, the large edges will exponentially increase the number of subfaces needed to create a simplicial complex, driving the simpliciality to zero. In contrast, increasing the number of small edges can create more small simplices, increasing SF.

To complement our analysis of empirical data, we also examine the simpliciality of synthetic data generated with generative models for higher-order networks.

We focus on models of hypergraphs designed to describe and analyze arbitrary higher-order structures. There are several random hypergraph 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 model [52]. See Ref. [7] for an extensive overview. Overwhelmingly, generative hypergraph models lack explicit control over the inclusion 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 model (biSBM) [52].

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

In all cases, when sampling synthetic higher-order networks from the three generative models, we generate 10³ 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 \times |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 biSBM, 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 models cannot accurately capture the simpliciality of datasets when they have a non-trivial inclusion structure. While it does not reproduce the correct values, the hypergraph configuration model consistently captures the inclusion structure better than the biSBM and the bipartite Chung-Lu model, irrespective of the simpliciality measure used. This may be due to the exact specification of the degree and edge size sequences; the Chung-Lu model and biSBM only match these sequences in expectation.

As a final demonstration, we apply our local measures of simpliciality 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.

Focusing on the histograms first, we find that the SF has the most variability and that the FES covers a similarly large range. In contrast, the ES tells us that nearly every neighborhood is strongly simplicial. This is expected behavior because the ES relies on a simplicial complex 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 hypergraph. As a result, the denominator of Eq. (2) is reduced, increasing the local ES 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 SF (and, similarly, to a small FES).

Turning to the spatial distribution of simpliciality shown in the insets, we see that the SF and FES find a region of high simpliciality at the network’s core with regions of low simpliciality on its edges. In fact, these two measures are largely in agreement, with a Pearson correlation coefficient of \(\rho =0.84\) between the local SF and FES. (The correlation drops to \(\rho =0.69\) when comparing the SF and ES). We also observe several nodes for which simpliciality 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 simpliciality tend to be connected to one another. To quantify this observation, we define the simplicial assortativity as the Pearson correlation coefficient of the simpliciality of pairs of nodes connected by at least one hyperedge. More formally, we use the unweighted adjacency matrix of the hypergraph, A, defined as where B is the incidence matrix of the hypergraph, such that \(B_{ij}=1\) if node edge j is incident on node i. The simplicial assortativity, ρ, can then be defined as where \(\sigma _{i}\) is the local simpliciality of node i according to one of our measures. The simplicial assortativity for SF, ES, and FES are denoted \(\rho _{\mathrm{SF}}\), \(\rho _{\mathrm{ES}}\), and \(\rho _{\mathrm{FES}}\) respectively. This coefficient is equivalent to the assortativity coefficient [56] of the local simpliciality on the unweighted pairwise projection of the hypergraph.

One should expect local simpliciality to be assortative as any given subface contributes to the simpliciality of all their nodes. Table 2 shows that the situation is a bit more nuanced. For tags-ask-ubuntu, FES is weakly assortative, whereas the other two measures are weakly disassortative. It is particularly striking that despite the hospital-lyon dataset being highly simplicial (as seen in Fig. 2), it is also weakly disassortative.