Binary-state dynamics on complex networks: pair approximation and beyond

Abstract

A wide class of binary-state dynamics on networks---including, for example, the voter model, the Bass diffusion model, and threshold models---can be described in terms of transition rates (spin-flip probabilities) that depend on the number of nearest neighbors in each of the two possible states. High-accuracy approximations for the emergent dynamics of such models on uncorrelated, infinite networks are given by recently-developed compartmental models or approximate master equations (AME). Pair approximations (PA) and mean-field theories can be systematically derived from the AME. We show that PA and AME solutions can coincide under certain circumstances, and numerical simulations confirm that PA is highly accurate in these cases. For monotone dynamics (where transitions out of one nodal state are impossible, e.g., SI disease-spread or Bass diffusion), PA and AME give identical results for the fraction of nodes in the infected (active) state for all time, provided the rate of infection depends linearly on the number of infected neighbors. In the more general non-monotone case, we derive a condition---that proves equivalent to a detailed balance condition on the dynamics---for PA and AME solutions to coincide in the limit $t\to \infty$. This permits bifurcation analysis, yielding explicit expressions for the critical (ferromagnetic/paramagnetic transition) point of such dynamics, closely analogous to the critical temperature of the Ising spin model. Finally, the AME for threshold models of propagation is shown to reduce to just two differential equations, and to give excellent agreement with numerical simulations. As part of this work, Octave/Matlab code for implementing and solving the differential equation systems is made available for download.

This version accepted for publication in Physical Review X. Octave/Matlab code for implementing and solving the differential equation systems is available from http://www.ul.ie/gleesonj

References in corpus (15)

• Statistical physics of social dynamics
• Critical phenomena in complex networks
• The Dynamics of Protest Recruitment through an Online Network
• Random graphs with clustering
• Adaptive networks: coevolution of disease and topology
• Analytical Solution of the Voter Model on Disordered Networks
• Bond percolation on a class of clustered random networks
• Cascading Dynamics in Modular Networks
• Epidemic threshold and control in a dynamic network
• Systems with two symmetric absorbing states: relating the microscopic dynamics with the macroscopic behavior
• Propagation dynamics on networks featuring complex topologies
• Cluster approximations for probabilistic systems: a new perspective of epidemiological modelling
• Zero temperature Glauber dynamics on complex networks
• The class of nonlinear stochastic models as a background for the bursty behavior in financial markets
• Universal and non-universal features of the generalized voter class for ordering dynamics

Cited by in corpus (95)

