Some features of the spread of epidemics and information on a random graph

Three Random Graphs

Small world graphs were first introduced by Watts and Strogatz (12). To construct their model, they take a one-dimensional ring Z mod n and connect all pairs of vertices that are distance m or less. They then rewire each edge with probability p by moving one of the ends at random, where the new end is chosen uniformly. This leads to a graph that has small diameter but, in contrast to the Erdös–Renyi model, has a nontrivial density of triangles. These are both properties that they observed in the collaboration graph of film actors, the power grid, and the neural network of the nematode C. elegans. The small world model has been extensively studied, although most investigators have found it more convenient to study the Newman and Watts (13) version in which all pairs of vertices that are distance m or less are connected, but in addition there is a density p of shortcuts that connect vertices to long-range neighbors chosen at random from the graph.

Barábasi and Albert (14) introduced the preferential attachment model. In this model, we successively add vertices. Each new vertex connects to m existing vertices, choosing them with probabilities proportional to their degrees. The fraction of vertices with degree k converges to a limit [1]If vertices are chosen with weight proportional to a + k with a > -1 then the limiting degree sequence has p_k ∼ Ck^-(3+a) [see Krapivsky, Redner, and Leyvrasz (15)]. When a≥0, this is equivalent to the rule: When a new edge is drawn, with probability a/(a + 1) we pick the vertex at random and with probability 1/(a + 1) we use preferential attachment. Cooper and Freize (16) show power-law degree distributions arise in a wide variety of related models.

The dynamic procedure used to grow the graphs provides an explanation for power-law behavior in some networks. However, if one only wants a graph with a power-law degree distribution, it is simpler to use the NSW recipe, see Newman et al. (17, 18). Given a degree distribution {p_k: k≥0} we construct a random graph G_n with vertex set {1,2,…,n} as follows: let d₁,…,d_n be independent and have the distribution P(d_i = k) = p_k. We condition on the event E_n = {d₁ + ⋯+d_n is even} to have a valid degree sequence. If P(d_i is odd)∈(0,1) then P(E_n) → 1/2 as n → ∞, so the conditioning will have a little effect on the distribution of d_i’s. Having chosen the degree sequence (d₁,d₂,…,d_n), we allocate d_i half-edges to the vertex i, and then pair those half-edges at random. This may produce self-loops or parallel edges, but when the degree distribution has finite variance, the probability these problems do not occur is bounded away from zero, so the reader who wants can condition on G_n being a proper graph.

Two Epidemics

Epidemic models come in two basic flavors: the susceptible-infected-removed (SIR) in which suspectible individuals become infected at a rate equal to λ times the number of infected neighbors, remain infected for an exponentially distributed amount of time with mean 1, and then enter the removed class when they are no long susceptible to the disease. The SIR model on random graphs has a detailed theory due to its connection to percolation: Given neighbors x and y in the graph, we draw an edge from x to y with probability λ/(λ + 1), which is the probability that x (or y) will succeed in infecting the other during the time it is infected. The size of an epidemic starting with x infected is just the size of the component containing x in the new random graph. See Moore and Newman (19) for results on the small world, and Newman (20) for results on a graph with a fixed degree distribution.

We will be interested in the more difficult susceptible-infected-susceptible (SIS) epidemic model. In this model, at any time t each site x is either infected or healthy (but susceptible). An infected site becomes healthy at rate 1 independent of other sites and is again susceptible to the disease, while a susceptible site becomes infected at a rate λ times the number of its infected neighbors. Harris (21) introduced this model on the d-dimensional integer lattice and named it the contact process. See Liggett (22) for an account of most of the known results. In the SIS case, which we will usually refer to as the contact process, one typically cannot compute the critical value because the epidemic can backtrack and run into itself, whereas the SIR model is forced to move forward into the set of susceptibles and is essentially equivalent to a branching process.

Small Worlds

We consider the following version of the small world. Start with a circle Z mod n and connect x to all vertices x - m,…x + m where the addition is done modulo n. The number of sites n is required to be even so that one can partition the n vertices into n/2 pairs. Consider all such partitions and then pick one uniformly at random. When m = 1 this construction of a graph with diameter ∼ log ₂n dates back to Bollobás and Chung (23), 10 years before Watts and Strogatz (12). We will call this the BC small world.

