## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Graph fission in an evolving voter model

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

In recent years, a variety of research efforts from different disciplines have combined with established studies in social network analysis and random graph models to fundamentally change the way we think about networks. Significant attention has focused on the implications of dynamics in establishing network structure, including preferential attachment, rewiring, and other mechanisms (1⇓⇓⇓–5). At the same time, the impact of structural properties on dynamics on those networks has been studied, (6), including the spread of epidemics (7⇓⇓–10), opinions (11⇓–13), information cascades (14⇓–16), and evolutionary games (17, 18). Of course, in many real-world networks the evolution of the edges in the network is tied to the states of the vertices and vice versa. Networks that exhibit such a feedback are called adaptive or coevolutionary networks (19, 20). As in the case of static networks, significant attention has been paid to evolutionary games (21⇓⇓–24) and to the spread of epidemics (25⇓⇓⇓–29) and opinions (30⇓⇓⇓⇓–35), including the polarization of a network of opinions into two groups (36, 37). In this paper, we examine two closely related variants of a simple, abstract model for coevolution of a network and the opinions of its members.

## Holme–Newman Model

Our starting point is the model of Holme and Newman (38⇓⇓–41). They begin with a network of *N* vertices and *M* edges, where each vertex *x* has an opinion *ξ*(*x*) from a set of *G* possible opinions and the number of people per opinion *γ*_{N} = *N*/*G* stays bounded as *N* gets large. On each step of the process, a vertex *x* is picked at random. If its degree *d*(*x*) = 0, nothing happens. For *d*(*x*) > 0, (*i*) with probability *α* an edge attached to vertex *x* is selected and the other end of that edge is moved to a vertex chosen at random from those with opinion *ξ*(*x*); (*ii*) otherwise (i.e., with probability 1 - *α*) a random neighbor *y* of *x* is selected and we set *ξ*(*x*) = *ξ*(*y*). This process continues until there are no longer any edges connecting individuals with different opinions.

When *α* = 1, only rewiring steps occur, so once all of the *M* edges have been touched, the graph has been disconnected into *G* components, each consisting of individuals who share the same opinion. Because none of the opinions have changed, the components are small (i.e., their sizes are Poisson with mean *γ*_{N}). By classical results for the coupon collector’s problem, this requires approximately *M* log *M* updates (see, e.g., ref. 42, p. 57).

In contrast, for *α* = 0, this system reduces to the voter model on a static graph. If we suppose that the initial graph is an Erdös–Rényi random graph in which each vertex has average degree *λ* > 1, then (see, e.g., ref. 12, chap. 2) there is a “giant component” that contains a positive fraction, *μN*, of the vertices and the second largest component is small having only *O*(log *N*) vertices; i.e., when *N* is large, the size will be approximately *C*_{λ} log *N*, where *C*_{λ} is a constant that depends on *λ*. The voter model on the giant component will reach consensus in *O*(*N*^{2}) steps (see, e.g., ref. 12, sect. 6.9), so the end result is that one opinion has *μN* followers while all of the other groups are small.

Using simulation and finite size scaling, Holme and Newman showed that there is a critical value *α*_{c} so that for *α* > *α*_{c} all of the opinions have a small number of followers at the end of the process, whereas for *α* < *α*_{c} “a giant community of like-minded individuals forms” (38). When the average degree *λ* = 2*M*/*N* = 4 and the number of individuals per opinion *γ*_{N} → 10, this transition occurs at *α*_{c} ≈ 0.46.

## Our Model and Simulation Results

The “rewire-to-same” model we study differs from that of Holme and Newman in two ways: (*i*) we consider two opinions (called 0 and 1) instead of a number proportional to the size of the graph; and (*ii*) on each step, we pick a discordant edge (*x*,*y*) at random rather than a vertex, avoiding the problem of picking vertices with degree zero or vertices that agree with all of their neighbors. With probability 1 - *α*, the voter at *x* adopts the opinion of the voter at *y*. Otherwise (i.e., with probability *α*), *x* breaks its connection to *y* and makes a new connection to a voter chosen at random from those that share its opinion. The process continues until there are no edges connecting voters that disagree.

