Pith. sign in

REVIEW 2 major objections 6 minor 42 references

The Informational Cost of Structure: Representational Complexity in Networked Dynamical Systems

T0 review · 2 major / 6 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read No exact structural representation of a dynamical system can undercut the Kolmogorov complexity of the dynamics itself; graphs and hypergraphs become distinguishable only when modeling restrictions limit how information may be split between

desk verdict Clean AIT reframing of the graph–hypergraph debate: RC and the floor theorem are solid; the regimes are conditional and the examples are only counting proxies. read the letter →

arxiv 2607.03608 v1 pith:YH7NIUY7 submitted 2026-07-03 cs.IT cond-mat.stat-mechmath.ITphysics.soc-ph

Cyril Rommens , Pietro Traversa , Guilherme Ferraz de Arruda , Yamir Moreno This is my paper
classification cs.ITcond-mat.stat-mechmath.ITphysics.soc-ph
keywords representationalcomplexityKolmogorovnetworkeddynamicalsystemsgraphshypergraphsalgorithmicinformationtheoryminimumdescriptionlengthhigher-orderinteractions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how much information it takes to describe a networked dynamical system as an interaction structure plus an evolution rule. Using algorithmic information theory, it defines Representational Complexity as the extra description length of any structure-plus-rule model above the shortest description of the dynamics alone. That shortest description is a hard floor: no exact representation can beat it. When rules may be arbitrary, graphs, hypergraphs and other formalisms all reach the floor by parking missing information inside the rule, so raw expressiveness cannot choose among them. Meaningful cost differences appear only after scientific modeling restricts the admissible structures and rules; under those restrictions the paper gives conditions for informational equivalence and for graph-preferred, hypergraph-preferred and mixed regimes. The choice of network language is therefore a question of informational cost and mechanistic transparency, not of universal power.

What carries the argument

Representational Complexity RC(S, D) := K(S, D) − K(F), together with the relative cost ΔRC between ideal graph and hypergraph representations. These quantities turn the structural-language debate into a comparison of how modeling constraints distribute algorithmic information between skeleton and dynamics.

What would settle it

Build restricted graph and hypergraph model classes whose mutual translators themselves require description length that grows with N; if the measured description-length gap then reverses sign relative to the fixed-translator prediction, the claimed regime classification fails for that system.

Watch

Extended reading notes

Core claim

Representational Complexity RC(S, D) = K(S, D) − K(F) is the excess Kolmogorov complexity of encoding a dynamical map F by a structure S and rule D. Theorem 3 proves that no exact representation can be shorter than K(F) up to an additive constant, so any explicit structure is a non-compressive modeling commitment. In the unrestricted setting every structural language reaches this floor by shifting information between skeleton and dynamics; real differences between graphs and hypergraphs arise only inside restricted model classes, and then only under explicit recoverability conditions that relate their structures and rules.

Load-bearing premise

All decoding conventions, projections and rule catalogues are treated as fixed finite objects that do not grow with system size, so that additive constants stay bounded as networks get larger.

Editorial extensions

If this is right

  • Unrestricted expressiveness alone cannot justify preferring graphs over hypergraphs or the reverse, because either language can absorb missing structure into an arbitrary rule.
  • Once admissible structures and rules are restricted, the sign of ΔRC identifies graph-preferred, hypergraph-preferred, mixed or equivalent regimes under stated recoverability conditions.
  • Explicit structure is justified by interpretability, mechanistic transparency and empirical observability, not by beating the Kolmogorov floor K(F).
  • Simple counting-based description-length estimates can serve as practical upper-bound surrogates for the incomputable Kolmogorov quantities when comparing concrete encodings.
  • Empirical selection of a structural language should jointly weigh informational cost and scientific adequacy under declared modeling constraints.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Minimum-description-length model selection between fixed graph and hypergraph code families on real group-interaction data would give a reproducible empirical test of which regime a system occupies.
  • The same cost accounting extends naturally to simplicial complexes, multilayer networks or temporal higher-order models once admissible code families are fixed for each language.
  • Systems whose interactions are recorded directly as joint events (conversations, co-authorships, biochemical complexes) are natural candidates for hypergraph-preferred descriptions whenever the residual cost of recovering the pairwise skeleton stays extensive.
  • If translators between languages grow with system size, asymptotic signs of ΔRC can flip, so stable regime claims require uniform fixed-length translators.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper introduces Representational Complexity, RC(S,D) := K(S,D) − K(F), as the excess description length of an exact structure-plus-rule representation of a finite dynamical map F relative to the Kolmogorov complexity of F itself. Theorem 3 establishes that no exact representation can undercut K(F) (up to additive constants), so the equation-based representation is a universal floor and any explicit structure is a non-negative modeling commitment. In the unrestricted setting, graphs, hypergraphs, and other formalisms are informationally interchangeable because missing structure can be absorbed into an arbitrary computable rule. Meaningful differences appear only under restricted admissible languages (L,C). Under two explicit sufficient assumptions (recoverability of H from the graph rule, and fixed-projection recoverability of G from H), graph and hypergraph ideal representations are informationally equivalent; relaxing those assumptions yields formal sufficient conditions for graph-preferred, hypergraph-preferred, and mixed regimes for ΔRC. Because K is uncomputable, the authors complement the theory with five explicit counting-based description-length estimates that illustrate analogous preferences under fixed codes, carefully labeled as heuristic proxies rather than Kolmogorov-level proofs.

