Exact analytical solution of irreversible binary dynamics on networks
arXiv:1711.02721 · doi:10.1103/PhysRevE.97.032302
Abstract
In binary cascade dynamics, the nodes of a graph are in one of two possible states (inactive, active), and nodes in the inactive state make an irreversible transition to the active state, as soon as their precursors satisfy a predetermined condition. We introduce a set of recursive equations to compute the probability of reaching any final state, given an initial state, and a specification of the transition probability function of each node. Because the naive recursive approach for solving these equations takes factorial time in the number of nodes, we also introduce an accelerated algorithm, built around a breath-first search procedure. This algorithm solves the equations as efficiently as possible, in exponential time.
arXiv comment9 pages, 5 figures
References in corpus (20)
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- Network robustness and fragility: Percolation on random graphs
- Percolation on sparse networks
- Random graphs containing arbitrary distributions of subgraphs
- Binary-state dynamics on complex networks: pair approximation and beyond
- Optimal hierarchical modular topologies for producing limited sustained activation of neural networks
- The unreasonable effectiveness of tree-based theory for networks with clustering
- Cascades on a class of clustered random networks
- Criticality of spreading dynamics in hierarchical cluster networks without inhibition
- Dynamic message-passing equations for models with unidirectional dynamics
- Three faces of node importance in network epidemiology: Exact results for small graphs
- A message-passing approach for threshold models of behavior in networks
- Dynamics on Modular Networks with Heterogeneous Correlations
- Equivalence of several generalized percolation models on networks
- General and exact approach to percolation on random graphs
- Bond percolation on a class of correlated and clustered random graphs
- Cascades on clique-based graphs
- Message-Passing Methods for Complex Contagions
- Exact solution of bond percolation on small arbitrary graphs