The reason for insisting that all individuals have exactly one long-range neighbor is that we can define an associated big world graph that is nonrandom. The graph can be succinctly described as the free product Z ∗ {0,1}, where the second factor is Z mod 2. Elements of the free product have the form z₀1z₁1…1z_k where z_i∈Z - {0} for 0 < i < k. In words, this is the point you reach by moving by z₀ in the first copy of Z, going down a long-range edge, moving sideways by z₁, going down a long-range edge, etc. The big world encapsulates the heuristic that in the beginning stages of the epidemic, an infection transmitted across a long-range edge brings it to a new uninfected part of the space.

Following Durrett and Jung (24), who proved the three results we will state in this section, we will consider the discrete-time contact process. On either the small world or the big world, an infected individual lives for one unit of time. During its infected period it will infect some of its neighbors. All infection events are independent, and each site that receives at least one infection is infected at the next time step. A site infects itself or its short-range neighbors, each with probability α/(2m + 1)d. It infects its long-range neighbor with probability β. Let λ = α + β and r = α/β We are interested in the phase diagram as a function of (α,β), but in some cases we fix the ratio 0 < r < 1 and vary λ.

The number of sites within distance r of a given site in the big world grows exponentially fast, so it is natural to guess that its contact process will behave like the contact process on a tree. Consider a tree in which each vertex has the same degree, let 0 be a distinguished vertex (the origin) of the tree, and let be the set of infected sites at time t on the tree starting from 0 occupied. For the contact process on the tree or on the big world, we can define two critical values: We call λ₁ the weak survival critical value and λ₂ the strong survival critical value. Pemantle (25) showed that for homogeneous trees where every vertex has at least four neighbors, λ₁ < λ₂. Liggett (26) then extended Pemantle’s result to trees with degree 3 by finding numerical bounds on the two critical values and thus showing that they are different. Later Stacey (27) found an elegant proof that did not rely on numerical bounds.

Durrett and Jung (24) were forced to take the range m to be large because the result is proved, as Pemantle did, by getting upper bounds on λ₁ and lower bounds on λ₂.

Having established the existence of two phase transitions on the big world, our next question is: How does this translate into behavior of the contact process on the small world? We will use B_t to denote the contact process on the big world and ξ_t for the contact process on the small world. Let and .In words, there is positive probability that the process survives for all time when λ > λ₁, but only for λ > λ₂ are we certain that 0 will become infected when the process does not die out.

Let and .

Combined with our table, this result shows that when λ₁ < λ < λ₂ the contact process survives with positive probability, but if it does it may take a time that grows with n until the origin is infected for the first time. Thus from the standpoint of an observer on the graph, the epidemic appears to die out, but then it comes back much later. To our knowledge this phenomenon has not been noticed by people simulating the process.

Because the small world is a finite graph, the infection will eventually die out. However, by analogy with results for the d-dimensional contact process on a finite set, we expect that if λ > λ₁ and the process does not become extinct quickly, it will survive for a long time. Durrett and Liu (28) showed that the supercritical contact process on the circle Z mod n survives for an amount of time of order exp(cn) starting from all ones, while Mountford (29) showed that the supercritical contact process on the torus (Z mod n)^d survives for an amount of time of order exp(cn^d).

On any graph with n nodes and ≤ Cn edges, the infection cannot persist for longer than O(e^cn) because there is probability ≥e^-γn that in the next unit of time all sites become healthy and no infections occur. Durrett and Jung (24) were only able to prove the last conclusion for a modification of the small world contact process where, in addition to the short- and long-range infections, at each time step each infected site it will with probability γ infect a vertex chosen uniformly random vertex from the entire grid.

