TY - JOUR
T1 - Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
AU - Torrisi, Giuseppe
AU - Annibale, Alessia
AU - Kuehn, Reimer
N1 - Funding Information:
G.T. is supported by the EPSRC Centre for Doctoral Training in Cross-Disciplinary Approaches to Non-Equilibrium Systems (CANES EP/L015854/1). We thank Professor Franca Fraternali's group for providing access to their computational facilities.
Publisher Copyright:
© 2021 American Physical Society.
PY - 2021/10/29
Y1 - 2021/10/29
N2 - 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 defacto barrier for the successful analysis of systems with fat-tailed in-degree distributions. In this paper, 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 analyze 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.
AB - 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 defacto barrier for the successful analysis of systems with fat-tailed in-degree distributions. In this paper, 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 analyze 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.
KW - Classical statistical mechanics
KW - Non equilibrium statistical mechanics
KW - Spin dynamics
KW - message passing
UR - http://www.scopus.com/inward/record.url?scp=85119493727&partnerID=8YFLogxK
U2 - https://doi.org/10.1103/PhysRevE.104.045313
DO - https://doi.org/10.1103/PhysRevE.104.045313
M3 - Article
SN - 2470-0045
VL - 104
JO - Physical Review E
JF - Physical Review E
IS - 4
M1 - A26
ER -