Graph fission in an evolving voter model
Proceedings of the National Academy of SciencesPublished 21 February 2012Open access
Richard Durrett, James P. Gleeson, Alun L. Lloyd, Peter J. Mucha, Feng Shi, David Sivakoff
Citations170
SJR quartileQ1
SJR score3.41
SNIP2.38
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Using simulations and approximate calculations, it is explained why these two nearly identical models of a social network in which individuals have one of two opinions and their opinions and the network connections coevolve have such dramatically different phase transitions.
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)(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.
Keywords
Decision SciencesPhysics and Astronomy
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
Networks: An Introduction
7,048 Citations2010Mark Newman
Reviews of Modern PhysicsStatistical physics of social dynamics
4,025 Citations2009Claudio Castellano, Santo Fortunato +1 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpread of epidemic disease on networks
3,285 Citations2002M. E. J. Newman
This paper shows that a large class of standard epidemiological models, the so-called susceptible/infective/removed (SIR) models can be solved exactly on a wide variety of networks.
Journal of the American Statistical AssociationProbability: Theory and Examples.
3,216 Citations1992Kathryn Prewitt, Richard Durrett
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Networks, crowds, and markets reasoning about a highly connected world
2,749 CitationsDavid Easley, Jon Kleinberg
This introductory book on the new science of networks takes an interdisciplinary approach, using economics, sociology, computing, information science and applied mathematics to address fundamental questions about the links that connect us, and the ways that the authors' decisions can have consequences for others.
Cambridge University Press eBooksDynamical Processes on Complex Networks
2,724 Citations2008Alain Barrat, Marc Barthélemy +1 more
A new and recent account presents a comprehensive explanation of the effect of complex connectivity patterns on dynamical phenomena in a vast number of everyday systems that can be represented as large complex networks.
Proceedings of the National Academy of SciencesA simple model of global cascades on random networks
2,669 Citations2002Duncan J. Watts
It is shown that heterogeneity plays an ambiguous role in determining a system's stability: increasingly heterogeneous thresholds make the system more vulnerable to global cascades; but anincreasingly heterogeneous degree distribution makes it less vulnerable.
Princeton University Press eBooksThe Structure and Dynamics of Networks
2,292 Citations2011Mark Newman, Albert-Ĺaszló Barabási +1 more
NatureA simple rule for the evolution of cooperation on graphs and social networks
2,241 Citations2006Hisashi Ohtsuki, Christoph Hauert +2 more
A surprisingly simple rule is described that is a good approximation for all graphs that are analysed, including cycles, spatial lattices, random regular graphs, random graphs and scale-free networks: natural selection favours cooperation if the benefit of the altruistic act, b, exceeds the average number of neighbours, k, which means b/c > k.
Grundlehren der mathematischen WissenschaftenStochastic Interacting Systems: Contact, Voter and Exclusion Processes
1,623 Citations1999Thomas M. Liggett
A new approach of financial volatility duration dynamics by stochastic interacting systems contact voter and core and passage time moments and hybrid zones for the exclusion.
The Annals of ProbabilityErgodic Theorems for Weakly Interacting Infinite Systems and the Voter Model
1,092 Citations1975Richard A. Holley, Thomas M. Liggett
Physical Review LettersEpidemic Dynamics on an Adaptive Network
909 Citations2006Thilo Groß, Carlos J. Dommar D’Lima +1 more
This work proposes a low-dimensional model to describe the epidemic dynamics on an adaptive network, where the susceptibles are able to avoid contact with the infected by rewiring their network connections, and presents a full local bifurcation analysis.
Journal of The Royal Society InterfaceAdaptive coevolutionary networks: a review
858 Citations2007Thilo Gross, Bernd Blasius
It is demonstrated that all these studies investigating the dynamics of adaptive networks are characterized by common themes, most prominently: complex dynamics and robust topological self-organization based on simple local rules.
Scale-Free Networks
753 Citations2007Guido Caldarelli
Complex Networks: Structure, Robustness and Function
723 Citations2010Reuven Cohen, Shlomo Havlin
This chapter discusses random network models, which are based on the Erdos-Renyi models, and their application in the context of complex networks, where distances in scale-free networks are small and distances in geographically embedded networks are large.
Physical Review LettersVoter Model on Heterogeneous Graphs
709 Citations2005Vishal Sood, S. Redner
The nonconservation of the magnetization is exploited to characterize how consensus is reached in the voter model on heterogeneous graphs and results agree with simulation data for networks with both uncorrelated and correlated node degrees.
Physical Review LettersCoevolution of Strategy and Structure in Complex Networks with Dynamical Linking
688 Citations2006Jorge M. Pacheco, Arne Traulsen +1 more
This work provides analytic results for the limiting cases where linking dynamics is much faster than evolutionary dynamics and vice versa, and shows how the individual capacity of forming new links or severing inconvenient ones maps into the problem of strategy evolution in a well-mixed population under a different game.
Physical Review ENonequilibrium phase transition in the coevolution of networks and opinions
598 Citations2006Petter Holme, M. E. J. Newman
A simple model of the convergence of opinion in social systems, with a single parameter controlling the balance of the two processes, that undergoes a continuous phase transition as this parameter is varied, from a regime in which opinions are arbitrarily diverse to one in which most individuals hold the same opinion.
Advances in MathematicsConvergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing
594 Citations2008Christian Borgs, Jennifer Chayes +3 more
Proceedings of the National Academy of SciencesA dynamic model of social network formation
574 Citations2000Brian Skyrms, Robin Pemantle
It is argued that modeling network structure as dynamic increases realism without rendering the problem of analysis intractable.
PLoS Computational BiologyCooperation Prevails When Individuals Adjust Their Social Ties
560 Citations2006Francisco C. Santos, Jorge M. Pacheco +1 more
These results show that simple topological dynamics reflecting the individual capacity for self-organization of social ties can produce realistic networks of high average connectivity with associated single-to-broad–scale heterogeneity and heterogeneity is found to become maximal when W reaches its critical value.
Physical Review ECoevolution of dynamical states and interactions in dynamic networks
496 Citations2004Martín Zimmermann, Vı́ctor M. Eguı́luz +1 more
The coupled dynamics of the internal states of a set of interacting elements and the network of interactions among them and the formation of a hierarchical interaction network that sustains a highly cooperative stationary state are explored.
Proceedings of the National Academy of SciencesThe spread of innovations in social networks
391 Citations2010Andrea Montanari, Amin Saberi
This paper characterizes the rate of convergence as a function of the structure of the interaction network and considers scenarios where the individuals’ behavior is the result of a strategic choice among competing alternatives based on the dynamics of coordination games.
Journal of Mathematical BiologySIR dynamics in random networks with heterogeneous connectivity
383 Citations2007Erik Volz
The dynamic equations provide an alternative way of determining the epidemic threshold where large-scale epidemics are expected to occur, and below which epidemic behavior is limited to finite-sized outbreaks.
Cambridge University Press eBooksNetworks, Crowds, and Markets
324 Citations2010David Easley, Jon Kleinberg
Physical Review ECooperation, social networks, and the emergence of leadership in a prisoner’s dilemma with adaptive local interactions
317 Citations2005Martín Zimmermann, Vı́ctor M. Eguı́luz
It is shown how the network adaptation dynamics favors the emergence of cooperators with the highest payoff, and these "leaders" are shown to sustain the global cooperative steady state.
Proceedings of the Royal Society B Biological SciencesSusceptible–infected–recovered epidemics in dynamic contact networks
297 Citations2007Erik Volz, Lauren Ancel Meyers
A mathematical approach to predicting disease transmission on dynamic networks in which each individual has a characteristic behaviour (typical contact number), but the identities of their contacts change in time, thereby providing a bridge between disparate classes of epidemiological models.
Physical Review LettersGeneric Absorbing Transition in Coevolution Dynamics
277 Citations2008Federico Vázquez, Victor M. Eguı́luz +1 more
A mean-field approximation reveals an absorbing transition from an active to a frozen phase at a critical value that only depends on the average degree micro of the network.
Physical Review ESeed size strongly affects cascades on random networks
273 Citations2007James P. Gleeson, Diarmuid J. Cahalane
It is demonstrated that the low- z transition may in fact be discontinuous in certain parameter regimes, and connections between these results and the zero-temperature random-field Ising model on random graphs are discussed.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsCoevolutionary games on networks
270 Citations2002Holger Ebel, Stefan Bornholdt
The transition from subcritical to critical avalanche dynamics can be traced to a change in the degeneracy of the cooperative macrostate and is observed for many variants of this game.
Physical Review EConsensus formation on adaptive networks
267 Citations2008B. Kozma, Alain Barrat
The investigations reveal that the adaptation of the network topology fosters cluster formation by enhancing communication between agents of similar opinion, although it also promotes the division of these clusters.
Physical Review LettersHigh-Accuracy Approximation of Binary-State Dynamics on Networks
228 Citations2011James P. Gleeson
Binary-state dynamics (such as the susceptible-infected-susceptible (SIS) model of disease spread, or Glauber spin dynamics) on random networks are accurately approximated using master equations.
Physical Review EAdaptive networks: Coevolution of disease and topology
212 Citations2010Vincent Marceau, Pierre‐André Noël +3 more
An improved compartmental formalism able to handle the simultaneous time evolution of the disease and the underlying network topology successfully is introduced and the interplay and outcomes of both dynamical elements, process and structure, on adaptive networks featuring different degree distributions at the initial stage are analyzed.
Journal of Mathematical BiologyA note on a paper by Erik Volz: SIR dynamics in random networks
210 Citations2010Joel C. Miller
An alternate derivation which arrives at a simpler—though equivalent—system of governing equations to that of Volz is offered, which is more closely connected to the underlying physical processes, and the resulting equations are of comparable complexity to the mass-action SIR equations.
Journal of The Royal Society InterfaceEpidemic thresholds in dynamic contact networks
206 Citations2008Erik Volz, Lauren Ancel Meyers
It is shown that social mixing fundamentally changes the epidemiological landscape and, consequently, that static network approximations of dynamic networks can be inadequate.
Proceedings of the National Academy of SciencesEmergence of segregation in evolving social networks
123 Citations2011Adam Douglas Henry, Paweł Prałat +1 more
A model of network evolution where actors are assumed to have a small aversion from being connected to others who are dissimilar to themselves, and yet no actor strictly prefers a segregated network is introduced.
Journal of Theoretical BiologyPair Approximation for Lattice Models with Multiple Interaction Scales
118 Citations2001Stephen P. Ellner
A multiscale pair approximation which allows different sized neighborhoods for each type of interaction and provides a useful intermediate between the standard pair approximation for a single interaction neighborhood, and a complete set of moment equations for more spatially detailed models.
Physical Review ECoevolutionary networks with homophily and heterophily
107 Citations2008Daichi Kimura, Yoshinori Hayakawa
It is found that this coevolutionary network model incorporating three processes-changes of opinions, homophily, and heterophily exhibits topologically complicated behaviors such as the small-world property.
Physics Letters ACoevolution of agents and networks: Opinion spreading and community disconnection
106 Citations2006Santiago Gil, Damián H. Zanette
Physical Review EOpinion and community formation in coevolving networks
88 Citations2009Gerardo Íñiguez, János Kertész +2 more
This model includes the opinion-dependent link-rewiring scheme to describe network topology coevolution with a slower time scale than that of the opinion formation and shows the importance of the separation between fast and slow time scales resulting in the network to organize as well-connected small communities of agents with the same opinion.
Physica D Nonlinear PhenomenaOpinion spreading and agent segregation on evolving networks
88 Citations2006Damián H. Zanette, Santiago Gil
A stochastic model where the distribution of opinions in a population of agents coevolves with their interaction network is studied, and a detailed account of such properties, as well as of the final opinion distribution is given.
PLoS Computational BiologyAdaptive Contact Networks Change Effective Disease Infectiousness and Dynamics
71 Citations2010Sven Van Segbroeck, Francisco C. Santos +1 more
Disease dynamics in finite populations in which infection occurs along the links of a dynamical contact network whose reshaping may be biased based on each individual's health status are studied.
The Annals of ProbabilityA Martingale Approach to Infinite Systems of Interacting Processes
58 Citations1976Richard A. Holley, D. W. Stroock
Journal of Physics A Mathematical and TheoreticalConsensus formation on coevolving networks: groups' formation and structure
54 Citations2008B. Kozma, Alain Barrat
The effect of adaptivity on a social model of opinion dynamics and consensus formation is studied, which finds that adaptive rewiring fosters group formation by enhancing communication between agents of similar opinion, though it also makes possible the division of clusters.
Probability Theory and Related FieldsOn the long term behavior of some finite particle systems
39 Citations1990J. Theodore Cox, Andreas Greven
Europhysics Letters (EPL)General coevolution of topology and dynamics in networks
33 Citations2011José Luís Herrera, M. G. Cosenza +2 more
It is shown that coevolution models correspond to curves on this space describing functional relations between Pr and Pc, and a region of this space is found where different node states can coexist for very long times on one large, connected network.
arXiv (Cornell University)Coevolution of agents and networks in an epidemiological model
12 Citations2007Damián H. Zanette
It is shown that a moderate reconnection frequency is enough to completely suppress the infection, and a partial, rather weak isolation of infected agents suffices to eliminate the endemic state.