• Epidemic processes in complex networks
• Unification of theoretical approaches for epidemic spreading on complex networks
• Network models of financial systemic risk: A review
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Kinetics of Social Contagion
• Opinion Polarization by Learning from Social Feedback
• The limitations of discrete-time approaches to continuous-time contagion dynamics
• Critical behaviors in contagion dynamics
• An adaptive voter model on simplicial complexes
• Statistical Physics Of Opinion Formation: is it a SPOOF?
• Solving the Dynamic Correlation Problem of the Susceptible-Infected-Susceptible Model on Networks
• Pair approximation for the q-voter model with independence on complex networks
• Analytical and numerical study of the non-linear noisy voter model on complex networks
• Heterogeneous pair-approximation for the contact process on complex networks
• Phase transitions in the q-voter model with noise on a duplex clique
• A network-based microfoundation of Granovetter's threshold model for social tipping
• Sampling methods for the quasistationary regime of epidemic processes on regular and complex networks
• Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
• The effect of algorithmic bias and network structure on coexistence, consensus, and polarization of opinions
• Explosive spreading on complex networks: the role of synergy
• Stochastic pair approximation treatment of the noisy voter model
• Dynamics on Modular Networks with Heterogeneous Correlations
• Competition of simple and complex adoption on interdependent networks
• Network cloning unfolds the effect of clustering on dynamical processes
• Hipsters on Networks: How a Small Group of Individuals Can Lead to an Anti-Establishment Majority
• Neural Ordinary Differential Equation Control of Dynamics on Graphs
• Robustness and fragility of the susceptible-infected-susceptible epidemic models on complex networks
• A universal data based method for reconstructing complex networks with binary-state dynamics
• Extracting information from S-curves of language change
• Spectral properties and the accuracy of mean-field approaches for epidemics on correlated networks
• Pair approximation for the noisy threshold $q$-voter model
• Homogeneous symmetrical threshold model with nonconformity: independence vs. anticonformity
• Social Clustering in Epidemic Spread on Coevolving Networks
• Noise in Coevolving Networks
• Finding nonlinear system equations and complex network structures from data: a sparse optimization approach
• Contagion dynamics on hypergraphs with nested hyperedges
• Pair approximation for the $q$-voter model with independence on multiplex networks
• Outbreaks in susceptible-infected-removed epidemics with multiple seeds
• Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks
• Majority-vote dynamics on multiplex networks
• Correlated fluctuations in strongly-coupled binary networks beyond equilibrium
• Network topology near criticality in adaptive epidemics
• High prevalence regimes in the pair quenched mean-field theory for the susceptible-infected-susceptible model on networks
• Reentrant phase transitions in threshold driven contagion on multiplex networks
• Effects of local and global network connectivity on synergistic epidemics
• A generalized linear threshold model for an improved description of the spreading dynamics
• Message-Passing Methods for Complex Contagions
• Binary-state dynamics on complex networks: Stochastic pair approximation and beyond
• Aging in binary-state models: The Threshold model for Complex Contagion
• Complex Contagions with Timers
• Uncertainty Reduction for Stochastic Processes on Complex Networks
• Link-based formalism for time evolution of adaptive networks
• Reference to Global State and Social Contagion Dynamics
• Pair approximation for the q-voter models with quenched disorder on networks
• Opinion formation on social networks with algorithmic bias: Dynamics and bias imbalance
• Dynamical universality of the contact process
• Adversarial attacks on voter model dynamics in complex networks
• Fitting In and Breaking Up: A Nonlinear Version of Coevolving Voter Models
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Logistic growth on networks: exact solutions for the SI model
• Lumping of Degree-Based Mean Field and Pair Approximation Equations for Multi-State Contact Processes
• In search for the social hysteresis -- the symmetrical threshold model with independence on Watts-Strogatz graphs
• Nonlinear $q$-voter model from the quenched perspective
• Understanding the temporal pattern of spreading in heterogeneous networks: Theory of the mean infection time
• The threshold model with anticonformity under random sequential updating
• Evolutionary hypergame dynamics
• Echo chamber effects in signed networks
• Bifurcations in synergistic epidemics on random regular graphs
• Mean-field models of dynamics on networks via moment closure: an automated procedure
• Concurrency and reachability in tree-like temporal networks
• Impact of random and targeted disruptions on information diffusion during outbreaks
• Continuous time limits of the Utterance Selection Model
• Spreading dynamics in networks under context-dependent behavior
• Correlations between thresholds and degrees: An analytic approach to model attacks and failure cascades
• Persistent individual bias in a voter model with quenched disorder
• Competing local and global interactions in social dynamics: how important is the friendship network?
• Synergistic epidemic spreading in correlated networks
• Altruism in populations at the extinction transition
• Dynamical correlations and pairwise theory for the symbiotic contact process on networks
• Learning Interpretable Collective Variables for Spreading Processes on Networks
• Diffusion dynamics of competing information on networks
• Coordination problems on networks revisited: statics and dynamics
• The $q$-neighbor Ising model on multiplex networks with partial overlap of nodes
• q-deformed evolutionary dynamics in simple matrix games
• Approximate master equations for the spatial public goods game
• On the dual nature of adoption processes in complex networks
• Modelling disease impact: lifespan reduction is greatest for young adults in an exogenous damage model of disease
• Exact analytical solution of irreversible binary dynamics on networks
• When heterogeneity drives hysteresis: Anticonformity in the multistate $q$-voter model on networks
• Analytical approach to the dynamics of facilitated spin models on random networks
• Social contagion induced by uncertain information
• Reducibility of higher-order to pairwise interactions: Social impact models on hypergraphs
• Restoring detailed balance in non-Hermitian Markov processes
• Critical Density of the Abelian Manna Model via a Multi-type Branching Process
• Mean-field approximation and phase transitions in an Ising-voter model on directed regular random graphs