Configuration Models of Random Hypergraphs

• The paper reviews dyadic configuration models, random hypergraphs, and random simplicial complexes before developing its own models.Source: Outline · p. 2

1. Graphs, Hypergraphs, and Simplicial Complexes

• A graph configuration model randomizes graphs with a fixed degree sequence, using either vertex-labeled or stub-labeled variants.Source: §1 · p. 2
• Stub- and vertex-labeled graph models agree after conditioning on simple graphs, but can differ when multiedges, self-loops, or high density matter.Source: §1 · p. 3
• The choice between labeling schemes depends on whether stub identities represent meaningfully distinct counterfactuals in the application domain.Source: §1 · p. 3
• Projecting a k-adic interaction into a clique can transform one six-agent interaction into 15 dyadic edges and obscure higher-order structure.Source: §1 · p. 4

Random Hypergraphs.

• Hypergraphs generalize graphs by allowing edges with arbitrary numbers of nodes, including parallel and potentially degenerate hyperedges.Source: Random Hypergraphs · p. 4
• Existing hypergraph null approaches include bipartite constructions, fixed-dimension models, projected-graph randomizations, and degree-preserving generalizations.Source: Random Hypergraphs · pp. 4–5
• Simplicial complexes impose subset inclusion, which can be unsuitable for interaction data when lower-dimensional collaborations are not observed.Source: Random Hypergraphs · p. 5

• The proposed hypergraph configuration models generalize the dyadic vertex- and stub-labeled models.Source: §2 · p. 5
• The vertex-labeled model is uniform over hypergraphs with specified degree and edge-dimension sequences.Source: §2 · p. 5
• The stub-labeled model partitions node stubs into edges with prescribed dimensions and is obtained by pushing forward the uniform stub-level distribution.Source: §2 · p. 6
• Vertex labeling is entropy-maximizing when stub identities are not meaningful, whereas stub labeling is entropy-maximizing when those identities matter.Source: §2 · p. 6

3. Sampling

• Pairwise reshuffles preserve node degree and edge-dimension sequences while retaining the intersection of the two reshuffled edges.These operations define the local moves used by the MCMC construction.Source: §3 · pp. 6–7
• The MCMC algorithm repeatedly selects two uniformly random edges and performs a reshuffle, with the transition construction yielding a Markov chain on hypergraphs.The induced hypergraph process is Markovian because its transition distribution depends only on the current hypergraph.Source: §3 · p. 7
• Theorem 1 establishes that the stub-labeled chain is irreducible and reversible, and—when at least two edge dimensions are at least two—aperiodic with equilibrium distribution μd,k.The projected hypergraph process has μd,k as its equilibrium distribution.Source: §3 · p. 8
• Theorem 2 provides an analogous irreducible and reversible chain for the vertex-labeled model ηd,k, with aperiodicity when k has at least two entries larger than 2.Under that condition, ηd,k is the equilibrium distribution of the hypergraph process.Source: §3 · p. 8
• For sufficiently large sample intervals, the algorithm produces asymptotically independent samples from the desired distribution, but no mixing-time bounds are known.The authors report practical sampling on configuration models with hundreds of thousands of edges, while noting that scaling could be poor.Source: §3 · p. 9

3.1. Connections to Random Bipartite Graphs.

• Simple bipartite configuration models are equivalent to the stub-labeled hypergraph model μd,k, but bipartite randomization does not directly provide vertex-labeled sampling.Vertex-labeled sampling requires accounting for permutations of parallel hyperedges, for which no analogous bipartite proposition is available.Source: §3.1 · p. 10

4.1. Triadic Closure.

• Projecting before randomization versus randomizing hypergraphs before projection changes the null expectation for the average local clustering coefficient.The latter preserves clustering induced by higher-dimensional edges, whereas projection converts a k-adic interaction into clique-based dyadic structure.Source: §4.1 · p. 11
• Hypergraph randomization reverses some triadic-closure conclusions relative to dyadic nulls, distinguishing communication networks as less clustered than expected and collaborations as approximately as clustered as expected.The polyadic tests are less sensitive to the choice between vertex- and stub-labeling than dyadic tests.Source: §4.1 · pp. 11–12

4.2. Degree-Assortativity.

• Three hypergraph Spearman measures capture distinct degree-correlation patterns by selecting uniform, top-2, or top-bottom node pairs within each edge.These measures support separate generic, junior-senior, and senior-senior assortativity hypotheses.Source: §4.2 · p. 13
• Polyadic assortativity tests can reverse the synthetic-network finding from statistically significant assortativity under dyadic testing to statistically significant disassortativity.Across empirical data sets, polyadic and dyadic tests generally agree directionally but reveal differences in significance and structure.Source: §4.2 · p. 13

4.3. Hyperedge Intersection Profiles.

• The conditional email-Enron profile has block structure: edges of dimensions 3–6 and 7–8 interact strongly within groups, while cross-group interactions are weaker than expected.This profile compares empirical average intersection sizes with vertex-labeled configuration-model expectations.Source: §4.3 · p. 15
• Email-Enron intersection profiles show fewer single-vertex intersections than expected but at least an order of magnitude more intersections for j ≥3, suggesting substantial higher-order correlation.The observed profile is roughly exponentially decaying through j = 6, and the excess likely reflects repeated messages among the same users.Source: §4.3 · pp. 15–16, Figure 3 · p. 15
• An analytic stub-labeled approximation agrees qualitatively with the email-Enron Monte Carlo profile and supports intersection-profile analysis for data sets of arbitrary size.The approximation is especially useful when Monte Carlo estimation is impractical.Source: Figure 3 · p. 15, §4.3 · pp. 16–17
• Across six large polyadic data sets, the approximate null profile underestimates large intersections by several orders of magnitude in some cases, while matching observed profiles more closely in others.These comparisons use full data sets without the temporal filtering described in Appendix A.Source: §4.3 · p. 17, Figure 4 · p. 17

5. Discussion

• Hypergraph configuration models preserve node degrees and edge dimensions while remaining maximally ignorant about additional data structure.The authors present them as extensions of dyadic configuration models and natural nulls for polyadic network analysis.Source: §5 · p. 17
• Choosing polyadic rather than dyadic nulls can change directional findings, while enabling measures such as extended assortativity and edge intersection profiles.The discussion emphasizes careful consideration of whether dyadic simplification yields relevant data representations and null spaces.Source: §5 · p. 17
• Future theory includes generalizing asymptotic results for component sizes, cycles, parallel edges, and connected-component diameters.These are identified as classical dyadic configuration-model results that invite hypergraph generalization.Source: §5 · p. 17
• Potential applications include motif analysis and hypergraph clustering or community detection, but vertex-labeled nulls may require methods beyond currently analytic approaches.The stub-labeled model is expected to yield an asymptotically equivalent modularity expression, whereas broader vertex-labeled settings may need other methods.Source: §5 · p. 18

Funding.

• The work was supported by a National Science Foundation Graduate Research Fellowship under award number 1122374.Source: Funding · p. 18

Appendix A. Data Preparation

• Temporal filtering excluded edges before a threshold τ, producing data sets with approximately m ≈10^4 edges for practical computation.The thresholds were otherwise arbitrary, and hypergraph configuration-model sampling was not the computational bottleneck.Source: Appendix A · p. 18
• Table 2 summarizes data preparation and reports node and edge counts for original and temporally subsetted data when applicable.Source: Appendix A · p. 18, Table 2 · p. 18