Despite the differences in implementation, this rewire-to-same model has a phase transition similar to that of Holme and Newman. In particular, the final fraction *ρ* of voters with the minority opinion undergoes a discontinuous transition at a value *α*_{c} that does not depend on the initial density. Fig. 1 shows results of simulations for the rewire-to-same model starting from an initial graph that is Erdös–Rényi with *N* = 100,000 vertices and average degree *λ* = 4. Opinions are initially assigned randomly with the probability of opinion 1 given by *u* = 0.5, 0.25, 0.1, and 0.05. The figure shows the final fraction *ρ* of voters with the minority opinion from five realizations for each *u*. For *α* > *α*_{c} ≈ 0.43, we observe *ρ* ≈ *u* and for *α* < *α*_{c}, *ρ* ≈ 0.

We also study a “rewire-to-random” variant of this model that differs from the rewire-to-same model in only one way: *x* makes its new connection to a voter chosen at random from all of the vertices in the graph. This single difference leads to fundamentally different model outcomes, as seen in Fig. 2, showing simulation results for the rewire-to-random model on initially Erdös–Rényi graphs with *N* = 100,000 nodes and average degree *λ* = 4 for *u* = 0.5, 0.25, 0.1, and 0.05. When *u* = 0.5, the fraction in the minority is constant at 0.5 over [*α*_{c}(0.5),1] and then decreases continuously to a value near zero as *α* decreases to zero.

The behavior of our models for *α* > *α*_{c} is easy to understand. As in the case of the Holme and Newman model, we expect consensus to be reached in *O*(*N* log *N*) steps when *α* = 1 and in *O*(*N*^{2}) steps when *α* = 0. We define the boundary between the fast and slow consensus regimes to be the value of *α*, where the average number of steps needed to reach consensus is *N*^{3/2} (any power between one and two would give the same results when *N* → ∞). When an edge is chosen between voters with different opinions, then a rewiring event does not change the number of ones, whereas a voting event will increase and decrease the number of ones with equal probability; i.e., the number of ones is a random walk that on each step stays constant with probability *α*. The central limit theorem implies that when consensus is reached in *O*(*N*^{3/2}) steps, the typical change in the number of ones from the initial configuration is *O*(*N*^{3/4}). Hence, when the initial fractions of ones is *u* ≤ 1/2, the final fraction *ρ* with the minority opinion will be approximately equal to *u*.

Turning to the curves in Fig. 2 for *u* = 0.25, 0.1, and 0.05, we see that each initial density *u* has a critical value *α*_{c}(*u*), so that for *α* > *α*_{c}(*u*), we have *ρ*(*α*,*u*) = *u*, whereas for *α* < *α*_{c}(*u*), we have *ρ*(*α*,*u*) = *ρ*(*α*,0.5). Because all of the *ρ*(*α*,*u*) agree with *ρ*(*α*,0.5) when they are < *u*, we call the graph of *ρ*(*α*,0.5) on [0,*α*_{c}(0.5)] the universal curve. The main goal of this paper is to explain this phenomenon.

## Quasi-Stationary Distributions