From a modeling point of view, this mechanism is reasonable. In addition to long-range connections with friends at school or work, one has random encounters with people one sits next to on airplanes or meets while shopping in stores. The strategy for establishing prolonged survival is to show that if the number of infected sites drops below ϵn, it will with probability≥1 - C exp(-γn) increase to ≥2ϵn before dying out. To do this we use the random connections to spread the particles out so that they can grow independently. Ideally one would use the long-range connections (instead of the random connections) to achieve this. However, one has to deal with unlikely but annoying scenarios such as all infected individuals being long-range neighbors of sites that are respectively short-range neighbors of each other.

Power-Law Degree Distribution

Pastor-Satorras and Vespignani (30, 31, 32) have made an extensive study of the contact process on graphs with power-law degree distributions, P(d_i = k) ∼ Ck^-α, using mean-field methods. Their nonrigorous computations suggest the following conjectures about λ_c the threshold for “prolonged persistence” of the contact process.

• If α ≤ 3, then λ_c = 0.

• If 3 < α ≤ 4, then λ_c > 0 but the critical exponent β, which controls the rate at which the equilibrium density of infected sites goes to 0, satisfies β > 1.

• If α > 4, then λ_c > 0 and the equilibrium density ∼C(λ - λ_c) as λ↓λ_c, i.e. the critical exponent β = 1.

Gómez-Gardeñes et al. (33) have recently extended their arguments to the bipartite case, which they think of as a social network of sexual contacts between men and women. They define the polynomial decay rates for degrees in the two sexes to be γ_M and γ_F and argue that the epidemic is supercritical when the transmission rates for the two sexes satisfy [2]where the angle brackets indicate expected value and k is shorthand for the degree distribution. Hence λ_c is positive when γ_M, γ_F > 3. Chatterjee and Durrett (34) have shown that the conclusions described above are not correct: λ_c = 0 for 3 < α < ∞. The argument extends easily to the bipartite case.

The assumption P(d_i ≤ 2) = 0 is not really necessary but is convenient, because it implies that P(G_n is connected) → 1 as n → ∞. Presumably λ_c = 0 for 1 < α ≤ 3, but the geometry of the graph changes, so we restricted our attention to the range in which the conclusion is the most surprising. Berger, Borgs, Chayes, and Saberi (35, 36) proved a similar result for the preferential attachment model of Barábasi and Alberts with α = 3 and for the generalization mentioned above that is a combination of preferential and random attachment.

Physicists “mean-field” arguments are usually reliable when dimension is sufficiently large, and our locally tree-like random graph is essentially infinite dimensional, so what went wrong? Let ρ_k denote the fraction of sites of degree k occupied in equilibrium, and let θ(λ) be the probability that a randomly chosen edge points to an infected site. The conclusions of Pastor-Satorras and Vespignani cited above are based on writing two equations: where q_k = kp_k/μ with .

The second equation is a self-consistency equation. The “size-biased distribution” q_k appears because when one picks an edge at random, vertices with degree k are k times as likely to be chosen. The first equation is the problem. It assumes that the state of a neighbor of a site is independent of the fact that it is vacant. This is rarely exactly true, but in high dimensions it is usually close enough to the truth to end up the right qualitative predictions. However, in this case it is not.

The proof of Theorem 4 is not difficult. One first shows that if λk²≥50 and we consider a vertex with degree k and all of its neighbors to make a star graph then the infection persists for time exp(kλ²/100) with high probability. Let ϵ > 0 and consider the vertices with degree ≥n^ϵ, which we call stars. Infection at a star persists for time exp(n^ϵλ²/100). The graph has diameter of order log n, so the probability a star can infect another by a chain of O(log n) events is ≥n^-b for some b < ∞. These observations and comparison with simple random walk with positive drift imply that for time ≥ exp(cn^-(1-δ)) most of the stars are infected.

To complete the proof we have to get a positive lower bound on the set of infected sites. To do this we will use the “self-duality” of the contact process. To state this relationship let denote the process with . In this notation, “self-duality” is [4]This is most conveniently proved by representing the process using a “graphical representation,” which is a sort of space-time percolation process, and noting that each side of the equation is the probability of a path from A × {0} to B × {t}. See Griffeath (37). We are mainly interested in the special case A = {1,…,n}, B = {x}. In this case, we have [5]To get a lower bound on the number of the density of occupied sites we show that if starting from x the process can infect a vertex with degree ≥λ^-(2+δ) then with high probability for a long time.

