The nestedness of higher-order networks
Pith reviewed 2026-05-19 23:38 UTC · model grok-4.3
The pith
Higher-order networks display nested containment that unifies several measures via encapsulation graphs
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By defining the encapsulation directed acyclic graph to capture containment relations, the paper shows that existing measures of nestedness, simpliciality, encapsulation, and inclusion are all functions of this graph's properties. Analysis of empirical higher-order networks from social domains demonstrates the prevalence of nested structures and the distinct information each measure provides. The absence of nestedness emerges as a signal of mesoscale organization in these systems.
What carries the argument
The encapsulation directed acyclic graph, a mathematical object that encodes containment among higher-order interactions and serves as the basis for expressing all related measures.
If this is right
- Nested structure is prevalent in social systems across several domains.
- Different measures capture complementary aspects of this structure.
- The absence of nestedness can itself be a powerful indicator of the mesoscale organization of a system.
Where Pith is reading between the lines
- Researchers could use this unified framework to compare results across studies that previously used incompatible measures.
- The approach might extend to other domains like biological or technological networks where containment occurs.
- Absence of nestedness could be used as a diagnostic tool for detecting specific types of community structures.
Load-bearing premise
The encapsulation directed acyclic graph can formulate each existing measure as a function of its properties without significant loss or distortion of the original definitions.
What would settle it
A concrete counterexample would be a higher-order network dataset where one of the original measures of nestedness or simpliciality differs substantially from the value computed via the encapsulation directed acyclic graph.
Figures
read the original abstract
In contrast to dyadic interactions, higher-order interactions may contain one another, with subgroups naturally embedded within larger groups. These containment patterns arise empirically in ecology, sociology, computer science and the science of science, and have been studied under the names nestedness, simpliciality, encapsulation, and inclusion. In this chapter, we review each of these measures and unify them through a mathematical object known as the encapsulation directed acyclic graph, formulating each measure as a function of its properties. We demonstrate that nested structure is prevalent in social systems across several domains, show that different measures capture complementary aspects of this structure, and find that the absence of nestedness can itself be a powerful indicator of the mesoscale organization of a system.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript reviews measures of nested structure in higher-order networks (nestedness, simpliciality, encapsulation, and inclusion) and unifies them by formulating each as a function of properties of the encapsulation directed acyclic graph (EDAG). It claims that such nested structure is prevalent in social systems across domains, that the different measures capture complementary aspects of the structure, and that the absence of nestedness can indicate mesoscale organization.
Significance. If the unification is shown to be exact and lossless, the work offers a useful synthesis across ecology, sociology, computer science, and the science of science, with empirical support for prevalence and the indicator role of nestedness. Credit is given for the broad review of prior measures and the attempt to ground multiple concepts in a single mathematical object.
major comments (2)
- [§3] §3 (Encapsulation DAG and unification): the claim that simpliciality (originally a closure property on the face lattice of a simplicial complex) can be exactly recovered as a function of EDAG reachability or topological order must be verified explicitly. Pairwise containment in the DAG may omit higher-dimensional subset constraints that are not recoverable from the reformulation, which would undermine the subsequent claims that the measures are complementary and that absence of nestedness signals mesoscale organization.
- [§4–5] §4–5 (Formulation of inclusion and encapsulation): if the mapping from original definitions to EDAG properties is not bijective, the demonstrations that different measures capture complementary aspects rest on an altered object rather than the source concepts. A concrete check (e.g., an example simplicial complex where the EDAG-derived simpliciality score differs from the lattice-based definition) is needed.
minor comments (2)
- [Abstract] Abstract: the phrase 'in this chapter' should be clarified for readers who encounter the manuscript as a standalone arXiv preprint.
- [Notation] Notation: introduce the acronym 'EDAG' at first use and ensure consistent terminology for 'containment' versus 'inclusion' across sections.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive comments. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation of the unification.
read point-by-point responses
-
Referee: [§3] §3 (Encapsulation DAG and unification): the claim that simpliciality (originally a closure property on the face lattice of a simplicial complex) can be exactly recovered as a function of EDAG reachability or topological order must be verified explicitly. Pairwise containment in the DAG may omit higher-dimensional subset constraints that are not recoverable from the reformulation, which would undermine the subsequent claims that the measures are complementary and that absence of nestedness signals mesoscale organization.
Authors: We appreciate the referee's emphasis on explicit verification. The EDAG is the Hasse diagram of the inclusion poset: nodes are the higher-order sets and a directed edge exists from A to B precisely when B properly contains A with no intermediate set. Reachability in this DAG therefore recovers the full transitive closure of the subset relation, which encodes all higher-order inclusions (including multi-level subset constraints) via chains rather than direct pairwise links alone. Simpliciality, as downward closure under subsets, is recovered by verifying that every node has all its lower-reachable nodes present in the collection. We will add an explicit proof of this equivalence to the revised §3, showing that the topological order and reachability preserve the original lattice properties without loss. This supports rather than undermines the claims of complementarity and the indicator role of nestedness absence. revision: yes
-
Referee: [§4–5] §4–5 (Formulation of inclusion and encapsulation): if the mapping from original definitions to EDAG properties is not bijective, the demonstrations that different measures capture complementary aspects rest on an altered object rather than the source concepts. A concrete check (e.g., an example simplicial complex where the EDAG-derived simpliciality score differs from the lattice-based definition) is needed.
Authors: We agree that a concrete check strengthens the argument. In the revised manuscript we will insert, in §4 or §5, a worked example of a small simplicial complex. For this example we will compute the simpliciality score both from the original face-lattice definition and from the corresponding EDAG reachability properties, demonstrating numerical agreement. This will also serve as an explicit test of bijectivity for the relevant cases. Should any non-bijective edge cases appear, we will delineate the precise conditions under which the mapping remains faithful. Because the EDAG is constructed directly from the inclusion relations that underlie the source definitions, we expect the scores to match, but the added example will make this transparent. revision: yes
Circularity Check
No significant circularity in unification of nestedness measures
full rationale
The paper reviews prior definitions of nestedness, simpliciality, encapsulation, and inclusion, then introduces the encapsulation directed acyclic graph as a unifying object and expresses each measure as a function of DAG properties. This is a standard review-and-reformulation contribution whose central claims rest on independent grounding in the original combinatorial definitions and empirical data rather than any self-definitional loop, fitted parameter renamed as prediction, or load-bearing self-citation. No equation or step reduces the unification result to its own inputs by construction; concerns about possible distortion in the mapping are questions of correctness or fidelity, not circularity.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Directed acyclic graphs can represent containment hierarchies without cycles
invented entities (1)
-
encapsulation directed acyclic graph
no independent evidence
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We represent the nested structure of higher-order interactions using line graphs... the encapsulation directed acyclic graph (DAG), introduced in Ref. [26]. ... each directed edge points from a containing hyperedge to the hyperedge it contains.
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
a hyperedge is a simplex if its out-degree is equal to the size of its power set minus two... d_out(e) = |P(e)|−2
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Measuring and Model- ing Bipartite Graphs with Community Structure
Sinan G. Aksoy, Tamara G. Kolda, and Ali Pinar. “Measuring and Model- ing Bipartite Graphs with Community Structure”. In:Journal of Complex Networks5.4 (Aug. 2017), pp. 581–603.issn: 2051-1310.doi: 10.1093/ comnet/cnx001.url: https://doi.org/10.1093/comnet/cnx001
-
[2]
Hypernetwork Science via High-Order Hypergraph Walks
Sinan G. Aksoy et al. “Hypernetwork Science via High-Order Hypergraph Walks”. In:EPJ Data Science9.1 (Dec. 2020), p. 16.issn: 2193-1127.doi: 10.1140/epjds/s13688-020-00231-0.url: https://doi.org/10.1140/epjds/ s13688-020-00231-0
-
[3]
The Measure of Order and Disorder in the Distribution of Species in Fragmented Habitat
Wirt Atmar and Bruce D. Patterson. “The Measure of Order and Disorder in the Distribution of Species in Fragmented Habitat”. In:Oecologia96.3 (Dec. 1993), pp. 373–382.issn: 1432-1939.doi: 10 . 1007 / BF00317508. url: https://doi.org/10.1007/BF00317508
-
[4]
Federica Baccini, Filippo Geraci, and Ginestra Bianconi. “Weighted Sim- plicial Complexes and Their Representation Power of Higher-Order Net- work Data and Topology”. In:Physical Review E106.3 (Sept. 2022), 22 T. LaRock, Y. Zhang, J.-G. Young, N. Eikmeier, R. Lambiotte, and N. Landry p. 034319.doi: 10.1103/PhysRevE.106.034319.url: https://doi.org/10. 1103...
-
[5]
Emergence of Scaling in Ran- dom Networks
Albert-L´ aszl´ o Barab´ asi and R´ eka Albert. “Emergence of Scaling in Ran- dom Networks”. In:Science286.5439 (Oct. 1999), pp. 509–512.doi: 10. 1126/science.286.5439.509.url: https://doi.org/10.1126/science.286. 5439.509
-
[6]
Counting Simplicial Pairs in Hypergraphs
Jordan Barrett et al. “Counting Simplicial Pairs in Hypergraphs”. In: Journal of Complex Networks13.4 (Aug. 2025), cnaf021.issn: 2051-1329. doi: 10.1093/comnet/cnaf021.url: https://doi.org/10.1093/comnet/ cnaf021
-
[7]
The Nested Assembly of Plant–Animal Mutu- alistic Networks
Jordi Bascompte et al. “The Nested Assembly of Plant–Animal Mutu- alistic Networks”. In:Proceedings of the National Academy of Sciences 100.16 (Aug. 2003), pp. 9383–9387.doi: 10.1073/pnas.1633576100.url: https://doi.org/10.1073/pnas.1633576100
-
[8]
Networks beyond Pairwise Interactions: Struc- ture and Dynamics
Federico Battiston et al. “Networks beyond Pairwise Interactions: Struc- ture and Dynamics”. In:Physics Reports. Networks beyond Pairwise In- teractions: Structure and Dynamics 874 (Aug. 2020), pp. 1–92.issn: 0370- 1573.doi: 10.1016/j.physrep.2020.05.004.url: https://doi.org/10.1016/ j.physrep.2020.05.004
-
[9]
Deep learning for early warning signals of tipping points
Austin R. Benson et al. “Simplicial Closure and Higher-Order Link Predic- tion”. In:Proceedings of the National Academy of Sciences115.48 (Nov. 2018), E11221–E11230.issn: 0027-8424, 1091-6490.doi: 10.1073/pnas. 1800683115.url: https://doi.org/10.1073/pnas.1800683115
-
[10]
Giulio Burgio, Sergio G´ omez, and Alex Arenas. “Triadic Approximation Reveals the Role of Interaction Overlap on the Spread of Complex Conta- gions on Higher-Order Networks”. In:Physical Review Letters132.7 (Feb. 2024), p. 077401.doi: 10 . 1103 / PhysRevLett . 132 . 077401.url: https : //doi.org/10.1103/PhysRevLett.132.077401
-
[11]
Configuration Models of Random Hypergraphs
Philip S Chodrow. “Configuration Models of Random Hypergraphs”. In: Journal of Complex Networks8.cnaa018 (June 2020).issn: 2051-1329. doi: 10.1093/comnet/cnaa018.url: https://doi.org/10.1093/comnet/ cnaa018
-
[12]
Generative Hy- pergraph Clustering: From Blockmodels to Modularity
Philip S. Chodrow, Nate Veldt, and Austin R. Benson. “Generative Hy- pergraph Clustering: From Blockmodels to Modularity”. In:Science Ad- vances7.28 (July 2021), eabh1303.doi: 10.1126/sciadv.abh1303.url: https://doi.org/10.1126/sciadv.abh1303
-
[13]
A Comparison of Relict versus Equilibrium Models for Insular Mammals of the Gulf of Maine
Kenneth L. Crowell. “A Comparison of Relict versus Equilibrium Models for Insular Mammals of the Gulf of Maine”. In:Biological Journal of the Linnean Society28.1-2 (May 1986), pp. 37–64.issn: 0024-4066.doi: 10. 1111/j.1095-8312.1986.tb01748.x.url: https://doi.org/10.1111/j.1095- 8312.1986.tb01748.x
-
[14]
Hypergraph Reconstruction from Dynamics
Robin Delabays et al. “Hypergraph Reconstruction from Dynamics”. In: Nature Communications16.1 (Mar. 2025), p. 2691.issn: 2041-1723.doi: 10.1038/s41467-025-57664-2.url: https://doi.org/10.1038/s41467-025- 57664-2. 1 The nestedness of higher-order networks 23
-
[15]
Line Graphs, Link Partitions, and Over- lapping Communities
T. S. Evans and R. Lambiotte. “Line Graphs, Link Partitions, and Over- lapping Communities”. In:Physical Review E80.1 (July 2009), p. 016105. doi: 10 . 1103 / PhysRevE . 80 . 016105.url: https : / / doi . org / 10 . 1103 / PhysRevE.80.016105
work page 2009
-
[16]
Connecting the Congress: A Study of Cosponsorship Networks
James H. Fowler. “Connecting the Congress: A Study of Cosponsorship Networks”. In:Political Analysis14.4 (2006), pp. 456–487.issn: 1047- 1987, 1476-4989.doi: 10.1093/pan/mpl002.url: https://doi.org/10. 1093/pan/mpl002
-
[17]
Legislative Cosponsorship Networks in the US House and Senate
James H. Fowler. “Legislative Cosponsorship Networks in the US House and Senate”. In:Social Networks28.4 (Oct. 2006), pp. 454–465.issn: 0378-8733.doi: 10.1016/j.socnet.2005.11.003.url: https://doi.org/10. 1016/j.socnet.2005.11.003
-
[18]
Improving the Analyses of Nestedness for Large Sets of Matrices
Paulo R. Guimar˜ aes and Paulo Guimar˜ aes. “Improving the Analyses of Nestedness for Large Sets of Matrices”. In:Environmental Modelling & Software21.10 (Oct. 2006), pp. 1512–1513.issn: 1364-8152.doi: 10.1016/ j.envsoft.2006.04.002.url: https://doi.org/10.1016/j.envsoft.2006.04.002
-
[19]
The Temporal Dy- namics of Group Interactions in Higher-Order Social Networks
Iacopo Iacopini, M´ arton Karsai, and Alain Barrat. “The Temporal Dy- namics of Group Interactions in Higher-Order Social Networks”. In:Na- ture Communications15.1 (Aug. 2024), p. 7391.issn: 2041-1723.doi: 10.1038/s41467-024-50918-5.url: https://doi.org/10.1038/s41467-024- 50918-5
-
[20]
Contagion Dynamics on Hy- pergraphs with Nested Hyperedges
Jihye Kim, Deok-Sun Lee, and K.-I. Goh. “Contagion Dynamics on Hy- pergraphs with Nested Hyperedges”. In:Physical Review E108.3 (Sept. 2023), p. 034313.doi: 10.1103/PhysRevE.108.034313.url: https://doi. org/10.1103/PhysRevE.108.034313
-
[21]
From Networks to Optimal Higher-Order Models of Complex Systems
Renaud Lambiotte, Martin Rosvall, and Ingo Scholtes. “From Networks to Optimal Higher-Order Models of Complex Systems”. In:Nature Physics 15.4 (Apr. 2019), pp. 313–320.issn: 1745-2481.doi: 10.1038/s41567-019- 0459-y.url: https://doi.org/10.1038/s41567-019-0459-y
-
[22]
Hypergraph Assortativity: A Dynamical Systems Perspective
Nicholas W. Landry and Juan G. Restrepo. “Hypergraph Assortativity: A Dynamical Systems Perspective”. In:Chaos: An Interdisciplinary Journal of Nonlinear Science32.5 (May 2022), p. 053113.issn: 1054-1500.doi: 10.1063/5.0086905.url: https://doi.org/10.1063/5.0086905
-
[23]
The Sim- pliciality of Higher-Order Networks
Nicholas W. Landry, Jean-Gabriel Young, and Nicole Eikmeier. “The Sim- pliciality of Higher-Order Networks”. In:EPJ Data Science13.1 (Dec. 2024), pp. 1–20.issn: 2193-1127.doi: 10.1140/epjds/s13688-024-00458-1. url: https://doi.org/10.1140/epjds/s13688-024-00458-1
-
[24]
Filtering Higher-Order Datasets
Nicholas W. Landry et al. “Filtering Higher-Order Datasets”. In:Journal of Physics: Complexity5.1 (Feb. 2024), p. 015006.issn: 2632-072X.doi: 10 . 1088 / 2632 - 072X / ad253a.url: https : / / doi . org / 10 . 1088 / 2632 - 072X/ad253a
work page 2024
-
[25]
XGI: A Python Package for Higher-Order Interaction Networks
Nicholas W. Landry et al. “XGI: A Python Package for Higher-Order Interaction Networks”. In:Journal of Open Source Software8.85 (May 2023), p. 5162.issn: 2475-9066.doi: 10.21105/joss.05162.url: https: //doi.org/10.21105/joss.05162. 24 T. LaRock, Y. Zhang, J.-G. Young, N. Eikmeier, R. Lambiotte, and N. Landry
-
[26]
Encapsulation Structure and Dynamics in Hypergraphs
Timothy LaRock and Renaud Lambiotte. “Encapsulation Structure and Dynamics in Hypergraphs”. In:Journal of Physics: Complexity4.4 (Dec. 2023), p. 045007.issn: 2632-072X.doi: 10.1088/2632-072X/ad0b39.url: https://doi.org/10.1088/2632-072X/ad0b39
-
[27]
Higher-Order Motif Analysis in Hyper- graphs
Quintino Francesco Lotito et al. “Higher-Order Motif Analysis in Hyper- graphs”. In:Communications Physics5.1 (Dec. 2022), p. 79.issn: 2399- 3650.doi: 10.1038/s42005-022-00858-7.url: https://doi.org/10.1038/ s42005-022-00858-7
- [28]
-
[29]
PLoS One18(5) (2015) https://doi.org/10.1371/journal.pone
Rossana Mastrandrea, Julie Fournet, and Alain Barrat. “Contact Patterns in a High School: A Comparison between Data Collected Using Wear- able Sensors, Contact Diaries and Friendship Surveys”. In:PLOS ONE 10.9 (Sept. 2015), e0136497.issn: 1932-6203.doi: 10.1371/journal.pone. 0136497.url: https://doi.org/10.1371/journal.pone.0136497
-
[30]
InAssociation for Computing Machinery In The World Wide Web Conference (WWW ’19)
Jan Overgoor, Austin Benson, and Johan Ugander. “Choosing to Grow a Graph: Modeling Network Formation as Discrete Choice”. In:The World Wide Web Conference. WWW ’19. New York, NY, USA: Association for Computing Machinery, May 2019, pp. 1409–1420.isbn: 978-1-4503-6674- 8.doi: 10.1145/3308558.3313662.url: https://doi.org/10.1145/3308558. 3313662
-
[31]
Laura Ozella et al. “Using Wearable Proximity Sensors to Characterize Social Contact Patterns in a Village of Rural Malawi”. In:EPJ Data Science10.1 (Sept. 2021), p. 46.issn: 2193-1127.doi: 10.1140/epjds/ s13688-021-00302-w.url: https://doi.org/10.1140/epjds/s13688-021- 00302-w
-
[32]
Alice Patania, Giovanni Petri, and Francesco Vaccarino. “The Shape of Collaborations”. In:EPJ Data Science6.1 (Aug. 2017), p. 18.issn: 2193- 1127.doi: 10.1140/epjds/s13688-017-0114-8.url: https://doi.org/10. 1140/epjds/s13688-017-0114-8
-
[33]
Nested Subsets and the Structure of Insular Mammalian Faunas and Archipelagos
Bruce D. Patterson and Wirt Atmar. “Nested Subsets and the Structure of Insular Mammalian Faunas and Archipelagos”. In:Biological Journal of the Linnean Society28.1-2 (1986), pp. 65–82.issn: 1095-8312.doi: 10.1111/j.1095-8312.1986.tb01749.x.url: https://doi.org/10.1111/j. 1095-8312.1986.tb01749.x
-
[34]
Hypergraph Analytics: Modeling Higher-Order Structures and Probabilities
Ankit Sharma. “Hypergraph Analytics: Modeling Higher-Order Structures and Probabilities”. PhD thesis. 2020, p. 269.isbn: 979-8-6623-8799-7.url: https://www.proquest.com/dissertations-theses/hypergraph-analytics- modeling-higher-order/docview/2425568146/se-2
-
[35]
Weighted Simplicial Complex: A Novel Approach for Predicting Small Group Evolution
Ankit Sharma et al. “Weighted Simplicial Complex: A Novel Approach for Predicting Small Group Evolution”. In:Advances in Knowledge Discovery and Data Mining. Ed. by Jinho Kim et al. Vol. 10234. Cham: Springer International Publishing, 2017, pp. 511–523.isbn: 978-3-319-57454-7.doi: 1 The nestedness of higher-order networks 25 10.1007/978-3-319-57454-7 40.u...
-
[36]
An Overview of Microsoft Academic Service (MAS) and Applications
Arnab Sinha et al. “An Overview of Microsoft Academic Service (MAS) and Applications”. In:Proceedings of the 24th International Conference on World Wide Web. WWW ’15 Companion. New York, NY, USA: As- sociation for Computing Machinery, May 2015, pp. 243–246.isbn: 978-1- 4503-3473-0.doi: 10.1145/2740908.2742839.url: https://doi.org/10. 1145/2740908.2742839
-
[37]
Partial Entropy Decomposition Reveals Higher- Order Information Structures in Human Brain Activity
Thomas F. Varley et al. “Partial Entropy Decomposition Reveals Higher- Order Information Structures in Human Brain Activity”. In:Proceedings of the National Academy of Sciences120.30 (July 2023), e2300888120. doi: 10.1073/pnas.2300888120.url: https://doi.org/10.1073/pnas. 2300888120
-
[38]
Vaiva Vasiliauskaite, Tim S. Evans, and Paul Expert. “Cycle Analysis of Directed Acyclic Graphs”. In:Physica A: Statistical Mechanics and its Applications596 (June 2022), p. 127097.issn: 03784371.doi: 10.1016/j. physa.2022.127097.url: https://doi.org/10.1016/j.physa.2022.127097
work page doi:10.1016/j 2022
-
[39]
Community Detection in Bipar- tite Networks with Stochastic Block Models
Tzu-Chi Yen and Daniel B. Larremore. “Community Detection in Bipar- tite Networks with Stochastic Block Models”. In:Physical Review E102.3 (Sept. 2020), p. 032309.doi: 10.1103/PhysRevE.102.032309.url: https: //doi.org/10.1103/PhysRevE.102.032309
-
[40]
Re- construction of Plant–Pollinator Networks from Observational Data
Jean-Gabriel Young, Fernanda S. Valdovinos, and M. E. J. Newman. “Re- construction of Plant–Pollinator Networks from Observational Data”. In: Nature Communications12.1 (June 2021), p. 3911.issn: 2041-1723.doi: 10.1038/s41467-021-24149-x.url: https://doi.org/10.1038/s41467-021- 24149-x
-
[41]
Yuanzhao Zhang, Maxime Lucas, and Federico Battiston. “Higher-Order Interactions Shape Collective Dynamics Differently in Hypergraphs and Simplicial Complexes”. In:Nature Communications14.1 (Mar. 2023), p. 1605.issn: 2041-1723.doi: 10.1038/s41467-023-37190-9.url: https: //doi.org/10.1038/s41467-023-37190-9
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.