Graph fission in an evolving voter model
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.
Acknowledgments.
The authors thank Raissa D’Souza, Eric Kolaczyk, Tom Liggett, and Mason Porter for their many helpful suggestions. This work began during the 2010–2011 program on Complex Networks at the Statistical and Applied Mathematical Sciences Institute. This work was partially supported by National Science Foundation Grants DMS-1005470 (to R.D.) and DMS-0645369 (to P.J.M.), by Science Foundation Ireland Grants 06/IN.1/I366, and Mathematics Applications Consortium for Science and Industry 06/MI/005 (to J.P.G.), and by the Research and Policy for Infectious Disease Dynamics program at National Institutes of Health (A.L.L.).
Supporting Information
Supporting Information (PDF)
Supporting Information
- Download
- 282.46 KB
References
1
AL Barabási, R Albert, Statistical mechanics of complex networks. Rev Mod Phys 74, 47–97 (2002).
2
SN Dorogovtstev, JFF Mendes, Evolution of networks. Adv Phys 51, 1079–1187 (2002).
3
MEJ Newman, AL Barabási, DJ Watts The Structure and Dynamics of Networks (Princeton Univ Press, Princeton, 2006).
4
G Caldarelli Scale-Free Networks: Complex Webs in Nature and Technology (Oxford Univ Press, Oxford, 2007).
5
R Cohen, S Havlin Complex Networks: Structure, Robustness, and Function (Oxford Univ Press, Oxford, 2010).
6
A Barrat, M Barthelemy, A Vespignani Dynamical Processes on Complex Networks (Oxford Univ Press, Oxford, 2008).
7
MEJ Newman, Spread of epidemic disease on networks. Phys Rev E Stat Nonlin Soft Matter Phys 66, 016128 (2002).
8
E Volz, SIR dynamics in random networks with heterogeneous connectivity. J Math Biol 56, 293–310 (2008).
9
JC Miller, A note on a paper by Erik Volz: SIR dynamics in random networks. J Math Biol 62, 349–358 (2011).
10
MEJ Newman Networks: An Introduction (Oxford Univ Press, Oxford, 2010).
11
V Sood, S Redner, Voter model on heterogeneous graphs. Phys Rev Lett 94, 178701 (2005).
12
R Durrett Random Graph Dynamics (Cambridge Univ Press, Cambridge, UK, 2008).
13
C Castellano, S Fortunado, V Loreto, Statistical physics of social dynamics. Rev Mod Phys 81, 591–646 (2009).
14
DJ Watts, A simple model of global cascades on random networks. Proc Natl Acad Sci USA 99, 5766–5771 (2002).
15
JP Gleeson, DJ Cahalane, Seed size strongly affects cascades on random networks. Phys Rev E Stat Nonlin Soft Matter Phys 75, 056103 (2007).
16
A Montanari, A Saberi, The spread of innovations in social networks. Proc Natl Acad Sci USA 107, 20196–20201 (2010).
17
H Ohtsuki, C Hauert, E Lieberman, MA Nowak, A simple rule for the evolution of cooperation on graphs and social networks. Nature 441, 502–505 (2006).
18
D Easley, J Kleinberg Networks, Crowds and Markets (Oxford Univ Press, Oxford, 2010).
19
T Gross, B Blasius, Adaptive coevolutionary networks: A review. J R Soc Interface 5, 259–271 (2008).
20
B Skyrms, R Pemantle, A dynamic model of social network formation. Proc Natl Acad Sci USA 97, 9340–9346 (2000).
21
H Ebel, S Bornholdt, Co-evolutionary games on networks. Phys Rev E Stat Nonlin Soft Matter Phys 66, 056118 (2002).
22
MG Zimmerman, VM Eguíluz, M San Miguel, Coevolution of dynamical states and interactions on networks. Phys Rev E Stat Nonlin Soft Matter Phys 69, 065102 (2004).
23
MG Zimmerman, VM Eguíluz, Cooperation, social networks, and the emergence of leadership in a prisoner’s dilemma game. Phys Rev E Stat Nonlin Soft Matter Phys 72, 056118 (2005).
24
FC Santos, JM Pacheco, T Lenaerts, Cooperation prevails when individuals adjust their social ties. PLoS Comput Biol 2, e140 (2006).
25
E Volz, LA Meyers, Susceptible-infected recovered epidemics in dynamic contact networks. Proc Biol Sci 274, 2925–2933 (2007).
26
E Volz, LA Meyers, Epidemic thresholds in dynamic contact networks. J R Soc Interface 6, 233–241 (2009).
27
T Gross, CJ Dommar D’Lima, B Blasius, Epidemic dynamics on an adaptive network. Phys Rev Lett 96, 208701 (2006).
28
DH Zanette, Coevolution of agents and networks in an epidemiological model., arXiv:0707.1249.
29
S van Segroeck, FC Santos, JM Pacheco, Adaptive contact networks change effective disease infectiousness and dynamics. PLoS Comput Biol 6, e1000895 (2010).
30
S Gil, DH Zanette, Coevolution of agents and opinions: Opinion spreading and community disconnection. Phys Lett A 356, 89–94 (2006).
31
DH Zanette, S Gil, Opinion spreading and agent segregation on evolving networks. Physica D 224, 156–165 (2006).
32
JM Pacheco, A Traulsen, MA Nowak, Coevolution of strategy and structure in complex networks with dynamical linking. Phys Rev Lett 97, 258103 (2006).
33
B Kozma, A Barrat, Consensus formation on adaptive networks. Phys Rev E Stat Nonlin Soft Matter Phys 77, 016102 (2008).
34
B Kozma, A Barrat, Consensus formation on coevolving networks: Groups’ formation and structure. J Phys A Math Gen 41, 224020 (2008).
35
G Iniguez, J Kertész, KK Kaksi, RA Barrio, Opinion and community formation in coevolving networks. Phys Rev E Stat Nonlin Soft Matter Phys 80, 066119 (2009).
36
MW Macy, JA Kitts, A Flache, Polarization of dynamic networks. Dynamic Social Network Modeling and Analysis (Natl Acad Press, Washington, DC), pp. 162–173 (2003).
37
AD Henry, P Pralat, CQ Zhang, Emergence of segregation in evolving social networks. Proc Natl Acad Sci USA 108, 8605–8610 (2011).
38
P Holme, MEJ Newman, Nonequilibrium phase transition in the coevolution of networks and opinions. Phys Rev E Stat Nonlin Soft Matter Phys 74, 056108 (2006).
39
D Kimura, Y Hayakawa, Coevolutionary networks with homophily and heterophily. Phys Rev E Stat Nonlin Soft Matter Phys 78, 016103 (2008).
40
F Vazquez, VM Eguíluz, MS San Miguel, Generic absorbing transition in coevolution dynamics. Phys Rev Lett 100, 108702 (2008).
41
JL Herrera, MG Cosenza, K Tucci, JC González-Avella, General coevolution of topology and dyanmics in networks., arXiv:1102.3647. (2011).
42
R Durrett Probability: Theory and Examples (Cambridge Univ Press, 4th Ed, Cambridge, UK, 2010).
43
RA Holley, TM Liggett, Ergodic theorems for weakly interacting systems and the voter model. Ann Probab 4, 195–228 (1976).
44
TM Liggett Stochastic Interacting Systems: Contact, Voter and Exclusion Processes (Springer, New York), pp. 139–145 (1999).
45
JT Cox, A Greven, On the long term behavior of some finite particle systems. Probab Theory Rel Fields 85, 195–237 (1990).
46
C Borgs, JT Chayes, L Lovász, VT Sós, K Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv Math 219, 1801–1851 (2008).
47
SP Ellner, Pair approximation for lattice models with multiple interaction scales. J Theor Biol 210, 435–447 (2001).
48
V Marceau, P-A Noël, L Hébert-Dufresne, A Allard, L Dubé, Adaptive networks: Coevolution of disease and topology. Phys Rev E Stat Nonlin Soft Matter Phys 82, 036116 (2010).
49
JP Gleeson, High-accuracy approximation of binary-state dynamics on networks. Phys Rev Lett 107, 068701, extended version arXiv:1104.1537. (2011).
Information & Authors
Information
Published in
Classifications
Copyright
Freely available online through the PNAS open access option.
Submission history
Published online: February 21, 2012
Published in issue: March 6, 2012
Keywords
Acknowledgments
The authors thank Raissa D’Souza, Eric Kolaczyk, Tom Liggett, and Mason Porter for their many helpful suggestions. This work began during the 2010–2011 program on Complex Networks at the Statistical and Applied Mathematical Sciences Institute. This work was partially supported by National Science Foundation Grants DMS-1005470 (to R.D.) and DMS-0645369 (to P.J.M.), by Science Foundation Ireland Grants 06/IN.1/I366, and Mathematics Applications Consortium for Science and Industry 06/MI/005 (to J.P.G.), and by the Research and Policy for Infectious Disease Dynamics program at National Institutes of Health (A.L.L.).
Authors
Competing Interests
The authors declare no conflict of interest.
Metrics & Citations
Metrics
Citation statements
Altmetrics
Citations
Cite this article
109 (10) 3682-3687,
Export the article citation data by selecting a format from the list below and clicking Export.
Cited by
Loading...
View Options
View options
PDF format
Download this article as a PDF file
DOWNLOAD PDFLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Personal login Institutional LoginRecommend to a librarian
Recommend PNAS to a LibrarianPurchase options
Purchase this article to access the full text.