Having shown that the contact process survives for a long time, we can define a quasi-stationary distribution by the state of at t = exp(n^1/2). Let ρ_n(λ) be the expected value of the fraction of sites occupied in this measure. Berger et al. (35) show that for the contact process on their preferential attachment graphs, there are positive, finite constants so that In the language of statistical physics, they are bounding the critical exponent β that describes the power at which ρ_n(λ) goes to 0.

The powers c and C are not given explicitly in (35). In contrast, Chatterjee and Durrett (34) get reasonably good numerical bounds.

When α > 3 and δ is small, the power in the upper bound is > 2 so the critical value β never takes its mean-field value of 1. Based on the intuition that the infection will survive if, and only if, it reaches a vertex with degree λ^-2, the correct power in Theorem 5 should be 1 + 2(α - 2), i.e., the upper bound needs some improvement.

Chaos in an Epidemic Model

The inspiration for this model arose more than 20 years ago. I had just moved to Ithaca, New York, and the Northeast was in the midst of a gypsy moth infestation that was killing many oak trees. For all of one summer, my wife and I destroyed egg masses, picked larvae off of trees, and put bands of sticky tape to catch them when they came down at night. When the next summer came, the outlook for the trees seemed bleak, but suddenly all of the larvae were dead, victims of an epidemic of the nuclear polyhedrosis virus.

To create a model, suppose that G_n is a graph with n vertices. Thinking of upstate New York it would be most natural to consider G_n to be a 2D lattice, and to resist the urge to identify the borders of the state to make a torus. Durrett and Remenik (38) have proved results for the d-dimensional case, but to keep with the theme of this paper and to allow us to do explicit calculations, we will suppose G_n is a random 3-regular graph. We use discrete time, where t = years, because moths lay eggs that hatch the next year. Because the epidemic spreads quickly within a year, we formulate the process as an alternation of two mechanisms.

• An occupied site gives rise to a Poisson mean β number of offspring sent to locations chosen at random from the entire graph.

• Each site is infected with a small probability α_n. If the site is occupied then the infection spreads and wipes out the connected component of occupied sites containing that vertex.

A similar system was considered earlier by Richards and coworkers (39, 40). They were primarily interested in the evolutionary response of individuals to this situation.

A random 3-regular graph looks locally like a tree. On this tree the critical probability for percolation is 1/2. If the fraction of occupied sites is < 1/2 then all components are small, while if p > 1/2 there is a “giant component” that contains a positive fraction of the graph, and the size of this component can be computed explicitly. This reasoning suggests that in the limit as n → ∞ the fraction of occupied sites in generation n, p_n, will satisfy p_n+1 = h(p_n), where h(p) = g(f(p)) with f and g defined as follows:

Growth. If density of occupied sites is p before growth then density after is [7]Epidemic. Because the infection probability per site, α_n, is small, if n is large then it is likely that only members of the giant component will be killed. A branching process calculation shows that if the density before infection is q the density after is [8]

As β increases, the behavior of the process changes:

• If β ≤ 1 then the concave function f(p) < p for all p > 0, so hⁿ(p) → 0.

• If 1 < β ≤ 2 log 2 then starting from a small positive p, fⁿ(p) increases to a fixed point p^∗ ≤ 1/2.

• If β > 2 log 2 then the fixed point p^∗ > 1/2 and the system becomes chaotic, in a sense that we will make precise.

Note that the system goes from having an attracting fixed point to chaos, and it does not follow the period doubling route to chaos found in the family of logisitic maps: x → βx(1 - x). This behavior is called a border collision bifurcation [see, e.g., Nusse et al. (41)].

To prove that the system is chaotic we use a result of Li and Yorke (42), which says “period 3 implies chaos.”

Using this result, we can easily show that

The proof is simple. Let a₀ = f^-1(1/2) and c = f^-1(a₀). Clearly c < f(c) = a₀ < f²(c) = 1/2. We need only check f(1/2) < a₀.

A more satisfying notion of chaos is that the system has an absolutely continuous stationary distribution. Lasota and Yorke (43) have shown

