Papers › Overcoming the complexity barrier of the dynamic message-passing method in networks...
Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
Giuseppe Torrisi, Alessia Annibale, Reimer Kühn
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The dynamic cavity method provides the most efficient way to evaluate probabilities of dynamic trajectories in systems of stochastic units with unidirectional sparse interactions. It is closely related to sum-product algorithms widely used to compute marginal functions from complicated global functions of many variables, with applications in disordered systems, combinatorial optimization and computer science. However, the complexity of the cavity approach grows exponentially with the in-degrees of the interacting units, which creates a de-facto barrier for the successful analysis of systems with fat-tailed in-degree distributions. In this manuscript, we present a dynamic programming algorithm that overcomes this barrier by reducing the computational complexity in the in-degrees from exponential to quadratic, whenever couplings are chosen randomly from (or can be approximated in terms of) discrete, possibly unit-dependent, sets of equidistant values. As a case study, we analyse the dynamics of a random Boolean network with a fat-tailed degree distribution and fully asymmetric binary ±J couplings, and we use the power of the algorithm to unlock the noise dependent heterogeneity of stationary node activation patterns in such a system.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections