pith. sign in

arxiv: 1906.10377 · v1 · pith:MZBN73U6new · submitted 2019-06-25 · ⚛️ physics.soc-ph · cond-mat.stat-mech

On the accuracy of message-passing approaches to percolation in complex networks

Antoine Allard , Laurent H\'ebert-Dufresne This is my paper

Pith reviewed 2026-05-25 16:17 UTC · model grok-4.3

classification ⚛️ physics.soc-ph cond-mat.stat-mech
keywords percolationmessage passingcomplex networkstree-like networksrandom ensemblesaccuracyshuffling
0
0 comments X

The pith

The message-passing approach for percolation computes results on infinitely shuffled random ensembles of a network rather than on any tree-like version of the specific network.

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

The paper establishes that the message-passing approach yields exact results on trees but does not achieve near-exact results on networks that are close to trees. Its equations instead solve the percolation problem exactly on an ensemble formed by taking the original network and shuffling it infinitely many times while keeping the same degrees. This matters because most real networks contain cycles yet are often treated as nearly tree-like, so the method's predictions reflect ensemble averages rather than the actual structure. A reader would care because this changes how one interprets and applies the widely used technique to spreading processes on empirical networks.

Core claim

The message-passing approach does not perform its calculations on some ill-defined tree-like approximation of the network, as its formulation leads to believe, but rather considers a random network ensemble in which the original network is cloned and shuffled an infinite number of times. We conclude that the fact that the MPA is exact on trees does not imply that it is nearly exact on tree-like networks. In fact we find that the closer a non-tree network is to a tree, the worse the MPA accuracy becomes.

What carries the argument

The message-passing approach (MPA) to percolation, whose equations are derived under an edge-independence assumption and solved by iteration along edges.

If this is right

  • MPA results match exact percolation only for trees and for the infinite-shuffle ensemble of any network.
  • For a network with cycles, MPA accuracy is governed by the structural difference between the given network and the average over its shuffles.
  • Percolation thresholds obtained via MPA on real networks represent ensemble expectations rather than properties of the observed connectivity.
  • Claims of near-exactness for tree-like networks must be replaced by statements about distance to the shuffled ensemble.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • For nearly tree-like empirical networks, direct Monte Carlo simulation on the fixed graph may outperform MPA.
  • One could derive correction terms that subtract the difference between the specific network and its shuffle average.
  • The same ensemble interpretation may apply to other message-passing calculations on networks, such as those for epidemic thresholds.
  • Controlled tests on networks with tunable cycle density near the tree limit would map the accuracy drop quantitatively.

Load-bearing premise

That the MPA equations are meant to approximate the specific given network rather than to solve exactly for the ensemble obtained by infinite degree-preserving shuffles of that network.

What would settle it

Generate a fixed network with a small number of cycles, compute exact percolation on it, compute exact percolation on many degree-preserving random shuffles of it, and compare both to the MPA output; agreement with the shuffled ensemble but not the fixed network would confirm the claim.

Figures

Figures reproduced from arXiv: 1906.10377 by Antoine Allard, Laurent H\'ebert-Dufresne.