Using this result with some computer calculations we can show that the condition holds for n = 3 if β∈(2 log 2,2.48]. We believe that there is a stationary distribution for all β > 2 log 2, but we do not think that this result is sufficient to prove the desired conclusion.

Random Boolean Networks

Random Boolean networks were originally developed by Kauffman (44) as an abstraction of genetic regulatory networks. In our version of his model, the state of each node x∈V_n ≡ {1,2,…,n} at time t = 0,1,2,… is η_t(x)∈{0,1}, and each node x receives input from r distinct nodes y₁(x),…,y_r(x), which are chosen randomly from V_n∖{x}.

We construct our random directed graph G_n on the vertex set V_n = {1,2,…,n} by putting oriented edges to each node from its input nodes. To be precise, we define the graph by creating a random mapping ϕ: V_n × {1,2,…,r} → V_n, where ϕ(x,i) = y_i(x), such that y_i(x) ≠ x for 1 ≤ i ≤ r and y_i(x) ≠ y_j(x) when i ≠ j, and taking the edge set E_n ≡ {(y_i(x),x): 1 ≤ i ≤ r,x∈V_n}. Thus our random graph G_n has uniform distribution over the collection of all directed graphs on the vertex set V_n in which each vertex has in-degree r. Once chosen the graph remains fixed through time. The rule for updating node x is [9]where the values f_x(v), x∈V_n, v∈{0,1}^r, chosen at the beginning and then fixed for all time, are independent and = 1 with probability p.

A number of simulation studies have investigated the behavior of this model. See Kadanoff et al. (45) for survey. Flyvberg and Kjaer (46) have studied the degenerate case of r = 1 in detail. Derrida and Pommeau (47) have argued that for r≥3 there is a phase transition in the behavior of these networks between rapid convergence to a fixed point and exponentially long persistence of changes, and they identified the phase transition curve to be given by the equation r·2p(1 - p) = 1. The networks with parameters below the curve have behavior that is “ordered,” and those with parameters above the curve have “chaotic” behavior. Since chaos is not healthy for a biological network, it should not be surprising that real biological networks avoid this phase. See Kauffman (48), Shmulevich et al. (49), and Nykter et al. (50).

To explain the intuition behind the conclusion of Derrida and Pomeau (47), we define another process {ζ_t(x): t≥1} for x∈V_n, which they called the annealed approximation. The idea is that ζ_t(x) = 1 if η_t(x) ≠ η_t-1(x), and ζ_t(x) = 0 otherwise. If the state of at least one of the inputs y₁(x),…,y_r(x) into node x has changed at time t, then the state of node x at time t + 1 will be computed by looking at a different value of f_x. If we ignore the fact that we may have used this entry before, we get the dynamics of the threshold contact process [10]and ζ_t+1(x) = 0 otherwise. Conditional on the state at time t, the decisions on the values of ζ_t+1(x), x∈V_n, are made independently.

We content ourselves to work with the threshold contact process, because it gives an approximate sense of the original model, and we can prove rigorous results about its behavior. To simplify notation and explore the full range of threshold contact processes we let q ≡ 2p(1 - p) and suppose 0 ≤ q ≤ 1.

As mentioned above, it is widely accepted that the condition for prolonged persistence of the threshold contact process is qr > 1. To explain this, we need to introduce the dual process, and for this it is convenient to rewrite our process as set-valued ξ_t = {x: ζ_t(x) = 1}. The dual coalescing branching process operates as follows: If x is occupied at time t, then with probability q it gives birth onto all of the sites y₁(x),…,y_r(x), and with probability 1 - q no birth from x occurs. All sites that receive at least one birth will be occupied at time t + 1. The two processes satisfy the following duality relationship: [11]

Again taking A = {1,2,…,n} and B = {x}, we see that the probability x is occupied at time t is equal to the probability that the dual process has not died out. At small times, the dual will behave like a branching process in which an individual has r children with probability q and no children with probability 1 - q. The mean number of children is qr. If qr > 1 the branching process is supercritical and the probability of no extinction is ρ = 1 - θ where the extinction probability θ is the root in [0,1) of [12]

