A message-passing approach for threshold models of behavior in networks
arXiv:1312.2070 · doi:10.1103/PhysRevE.89.022805
Abstract
We study a simple model of how social behaviors, like trends and opinions, propagate in networks where individuals adopt the trend when they are informed by threshold neighbors who are adopters. Using a dynamic message-passing algorithm, we develop a tractable and computationally efficient method that provides complete time evolution of each individual's probability of adopting the trend or of the frequency of adopters and non-adopters in any arbitrary networks. We validate the method by comparing it with Monte Carlo based agent simulation in real and synthetic networks and provide an exact analytic scheme for large random networks, where simulation results match well. Our approach is general enough to incorporate non-Markovian processes and to include heterogeneous thresholds and thus can be applied to explore rich sets of complex heterogeneous agent-based models.
arXiv comment10 pages, 6 figures
References in corpus (15)
- Emergence of scaling in random networks
- Epidemic spreading in scale-free networks
- Cooperative Game Theory Approaches for Network Partitioning
- Catastrophic cascade of failures in interdependent networks
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- The Web of Human Sexual Contacts
- Epidemics and percolation in small-world networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Small world effect in an epidemiological model
- A message passing approach for general epidemic models
- Bootstrap Percolation on Complex Networks
- Bootstrap percolation on the random graph
- Nucleation and growth for the Ising model in dimensions at very low temperatures
- The onset of jamming as the sudden emergence of an infinite -core cluster
Cited by in corpus (24)
- Suppressing epidemic spreading in multiplex networks with social-support
- A message-passing approach for recurrent-state epidemic models on networks
- Predicting the speed of epidemics spreading on networks
- Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
- Dynamic message-passing equations for models with unidirectional dynamics
- Minimal contagious sets in random regular graphs
- Network cloning unfolds the effect of clustering on dynamical processes
- Reversible bootstrap percolation: Fake news and fact checking
- Message-Passing Methods for Complex Contagions
- Complex Contagions with Timers
- Aging in binary-state models: The Threshold model for Complex Contagion
- Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
- Exotic phase transitions of k-cores in clustered networks
- A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
- Scalable Influence Estimation Without Sampling
- Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
- Dynamical Phase Transitions in Graph Cellular Automata
- The matrix product approximation for the dynamic cavity method
- Vulnerability and Resilience of Social Engagement: Equilibrium Theory
- Exact analytical solution of irreversible binary dynamics on networks
- Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
- On the accuracy of message-passing approaches to percolation in complex networks
- A large deviation approach to super-critical bootstrap percolation on the random graph
- Bootstrap percolation on the stochastic block model with k communities