pith. sign in

arxiv: 2604.10193 · v1 · submitted 2026-04-11 · 🧮 math.CO · cs.DM

Strong modules and asynchronous attractors of Boolean networks

Paul Ruet This is my paper

Pith reviewed 2026-05-10 16:04 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Boolean networksasynchronous attractorsstrong modulesinteraction graphsattractor decompositioncanalizing functionspolynomial-time computation
0
0 comments X

The pith

Asynchronous attractors of Boolean networks decompose into products of attractors from controlled strong modules.

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

The paper proves that when the interaction graph of a Boolean network splits into strongly connected components called strong modules, the network's asynchronous attractors equal a dependent sum of the products of the attractors of those modules viewed as controlled subsystems. This turns the search for global attractors into a composition of smaller, independent local problems whose solutions multiply together according to the module controls. A sympathetic reader would care because the construction yields a polynomial-time algorithm for listing all attractors whenever the modules are small and the network is either sparse or defined by simple functions such as nested canalizing ones. The result is shown to work on an existing published model.

Core claim

The asynchronous attractors of a network can be described as a dependent sum construction: as products of attractors of its controlled strong modules.

What carries the argument

Dependent sum construction that multiplies the asynchronous attractors of controlled strong modules according to their external inputs.

Load-bearing premise

The interaction graph admits a partition into strongly connected components that can be treated as controlled subsystems whose attractors combine independently under asynchronous updates.

What would settle it

Identify the strong modules of a concrete Boolean network, compute the product of their individual asynchronous attractors, and compare it to the set of attractors obtained by exhaustive simulation of the full network; any mismatch disproves the claim.

Figures

Figures reproduced from arXiv: 2604.10193 by Paul Ruet.