Significance. If the results hold—and the core AIT arguments are standard and carefully scoped—the paper usefully relocates the graph–hypergraph debate from unrestricted expressiveness to informational cost under modeling restrictions. The floor result (Theorem 3) and the unrestricted interchangeability claim are clean, machine-independent, and rest only on the definition of prefix complexity and a fixed evaluator. The conditional equivalence derivation is a short, correct application of the chain rule and symmetry of information under two stated sufficient assumptions, not a generic claim of equivalence. The paper is unusually transparent about what is proven versus what is only suggested by counting proxies, and it correctly frames structure as a scientific commitment rather than free compression. Strengths include the explicit separation of unrestricted vs restricted regimes, the non-constructive but well-defined ideal restricted representation, and the fully derived counting arguments in Appendix A. The contribution is primarily conceptual and formal rather than empirical; its value is as a language for reasoning about modeling cost and mechanistic transparency.

major comments (2)
  1. [Section III C 2–3; Section IV caveats; Discussion] Section III C 2–3 and the caveats in Section IV: the formal regime results give sufficient conditions under which ΔRC has a definite sign, but the manuscript never exhibits an explicit map F together with ideal restricted representations for which the strict Kolmogorov inequalities (e.g., K(DG|G*) +< K(H|G*) + K(DH|H*)) are known to hold. The five counting examples are correctly labeled non-proofs of Kolmogorov-level regimes. For the abstract and Discussion claim that graph-preferred and hypergraph-preferred regimes “can emerge,” either a brief constructive existence argument (or a standard AIT existence note) or a slight softening of the language that equates the conditional mechanisms with demonstrated emergence would close the gap between proven implication and existence.
  2. [Section IV (code-dependence paragraph and Examples I–V)] Section IV, paragraph on code dependence: the paper notes that the sign of ΔL can depend on the chosen code (e.g., “all k-subsets of each neighborhood” as a short generative code collapses Example I into equivalence), yet the examples still report definite regime placements under one fixed explicit-list convention. Because the operational half of the paper is the only concrete evidence offered for preferred regimes, a short robustness check—or an explicit modeling justification for why the chosen codes are the scientifically admissible ones—would make the proxy comparisons more load-bearing for the claimed regimes.
minor comments (6)
  1. [Section II A; Section III C] The + superscript notation for O(1) relations is introduced clearly in Section II A, but a one-line reminder near Eq. (8) and the regime definitions would help readers who jump to the graph–hypergraph comparison.
  2. [Figure 1; Remark after Assumptions 1–2] Figure 1 is described as a schematic decomposition under Assumptions 1–2; ensure the figure caption restates that these are sufficient, not necessary, conditions for equivalence, matching the Remark after Eq. (13).
  3. [Definition 5; Eq. (7)] In Definition 5 and Eq. (7), the ideal restricted representation is a non-constructive set-theoretic minimum. A brief sentence noting that membership in L or C need not be decidable (already present) could be paired with a pointer that all later operational comparisons therefore use explicit codes rather than the ideal minimizer.
  4. [Appendix A, Encoding conventions] Appendix A encoding conventions suppress O(1) catalogue indices for named rules. This is fine for leading-order signs, but a short note that the convention is invalid if the admissible rule catalogue itself grows with N would align with the uniformity discussion in Section III C.
  5. [Introduction; Discussion; References] References [15]–[18] are concurrent preprints central to the debate the paper reframes; ensure citation versions and arXiv identifiers remain accurate at publication, and that the Discussion’s compatibility claim with Peixoto et al. remains precise (unrestricted expressiveness vs restricted cost).
  6. [Throughout] Typographical consistency: “Representational Complexity” is capitalized as a defined term in some places and not others; “hypergraph-preferred” hyphenation is mostly consistent but check the mixed-regime subsection heading and abstract.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: RC and the floor/regime results follow directly from standard prefix Kolmogorov identities applied to a new but non-self-referential definition.

