Binary-State Dynamics on Complex Networks: Pair Approximation and Beyond
Top Cited Papers
Open Access
- 29 April 2013
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review X
- Vol. 3 (2) , 021004
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 (AMEs). Pair approximations (PAs) 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., susceptible-infected disease spread or Bass diffusion), PA and the AME give identical results for the fraction of nodes in the infected (active) state for all time, provided that the rate of infection depends linearly on the number of infected neighbors. In the more general nonmonotone case, we derive a condition—that proves to be equivalent to a detailed balance condition on the dynamics—for PA and AME solutions to coincide in the limit . This equivalence permits bifurcation analysis, yielding explicit expressions for the critical (ferromagnetic or paramagnetic transition) point of such dynamics, that is 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, the Octave or Matlab code for implementing and solving the differential-equation systems is made available for download.
Keywords
All Related Versions
This publication has 71 references indexed in Scilit:
- Graph fission in an evolving voter modelProceedings of the National Academy of Sciences, 2012
- The Dynamics of Protest Recruitment through an Online NetworkScientific Reports, 2011
- The spread of innovations in social networksProceedings of the National Academy of Sciences, 2010
- Infectious Disease Modeling of Social Contagion in NetworksPLOS Computational Biology, 2010
- Discrete-time Markov chain approach to contact-based disease spreading in complex networksEurophysics Letters, 2010
- Influentials, Networks, and Public Opinion FormationJournal of Consumer Research, 2007
- Cluster approximations for epidemic processes: a systematic description of correlations beyond the pair levelJournal of Theoretical Biology, 2004
- Universal Behavior in a Generalized Model of ContagionPhysical Review Letters, 2004
- Isotropic majority-vote model on a square latticeJournal of Statistical Physics, 1992
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980