Figure 1
Figure 1. Figure 1: Example of Section 3.3: (a) interaction graph (positive interactions, except [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Networks induced by a generalized decomposition. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An associativity relation from Proposition 5. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Attractors of N as products of attractors of constrained networks N1, N a1 2 , N a1,a2 3 , . . . in Theorem 8. 4.3 Example Let us consider again the example of [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Example of Section 4.3: (a) interaction graph; (b)–(c) variant of interac ′′ [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Condensation and subnetworks N0 A, N1 A. the other genes are represented by a number from 1 to 19, as in Appendix A. The 2 strong modules with 4 vertices are represented by A = {7, 8, 10, 11} = {IGF1R,ERα, AKT1, MEK1} B = {12, 13, 17, 18} = {CDK2, CDK4, p21, p27}. The small strong modules enable to compute all asynchronous attractors. Propa￾gating attractors top-down in the consensation, we find that if th… view at source ↗
read the original abstract

We consider Boolean networks with interaction graphs partitioned into strongly connected components, which we call strong modules. This type of network decomposition has been considered in the literature, primarily from the perspective of attractor detection algorithms. In this paper, we aim to provide an algebraic basis for this line of research in the case of asynchronous Boolean networks. We prove that the asynchronous attractors of a network can be described as a dependent sum construction: as products of attractors of its controlled strong modules. We then show that a representation of all attractors can be computed in polynomial time under two conditions: the strong modules are small, and either the network is sparse or its defining functions have small size circuits (in particular when they are nested canalizing). We illustrate these results on a published Boolean model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that asynchronous attractors of a Boolean network whose interaction graph is partitioned into strongly connected components (strong modules) can be expressed as a dependent sum of attractors of controlled versions of those modules. The construction proceeds by topological order on the condensation DAG, using the fact that intra-module updates depend only on internal states plus upstream control signals. It further establishes that all attractors can be enumerated in polynomial time when modules are small and the network is sparse or the Boolean functions have small circuit size (in particular when nested canalizing), and illustrates the results on a published biological model.

Significance. If the central theorem is correct, the work supplies a clean algebraic decomposition of asynchronous attractor structure that directly leverages the SCC partition of the interaction graph. This strengthens the theoretical basis for existing algorithmic approaches to attractor detection and yields a practical polynomial-time procedure under natural restrictions on module size and function complexity. The dependent-sum formulation and the explicit use of controlled attractors along the condensation DAG are particularly useful for modular analysis of large Boolean models in systems biology.

minor comments (3)
  1. Abstract: the term 'dependent sum construction' is used without a short gloss or pointer to its precise meaning in the context of varying control inputs; a one-sentence clarification would help readers outside category theory or dependent-type literature.
  2. The polynomial-time claim (small modules plus sparsity or small-circuit functions) would be strengthened by an explicit statement of the resulting time bound in terms of the number and sizes of modules and the circuit size parameter.
  3. The illustration section would benefit from a brief table or diagram showing the condensation DAG, the controlled attractors of each module, and how they combine into the global attractors for the example network.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their accurate summary of the paper and for recognizing the value of the dependent-sum decomposition of asynchronous attractors along the condensation DAG of strong modules. We are pleased that the work is viewed as strengthening the theoretical foundation for modular attractor analysis and providing a practical polynomial-time procedure under the stated restrictions on module size and function complexity. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes a direct mathematical proof that asynchronous attractors factor as a dependent sum over controlled attractors of strong modules obtained from the SCC partition of the interaction graph. The argument proceeds by topological order on the condensation DAG, using only the independence of intra-module updates given external controls and the absence of inter-module cycles; no parameter fitting, self-referential definitions, or load-bearing self-citations appear in the derivation chain. The result is self-contained against standard graph and Boolean dynamics primitives.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard definitions from graph theory and Boolean network theory with no free parameters, no invented entities, and only background mathematical axioms.

axioms (2)
  • domain assumption Interaction graphs of Boolean networks can be partitioned into strongly connected components
    Invoked to define strong modules as the basis for the decomposition.
  • domain assumption Asynchronous updates allow independent evolution of controlled modules
    Required for the product construction of attractors.

pith-pipeline@v0.9.0 · 5415 in / 1300 out tokens · 48238 ms · 2026-05-10T16:04:14.135889+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    U. Alon. Network motifs: theory and experimental approaches.Nature Reviews Genetics8: 450–461, 2007

    work page 2007

  2. [2]

    Barabási and R

    A.-L. Barabási and R. Albert. Emergence of scaling in random networks.Science 286: 509–512, 1999

    work page 1999

  3. [3]

    Deritei, W

    D. Deritei, W. Aird, M. Ercsey-Ravasz, E. Ravasz Regan. Principles of dynamical modularity in biological regulatory networks.Sci. Rep.6(21957), 2016. 16 Paul Ruet

    work page 2016

  4. [4]

    D. J. Irons and N. A. Monk. Identifying dynamical modules from genetic regula- tory systems: applications to the segment polarity network.BMC Bioinformatics, 8(413), 2007

    work page 2007

  5. [5]

    Jaeger and N

    J. Jaeger and N. Monk. Dynamical modularity of the genotype-phenotype map. In: Evolutionary Systems Biology, Springer, 245–280, 2021

    work page 2021

  6. [6]

    Kadelka, M

    C. Kadelka, M. Wheeler, A. Veliz-Cuba, D. Murrugarra, and R. Laubenbacher. Modularity of biological systems: a link between structure and functionJ. R. Soc. Interface, 20(207), 2023

    work page 2023

  7. [7]

    Kauffman.The origins of order: Self organization and selection in evolution

    S. Kauffman.The origins of order: Self organization and selection in evolution. Oxford University Press, 1993

    work page 1993

  8. [8]

    RandomBooleannetwork modelsandtheyeasttranscriptionalnetwork.Proc

    S.Kauffman,C.Peterson,B.Samuelsson,andC.Troein. RandomBooleannetwork modelsandtheyeasttranscriptionalnetwork.Proc. Natl. Acad. Sci.,100(25),2003

    work page 2003

  9. [9]

    W. S. McCulloch and W. Pitts. A logical calculus of ideas immanent in nervous activity.Bulletin of Mathematical Biophysics, 5(4):115–133, 1943

    work page 1943

  10. [10]

    Mizera , J

    A. Mizera , J. Pang , H. Qu, and Q. Yuan. Taming asynchrony for attractor detection in large Boolean networks.IEEE/ACM Transactions on Computational Biology and Bioinformatics, 16:31–42, 2019

    work page 2019

  11. [11]

    Murrugarra, A

    D. Murrugarra, A. Veliz-Cuba, E. Dimitrova, C. Kadelka, M. Wheeler, and R. Laubenbacher. Modular control of Boolean network models.Bull. Math. Biol., 87(91), 2025

    work page 2025

  12. [12]

    É. Remy, P. Ruet, and D. Thieffry. Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework.Adv. Appl. Math., 41(3):335– 350, 2008

    work page 2008

  13. [13]

    P. Ruet. Negative local feedbacks in Boolean networks.Discrete Appl. Math., 221:1–17, 2017

    work page 2017

  14. [14]

    Sahin, H

    O. Sahin, H. Fröhlich, C. Löbke, U. Korf, S. Burmester, M. Majety, J. Mattern, I. Schupp, C. Chaouiya, D. Thieffry, A. Poustka, S. Wiemann, T. Beissbarth, and D. Arlt. Modeling ERBB receptor-regulated G1/S transition to find novel targets for de novo trastuzumab resistance .BMC Syst. Biol., 1:3:1, 2009

    work page 2009

  15. [15]

    Subbaroyan, O

    A. Subbaroyan, O. C. Martin, and A. Samal. Minimum complexity drives regula- tory logic in Boolean models of living systems.PNAS Nexus, 1:1–12, 2022

    work page 2022

  16. [16]

    R. Thomas. On the relation between the logical structure of systems and their ability to generate multiple steady states and sustained oscillations.Springer Ser. Synergetics, 9:180–193, 1981

    work page 1981

  17. [17]

    Tournier and M

    L. Tournier and M. Chaves. Interconnection of asynchronous Boolean networks, asymptotic and transient dynamics.Automatica, 49(4):884–893, 2013

    work page 2013

  18. [18]

    von Neumann

    J. von Neumann. Theory of self-reproducing automata. University of Illinois Press, 1966

    work page 1966

  19. [19]

    Waddington

    C.H. Waddington. Canalization of development and the inheritance of acquired characters.Nature, 150:563–565, 1942

    work page 1942

  20. [20]

    Watts and S

    D. Watts and S. Strogatz. Collective dynamics of ‘small-world’ networks.Nature 393: 440–442, 1998

    work page 1998

  21. [21]

    Y. Zhao, J. Kim, and M. Filippone. Aggregation algorithm towards large-scale Boolean network analysis.IEEE Trans. on Automatic Control, 58(8):1976–1985, 2013. Strong modules and asynchronous attractors of Boolean networks 17 A Regulatory functions of the G1/S transition model We recall here the regulatory functions of the G1/S transition model presented i...

    work page 1976