full rationale

The paper defines Representational Complexity as RC(S,D) := K(S,D) - K(F) and proves non-negativity (Theorem 3) by the elementary observation that a fixed evaluator computes F from the pair (S,D), so K(F) +O(1) <= K(S,D). Unrestricted interchangeability and the conditional equivalence of graph/hypergraph representations (Eqs. 9-13) are obtained by substituting the chain rule and symmetry of information (standard, externally established identities) under two explicitly labeled sufficient modeling assumptions; those assumptions are not derived from the conclusion. The counting examples of Section IV are declared non-proofs and use only explicit bit-count upper bounds. No parameters are fitted, no uniqueness theorem is imported from the authors' prior work, and the two-part-code framing is openly acknowledged as an application of algorithmic statistics rather than a new derivation. The entire formal chain is therefore self-contained against external AIT benchmarks.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

The central claims rest on standard prefix Kolmogorov complexity identities plus two modeling assumptions that restrict admissible structures and rules; the only invented object is the RC measure itself. No free parameters are fitted. The ledger therefore contains ordinary mathematical background, domain modeling choices, and one definitional entity.

assumptions (6)
  • standard math Prefix-free Kolmogorov complexity satisfies the chain rule K(x,y) = K(x)+K(y|x*) + O(1) and symmetry of information (Eqs. 1–2).
    Invoked throughout Sections II–III to decompose RC and ΔRC; standard textbook fact (Li & Vitányi).
  • domain assumption Every finite Boolean map F:{0,1}^N o {0,1}^N is identified with its truth table (binary string of length N 2^N).
    Stated in Section II B; required to treat K(F) as ordinary string complexity.
  • domain assumption Model classes (L,C) are realizable: at least one admissible pair (S,D) with D(S)=F exists.
    Definition 5 and surrounding text; guarantees the minimum defining ideal restricted representations is attained.
  • ad hoc to paper Assumption 1: K(DG|G*) = K(H|G*) + K(DH|H*) (graph rule recovers hypergraph optimally).
    Section III C 1; sufficient condition for informational equivalence; paper notes it may fail empirically.
  • ad hoc to paper Assumption 2: K(G|H*) = 0 (graph is fixed computable projection of hypergraph).
    Section III C 1; second sufficient condition for equivalence; likewise may fail for non-projectable groups.
  • domain assumption Uniformity: decoding conventions, pairing, evaluator and projection maps are fixed finite objects independent of N.
    Section III C asymptotic paragraph; needed so that O(1) terms do not grow with system size and regime signs are asymptotically stable.
invented entities (1)
  • Representational Complexity RC(S,D) := K(S,D) - K(F)
    purpose: Quantifies the excess description length of any exact structure-plus-rule representation relative to the intrinsic complexity of the dynamical map.
    Definition 2; the central invented quantity of the paper. Independent evidence is definitional rather than empirical; the paper supplies no external falsifiable prediction that would confirm RC outside its own formalism.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Informational Cost of Structure: Representational Complexity in Networked Dynamical Systems." pith.science (2026). https://pith.science/paper/YH7NIUY7

@misc{pith2026260703608,
  author       = {Pith},
  title        = {Pith review of: The Informational Cost of Structure: Representational Complexity in Networked Dynamical Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YH7NIUY7}},
  note         = {Machine review of arXiv:2607.03608}
}
read the original abstract

How much information is required to represent a dynamical system in terms of an interaction structure and an evolution rule? We address this question using algorithmic information theory. We introduce Representational Complexity, the excess description length of a structure-plus-rule model relative to the shortest possible description of the dynamics itself. This intrinsic description defines a universal lower bound: no exact structural representation can be more concise. If arbitrary rules are allowed, graphs, hypergraphs, and other formalisms can all reach this bound by shifting information between structure and dynamics, so expressiveness alone cannot distinguish them. Meaningful differences arise only when scientific modeling restricts the admissible structures and rules. Within this setting, we identify conditions under which graph and hypergraph descriptions are informationally equivalent, and show how graph-preferred, hypergraph-preferred, and mixed regimes can emerge when those conditions are relaxed. Because Kolmogorov complexity is not computable, we complement the formal results with explicit description-length estimates. Our framework reframes the choice of network representation as a question of informational cost and mechanistic transparency rather than universal expressive power.