This result and Theorem 11 are from Chatterjee and Durrett (51). The key to studying the survival of the dual is an “isoperimetric inequality”. Let be the graph obtained from our original graph G_n = (V_n,E_n) by reversing the orientation of the edges. Given a set U⊂V_n, let where x → y means . Note that U^∗ can contain vertices of U. The idea behind this definition is that if U is occupied at time t in the coalescing branching process, then the vertices in U^∗ may be occupied at time t + 1.

In words, the isoperimetric constant for small sets is r - 1. It is this result that forces us to assume q(r - 1) > 1 in Theorem 10. By using another strategy for guaranteeing persistence based on the locally tree-like nature of the graph, we are able to show:

We believe the correct result is that the process persists for time O(e^cn) when qr > 1, but this seems to be a difficult problem.

Voter Models

Diseases are not the only things that spread through networks. Opinions, gossip, and information do as well. A simple model for the dynamic evolution of two opinions 0 and 1 (think of Democrats and Republicans) was introduced 35 years ago by Clifford and Sudbury (52) and Holley and Liggett (53) on the d-dimensional integer lattice Z^d. Each site at times of a rate one Poisson process decides to change its mind, and when it does, it adopts the opinion of a randomly chosen neighbor. One can also formulate a slightly different process in terms of the edges of the graph. Each edge becomes active at rate one. When it is active, one endpoint is chosen at random, and the voter there adopts the opinion at the other end. On a graph in which all vertices have the same degree, the two recipes give the same result (run on slightly different time scales), but in general they are different, and, as we will see, the edge voter model is considerably simpler than the vertex voter model.

The key to the study of the voter model is again duality. Let ζ_t(x) be the opinion of x at time t. Either of the two voter models can be constructed by having a Poisson process for each oriented edge (x,y), so that when a Poisson arrival occurs we draw an arrow from x to y and the voter at x imitates the one at y. In the vertex voter model, the rate for the (x,y) Poisson process is λ(x,y) = 1/d(x), where d(x) is the degree of x. In the edge voter model, it is λ(x,y) = 1/2. Given a starting point x and time t, we can define a dual process that starts at x and time t and works backwards in time, jumping when it encounters the tail of an arrow. It follows from the definition that

To convert this into the duality equation we have seen twice before, let be the set of sites with opinion 1 at time t when initially . Let be the coalescing random walk system in which (i) a particle at x jumps to y at rate q(x,y), (ii) two particles on the same site coalesce to 1, and (iii) . With these definitions we again have: [13]Thus to study the voter model it suffices to investigate the coalescing random walk.

To set the stage for the discussion of the voter model on random graphs, we will begin by considering the voter model on d-dimensional integer lattice with edges connecting each point to it 2d nearest neighbors. Holley and Liggett (53) have shown

This result follows from the behavior of simple random walk on Z^d. In d ≤ 2 two random walks will eventually hit, while in d≥3 there is positive probability that they never do. Letting |S| denote the number of points in a set S, and , which exists by monotonicity, duality tells us that

The voter model on the torus Λ = (Z mod L)^d will eventually reach consensus. Let N = L^d and . Cox (54) has proved the following

In the language of Markov chains ν_p is a quasi-stationary distribution for the voter model on the torus.

Turning to random graphs, we begin with BC small world, . All vertices have degree 3, so the two voter models have the same properties, and we study the site version. The first step in doing that is to consider what happens in the coalescing random walk when B = {x,y}. Let X_t and Y_t be independent random walks starting from x and y that jump at rate 1 and go to each of the three neighbors with probability 1/3. Let P_π×π denote the law of the process (X_t,Y_t) when X₀ and Y₀ are chosen independently at random from the graph according to the stationary distribution π(x) = 1/n. Let , and let P_A = P_π×π(·|X₀ = Y₀). Let T_A = min{t: X_t = Y_t} be the hitting time of A, and let be the return time, i.e., the first time X_t = Y_t after the first jump occurs. Applying a theorem of Kac [see (3.3) in Chapter 6 of Durrett (55)] to the embedded discrete time chain and recalling that jumps in (X_t,Y_t) occur at rate 2, [14]From this we see that the for the BC small world, or any random graph with n vertices all of which have the same degree, .

