Message-Passing Methods for Complex Contagions

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 $N$ 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.

14 pages, 3 figures

References in corpus (10)

• Percolation on sparse networks
• Analysis of complex contagions in random multiplex networks
• Complex contagion process in spreading of online innovation
• Predicting percolation thresholds in networks
• Dynamical Systems on Networks: A Tutorial
• Dynamic message-passing equations for models with unidirectional dynamics
• Breaking of the site-bond percolation universality in networks
• 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 $z$-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