Figures

Figures reproduced from arXiv: 2607.03608 by the authors.

Figure 1
Figure 1. FIG. 1. Schematic decomposition of the complexity contributions of the graph and hypergraph representations under Assump [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references · 2 linked inside Pith

  1. [1]

    The Unrestricted Setting Definition 4(Unrestricted representation).A representation R = (S, D)of F isunrestrictedif S and D are subject to no constraint beyond computability and D(S) = F ; in particular, no constraint is imposed on how information is distributed betweenSandD. 5 If, in this setting, the structural part S instantiates a specific, familiar s...

  2. [2]

    S∈ L ) and D is constrained to belong to an admissible class of computable dynamical rules C (i.e

    The Restricted Setting Definition 5(Restricted representation).A representation R = (S, D)of F isrestrictedif S is constrained to belong to a structural language L (i.e. S∈ L ) and D is constrained to belong to an admissible class of computable dynamical rules C (i.e. D∈ C ). The constraints( L,C )fix how information may be distributed between S and D. We...

  3. [3]

    Equivalence regime (∆RC + = 0) By Eq. (8), graph and hypergraph representations lie in the equivalence regime precisely when K(G) + K(DG |G ∗) + = K(H) + K(DH |H ∗).(9) In this regime, neither representation enjoys a compressive advantage: both carry the same algorithmic information, differing only in how that information is distributed between structure ...

  4. [4]

    Graph-preferred regime (∆RC + <0) This regime is obtained from the equivalence case by retaining Assumption 2 but breaking Assumption 1 in the graph’s favour. Concretely, suppose the graph still arises as a fixed projection of the hypergraph, K(G|H ∗) + = 0,(14) but that the graph-based rule encodes the higher-order informationstrictlymore compactly than ...

  5. [5]

    Hypergraph-preferred regime (∆RC + >0) The previous two regimes retained Assumption 2, that the graph is a fixed projection of the hypergraph. The hypergraph-preferred regime is the one in which this assumptionfails: the operative higher-order groups are not recoverable from the pairwise skeleton by a fixed program, so K(G|H ∗) + >0.(16) Suppose, in addit...

  6. [6]

    all k-subsets of each neighborhood

    Mixed regime The remaining possibility combines a graph-favouring dynamical term with a hypergraph-favoring structural term: Assumption 1 tips toward the graph, K(DG |G ∗) + <K(H|G ∗) + K(DH |H ∗), while Assumption 2 fails, so the skeleton is not recoverable from the hypergraph, K(G|H ∗) + >0. 9 Carrying out the same chain-rule and symmetry-of-information...

    doi:10.13039/501100011033 2024

  7. [7]

    Oxford university press, 2018

    Mark Newman.Networks. Oxford university press, 2018

    2018

  8. [8]

    Network science.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1987):20120375, 2013

    Albert-L´ aszl´ o Barab´ asi. Network science.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1987):20120375, 2013

    1987

