Graph fission in an evolving voter model
- Richard Durretta,1,
- James P. Gleesonb,
- Alun L. Lloydc,d,
- Peter J. Muchae,
- Feng Shie,
- David Sivakoffa,
- Joshua E. S. Socolarf, and
- Chris Varghesef
-
Contributed by Richard T. Durrett, January 13, 2012 (sent for review October 26, 2011)
Abstract
We consider a simplified model of a social network in which individuals have one of two opinions (called 0 and 1) and their opinions and the network connections coevolve. Edges are picked at random. If the two connected individuals hold different opinions then, with probability 1 - α, one imitates the opinion of the other; otherwise (i.e., with probability α), the link between them is broken and one of them makes a new connection to an individual chosen at random (i) from those with the same opinion or (ii) from the network as a whole. The evolution of the system stops when there are no longer any discordant edges connecting individuals with different opinions. Letting ρ be the fraction of voters holding the minority opinion after the evolution stops, we are interested in how ρ depends on α and the initial fraction u of voters with opinion 1. In case (i), there is a critical value αc which does not depend on u, with ρ ≈ u for α > αc and ρ ≈ 0 for α < αc. In case (ii), the transition point αc(u) depends on the initial density u. For α > αc(u), ρ ≈ u, but for α < αc(u), we have ρ(α,u) = ρ(α,1/2). Using simulations and approximate calculations, we explain why these two nearly identical models have such dramatically different phase transitions.
- coevolutionary network
- quasi-stationary distribution
- Wright–Fisher diffusion
- approximate master equation
Footnotes
- ↵1To whom correspondence should be addressed. E-mail: rtd@math.duke.edu.
-
Author contributions: R.D., J.P.G., A.L.L., P.J.M., F.S., D.S., J.E.S.S., and C.V. performed research; and R.D. and P.J.M. wrote the paper.
-
The authors declare no conflict of interest.
-
This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1200709109/-/DCSupplemental.
Freely available online through the PNAS open access option.