Critical Network Cascades with Re-excitable nodes: Why tree-like approximations usually work, when they breakdown, and how to correct them

Abstract

Network science is a rapidly expanding field, with a large and growing body of work on network-based dynamical processes. Most theoretical results in this area rely on the so-called \emph{locally tree-like approximation}. This is, however, usually an `uncontrolled' approximation, in the sense that the magnitudes of the error are typically unknown, although numerical results show that this error is often surprisingly small. In this paper, we place this approximation on more rigorous footing by calculating the magnitude of deviations away from tree-based theories in the context of discrete-time critical network cascades with re-excitable nodes. We discuss the conditions under which tree-like approximations give good results for calculating network criticality, and also explain the reasons for deviation from this approximation, in terms of the density of certain kinds of network motifs. Using this understanding, we derive results for network criticality that apply to general networks that explicitly do not satisfy the locally tree-like approximation. In particular, we focus on the bi-parallel motif, the smallest motif relevant to the failure of a tree-based theory in this context, and we derive the corrections due to such motifs on the conditions for criticality. We verify our claims on computer-generated networks, and we confirm that our theory accurately predicts the observed deviations from criticality. Using our theory, we explain why numerical simulations often show that deviations from a tree-based theory are surprisingly small. More specifically, we show that these deviations are negligible for networks whose average degree is even modestly large compared to one, justifying why tree-based theories appear to work well for most real-world networks.

arXiv comment22 pages, 8 figures

References in corpus (20)

• Power-law distributions in empirical data
• Error and attack tolerance of complex networks
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• Cascade-based attacks on complex networks
• Epidemic dynamics and endemic states in complex networks
• Powerlaw: a Python package for analysis of heavy-tailed distributions
• Epidemics and percolation in small-world networks
• Optimal Dynamical Range of Excitable Networks at Criticality
• Discrete-time Markov chain approach to contact-based disease spreading in complex networks
• Epidemic spreading in correlated complex networks
• Epidemic threshold for the SIS model on networks
• Predicting criticality and dynamic range in complex networks: effects of topology
• Analytical computation of the epidemic threshold on temporal networks
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Branching Dynamics of Viral Information Spreading
• Statistical Properties of Avalanches in Networks
• Beyond the locally tree-like approximation for percolation on real networks
• Dynamic range of hypercubic stochastic excitable media
• Effects of network topology, transmission delays, and refractoriness on the response of coupled excitable systems to a stochastic stimulus