Message-Passing Methods for Complex Contagions
arXiv:1703.08046 · doi:10.1007/978-3-319-77332-2_5
Abstract
Message-passing methods provide a powerful approach for calculating the expected size of cascades either on random networks (e.g., drawn from a configuration-model ensemble or its generalizations) asymptotically as the number of nodes becomes infinite or on specific finite-size networks. We review the message-passing approach and show how to derive it for configuration-model networks using the methods of (Dhar et al., 1997) and (Gleeson, 2008). Using this approach, we explain for such networks how to determine an analytical expression for a "cascade condition", which determines whether a global cascade will occur. We extend this approach to the message-passing methods for specific finite-size networks (Shrestha and Moore, 2014; Lokhov et al., 2015), and we derive a generalized cascade condition. Throughout this chapter, we illustrate these ideas using the Watts threshold model.
arXiv comment14 pages, 3 figures
References in corpus (27)
- Assortative mixing in networks
- Epidemic processes in complex networks
- Multilayer Networks
- Spectral redemption: clustering sparse networks
- Statistical physics of inference: Thresholds and algorithms
- Comparing Community Structure to Characteristics in Online Collegiate Social Networks
- Localization and centrality in networks
- Percolation on sparse networks
- Binary-state dynamics on complex networks: pair approximation and beyond
- Analysis of complex contagions in random multiplex networks
- Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
- The unreasonable effectiveness of tree-based theory for networks with clustering
- Zero-temperature Hysteresis in Random-field Ising Model on a Bethe Lattice
- Complex contagion process in spreading of online innovation
- Predicting percolation thresholds in networks
- Dynamical Systems on Networks: A Tutorial
- Multi-Stage Complex Contagions
- The limitations of discrete-time approaches to continuous-time contagion dynamics
- Leveraging percolation theory to single out influential spreaders in networks
- Dynamic message-passing equations for models with unidirectional dynamics
- Breaking of the site-bond percolation universality in networks
- Analysis of a threshold model of social contagion on degree-correlated networks
- A message-passing approach for threshold models of behavior in networks
- Dynamics on Modular Networks with Heterogeneous Correlations
- Network cloning unfolds the effect of clustering on dynamical processes
- Assessing node risk and vulnerability in epidemics on networks
- The Unfolding and Control of Network Cascades
Cited by in corpus (8)
- Rare events and discontinuous percolation transitions
- Fluctuations in percolation of sparse complex networks
- Dynamics of diffusion on monoplex and multiplex networks: A message-passing approach
- Unstable diffusion in social networks
- Statistical mechanics of bipartite -matchings
- Exact analytical solution of irreversible binary dynamics on networks
- On the accuracy of message-passing approaches to percolation in complex networks
- Persistent Threshold Dynamics with Recovery in Complex Networks