Construction of simplicial complexes with prescribed degree-size sequences

Abstract

We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and the facet size distribution, respectively. While the $s$-uniform variant of the problem is $\mathsf{NP}$-complete when $s\ge 3$, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [J.-G. Young $\text{et al.}$, Phys. Rev. E $\text{96}$, 032312 (2017)], we facilitate the efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing the nodes' degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analysis of higher-order phenomena based on local structures.

arXiv comment6 pages, 4 figures; 3-page supplemental material. Code implementing our methods is available at https://github.com/junipertcy/simplicial-test (Python, pip installable). Read the Docs at https://docs.netscied.tw/simplicial-test/index.html v2: revised and accepted at Phys. Rev. E

References in corpus (26)

• Networks beyond pairwise interactions: structure and dynamics
• Simplicial models of social contagion
• A roadmap for the computation of persistent homology
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• What are higher-order networks?
• Explosive higher-order Kuramoto dynamics on simplicial complexes
• Higher-order interactions in complex networks of phase oscillators promote abrupt synchronization switching
• The origin of degree correlations in the Internet and other networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Random graphs containing arbitrary distributions of subgraphs
• The effect of heterogeneity on hypergraph contagion models
• Simplicial Activity Driven Model
• All scale-free networks are sparse
• The entropic origin of disassortativity in complex networks
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• A Universal Route to Explosive Phenomena
• An adaptive voter model on simplicial complexes
• Construction of and efficient sampling from the simplicial configuration model
• A Clarified Typology of Core-Periphery Structure in Networks
• Topological Percolation on Hyperbolic Simplicial Complexes
• Social confinement and mesoscopic localization of epidemics on networks
• Homological Percolation and the Euler Characteristic
• A loop enhancement strategy for network robustness
• Random graphs with arbitrary clustering and their applications
• Connectedness matters: Construction and exact random sampling of connected graphs