Edited* by Simon A. Levin, Princeton University, Princeton, NJ, and accepted by the Editorial Board January 4, 2010 (received for review December 14, 2009)
Random graphs are useful models of social and technological networks. To date, most of the research in this area has concerned geometric properties of the graphs. Here we focus on processes taking place on the network. In particular we are interested in how their behavior on networks differs from that in homogeneously mixing populations or on regular lattices of the type commonly used in ecological models.
The subject of random graphs dates to the late 1950s when Erdös and Renyi sat in Hungarian cafes and tried to imagine what a random pick from the collection of graphs with n vertices and m edges looks like. To answer this question it is easier to instead flip a coin with probability p = 2m/n(n - 1) of heads for each edge to determine if it is present. In this case there is interesting behavior when p = c/n: When c < 1 most connected components are small, with the largest of size O(log n) (in words, “of order log n”); when c > 1 there is a giant component of size asymptotically ρn. This phase transition inspired a lot of work in the subject, as did concepts from graph theory such as Hamiltonian circuits, matchings, chromatic number, Ramsey theory, etc. See Bollobás (1) or Janson et al. (2) for more on this.
The beginning of the twenty-first century saw a number of new motivations for the study of random graphs. The Kevin Bacon game taught us that the screen actors collaboration network was a “small world,” and made the phrase “six degrees of separation” famous. Statistical studies of the Internet (3), academic collaborations (4, 5, 6), and sex in Sweden (7) showed that the degree d of a randomly chosen vertex often followed a power law P(d = k) ∼ Ck-α rather than the Poisson distribution that occurs in the Erdös–Renyi model with p = c/n. For popular accounts see the books by Barabási (8) and Watts (9).
In the next section we will describe some of the random graphs at the center of this development. Their geometric properties, e.g., “Do they have a giant component?” and “What is the average distance between two points?,” are by now well-understood. See the books by Chung and Lu (10) and Durrett (11). Our focus will be on the behavior of processes (e.g., the spread of epidemics and opinions) on these networks.
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 pk ∼ 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 {pk: k≥0} we construct a random graph Gn with vertex set {1,2,…,n} as follows: let d1,…,dn be independent and have the distribution P(di = k) = pk. We condition on the event En = {d1 + ⋯+dn is even} to have a valid degree sequence. If P(di is odd)∈(0,1) then P(En) → 1/2 as n → ∞, so the conditioning will have a little effect on the distribution of di’s. Having chosen the degree sequence (d1,d2,…,dn), we allocate di 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 Gn being a proper graph.
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.
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 2n 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 z01z11…1zk where zi∈Z - {0} for 0 < i < k. In words, this is the point you reach by moving by z0 in the first copy of Z, going down a long-range edge, moving sideways by z1, 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 λ1 the weak survival critical value and λ2 the strong survival critical value. Pemantle (25) showed that for homogeneous trees where every vertex has at least four neighbors, λ1 < λ2. 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.
For each ratio r = α/β∈(0,1) there is an M such that for all m≥M, λ1 < λ2 for the contact process on 
.
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 λ1 and lower bounds on λ2.
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 Bt 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 λ > λ1, but only for λ > λ2 are we certain that 0 will become infected when the process does not die out.
Let 
and 
.
Writing ⇒ for convergence in distribution as n → ∞ we have
τS is stochastically bounded above by τB and τS⇒τB.
σS is stochastically bounded above by σB and σS⇒σB.
Combined with our table, this result shows that when λ1 < λ < λ2 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 λ > λ1 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(cnd).
On any graph with n nodes and ≤ Cn edges, the infection cannot persist for longer than O(ecn) 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.
Consider the modified contact process on the small world described above. If λ > λ1, the lower critical for the contact process on 
and we start with all individuals infected, then there is a constant c > 0 so that the probability the infection persists to time exp(cn) tends to 1 as n → ∞.
Pastor-Satorras and Vespignani (30, 31, 32) have made an extensive study of the contact process on graphs with power-law degree distributions, P(di = 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.
Consider a Newman, Strogatz and Watts random graphs Gn on the vertex set {1,2,…,n}, where the degrees di satisfy P(di = k) ∼ Ck-α as k → ∞ for some constant C and some α > 3, and P(di ≤ 2) = 0. Let 
denote the infected sites in the contact process on the random graph Gn starting from all sites infected. Then for any value of the infection rate λ > 0, there is a positive constant p(λ) so that for any δ > 0 
[3]
The assumption P(di ≤ 2) = 0 is not really necessary but is convenient, because it implies that P(Gn 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 qk = kpk/μ with 
.
The second equation is a self-consistency equation. The “size-biased distribution” qk 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 λk2≥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λ2/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ϵλ2/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(n1/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.
Suppose α > 3. There is a λ0 > 0 so that if 0 < λ < λ0 and 0 < δ < 1, then there exists two constants c(α,δ) and C(α,δ) so that as n → ∞ 
[6]
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.
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 Gn is a graph with n vertices. Thinking of upstate New York it would be most natural to consider Gn 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 Gn 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, pn, will satisfy pn+1 = h(pn), 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]
Suppose αn → 0 and αn log n → ∞. If we start in product measure with density p, densities in process at times n≥0 on graph converge in probability to hn(p).
As β increases, the behavior of the process changes:
If β ≤ 1 then the concave function f(p) < p for all p > 0, so hn(p) → 0.
If 1 < β ≤ 2 log 2 then starting from a small positive p, fn(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.”
If there is a point with h3(c) ≤ c < h(c) < h2(c) then
For every k there is a point with period k.
There is an uncountable S so that if p,q∈S and r is periodic 
Using this result, we can easily show that
If β > 2 log 2 then the map is chaotic.
The proof is simple. Let a0 = f-1(1/2) and c = f-1(a0). Clearly c < f(c) = a0 < f2(c) = 1/2. We need only check f(1/2) < a0.
A more satisfying notion of chaos is that the system has an absolutely continuous stationary distribution. Lasota and Yorke (43) have shown
There is an absolutely continuous invariant measure if 
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 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∈Vn ≡ {1,2,…,n} at time t = 0,1,2,… is ηt(x)∈{0,1}, and each node x receives input from r distinct nodes y1(x),…,yr(x), which are chosen randomly from Vn∖{x}.
We construct our random directed graph Gn on the vertex set Vn = {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 ϕ: Vn × {1,2,…,r} → Vn, where ϕ(x,i) = yi(x), such that yi(x) ≠ x for 1 ≤ i ≤ r and yi(x) ≠ yj(x) when i ≠ j, and taking the edge set En ≡ {(yi(x),x): 1 ≤ i ≤ r,x∈Vn}. Thus our random graph Gn has uniform distribution over the collection of all directed graphs on the vertex set Vn 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 fx(v), x∈Vn, 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∈Vn, 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 y1(x),…,yr(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 fx. 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∈Vn, 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 y1(x),…,yr(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]
Let 
be the threshold contact process with 
. Suppose q(r - 1) > 1 and let δ > 0. Then there is a positive constant C(δ) so that as n → ∞
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 Gn = (Vn,En) by reversing the orientation of the edges. Given a set U⊂Vn, 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.
Let E(m,k) be the event that there is a subset U⊂Vn with size |U| = m so that |U∗| ≤ k. Given η > 0, there is an ϵ0(η) > 0 so that for m ≤ ϵ0n 
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:
Suppose qr > 1. If δ0 is small enough, then for any 0 < δ < δ0, there are constants C(δ) > 0 and B(δ) = (1/8 - 2δ) log(qr - δ)/ log r so that as n → ∞ 
We believe the correct result is that the process persists for time O(ecn) when qr > 1, but this seems to be a difficult problem.
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 Zd. 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
In d ≤ 2 P(ζt(x) ≠ ζt(y)) → 0 while in d≥3 there is a one-parameter family of stationary distributions νp, which can be obtained by taking the limit as t → ∞ starting from product measure, i.e., {ζ0(x) = 1} are independent and have probability p.
This result follows from the behavior of simple random walk on Zd. 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 = Ld and 
. Cox (54) has proved the following
If we let 
then TN/sN converges in distribution to a limit.
If we pick two sites x,y∈Λ at random then in d≥2 their coalescence time 
has 
where κ = 2/π in d = 2 and 
in d≥3 where pn(x,y) is the transition probability of simple random walk.
In d≥3 if we start from product measure and observe the process at time tN with 1 ≪ tN ≪ N then the system looks like the stationary distribution νp.
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 Xt and Yt 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 (Xt,Yt) when X0 and Y0 are chosen independently at random from the graph according to the stationary distribution π(x) = 1/n. Let 
, and let PA = Pπ×π(·|X0 = Y0). Let TA = min{t: Xt = Yt} be the hitting time of A, and let 
be the return time, i.e., the first time Xt = Yt 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 (Xt,Yt) 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 Tmix be the mixing time for the random walk: 
where pt(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 Tmix = o(n), Proposition 23 of Aldous and Fill (57) implies that 
Intuitively, if the random walks have not hit by time ns and Kn → ∞ slowly then at time ns + KnTmix 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:
Pick m sites at random and start coalescing random walks at these locations. The number of particles at time nt converges to Kingman’s coalescent, which makes transitions from k to k - 1 at rate k(k - 1)/2.
Let qi,j(t) be the transition probability of Kingman’s coalescent. Since 
we can start Kingman’s process at infinity. In Cox’s work, TN/sN⇒τ 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 pk ∼ Ck-α 
These graphs are rather ugly when α < 2. There are vertices of degree n1/(α-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)2 < ∞ so 
.
If α = 3 then using (5.5) in Chapter 1 of Durrett (53) with bn = n log n shows that 
When 2 < α < 3, Ed(x) < ∞ but P(d(x)2 > 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 p0 = 0. If p1 = p2 = 0 then the mixing time tn = O(log n). [Combine Theorems 6.3.2, 6.2.1, and 6.1.2 in Durrett (11).] If p2 > 0 then there are chains of vertices of degree 2 of length O(log n), and the mixing time tn = O(log2n). See Section 6.7 in Durrett (11). If, in addition, p1 > 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 n0.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), TA/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.
Here we have presented a small sample of work concerning processes on random graphs, which is biased because it concentrates on topics to which I have contributed. A more extensive survey can be found in Barrat et al. (66). Most of the work cited there has been done by physicists and is not rigorous, but there is more for mathematicians to contribute than just dotting the i’s and crossing the t’s. In addition to occasionally correcting an error, rigorous analysis adds to our understanding of underlying mechanisms and in some cases identifies phenomena not found by simulation.
My philosophy about these models is that, like the Ising model of statistical physics, they are too simplified to make quantitative predictions reliable but are designed to give insights into how features of complex networks affect the qualitative behavior of processes that take place on them. Rigorous results, like simulations, must be interpreted carefully. Chatterjee and Durrett (34) proved that λc = 0 for graphs with power-law degree distributions. If λ = 0.01 then one needs a vertex of degree 1/λ2 = 104 to ensure prolonged persistence, but if pk ∼ 3p-4 then this requires n = 1012 vertices.
In all of the problems considered here, the network remains constant while the states of the vertices change. However, in reality, the connections between individuals change over time, and I think this is an important direction for research. Networks is one of two programs at the Statistical and Applied Mathematical Sciences Institute in 2010–2011. Evolving networks will be one of the several themes considered there.
Author contributions: R.T.D. wrote the paper.
This article is part of the special series of Inaugural Articles by members of the National Academy of Sciences elected in 2007.
The author declares no conflict of interest.
*This Direct Submission article had a prearranged editor.
Freely available online through the PNAS open access option.