To get from this to the quantity that we really want, let T_mix be the mixing time for the random walk: where p_t(x,y) is the transition probability of the random walk and the total variation distance is . I claim that [15]This is the Poisson clumping heuristic of Aldous (56): The naive waiting time between returns is 1/(2π × π(A)), but this must be corrected for by multiplying by the clump size, i.e., the expected number returns that happen soon after the first one.

Locally the BC small world looks like a tree in which all vertices have degree 3, so The mixing time for the random walk on the BC small world is O(log n) [see Theorem 6.3.4 in Durrett (11)]. Since T_mix = o(n), Proposition 23 of Aldous and Fill (57) implies that Intuitively, if the random walks have not hit by time ns and K_n → ∞ slowly then at time ns + K_nT_mix the two walkers are distributed according to π, and so which is the lack of memory property that characterizes the exponential. For more on this see the proof of Theorem 6.8.1 in Durrett (11).

By working harder with this argument one can show:

Let q_i,j(t) be the transition probability of Kingman’s coalescent. Since we can start Kingman’s process at infinity. In Cox’s work, T_N/s_N⇒τ where In words, if the dual coalescing random walk starting from all sites on the torus occupied has been reduced to k particles, then for consensus to hold all k walkers must sit on sites with the same value. This result is presumably true on the BC small world, but to finish the proof one must investigate the big bang that occurs in the coalescent starting with all sites occupied at time 0 [see Section 4 in Cox (54)].

Formula 14 in Sood and Redner (58) asserts that for the vertex random walk on a Newman Strogatz Watts (NSW) random graph with a power-law degree distribution p_k ∼ Ck^-α These graphs are rather ugly when α < 2. There are vertices of degree n^1/(α-1)≫n, so there are numerous self-loops and parallel edges. van der Hofstad et al. (59) have shown that the distance between two randomly chosen vertices is 2 with probability p and 3 with probability 1 - p. For this reason we will not consider the ultrasmall worlds with α < 2 or the borderline case α = 2.

To begin to prove Sood and Redner’s claims for α > 2, we note that the reasoning in refs. 14 and 15 applies in general. To determine the asymptotics of π × π(A) we note

• If α > 2 then

• If α > 3 then Ed(x)² < ∞ so .

• If α = 3 then using (5.5) in Chapter 1 of Durrett (53) with b_n = n log n shows that

• When 2 < α < 3, Ed(x) < ∞ but P(d(x)² > k) ∼ ck^-(α-1)/2, so d(x) is in the domain of attraction of a stable law of index (α - 1)/2, and where Y is a positive stable law with index (α - 1)/2.

We will always suppose that the degree distribution has p₀ = 0. If p₁ = p₂ = 0 then the mixing time t_n = O(log n). [Combine Theorems 6.3.2, 6.2.1, and 6.1.2 in Durrett (11).] If p₂ > 0 then there are chains of vertices of degree 2 of length O(log n), and the mixing time t_n = O(log²n). See Section 6.7 in Durrett (11). If, in addition, p₁ > 0 nothing bad happens, but we have to assume that so that a giant component exists and then restrict our attention to the voter model on it.

Suchecki et al. (60) claim, based on simulations, that on the Barabási–Albert preferential attachment graph, the vertex voter model reaches consensus in time n^0.88, while the edge voter model takes time asymptotically cn. However, as Sood and Redner (58) observe, the first quantity may just be the n/ log n given above. The result for the edge voter model is easy. π × π(A) = 1/n so as long as the mixing time is o(n), T_A/n will converge to an exponential.

Lieberman et al. (61) and Sood and coworkers (62,63) have considered biased version of the edge voter model in which 0s always switch to 1s but 1s only switch to 0s with probability 1 - s. In genetic terms, 1s have a selective advantage over the 0s. Remarkably the fixation probability for a single 1 in a sea of 0s is independent of the structure of the graph, a result discovered much earlier by Maruyama (64). [See also Slatkin (65).] The proof is trivial. The embedded discrete-time chain is a biased random walk.