Show all 42 references
  1. [9]

    Strogatz

    Steven H. Strogatz. Exploring complex networks.Nature, 410(6825):268–276, 2001

    2001

  2. [10]

    Oliveira, Gonzalo Travieso, Francisco Aparecido Rodrigues, Paulino Ribeiro Villas Boas, Lucas Antiqueira, Matheus Palhares Viana, and Luis Enrique Correa da Rocha

    Luciano da Fontoura Costa, Osvaldo N. Oliveira, Gonzalo Travieso, Francisco Aparecido Rodrigues, Paulino Ribeiro Villas Boas, Lucas Antiqueira, Matheus Palhares Viana, and Luis Enrique Correa da Rocha. Analyzing and modeling real-world phenomena with complex networks: a survey...

    2011

  3. [11]

    Boccaletti, V

    S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics.Physics Reports, 424(4–5):175–308, 2006

    2006

  4. [12]

    Twenty years of network science.Nature, 558:528–529, 2018

    Alessandro Vespignani. Twenty years of network science.Nature, 558:528–529, 2018

    2018

  5. [13]

    Blevins, Danielle Bassett, and Tina Eliassi-Rad

    Leo Torres, Ann S. Blevins, Danielle Bassett, and Tina Eliassi-Rad. The why, how, and when of representations for complex systems.SIAM Review, 63(3):435–485, 2021

    2021

  6. [14]

    Networks beyond pairwise interactions: Structure and dynamics.Physics Reports, 874:1–92, 2020

    Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. Networks beyond pairwise interactions: Structure and dynamics.Physics Reports, 874:1–92, 2020

    2020

  7. [15]

    Harrington, and Michael T

    Christian Bick, Elizabeth Gross, Heather A. Harrington, and Michael T. Schaub. What are higher-order networks?SIAM Review, 65(3):686–731, 2023

    2023

  8. [16]

    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. Nature Physics, 15:313–320, 2019

    2019

  9. [17]

    The physics of higher-order interactions in complex systems

    Federico Battiston, Enrico Amico, Alain Barrat, Ginestra Bianconi, Guilherme Ferraz de Arruda, Benedetta Franceschiello, Iacopo Iacopini, Sonia K´ efi, Vito Latora, Yamir Moreno, et al. The physics of higher-order interactions in complex systems. Nature physics, 17(10):1093–1098, 2021

    2021

  10. [18]

    Carter T. Butts. Revisiting the foundations of network analysis.Science, 325(5939):414–416, 2009

    2009

  11. [19]

    Gleeson, Yamir Moreno, and Mason A

    Mikko Kivel¨ a, Alex Arenas, Marc Barthelemy, James P. Gleeson, Yamir Moreno, and Mason A. Porter. Multilayer networks. Journal of Complex Networks, 2(3):203–271, 2014

    2014

  12. [20]

    Temporal networks.Physics Reports, 519(3):97–125, 2012

    Petter Holme and Jari Saram¨ aki. Temporal networks.Physics Reports, 519(3):97–125, 2012

    2012

  13. [21]

    Peixoto, Leto Peel, Thilo Gross, and Manlio De Domenico

    Tiago P. Peixoto, Leto Peel, Thilo Gross, and Manlio De Domenico. Graphs are maximally expressive for higher-order interactions. Preprint, arXiv:2602.16937, 2026

    2026

  14. [22]

    Exploring the non-uniqueness of node co-occurrence matrices of hypergraphs

    Timothy LaRock and Renaud Lambiotte. Exploring the non-uniqueness of node co-occurrence matrices of hypergraphs. Preprint, arXiv:2506.01479, 2025

    2025 arXiv

  15. [23]

    On the equivalence between nonlinear graph-based dynamics and linear dynamics on higher-order networks

    Lucas Lacasa. On the equivalence between nonlinear graph-based dynamics and linear dynamics on higher-order networks. Preprint, arXiv:2602.21727, 2026

    2026

  16. [24]

    Reducibility of higher-order to pairwise interactions: Social impact models on hypergraphs.Physical Review Research, 2026

    Jaume Llabre´ s, Ra´ ul Toral, Maxi San Miguel, and Federico V´ azquez. Reducibility of higher-order to pairwise interactions: Social impact models on hypergraphs.Physical Review Research, 2026

    2026

  17. [25]

    Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    Jorma Rissanen. Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    1978

  18. [26]

    The minimum description length principle in coding and modeling.IEEE transactions on information theory, 44(6):2743–2760, 1998

    Andrew Barron, Jorma Rissanen, and Bin Yu. The minimum description length principle in coding and modeling.IEEE transactions on information theory, 44(6):2743–2760, 1998

    1998

  19. [27]

    Gr¨ unwald.The Minimum Description Length Principle

    Peter D. Gr¨ unwald.The Minimum Description Length Principle. MIT Press, Cambridge, MA, 2007

    2007

  20. [28]

    Contagion dynamics on higher-order networks.Nature Reviews Physics, 6(8):468–482, 2024

    Guilherme Ferraz de Arruda, Alberto Aleta, and Yamir Moreno. Contagion dynamics on higher-order networks.Nature Reviews Physics, 6(8):468–482, 2024

    2024

  21. [29]

    Defining and classifying models of groups: The social ontology of higher-order networks.arXiv preprint arXiv:2507.02758, 2025

    Jonathan St-Onge, Randall Harp, Giulio Burgio, Timothy M Waring, Juniper Lovato, and Laurent H´ ebert-Dufresne. Defining and classifying models of groups: The social ontology of higher-order networks.arXiv preprint arXiv:2507.02758, 2025

    2025 arXiv

  22. [30]

    Hypergraphs and simplicial complexes in focus: A roadmap for future research in higher-order interactions.Journal of Physics: Complexity, 2026

    Aida Abiad, Alex Arenas, Agnes Backhausz, Jozsef Balogh, Christopher RS Banerji, Sergio Barbarossa, Ginestra Bianconi, Christian Bick, Magnus Bakke B Botnan, Timoteo Carletti, et al. Hypergraphs and simplicial complexes in focus: A roadmap for future research in higher-order i...

    2026

  23. [31]

    A new look at the statistical model identification.IEEE Transactions on Automatic Control, 19(6):716–723, 1974

    Hirotugu Akaike. A new look at the statistical model identification.IEEE Transactions on Automatic Control, 19(6):716–723, 1974

    1974

  24. [32]

    On structural identifiability.Mathematical Biosciences, 7(3):329–339, 1970

    Richard Bellman and Karl Johan ˚Astr¨ om. On structural identifiability.Mathematical Biosciences, 7(3):329–339, 1970

    1970

  25. [33]

    Peter Machamer, Lindley Darden, and Carl F. Craver. Thinking about mechanisms.Philosophy of Science, 67(1):1–25, 2000

    2000

  26. [34]

    Ming Li and Paul M. B. Vit´ anyi.An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, 4 edition, 2019

    2019

  27. [35]

    Tromp, and Paul M

    P´ eter G´ acs, John T. Tromp, and Paul M. B. Vit´ anyi. Algorithmic statistics.IEEE Transactions on Information Theory, 47(6):2443–2463, 2001

    2001

  28. [36]

    Nikolai Vereshchagin and Paul M. B. Vit´ anyi. Kolmogorov’s structure functions and model selection.IEEE Transactions on Information Theory, 50(12):3265–3290, 2004. 14

    2004

  29. [37]

    OR over neighbors

    Guilherme Ferraz de Arruda, Alberto Aleta, and Yamir Moreno. Contagion dynamics on higher-order networks.Nature Reviews Physics, 6:468–482, 2024. Appendix A: Description-length derivations for the examples This appendix gives the detailed counting arguments behind the descript...

    2024

  30. [38]

    A graph preferred case: example IV A Let G be d-regular with neighborhoods Ui of size d, and fix 1 ≤θ≤k≤d . The hypergraph assigns to each node the family Hi = {A⊆U i : |A| = k} of all k-subsets of its neighborhood, and the dynamics is the group-threshold rule xi(t+ 1) =1 h ∃A...

  31. [39]

    Graph cost.The structure is the adjacency, with P i |Ai| incidences, hence L(G) =P i |Ai|logN

    A graph preferred case: example IV B Let N binary nodes evolve by the SI-type rule xi(t + 1) =W j∈Ai xj(t) on a graph G with adjacency sets Ai, and let a hypergraph H of M size-k edges be supplied independently of G (for instance as external metadata), so that H carries no inf...

  32. [40]

    Graph cost.The edge list costs L(G) = 2|E|logN (two labels per edge), equivalently P i |Ai|logN = 2|E|logN since each edge contributes two incidences

    An equivalence case: example IV C Let the dynamics depend only on pairwise relations carried by the edges of G, with |E| edges, and let H be the size-two hypergraph whose hyperedges are exactly those pairs. Graph cost.The edge list costs L(G) = 2|E|logN (two labels per edge), ...

  33. [41]

    The hypergraph of operative groups isH={A i}N i=1

    A hypergraph preferred case: example IV D Let G be d-regular, and suppose each node i has a single true interaction group Ai ⊆U i of size k, with threshold dynamicsx i(t+ 1) =1[ P j∈Ai xj(t)≥θ] over that group. The hypergraph of operative groups isH={A i}N i=1. Hypergraph cost...

  34. [42]

    Hypergraph cost.The structure lists M size-k edges, so L(H) = M klogN

    A hypergraph preferred case: example IV E LetNnodes interact throughMrandomk-hyperedges withk≥3, under the XOR–AND rule xi(t+ 1) = _ ℓ:i∈e ℓ ^ j∈eℓ\{i} xj(t). Hypergraph cost.The structure lists M size-k edges, so L(H) = M klogN . The dynamics is the named rule (conjunction wi...

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.