Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
arXiv:2105.04197 · doi:10.1103/PhysRevE.104.045313
Abstract
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 couplings, and we use the power of the algorithm to unlock the noise dependent heterogeneity of stationary node activation patterns in such a system.
arXiv comment7 pages, 3 figures
References in corpus (25)
- Statistical mechanics of complex networks
- Error and attack tolerance of complex networks
- Emergence of Cooperation and Organization in an Evolutionary Game
- The Bethe lattice spin glass revisited
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Expectation bubbles in a spin model of markets: Intermittency from frustration across scales
- Multitasking associative networks
- Exact solutions for diluted spin glasses and optimization problems
- Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
- Optimizing spread dynamics on graphs by message passing
- Dynamic message-passing equations for models with unidirectional dynamics
- Extensive load in multitasking associative networks
- Immune networks: multi-tasking capabilities near saturation
- Dynamical TAP equations for non-equilibrium Ising spin glasses
- The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
- Dynamic mean-field and cavity methods for diluted Ising systems
- Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
- Inference of kinetic Ising model on sparse graphs
- Heterogeneous micro-structure of percolation in sparse networks
- Phase Transitions in Operational Risk
- Effects of Economic Interactions on Credit Risk
- Network resilience against intelligent attacks constrained by degree dependent node removal cost
- Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function
- Contagion in an interacting economy