Let *N*_{i} be the number of vertices in state *i*. Our first clue to the reason for a universal curve in the rewire-to-random model came from Fig. 3, which shows the change over time of the fraction of vertices with the minority opinion min{*N*_{1},*N*_{0}}/*N* and the number of edges connecting vertices with opposite opinions, *N*_{10}, for a simulation in which the initial density of ones is *u* = 1/2, *α* = 0.3, the number of nodes is *N* = 1,000, and we start with an Erdös–Rényi graph with average degree *λ* = 4. In the visualization of these results and the theoretical discussions that follow, the model is considered in continuous time with each edge subject to change at times of a rate one Poisson process. The sequence of states visited by the model is the same in discrete or continuous time, but *tM* updates correspond to continuous time *t*. Hence, in the slow consensus regime, *O*(*N*^{2}) updates becomes time *O*(*N*).

There are *M* ≈ 2,000 edges in this graph simulated in Fig. 3, so the initial number of 1-0 edges is approximately 1,000, but the curve drops very quickly to a value near 600, and then begins to change more slowly. The second key observation is that the number of 0-1 edges and the fraction with the minority opinion min{*N*_{1},*N*_{0}}/*N* appear to be strongly correlated. The initial transient and the reason for the correlation will be seen more clearly in Fig. 4.

To explain the key insight derived from this simulation, we recall results for the voter model on the *d*-dimensional integer lattice , in which each vertex decides to change its opinion at rate 1, and when it does, it adopts the opinion of one of its 2*d* nearest neighbors chosen at random. Let *ξ*_{t}(*x*) be the opinion of the voter at *x* at time *t*. Holley and Ligget (43) and Liggett (44) proved the following result.

In *d* ≤ 2, the voter model approaches complete consensus; that is, if *x* ≠ *y* then *P*[*ξ*_{t}(*x*) ≠ *ξ*_{t}(*y*)] → 0. In *d*≥3, if the voter model starts from product measure with density *p* [i.e., are independent and equal to one with probability *p*], then converges in distribution to a limit *ν*_{p}, which is a stationary distribution for the voter model.

Simulations of the voter model are done on a finite set, typically the torus . In this setting, the behavior of the voter model is “trivial” because it is a finite Markov chain with two absorbing states, all ones and all zeros. As the next result shows (see Cox and Greven, ref. 45), the voter model has interesting behavior along the road to absorption.

If the voter model on the torus in *d*≥3 starts from product measure with density *p*, then at time *Nt* it looks locally like *ν*_{θ(t)} where the density *θ*_{t} changes according to the Wright–Fisher diffusion process and *β*_{d} is the probability that two random walks starting from neighboring sites never hit.

In the next section we will describe conjectures for the evolving voter model that are analogues of the last theorem. To prepare for stating our conjectures, note that (*i*) although the voter model on the torus does not have a nontrivial stationary distribution, it does have a one parameter family of “quasi-stationary distributions” that look locally like *ν*_{p}, and (*ii*) the quantity under the square root in the Wright–Fisher diffusion is, by results of Holley and Liggett (43), the expected value of *N*_{10}/*M* under *ν*_{θ(t)}.

## Conjectures

Our next goal is to use simulation results to formulate the analogues of the Cox and Greven result (45) for our two evolving voter models, beginning with the more interesting rewire-to-random case. Fig. 4 shows results from simulations of the system with *α* = 0.5. The initial graph is Erdös–Rényi with *N* = 10,000 vertices and average degree *λ* = 4. Observations of the pair (*N*_{1}/*N*,*N*_{10}/*M*) are plotted every 1,000 steps starting from densities *u* = 0.2, 0.35, 0.5, 0.65, and 0.8. The plotted points converge quickly to a curve that is approximately (fitting to a parabola) 1.707*x*(1 - *x*) - 0.1867 and then diffuse along the curve until they hit the axis near 0.125 or 0.875. Thus the final fraction with the minority opinion *ρ* ≈ 0.125, a value that agrees with the universal curve in Fig. 2 at *α* = 0.5.

The fact that, after the initial transient, *N*_{10}/*M* is a function of *N*_{1}/*N* supports the conjecture that the evolving voter model has a one parameter family of quasi-stationary distributions, for if this is true, then the values of all of the graph statistics can be computed from *N*_{1}/*N*. To further test this conjecture, we examined the joint distribution of the opinions at three sites. Let *N*_{ijk} be the number of oriented triples *x*-*y*-*z* of adjacent sites having states *i*, *j*, *k*, respectively. Note for example, in the 010 case, this will count all such triples twice, but this is the approach taken in the theory of limits of dense graphs (46), where the general statistic is the number of homomorphisms of some small graph (labeled by ones and zeros in our case) into the random graph being studied.

Fig. 5 shows a plot of *N*_{010}/*N* versus *N*_{1}/*N*. After an initial transient, the observed values stay close to a curve that is well approximated by a cubic. Simulations of the other *N*_{ijk} show similar behavior. Because the numbers of 010 triples must vanish when the number of 1-0 edges do, the fitted cubic shares two roots with the quadratic approximating the graph of *N*_{10}/*M* versus *N*_{1}/*N*. This quadratic curve (see again Fig. 4 for *α* = 0.5) is fundamental to our understanding of the observed system behavior, and we hereafter refer to it as the “arch.”

The phenomena just described for *α* = 0.5 also hold for other values of *α*. Fig. 6 shows the arches that correspond to *α* = 0.1,0.2,…,0.7. Numerical results show that the curves are well approximated by *c*_{α}*u*(1 - *u*) - *b*_{α}. Let (*v*(*α*),1 - *v*(*α*)) be the “support interval” where the arch has positive values. Simulations show that if *u* < *v*(*α*), then the simulated curve rapidly goes almost straight down and hits the axis where *N*_{10} = 0.

In the rewire-to-random model, if *α* < *α*_{c}(1/2) and *v*(*α*) < *u* ≤ 1/2, then starting from product measure with density *u* of ones, the evolving voter model converges rapidly to a quasi-stationary distribution *ν*_{α,u}. At time *tN*, the evolving voter model looks locally like *ν*_{α,θ(t)} where the density changes according to a generalized Wright–Fisher diffusion process until *θ*_{t} reaches *v*(*α*) or 1 - *v*(*α*).

Here the quantity under the square root is (1 - *α*)*N*_{10}/*M* with (1 - *α*) equal to the fraction of steps that are voter steps because rewiring steps do not change the number of ones.

If Conjecture 1 is true, then the universal curve in Fig. 2 has *ρ*(*α*,0.5) = *v*(*α*) for *α* < *α*_{c}(0.5). When *α* is close to *α*_{c}(0.5), *v*(*α*) ≈ 1/2, so when the evolving voter model hits *N*_{10} = 0 both opinions are held by large groups, and the graph splits into two giant connected components (that is, their size is proportional to *N* for large graphs). Fig. 7 visualizes a network shortly before this “graph fission” for *α* = 0.65.

Though the nature of the phase transition looks different in the rewire-to-same model, the underlying picture is the same. Fig. 8 shows arches computed from simulations for the rewire-to-same model that correspond to the ones in Fig. 6 for the rewire-to-random model. However, now all the arches have the same support interval, (0,1), and the formulas in that figure show that the curves are well approximated by *c*_{α}*u*(1 - *u*) for different values of *c*_{α}.

In the rewire-to-same case, Vazquez et al. (40) noticed that the fraction of active links *N*_{10}/*M* plotted versus the fraction of ones converged rapidly to an arch and then diffused along it (see ref. 40, figure 4). However, they did not formulate the following:

In the rewire-to-same model, the behavior is as described in Conjecture 1 but now *b*_{α} = 0, so *α*_{c} is independent of the initial density *u*, and for *α* < *α*_{c}, *ρ* ≈ 0.

## Approximate Calculations

Our next question is why is there a difference in the behavior of the support intervals of the arches in the two models? Consider first the rewire-to-random model. By considering all of the possible changes, one can write differential equations for the graph statistics. For example, To be mathematically precise, for any *T* < ∞ this holds for *t* ≤ *T* in the limit as the number of vertices tends to ∞. Thus these equations describe the initial behavior (i.e., as the evolving voter model converges to the arch of quasi-stationary distributions) and their equilibria as a function of *u* describe the arch itself.

Note that the derivatives of the two-vertex quantities *N*_{ij} involve two or three vertices. Derivatives of three-vertex quantities involve up to four vertices. To be able to solve the equations, we need some approximation to close the equations. In physics and ecology (see ref. 47 and references therein), it is common to use the pair approximation (PA), which in essence assumes the equilibrium state is a Markov chain: *N*_{100} = *N*_{10}*N*_{00}/*N*_{0}. A little algebra then shows (see *SI Materials* for more details about the results in this section) that, for *u*∈(0,1/2], [1]When *λ* = 4, *α*_{c}(1/2) = 6/7 and *α*_{c}(*u*) → 3/4 as *u* → 0, so the predicted fraction *ρ* with the minority opinion at the end rises from zero to one-half on [3/4,6/7]. Fig. 9 compares the predicted value of *ρ* with simulations in Fig. 2 and shows the agreement is very poor.

One gets much better estimates of *ρ* from the approximate master equation (AME) framework introduced in ref. 48 to analyze binary state dynamics such as epidemic models. Here we follow the approach in refs. 49. Let [] be the number of nodes at time *t* that are in state 0 (susceptible) [in state 1 (infected)], have degree *k*, and have *m* neighbors in state 1.

To describe the logic behind the AME, let *x* be a vertex and let *y* be one of its neighboring vertices. Three types of things can happen: (*i*) rewiring may break the connection between *x* and *y* or bring a new edge to connect to *x*; (*ii*) *x* or *y* may influence the other by a voting step; or (*iii*) the opinion of *y* may be changed by imitating one of its neighbors *z* ≠ *x*.

Exact equations can be written for the first two types of events in terms of and , but the third type requires an approximation. For example, if *x* and *y* are both in state 0, we postulate that *y* changes from zero to one at rate *N*_{001}/*N*_{00}, the expected number of 1 neighbors of a 0-0 edge. This reasoning is similar to the PA, but now we do not suppose that *N*_{001}/*N*_{00} = *N*_{01}/*N*_{0}, which, if numerical results are accurate, approximates the ratio of two cubic by a quadratic over the density *u*. Instead, we use identities such as to compute the evolution of *N*_{001}/*N*_{00} and other similar terms. As shown in Fig. 10, the AME gives a better approximation of the final minority fraction *ρ* than the PA. More importantly, the AME gives the correct qualitative behavior: the predicted *ρ*(*α*) > 0 for all *α* > 0 and tends to zero as *α* → 0.

One can repeat the analysis described above for the rewire-to-same model. Using the PA, we conclude that *α*_{c} = (*λ* - 1)/*λ* and the arches *N*_{10}/*N* = *u*(1 - *u*)[*λ* - 1/(1 - *α*)] always span (0,1). This qualitative behavior agrees with Fig. 8, but the PA estimate of *α*_{c} = 3/4 when *λ* = 4 drastically overestimates the value *α*_{c} ≈ 0.43 that comes from simulation (see Fig. 1). Again, one can numerically solve differential equations to employ the AME. The computed arches span (0,1) but the numerical predictions of *ρ* and the estimate of *α*_{c} are more accurate. See *SI Materials* for details of the application of the PA and AME to both models.

## Discussion

We have considered a model in which the opinions of individuals and network structure coevolve. Based on a combination of simulation and approximate calculations we conclude that (*i*) there is a discontinuous transition in the rewire-to-same model, similar to that in Holme and Newman (38), which occurs at an *α*_{c} independent of the initial fraction *u* of ones; and (*ii*) there is a continuous transition in the rewire-to-random model at the critical value *α*_{c}(*u*) that depends on *u*, and the curves for the final fraction *ρ*(*α*,*u*) of voters in the minority agree with *ρ*(*α*,1/2) for *α* < *α*_{c}(*u*).

Thus, a small change in the dynamics of the model results in a large change in the qualitative behavior and in a manner that we find counterintuitive. One would think that the rewire-to-same dynamic would result in a more rapid division of the population into two noninteracting groups with different opinions. The critical value for the amount of rewiring *α*_{c} needed to produce rapid disconnection is smaller in the rewire-to-same case than *α*_{c}(1/2) for the rewire-to-random. Moreover, in the rewire-to-same case, the size of the minority opinion shrinks to almost zero for *α* < *α*_{c}, whereas in the rewire-to-random case, the group fissions into two, leaving a significant minority group.

Calculations based on the approximate master equation reproduce the qualitative behavior of the phase transition. However, it would be nice to derive results directly from the exact differential equations and in a way that gives some insight into the mechanisms underlying the differences between the two models.

## 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.).

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: rtd{at}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.

## References

- ↵
- ↵
- ↵
- Newman MEJ,
- Barabási AL,
- Watts DJ

- ↵
- Caldarelli G

- ↵
- Cohen R,
- Havlin S

- ↵
- Barrat A,
- Barthelemy M,
- Vespignani A

- ↵
- ↵
- ↵
- ↵
- Newman MEJ

- ↵
- ↵
- Durrett R

- ↵
- ↵
- Watts DJ

- ↵
- ↵
- Montanari A,
- Saberi A

- ↵
- ↵
- Easley D,
- Kleinberg J

- ↵
- Gross T,
- Blasius B

- ↵
- Skyrms B,
- Pemantle R

- ↵
- ↵
- ↵
- ↵
- ↵
- Volz E,
- Meyers LA

- ↵
- Volz E,
- Meyers LA

- ↵
- ↵
- Zanette DH

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Macy MW,
- Kitts JA,
- Flache A

- ↵
- Henry AD,
- Pralat P,
- Zhang CQ

- ↵
- ↵
- ↵
- ↵
- Herrera JL,
- Cosenza MG,
- Tucci K,
- González-Avella JC

- ↵
- Durrett R

- ↵
- ↵
- Liggett TM

- ↵
- ↵
- ↵
- ↵
- ↵

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Applied Mathematics