Figure 1
Figure 1. Figure 1: FIG. 1. Comparison between the predictions of the MPA (lines) and the results obtained by numerical simuations (symbols) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. (a)–(c) The simple networks considered in the main [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Comparison between the predictions of the MPA [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Scatter plot of the error made by the MPA on 111 net [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 1
Figure 1. Figure 1: Because a tree contains the minimum number of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
read the original abstract

The Message-Passing Approach (MPA) is the state-of-the-art technique to obtain quasi-analytical predictions for percolation on real complex networks. Besides being intuitive and straightforward, it has the advantage of being mathematically principled: it is exact on trees, while yielding generally good predictions on networks containing cycles as do most real complex networks. Here we show that the MPA does not perform its calculations on some ill-defined tree-like approximation of the network, as its formulation leads to believe, but rather considers a random network ensemble in which the original network is cloned and shuffled an infinite number of times. We conclude that the fact that the MPA is exact on trees does not imply that it is nearly exact on tree-like networks. In fact we find that the closer a non-tree network is to a tree, the worse the MPA accuracy becomes.

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

2 major / 1 minor

Summary. The manuscript argues that the message-passing approach (MPA) to percolation on complex networks solves the problem on the configuration-model ensemble generated by infinite random shuffles of the input network's degree sequence, rather than on any tree-like approximation of the specific supplied graph. It concludes that MPA accuracy therefore degrades as a non-tree network approaches a tree, contrary to the usual interpretation that exactness on trees implies near-exactness on locally tree-like networks.

Significance. If substantiated, the reinterpretation would alter how MPA predictions are understood and applied in network science, particularly for real networks that are locally tree-like but contain cycles. The result would also clarify the relationship between MPA and ensemble-based generating-function methods.

major comments (2)
  1. [Abstract / central claim] The central claim requires an explicit derivation showing that the fixed-point messages obtained by iterating the MPA equations on the fixed adjacency list of a given finite network are mathematically identical to the ensemble averages over the configuration-model ensemble with the same degree sequence. No such derivation is visible in the abstract, and the conclusion does not follow from the mere fact that MPA is exact on trees.
  2. [Results / discussion of accuracy] The argument that accuracy worsens as the network approaches a tree rests on the ensemble reinterpretation. Without the equivalence proof, the numerical evidence (if any) comparing MPA to exact percolation on specific networks cannot be interpreted as testing the ensemble claim versus the tree-like approximation claim.
minor comments (1)
  1. [Introduction] Clarify in the introduction whether the MPA equations are written with the specific edge set or with the degree sequence only.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments on our manuscript. We address each major comment below, providing clarifications on the central claim and the supporting evidence.

read point-by-point responses

  1. Referee: [Abstract / central claim] The central claim requires an explicit derivation showing that the fixed-point messages obtained by iterating the MPA equations on the fixed adjacency list of a given finite network are mathematically identical to the ensemble averages over the configuration-model ensemble with the same degree sequence. No such derivation is visible in the abstract, and the conclusion does not follow from the mere fact that MPA is exact on trees.

    Authors: The abstract is necessarily concise and does not contain the full derivation. The main text develops the argument that MPA iterations on a fixed adjacency list are equivalent to ensemble averages because the update rules depend only on node degrees and the probabilistic connections implied by repeated random shuffles of the degree sequence (i.e., the configuration-model ensemble), not on the specific wiring of the input graph. This equivalence is what allows the reinterpretation. While the conclusion does not rest solely on exactness on trees, we agree that an explicit step-by-step derivation of the fixed-point equivalence would strengthen the presentation and will add a dedicated paragraph or appendix in the revision. revision: yes

  2. Referee: [Results / discussion of accuracy] The argument that accuracy worsens as the network approaches a tree rests on the ensemble reinterpretation. Without the equivalence proof, the numerical evidence (if any) comparing MPA to exact percolation on specific networks cannot be interpreted as testing the ensemble claim versus the tree-like approximation claim.

    Authors: The numerical comparisons in the manuscript show MPA predictions diverging from exact results precisely when the input network is made progressively closer to a tree (while retaining a small number of cycles), which is the opposite of what a pure tree-like approximation would predict. This pattern is difficult to reconcile with the standard interpretation but follows directly once MPA is understood as ensemble averaging. We will expand the discussion section to make this interpretive link more explicit and to address the referee's concern about distinguishing the two claims. revision: partial

Circularity Check

0 steps flagged

MPA reinterpretation as infinite-shuffle ensemble follows from direct equation analysis with no reduction to inputs or self-citations

full rationale

The paper's central argument reinterprets the standard MPA equations as computing ensemble averages over configuration-model shuffles rather than a local tree approximation on the given graph. This follows from algebraic inspection of the message-passing fixed-point equations themselves (exact on trees by construction, but ensemble-averaged for finite networks with cycles). No parameters are fitted and then relabeled as predictions, no load-bearing uniqueness theorems are imported via self-citation, and the derivation does not rename a known empirical pattern. The claim that accuracy degrades closer to trees is a direct consequence of this ensemble view and remains independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, no specific free parameters, axioms, or invented entities are identifiable or required for the stated claim.

pith-pipeline@v0.9.0 · 5675 in / 1037 out tokens · 48992 ms · 2026-05-25T16:17:42.925353+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Message passing and cyclicity transition

    physics.soc-ph 2026-04 unverdicted novelty 7.0

    Message passing solutions in percolation identify reachability from cycles, not giant component membership, on any directed or undirected networks.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Unsupervised feature learning from finite data by message passing: Discon- tinuous versus continuous phase transition,

    H. Huang and T. Toyoizumi, “Unsupervised feature learning from finite data by message passing: Discon- tinuous versus continuous phase transition,” Phys. Rev. E 94, 062310 (2016)

    work page 2016

  2. [2]

    M´ ezard and A

    M. M´ ezard and A. Montanari,Information, Physics, and Computation (Oxford University Press, 2009) p. 569

    work page 2009

  3. [3]

    Statistical physics of inference: Thresholds and algorithms,

    L. Zdeborov´ a and F. Krzakala, “Statistical physics of inference: Thresholds and algorithms,” Adv. Phys. 65, 453–552 (2016)

    work page 2016

  4. [4]

    Correctness of Local Probability Propagation in Graphical Models with Loops,

    Y. Weiss, “Correctness of Local Probability Propagation in Graphical Models with Loops,” Neural Comput. 12, 1–41 (2000)

    work page 2000

  5. [5]

    Containing Epidemic Outbreaks by Message-Passing Techniques,

    F. Altarelli, A. Braunstein, L. Dall’Asta, J. R. Wakeling, and R. Zecchina, “Containing Epidemic Outbreaks by Message-Passing Techniques,” Phys. Rev. X 4, 021024 (2014)

    work page 2014

  6. [6]

    Message passing ap- proach for general epidemic models,

    B. Karrer and M. E. J. Newman, “Message passing ap- proach for general epidemic models,” Phys. Rev. E 82, 016101 (2010)

    work page 2010

  7. [7]

    Inferring the origin of an epidemic with a dynamic message-passing algorithm,

    A. Y. Lokhov, M. M´ ezard, H. Ohta, and L. Zdeborov´ a, “Inferring the origin of an epidemic with a dynamic message-passing algorithm,” Phys. Rev. E 90, 012801 (2014)

    work page 2014

  8. [8]

    Dynamic message-passing equations for models with unidirectional dynamics,

    A. Y. Lokhov, M. M´ ezard, and L. Zdeborov´ a, “Dynamic message-passing equations for models with unidirectional dynamics,” Phys. Rev. E 91, 012811 (2015)

    work page 2015

  9. [9]

    Message- passing approach for recurrent-state epidemic models on networks,

    M. Shrestha, S. V. Scarpino, and C. Moore, “Message- passing approach for recurrent-state epidemic models on networks,” Phys. Rev. E 92, 022821 (2015)

    work page 2015

  10. [10]

    Message passing and moment closure for susceptible-infected-recovered epidemics on finite networks,

    R. R. Wilkinson and K. J. Sharkey, “Message passing and moment closure for susceptible-infected-recovered epidemics on finite networks,” Phys. Rev. E 89, 022808 (2014)

    work page 2014

  11. [11]

    Modeling functional resting-state brain networks through neural message passing on the human connectome

    J. A. Peraza-Goicolea, E. Martnez-Montes, E. Aubert, P. A. Valds-Hernndez, and R. Mulet, “Modeling functional resting-state brain networks through neu- ral message passing on the human connectome,” arXiv:1906.05369 (2019)

    work page internal anchor Pith review Pith/arXiv arXiv 1906

  12. [12]

    Message-passing approach for threshold models of behavior in networks,

    M. Shrestha and C. Moore, “Message-passing approach for threshold models of behavior in networks,” Phys. Rev. E 89, 022805 (2014)

    work page 2014

  13. [13]

    Anomalous structure and dynamics in news diffusion among heterogeneous in- dividuals,

    X. Wang, Y. Lan, and J. Xiao, “Anomalous structure and dynamics in news diffusion among heterogeneous in- dividuals,” Nat. Hum. Behav. (2019), 10.1038/s41562- 019-0605-7

    work page doi:10.1038/s41562- 2019

  14. [14]

    Scalable detection of statisti- cally significant communities and hierarchies, using mes- sage passing for modularity,

    P. Zhang and C. Moore, “Scalable detection of statisti- cally significant communities and hierarchies, using mes- sage passing for modularity,” Proc. Natl. Acad. Sci. USA 111, 18144–18149 (2014)

    work page 2014

  15. [15]

    Message-Passing Meth- ods for Complex Contagions,

    J. P. Gleeson and M. A. Porter, “Message-Passing Meth- ods for Complex Contagions,” inComplex Spreading Phe- nom. Soc. Syst. , edited by S. Lehmann and Y.-Y. Ahn (Springer International Publishing, 2018) pp. 81–95

    work page 2018

  16. [16]

    Spectra of random networks with arbitrary degrees,

    M. E. J. Newman, X. Zhang, and R. R. Nadakuditi, “Spectra of random networks with arbitrary degrees,” Phys. Rev. E 99, 042309 (2019)

    work page 2019

  17. [17]

    Spectra of networks containing short loops,

    M. E. J. Newman, “Spectra of networks containing short loops,” arXiv:1902.04595 (2019)

    work page arXiv 1902

  18. [18]

    Dynamic message-passing approach for kinetic spin models with reversible dynam- ics,

    G. Del Ferraro and E. Aurell, “Dynamic message-passing approach for kinetic spin models with reversible dynam- ics,” Phys. Rev. E 92, 010102 (2015)

    work page 2015

  19. [19]

    Percolation in real multi- plex networks,

    G. Bianconi and F. Radicchi, “Percolation in real multi- plex networks,” Phys. Rev. E 94, 060301 (2016)

    work page 2016

  20. [20]

    Fluctuations in percolation of sparse com- plex networks,

    G. Bianconi, “Fluctuations in percolation of sparse com- plex networks,” Phys. Rev. E 96, 012302 (2017)

    work page 2017

  21. [21]

    Rare events and discontinuous percolation transitions,

    G. Bianconi, “Rare events and discontinuous percolation transitions,” Phys. Rev. E 97, 022314 (2018)

    work page 2018

  22. [22]

    Mes- sage passing theory for percolation models on multiplex networks with link overlap,

    D. Cellai, S. N. Dorogovtsev, and G. Bianconi, “Mes- sage passing theory for percolation models on multiplex networks with link overlap,” Phys. Rev. E 94, 032301 (2016)

    work page 2016

  23. [23]

    Perco- lation on Sparse Networks,

    B. Karrer, M. E. J. Newman, and L. Zdeborov´ a, “Perco- lation on Sparse Networks,” Phys. Rev. Lett.113, 208702 (2014)

    work page 2014

  24. [24]

    Heterogeneous micro-structure of percolation in sparse networks,

    R. K¨ uhn and T. Rogers, “Heterogeneous micro-structure of percolation in sparse networks,” EPL (Europhysics Lett. 118, 68003 (2017)

    work page 2017

  25. [25]

    Influence maximization in complex networks through optimal percolation,

    F. Morone and H. A. Makse, “Influence maximization in complex networks through optimal percolation,” Nature 524, 65–68 (2015)

    work page 2015

  26. [26]

    Beyond the locally tree- like approximation for percolation on real networks,

    F. Radicchi and C. Castellano, “Beyond the locally tree- like approximation for percolation on real networks,” Phys. Rev. E 93, 030302 (2016)

    work page 2016

  27. [27]

    Percolation in real interdependent net- works,

    F. Radicchi, “Percolation in real interdependent net- works,” Nature Phys. 11, 597–602 (2015)

    work page 2015

  28. [28]

    Mapping the Structure of Directed Networks: Beyond the Bow-Tie Diagram,

    G. Tim´ ar, A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, “Mapping the Structure of Directed Networks: Beyond the Bow-Tie Diagram,” Phys. Rev. Lett. 118, 078301 (2017)

    work page 2017

  29. [29]

    Graphs over time: densification laws, shrinking diameters and possible explanations,

    J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graphs over time: densification laws, shrinking diameters and possible explanations,” in Proc. Elev. ACM SIGKDD Int. Conf. Knowl. Discov. data Min. (KDD ’05) (ACM Press, New York, New York, USA, 2005) p. 177

    work page 2005

  30. [30]

    Random graphs with arbitrary degree distributions and their applications,

    M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Random graphs with arbitrary degree distributions and their applications,” Phys. Rev. E 64, 026118 (2001)

    work page 2001

  31. [31]

    Resilience to damage of graphs with degree correlations,

    A. V´ azquez and Y. Moreno, “Resilience to damage of graphs with degree correlations,” Phys. Rev. E 67, 015101 (2003)

    work page 2003

  32. [32]

    Percolation and the Effective Structure of Complex Networks,

    A. Allard and L. H´ ebert-Dufresne, “Percolation and the Effective Structure of Complex Networks,” Phys. Rev. X 9, 011023 (2019)

    work page 2019

  33. [33]

    Network cloning unfolds the effect of clustering on dynamical pro- cesses,

    A. Faqeeh, S. Melnik, and J. P. Gleeson, “Network cloning unfolds the effect of clustering on dynamical pro- cesses,” Phys. Rev. E 91, 052807 (2015)

    work page 2015

  34. [34]

    Christensen and N

    K. Christensen and N. R. Moloney, Complexity and Crit- icality (World Scientific Publishing, 2005) p. 408

    work page 2005

  35. [35]

    Smeared phase transitions in percolation on real complex networks,

    L. H´ ebert-Dufresne and A. Allard, “Smeared phase transitions in percolation on real complex networks,” 7 arXiv:1810.00735 (2018)

    work page arXiv 2018