Construction of and efficient sampling from the simplicial configuration model

Simplicial complexes are now a popular alternative to networks when it comes to describing the structure of complex systems, primarily because they encode multinode interactions explicitly. With this new description comes the need for principled null models that allow for easy comparison with empirical data. We propose a natural candidate, the simplicial configuration model. The core of our contribution is an efficient and uniform Markov chain Monte Carlo sampler for this model. We demonstrate its usefulness in a short case study by investigating the topology of three real systems and their randomized counterparts (using their Betti numbers). For two out of three systems, the model allows us to reject the hypothesis that there is no organization beyond the local scale.

Figure 1

(a) Simplicial complex $K$ and (b) its graphical representation $B$. In the bipartite graph, small square nodes represent facets and large orange nodes represent the nodes of $K$. An edge connects a facet ${\sigma }_i$ and a node $v_j$ in $B$ if the facet ${\sigma }_i$ is incident on node $v_j$ in $K$. Notice how some cliques are not filed (i.e., $k$ fully connected nodes do not necessarily form a size $k$), and how isolated nodes are attached to facets of size 1.

Figure 2

Example of non-degree-preserving bipartite graphs. The two bipartite graphs (left column) encode the joint degree sequences $(\mathit{d},\mathit{s})=\left(\right[2,2,1,1,1],[3,2,2\left]\right)$, but the associated simplicial complexes (right column) have different size and degree sequences, respectively $({\mathit{d}}^{\prime },{\mathit{s}}^{\prime })=([1,1,1,1,1],[3,2])$ and $({\mathit{d}}^{\prime },{\mathit{s}}^{\prime })=([2,1,1,1,1],[2,2,2])$. The disparities are due to the presence of (a) a fully included neighborhood, and (b) pairs of nodes connected by more than one edge.

Figure 3

Effect of the parametrization of the proposal distribution $\mathbb{P}$ on the mixing time, as quantified by the edit distances of the graphical representation of the samples. We investigate the family of distributions $\mathbb{P}[L=\ell ;\lambda ]=e^{\lambda \ell }/Z$, and use the regular SCM of $f=1000$ facets of size $s=8$, and $n=2000$ nodes of degrees $d=4$. Pairs of samples are separated by 100 proposed MCMC moves and are obtained from a unique initial configuration found via rejection sampling. The shaded region lies below the upper bound on $L_{max}^{*}$ of Eq. (3). $\lambda =1$ balances high-rejection probability but efficient moves with safe but inefficient moves, yielding the best overall performance for all $L_{max}$. In practice, we have found that medium values of $L_{max}$ are better, because checking for resampling is of complexity $O\left(L_{max}\langle d\rangle \right)$, which translates into slower effective mixing time when $L_{max}\gg 1$.

Figure 4

Significance of the Betti numbers of real systems. The datasets are bipartite networks, which we convert to simplicial complexes (we prune included faces). They map the relationships between (a) flower-visiting insects (nodes, $n=679$) and plants (facets $f=57$) in Kyoto [33], (b) human disease (nodes $n=1100$) and genes (facets $f=752$) linked by known disorder-gene associations [34], and (c) crimes (nodes, $n=829$) and suspects, victims, and witnesses (facets, $f=378$) in St. Louis [35]. The Betti numbers of these real systems appear as solid vertical lines and are equal to (a) ${\beta }_0=2, {\beta }_1=17$ (b) ${\beta }_0=503,{\beta }_1=27,$ and (c) ${\beta }_0=20,{\beta }_1=23$. We show the distributions of Betti numbers for the equivalent SCM with solid symbols (computed from 1000 instances of the model). The shaded regions contain $95\%$ of the samples. The parameters of the SCM—extracted from real systems—are shown in insets.