A message-passing approach for threshold models of behavior in networks

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

10 pages, 6 figures

References in corpus (3)

• Cooperative Game Theory Approaches for Network Partitioning
• A message passing approach for general epidemic models
• The onset of jamming as the sudden emergence of an infinite $k$-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 $G_{n,p}$
• Bootstrap percolation on the stochastic block model with k communities