Source-linked AI summary
Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
Owen T. Courtney, Ginestra Bianconi
TL;DR
Simplicial complexes require null models that represent many-body interactions while controlling generalized degrees. This paper develops configuration and canonical ensembles, calculates their entropy, derives asymptotic counts, provides generation algorithms, and analyzes structural cutoffs and resulting correlations.
Problem
Existing network models do not fully capture generalized network structures with many-body interactions, motivating null models for simplicial complexes.
Method
The paper characterizes simplicial complexes by generalized degrees and develops configuration and canonical ensembles with fixed and expected generalized-degree sequences, respectively.
Results
The paper analytically derives ensemble entropies and an asymptotic counting formula, provides construction algorithms, and studies structural cutoffs and natural correlations.
Takeaways & Limitations
The framework extends configuration and canonical network ensembles to simplicial complexes and identifies how dimensionality and structural cutoffs relate to generalized-degree correlations.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Simplicial complexes extend networks to many-body interactions and support topological and geometric analysis across diverse complex systems. The paper develops equilibrium null models that constrain generalized degrees, characterizes their entropies and correlations, and provides construction algorithms.
- I. INTRODUCTION: They model brain, social, collaboration, immune, tagged-social, and folksonomy networks, while also supporting topological analysis and hidden-geometry investigations.Their many short loops and large clustering coefficients motivate these applications.
- I. INTRODUCTION: Simplicial complexes generalize networks with triangles, tetrahedra, and higher-dimensional simplices, encoding interactions among more than two nodes.A d-dimensional simplex contains d + 1 interacting nodes and all lower-dimensional faces.
- I. INTRODUCTION: The paper characterizes simplicial complexes using generalized degrees, counting incident d-dimensional simplices for each δ-dimensional face.The generalized degrees of different faces are linked by combinatorial relations and are not independent.
- I. INTRODUCTION: It introduces a configuration model with fixed generalized-degree sequences and a canonical ensemble with expected generalized-degree sequences.These are conjugate micro-canonical and canonical ensembles, respectively, but enforce an extensive number of constraints and are not asymptotically equivalent.
- I. INTRODUCTION: The paper analytically calculates ensemble entropy, derives an asymptotic counting formula, and supplies algorithms for generating configuration-model and canonical simplicial complexes.The entropy-based counting result generalizes the Canfield-Bender formula for sparse configuration-model networks.
- I. INTRODUCTION: Structural cutoffs determine when generalized-degree correlations are absent; without the cutoff, numerical realizations exhibit relevant natural degree correlations.For d > 1, the simplicial-complex cutoff is larger than the simple-network cutoff.
C. Case of a simplicial complex of dimension d = 2
For two-dimensional simplicial complexes formed exclusively by triangles, the canonical ensemble constrains expected node generalized degrees and yields independent triangle probabilities, with a structural cutoff scaling as N^2/3.
- Definitions: Triangles are represented by an adjacency tensor, with node generalized degree counting incident triangles and link generalized degree counting incident triangles on each link.Each triangle contributes to three node generalized degrees.
- Ensemble construction: The canonical ensemble assigns probabilities to triangle complexes while enforcing a prescribed sequence of expected node generalized degrees.It is obtained by maximizing entropy subject to the expected-degree and normalization constraints.
- Ensemble construction: The probability of a simplicial complex factorizes into marginal probabilities for its individual triangles.This factorization follows from the canonical-ensemble probability construction.
- Structural cutoff: The factorized approximation is valid when the maximum generalized degree is much smaller than the structural cutoff K_d.The approximation assumes large N and e^−λ_r ≪ 1.
- Structural cutoff: The structural cutoff K_d scales as N^d/(d+1), so for d = 2 it scales as N^2/3 and increases with dimension.Below this cutoff, generalized-degree correlations are absent in the stated regime.
- Structural cutoff: Only node pairs with generalized degrees kr, km ≫ N^1/2 and kr, km ≪ N^d/(d+1) are likely to share more than one d-dimensional simplex.This identifies the degree range associated with repeated simplex incidence.
C. The canonical ensemble of simplicial complexes of dimension d = 1
The one-dimensional case recovers the canonical ensemble of networks with a prescribed expected degree sequence. Its graph probabilities factorize over links, and its structural cutoff reduces to the simple-network cutoff.
- Network limit: For d = 1, the simplicial-complex construction becomes the canonical or exponential ensemble of networks with a given expected degree sequence.Links are the one-dimensional simplices represented by the adjacency tensor.
- Network limit: The probability of a network is expressed as a product of marginal probabilities for individual links.Each link probability is denoted prm.
- Entropy: The canonical network ensemble entropy is obtained from the ensemble probability distribution over networks or adjacency tensors.The entropy is the corresponding ensemble quantity.
- Structural cutoff: Under the structural-cutoff condition, link probabilities take a simple factorized form.The condition constrains the maximum generalized degree Kmax.
- Structural cutoff: For d = 1, the simplicial-complex structural cutoff reduces to the structural cutoff of simple networks.This provides the expected network-theory limit of the generalized construction.
- Comparison with d = 2: The d = 2 case uses triangle probabilities and has a structural cutoff K2 scaling as N^2/3, unlike the one-dimensional link case.The two-dimensional formulation treats three-node simplices as homogeneous node interactions.
E. Generation of simplicial complexes by the canonical ensemble
The canonical ensemble is introduced alongside configuration-model constructions for simplicial complexes, using generalized-degree constraints and simplex probabilities. The construction algorithm matches node stubs to auxiliary factor nodes while rejecting forbidden repeated or non-distinct simplices.
- Canonical ensemble: The canonical ensemble is generated using the expected generalized-degree sequence and simplex probabilities pα.The probability for each simplex is selected according to the structural-cutoff regime.
- Configuration model: The configuration model assigns equal probability to simplicial complexes sharing a graphical generalized-degree sequence.The sequence must be graphical, meaning at least one compatible simplicial complex exists.
- Stub matching: The construction algorithm assigns kr stubs to each node and d + 1 stubs to every auxiliary factor node before matching them.For d = 2, each factor node connects three node stubs and thereby represents a two-dimensional simplex.
- Validity constraints: A uniformly selected set of d + 1 unmatched node stubs is accepted only when its nodes are distinct and the simplex is not duplicated.After all stubs are matched, each factor node induces a simplex among its connected nodes.
- Algorithmic trade-off: Rejecting forbidden moves prevents spurious correlations, but broad generalized-degree distributions can significantly slow the algorithm.Allowing a small number nF of forbidden moves speeds computation when nF ≪ N without significantly altering simplicial-complex properties.
C. Relation with bipartite network models
The paper relates simplicial-complex configuration and canonical ensembles to bipartite network models, distinguishing hard constraints on generalized degrees from soft expected-degree constraints. It analytically compares their entropies and derives the asymptotic number of complexes under a structural cutoff.
- Relation to bipartite models: Bipartite networks connect nodes to factor nodes, and equal factor-node degree d produces d-dimensional simplicial complexes.A factor node represents a group whose connected nodes are joined into a simplex.
- Relation to bipartite models: Simplicial-complex models differ because factor nodes are unlabelled and repeated factors connecting the same node set are not distinguished.Bipartite author–paper data distinguish multiple papers with identical authors, whereas the corresponding simplicial complex does not.
- Conjugate ensembles: The configuration model fixes each node’s generalized degree, whereas the canonical ensemble fixes its expected generalized degree.These are respectively micro-canonical and canonical conjugate ensembles.
- Entropy relation: The entropy difference is governed by Ω, the logarithm of the probability that canonical generalized degrees exactly match the imposed sequence.Because Ω is non-negative, the Gibbs entropy is no greater than the Shannon entropy, and non-negligible Ω signals non-equivalence.
- Asymptotic counting: The asymptotic number of complexes generalizes the Canfield–Bender formula and depends on the generalized-degree distribution, even at fixed mean degree.For d > 1, scale-free distributions with smaller exponent γ yield smaller entropy and fewer complexes.
G. Combinatorial arguments for Eq. (60)
The combinatorial derivation counts stub matchings that construct simplicial complexes while initially ignoring forbidden moves, then corrects for equivalent node-stub permutations and forbidden configurations.
- G. Combinatorial arguments for Eq. (60): Ignoring forbidden moves, the combinatorial factor counts arrangements of node stubs into groups of d + 1.Factor nodes are unlabelled, so each newly selected unmatched factor node gives a unique matching choice at that stage.
- G. Combinatorial arguments for Eq. (60): For finite d and large N, the matching count is approximated asymptotically using the total number of factor nodes M = ⟨k⟩N/(d + 1).This approximation is applied to the product of choices generated during the sequential matching process.
- G. Combinatorial arguments for Eq. (60): The matching procedure repeatedly pairs a node stub with an unmatched factor node, then assigns the factor node’s remaining d stubs.The process continues until all node stubs are matched.
- G. Combinatorial arguments for Eq. (60): Equivalent permutations of the stubs belonging to each node are removed by dividing by the product of generalized-degree factorials.This converts ordered stub arrangements into distinct simplicial-complex matchings.
- G. Combinatorial arguments for Eq. (60): The exponential factor in Eq. (60) corrects the count for forbidden matchings excluded from valid simplicial complexes.The figure illustrates the underlying matching sequence in the absence of such forbidden moves.
the canonical ensemble
This section formulates the canonical ensemble through expected generalized degrees and relates its Shannon entropy to the configuration model’s Gibbs entropy via a large-deviation term.
- the canonical ensemble: The configuration-model entropy Σ is the logarithm of the number of simplicial complexes satisfying fixed generalized-degree constraints.These are hard constraints on kd,0(r) = kr.
- the canonical ensemble: The canonical entropy S describes an ensemble enforcing expected generalized degrees equal to the target sequence.The comparison sets the expected values kr equal to the hard-constrained values kr.
- the canonical ensemble: The derivation uses Kronecker-delta integral representations and sums over binary adjacency-tensor elements.Canonical parameters are related to the prescribed generalized-degree sequence through saddle-point equations.
- the canonical ensemble: Ω is the logarithm of the probability that canonical generalized degrees take exactly the target hard-constrained values.The entropy relation identifies the first terms with the canonical Shannon entropy and the remaining term with Ω.
Appendix B: Derivation of the Eq. (56) for Ω
Appendix B evaluates Ω under a structural cutoff using a factorized canonical probability and a saddle-point calculation. The result is expressed through Poisson probabilities for generalized degrees.
- Appendix B: Derivation of the Eq. (56) for Ω: Under the structural cutoff, the canonical probabilities pα are factorized and satisfy the sparse uncorrelated-ensemble approximation pα ≪ 1.This approximation is used to simplify the generating functional before saddle-point evaluation.
- Appendix B: Derivation of the Eq. (56) for Ω: The calculation groups nodes by generalized degree using the density of nodes with kr = k and the distribution Pd,0(k).This rewrites the saddle-point equations in terms of degree classes rather than individual nodes.
- Appendix B: Derivation of the Eq. (56) for Ω: The functional integral is evaluated by the saddle-point method, with saddle-point equations determining the relevant auxiliary variables.The functional F[c(ω|k), ĉ(ω|k)] is the object evaluated at the saddle point.
- Appendix B: Derivation of the Eq. (56) for Ω: The final Ω expression is obtained by evaluating the integral at the saddle point and involves πkr(kr), the Poisson distribution with average kr evaluated at kr.This probability represents observing the exact target generalized degree in the canonical ensemble.
SUPPLEMENTARY MATERIAL
The supplementary material extends the network configuration model to simplicial complexes of dimensions d = 2 and d = 3, generating complexes with a specified generalized degree sequence.
- The supplied code extends the network configuration model from d = 1 to simplicial complexes of dimensions d = 2 and d = 3.The generalized configuration model generates simplicial complexes with a given generalized degree sequence.
Codes for generating simplicial complexes using the configuration model
Three C programs generate simplicial complexes in the configuration model for dimensions d = 1, 2, and 3, using configurable generalized degree distributions.
- Three C codes generate simplicial complexes in the configuration model for dimensions d = 1, 2, and 3.The codes can be modified to accept pre-specified generalized degree sequences.
- The default generalized degree sequences are drawn randomly from a scale-free distribution, with commented alternatives for a Poisson distribution.The Poisson option is included in comments and can be enabled at the relevant points in the code.
Code for d = 1
The d = 1 implementation constructs a simple network by matching node stubs while rejecting illegal self-loops or repeated links, then computes and exports the resulting degrees and edge list.
- Initialization: Nodes receive desired generalized degrees from a scale-free distribution, with values above N−1 redrawn using the natural cutoff.The code initializes actual generalized degrees and ordinary degrees to zero before matching begins.
- Stub matching: Two nodes are selected proportionally to their unmatched stubs for each proposed matching.The matching process continues while more than two unmatched stubs remain.
- Stub matching: A proposed matching is legal only when the nodes differ and no link already connects them.Legal proposals create a link; illegal proposals trigger backtracking when enabled.
- Output: The implementation calculates each node’s degree from the adjacency matrix after matching.It then prints the edge list to an output file.
Code for d = 2
The d = 2 implementation builds simplicial complexes by matching triples of node stubs, rejecting duplicate triangles, updating links, and optionally exporting the resulting edge list.
- Triangle matching: Three nodes are selected proportionally to their remaining unmatched stubs during the matching process.The loop continues while more than three unmatched stubs remain and the backtracking limit is not exceeded.
- Triangle matching: A proposed triple is legal when its nodes are distinct and no incident triangle already exists.Legal triples create a triangle and its links; illegal proposals increment the backtracking counter.
- Output: The code computes ordinary node degrees from the adjacency matrix and can print the resulting edge list when figure is set to 1.The generated edge list is written using pairs of node indices.
Code for d = 3
The d = 3 code generates random simplicial complexes with scale-free generalized degrees by repeatedly matching node stubs into tetrahedra while checking legality and tracking network statistics.
- Tetrahedron construction: When a tetrahedron is created, its three neighboring nodes are appended to each of the four nodes’ triangle-incidence lists.The implementation reallocates storage and records the other three node indices for every tetrahedron participant.
- Network analysis: The program outputs an edge list and allocates arrays for adjacency, degrees, neighbor-degree statistics, and clustering coefficients.These structures support extracting and analyzing the network induced by the generated simplicial complex.
- Initialization: Each node receives a desired generalized degree from a scale-free distribution, with values above the natural cutoff redrawn.The natural cutoff is implemented as the maximum possible generalized degree, pow(N, 3.)/6.
- Tetrahedron construction: The matching loop randomly selects four nodes in proportion to their remaining unmatched stubs and proposes a tetrahedron.The process continues while more than four unmatched stubs remain and within the configured backtracking budget.
- Tetrahedron construction: A proposed tetrahedron is accepted only if the legality check finds no existing incident triangle among the four nodes.The Check function also rejects proposals containing repeated node indices.