Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes

Simplicial complexes are generalized network structures able to encode interactions occurring between more than two nodes. Simplicial complexes describe a large variety of complex interacting systems ranging from brain networks to social and collaboration networks. Here we characterize the structure of simplicial complexes using their generalized degrees that capture fundamental properties of one, two, three, or more linked nodes. Moreover, we introduce the configuration model and the canonical ensemble of simplicial complexes, enforcing, respectively, the sequence of generalized degrees of the nodes and the sequence of the expected generalized degrees of the nodes. We evaluate the entropy of these ensembles, finding the asymptotic expression for the number of simplicial complexes in the configuration model. We provide the algorithms for the construction of simplicial complexes belonging to the configuration model and the canonical ensemble of simplicial complexes. We give an expression for the structural cutoff of simplicial complexes that for simplicial complexes of dimension $d=1$ reduces to the structural cutoff of simple networks. Finally, we provide a numerical analysis of the natural correlations emerging in the configuration model of simplicial complexes without structural cutoff.

Figure 1

Examples of simplicial complexes of dimension $d=1$ (panel A) and $d=2$ (panel B) are shown. Simplicial complexes of dimension $d=1$ are simple networks. Simplicial complexes of dimension $d\ge 2$ characterize interactions occurring between more than two nodes (specifically interactions occurring between $d+1$ nodes).

Figure 2

The figure shows the construction of two different $d=2$ dimensional simplicial complexes belonging to the same configuration model of simplicial complexes. In panel (a) the $N=6$ nodes are shown together with stubs, indicating their generalized degree. In panel (b) triples of stubs are matched together to form two-dimensional simplices. In panel (c) the corresponding simplicial complex is visualized. In panels (d) and (e) a different matching of the stubs is shown together with its corresponding simplicial complex. As is evident from the figure, a given generalized degree sequence of the nodes can give rise to different simplicial complexes. The logarithm of the total number $\mathcal{N}$ of simplicial complexes that can be constructed from a given generalized degree sequence of the nodes is the Gibbs entropy $\mathrm{\Sigma }$ of the configuration model.

Figure 3

A scheme representing the algorithm for the construction of the configuration model is shown for the case $d=2$. Panel A represents steps (i), (ii), and (iii). To each node $r$ with $r=1,2...,N=6$ we assign $k_r$ stubs. The nodes are represented with black circles. A set of $M$ auxiliary factor nodes (cyan triangles) is considered. Each factor node has $d+1$ stubs. Subsequently, an allowed matching of the stubs is found. Panel B shows how from the matching of the stubs we can construct a simplicial complex by adding a simplex between all of the nodes connected to a common factor node in panel A.

Figure 4

Two examples of forbidden moves are shown. In panel A the same set of nodes $(r_1,r_2,\cdots ,r_{d+1})$ is selected more than once to form a simplex. In panel B the set of nodes $(r_1,r_2,...,r_{d+1})$ selected to form a simplex is not formed by $d+1$ distinct nodes. Here the forbidden moves are shown for the configuration model of simplicial complexes of dimension $d=2$.

Figure 5

The subsequent matching of the node stubs with the stubs of the factor nodes is shown here in order to justify Eq. (61) evaluating the asymptotic number of matchings in the absence of forbidden moves. First a random stub of a node is matched with a stub of an arbitrary unmatched factor node (panel A). Subsequently, all the remaining $d$ stubs of the factor node are matched with stubs of the nodes (panel B). At this point the unmatched factor nodes are reduced by one. An unmatched node-stub is matched to a stub of an arbitrary unmatched factor node (panel C). Subsequently, all the remaining stubs of the second factor node are matched with stubs of the nodes (panel D). This procedure continues in the absence of forbidden moves, until all of the stubs of the nodes are matched with all the stubs of the factor nodes. By calculating the probability of these moves, as describe in Sec. 4g we can derive Eq. (61).

Figure 6

The average degree $knn\left(\kappa \right)$ of the neighbors of the nodes of degree $\kappa$ and the average clustering coefficient $C\left(\kappa \right)$ of the nodes of degree $\kappa$, for simplicial complexes of dimension $d=1,2,3$ constructed according to the configuration model with distribution of the generalized degrees of the nodes $P_{d,0}\left(k\right)$ given by Eq. (65) and $\gamma =2.3,2.8$. The simplicial complexes have $N={10}^4$ nodes, and $n_F=70$. The data are averaged over 100 realizations.