Source-linked AI summary
Higher-order rich clubs and configuration models on general directed hypergraphs
Jason P. Smith, Celia Hacker, Jānis Lazovskis, Florian Unger, Keith M. Smith, Daniela Egas Santander
TL;DR
Pairwise rich-club analysis misses higher-order interactions and often omits direction, limiting its description of complex systems. The paper introduces a hyper-rich club pipeline on general directed hypergraphs, with null models and domain-specific design choices that encompass several existing hypergraph types. Across connectomes and other diverse networks, the pipeline recovers meaningful higher-order structure that standard graph rich clubs miss.
Problem
Pairwise rich-club analysis does not capture higher-order interactions and directional information that can be meaningful in complex systems.
Method
The paper defines a hyper-rich club framework on general directed hypergraphs, paired with null models and explicit choices fixed according to research goals.
Results
Across connectomes, temporal infectious-spread networks, poetic data, and the XGI database, the pipeline recovers meaningful higher-order structure that standard graph rich clubs miss.
Takeaways & Limitations
The framework unifies undirected, totally ordered, and heads-and-tails hypergraph cases while enabling rich-club analysis for directed higher-order interactions.
Takeaways & Limitations
The null model can generate degenerate edges, and its behavior for non-Erdős–Rényi degree distributions remains unresolved.
Abstract
from arXiv · showhide
Detecting structure in complex networks, especially those arising from physical systems, is a central problem across the sciences. One approach is via rich club analysis, which identifies important vertices using a centrality metric and measures whether those vertices are more tightly interconnected than expected by chance. While informative, this approach captures only pairwise interactions, missing out on higher-order ones known to shape the structure and function of many complex systems. We propose a hyper-rich club pipeline that asks whether central vertices are more tightly interconnected than expected by chance through hyperedges encoding higher-order interactions, which also enables the inclusion of important, often omitted, directional information. We work in a broad class of hypergraphs, which we call general directed hypergraphs, that includes as special cases undirected hypergraphs, head-and-tail directed hypergraphs, and totally ordered hypergraphs (a hypergraph related to directed simplicial complexes from topological data analysis). This unifies several non-equivalent notions of directed hypergraph under one definition. On these hypergraphs we define a hyper-rich club framework whose concrete construction depends on explicit choices the domain scientist fixes according to their research goals. Particular choices recover the existing rich club notions for graphs and undirected hypergraphs, and yield the first such notion for each version of directed hypergraphs. We demonstrate that the pipeline recovers meaningful structure in data by studying networks of very different origins: connectomes, temporal networks of infectious spread, networks of poems, and the XGI hypergraph database, in each case detecting structure the standard graph rich club misses.
1. Introduction
Rich-club analysis reveals higher-centrality vertices’ preferential interconnection, but pairwise metrics miss higher-order and directional structure. The paper therefore introduces a directed hypergraph framework that generalizes existing rich-club notions across several hypergraph types.
- Rich-club analysis measures whether highly central vertices connect to one another more than expected by chance.
- Pairwise connectivity alone can inadequately describe brain structure and function, motivating rich-club analysis based on higher-order interactions.
- Existing work defines higher-order rich clubs for undirected hypergraphs, but undirected structure is insufficient for some brain-network applications.
- The paper introduces a hyper-rich club for directed hypergraphs, paired with a null model testing preferential directed-hyperedge connectivity.
- The framework can produce different rich vertices for each hyperedge size, distinguishing its results from the standard graph-theoretic rich club.
- A unified formulation encompasses undirected, totally ordered, and heads-and-tails hypergraphs, recovering prior undirected constructions and providing the first heads-and-tails version.
2. Preliminaries
The preliminaries define hypergraphs, directed and totally ordered variants, degree notions, and several induced subhypergraphs. They distinguish strict, cropped, and edge-induced constructions while emphasizing terminology that varies across the literature.
- A hypergraph generalizes a graph by allowing edges to connect more than two vertices, while directed hypergraph definitions are not unique.
- A TO-hypergraph is a finite multiset of totally ordered hyperedges containing distinct vertices, with edge size given by cardinality.
- Hypergraph degree records both vertex participation and edge size; k-degree counts k-edges, while position-specific k-degree records a vertex’s position.
- For a vertex set W, strict subhypergraphs retain edges wholly contained in W, whereas cropped subhypergraphs retain intersections containing more than one vertex.
- Terminology for induced subhypergraphs differs across sources, and cropped constructions may introduce duplicate edges.
- Edge-induced subhypergraphs retain selected hyperedges and only vertices appearing in them; H_k is the subhypergraph induced by k-edges.
3. Rich club for graphs
Graph rich-club curves measure connectivity among increasingly high-degree vertices, but increasing curves can arise by chance. Configuration-model normalization preserves degree sequences to identify deviations attributable to rich-club structure.
- A degree filtration creates vertex-induced subgraphs containing vertices above successive degree thresholds, defining the rich-club curve from their densities.
- Directed rich-club curves can use in-degree, out-degree, or total degree, reflecting different notions of vertex centrality.
- An increasing rich-club curve is not sufficient evidence because Erdős–Rényi graphs can show the same trend; comparison with a null model is required.
- The directed configuration model randomly pairs outgoing and incoming half-edges while prescribing the original in- and out-degree sequences, then discards loops and repeated edges.
- The normalized rich-club curve compares observed connectivity with the configuration-model expectation, with values above one originally indicating a rich club.
- The connectome comparison uses in-degree, out-degree, and total-degree curves across C. elegans, Drosophila larva, and mouse visual cortex, with 1000 null-model repetitions.
- Prior connectome rich-club studies analyzed total degree only, thereby ignoring direction.
4. Rich club on totally ordered hypergraphs
The paper generalizes rich-club analysis to totally ordered hypergraphs by combining vertex filtrations, induced subhypergraphs, connectivity metrics, and null-model normalization. Its density choices quantify higher-order connectivity while recovering standard directed-graph rich-club curves when k = 2.
- The directed hypergraph rich club measures whether well-connected vertices preferentially connect through directed hyperedges.
- A hyper-rich club curve requires choices of vertex filtration, null model, subhypergraph, and connectivity metric.The null model approximately preserves edges and vertices at each filtration level while randomizing other structure.
- Tiered curves use k-edges and k-degree filtrations, whereas combined curves use multiple edge sizes and combined-degree filtrations.
- Simple and reduced k-densities quantify connectivity through k-edges, with both reducing to |E_k|/P_k(V) for k-regular hypergraphs.
4.3. Unnormalized tiered hyper-rich clubs.
Unnormalized tiered curves track connectivity through k-edges as vertex k-degree increases, but random hypergraphs also show increasing curves. The TO-configuration model preserves positional degree sequences approximately and provides the corresponding baseline.
- Unnormalized tiered hyper-rich clubs: Tiered curves measure whether vertices in k-edges increasingly connect through k-hyperedges as their k-degree grows.
- Unnormalized tiered hyper-rich clubs: For k = 2, tiered curves recover total-degree, out-degree, and in-degree directed-graph rich clubs.
- Unnormalized tiered hyper-rich clubs: Strict filtrations retain complete k-edges, whereas cropped filtrations also retain subedges and preserve their multiplicity.
- The TO-configuration model: The TO-configuration model independently shuffles each edge-position column, preserving positional k-degree sequences unless degenerate edges occur.
- The TO-configuration model: For fixed k and bounded edge counts, the number of degenerate edges tends to zero in ER-TO-hypergraphs and their TO-configuration controls.
- The TO-configuration model: The authors leave open whether the model extends beyond ER degree distributions and whether rerolling samples uniformly.
4.5. Normalized tiered hyper-rich clubs.
Normalized tiered curves compare observed higher-order connectivity with a TO-configuration baseline, using permutation significance and support filtering. In the C. elegans examples, normalization removes spurious tails in some randomizations while revealing a localized rich club in another.
- Normalized tiered hyper-rich clubs: The normalized k-hyper-rich club curve divides observed connectivity by its expected value under a TO-configuration null model.
- Normalized tiered hyper-rich clubs: Weighted edge counts provide a more numerically stable approximation than densities in large sparse hypergraphs.The counts remain integers, while density normalizations can be enormous or infeasible to compute.
- Normalized tiered hyper-rich clubs: High-filtration values are discarded when controls become under-supported because sparse vertex sets make densities noisy or undefined.
- Normalized tiered hyper-rich clubs: A hyper-rich club region requires a curve above τ, a p-value below α, and an under-supported fraction no greater than θ.Default thresholds are τ = 1.2, α = 0.05, and θ = 0.2.
- Normalized tiered hyper-rich clubs: In the C. elegans randomizations, ER-hypergraphs and CM-graphs show no genuine tail after normalization, while ER-graphs show a rich club only in a small middle-degree region.
4.6. Combined hyper-rich clubs.
Combined hyper-rich clubs aggregate selected edge sizes and normalize their connectivity against an I-combined configuration model. This model preserves total I-degree but discards within-edge-size positional information.
- Combined hyper-rich clubs: Combined hyper-rich club curves measure connectivity through a selected set I of edge sizes using an I-degree filtration.
- Combined hyper-rich clubs: The I-combined configuration model pools vertices from all selected edge sizes and randomly redistributes them into edges.
- Combined hyper-rich clubs: Unlike the TO-configuration model, the {k}-combined model fixes only total k-degree and loses per-position degree information.
- Combined hyper-rich clubs: The normalized combined curve divides the combined connectivity curve by the expectation under its combined configuration-model control.
- Combined hyper-rich clubs: The paper presents TO-hypergraph examples from multiple real-world datasets and discusses implications of their rich-club computations.
4.7. Applications.
Applications show that hyper-rich clubs recover higher-order and directional structure missed by pairwise rich clubs across connectomes and poetic hypergraphs. The analyses also expose domain-specific patterns while highlighting representation choices that affect interpretation.
- Connectomes: All three connectomes exhibit hyper-rich clubs under k-degree, but only at larger edge sizes.C. elegans and Drosophila have clubs for k > 3, while MICrONS has none for k = 2, 3, 4, a weak club for k = 5, 6, and a strong club for k = 7.
- Connectomes: Hyper-rich clubs identify neuron groups distinct from the pairwise rich club and reveal connectivity organized through large, directionally consistent hyperedges.In C. elegans, the 7-hyper-rich club has many more large maximal directed cliques than the pairwise club despite similar graph density.
- Connectomes: The MICrONS 5-hyper-rich club contains an edge participating in 6982 5-hyperedges, revealing higher-order interconnection despite lacking a standard graph rich club.The example illustrates why hyper-rich clubs can detect structure invisible to pairwise metrics.
- Poetic hypergraphs: Poetic hypergraphs represent words as vertices and poem lines as hyperedges, preserving repeated words, repeated lines, and higher-order word order.The construction allows repeated vertices within edges and retains degenerates to capture poem structure.
- Poetic hypergraphs: Ignoring punctuation may fundamentally alter the poetic hypergraph structure, so punctuation is left for future exploration.The paper notes that punctuation can be integral to natural-language structure.
5. A unified view of the hyper-rich club
The paper defines general directed hypergraphs as a unifying framework for several directed and undirected hypergraph notions, then builds hyper-rich-club curves and a configuration-model control within it. The resulting framework recovers established constructions and supplies new directed-hypergraph variants while detecting distinct higher-order structure across networks.
- General directed hypergraphs: General directed hypergraphs use hyperedges composed of ordered parts, with breadth recording the number of parts and size their total vertex count.When all edges have breadth two they recover HT-hypergraphs; breadth one recovers undirected hypergraphs, and totally ordered hypergraphs arise when every part is a singleton.
- Special cases: The framework includes HT-hypergraphs, ordinary undirected hypergraphs, simple undirected graphs, and totally ordered hypergraphs as special cases.It also treats the hypergraphs of as a special case after dropping additional conditions unrelated to the hyper-rich-club definition.
- Subhypergraphs and density: Vertex-induced cropping intersects every part with the selected vertex set, discards empty parts, and can reduce an edge’s breadth.The induced subhypergraph is not necessarily simple and retains cropped edges whose size exceeds one.
- Subhypergraphs and density: Generalized density normalizes edge counts by all possible edges of a given breadth and any possible part sizes on the fixed vertex set.The corresponding counting formula sums over possible part sizes, replacing the ordinary hypergraph normalization by a generalized constant.
- Null model: The general configuration model preserves position-specific k-degree sequences, breadth counts, and part sizes while randomly repartitioning vertex multisets.For each breadth and position, parts are shuffled into groups with the prescribed sizes to form null-model hyperedges.
- Applications: The resulting normalized hyper-rich-club construction recovers established TO- and undirected-hypergraph notions, while ρ2 provides the first such notion for HT-hypergraphs.In metabolic-network comparisons, every HT-network met the criterion ρ(ℓ) ≥1.2, compared with 54.2% of undirected networks.
- Applications: Peak hyper-rich-club values distinguish network classes: mammalian and parasite metabolic HT-networks rank highest, whereas collaboration networks rank highest among undirected networks.Face-to-face contact networks fluctuate around 1, while the ndc-classes network exhibits anti-rich-club behavior.
6. Conclusion and Perspectives
The conclusion frames the work as a broad hyper-rich-club framework for directed hypergraphs whose concrete realization depends on domain-specific choices. Across diverse network types, the pipeline recovers higher-order structure missed by standard graph rich-club analysis, while several theoretical and application questions remain open.
- Contributions: The framework’s concrete hyper-rich-club realization depends on explicit choices made by domain scientists for their research goals.Those choices recover existing graph and undirected-hypergraph notions and yield first notions for each directed-hypergraph version.
- Empirical scope: Across connectomes, infectious-spread temporal networks, poetic databases, and other datasets, the pipeline detects meaningful higher-order structure missed by the standard graph rich club.The paper presents this as the central empirical conclusion across networks of diverse origins.
- Perspectives: Open questions include realizability of degree sequences, non-uniformity and degenerate edges in the null model, and links to edge-level metrics.The authors also identify open problems for structured simplicial-complex data and connectomics.
Appendix A. Statistics
The appendix introduces statistical testing for normalized rich-club curves by comparing observed connectivity with null-model behavior at each filtration value.
- Single-hypergraph testing: For a single hypergraph, the analysis tests whether its chosen connectivity metric is significantly larger than the null-model expectation at each filtration value.The test uses a one-sided alternative that the observed metric is stochastically larger.
- Statistical rationale: The reported procedure evaluates normalized rich-club significance through filtration-specific statistical comparisons rather than relying on curve increases alone.The supplied passages establish the testing setup but do not specify a final significance threshold.
A.1. One sample tests.
The one-sample procedure estimates, at each filtration value, how often null-model samples attain connectivity at least as extreme as the observed hypergraph. It uses a one-sided alternative and differs from the two-sample permutation test discussed in related work.
- One-sample test: At each filtration value, the p-value is the fraction of null-model samples whose connectivity is at least as large as the observed value.The null-model sample size is denoted nℓ.
- One-sample test: The alternative hypothesis is that the observed connectivity metric is stochastically larger than the null-model value.This makes the procedure one-sided rather than testing for any difference in either direction.
- Permutation-test distinction: The literature’s permutation test is a two-sample test with one observed sample, and it is not generally equivalent to the Fisher one-sample permutation test.The distinction arises because the two procedures have different null permutation distributions.
A.2. Two sample tests.
The paper extends its one-sample testing framework to compare observed and null-model connectivity metrics using a two-sample permutation test. The procedure uses differences in sample means and recovers the one-sample test as a limiting special case.
- The two-sample test compares samples from an observed baseline ensemble and a corresponding null model using the difference in means.The samples are denoted X1 and X2, with sizes n1 and n2.
- A null permutation distribution is formed by randomly reassigning observations into samples of the original sizes and recomputing the test statistic.The p-value is the probability of obtaining a difference at least as extreme as the observed one under this permutation distribution.
- In practice, finite ensembles are sampled rather than exhaustively enumerated because full enumeration is computationally prohibitive for large graphs.Large samples of the two ensembles and of the null permutation distribution are treated as sufficient for computation.
- With one observed baseline value, the permutation distribution reduces to n2 + 1 possible differences involving each null-model observation or the baseline value.This establishes the connection between the two-sample construction and the one-sample statistic.
- As the null-model sample size grows, the one-sample expression is recovered, providing consistent tests for observed curves against corresponding null models.
Appendix B. Supplementary Tables and Figures
The supplementary material documents degeneracy in TO-configuration models and presents rich-club analyses for three connectomes and poem-derived TO-hypergraphs. These materials support comparisons of higher-order structure across datasets and null models.
- Table S1 reports average degenerate-edge counts for TO-configuration models of the C. elegans, Drosophila larva, and MICrONS hypergraphs.It compares models without rerolling and with up to 10 rerolls, alongside original k-edge counts and the total nodes in those edges.
- Supplementary figures show rich-club analyses for the C. elegans, Drosophila larva, and MICrONS connectomes.The figures include pairwise rich clubs, Jaccard similarities, k-hyper-rich-club curves, and induced subgraph or spatial visualizations, normalized by 1000 configuration models.
- Figure S4 presents hyper-rich clubs for totally ordered hypergraphs constructed from poems by Shakespeare, Burn, and Whitman.