Main

Ecological and evolutionary dynamics depend on population structure13,14,15. Evolutionary graph theory1,3,7 provides a mathematical tool for representing population structure: vertices correspond to individuals and edges indicate interactions. Graphs can describe spatially structured populations of bacteria, plants, animals16, tissue architecture in multi-cellular organisms17, or social networks18,19. Graph topology affects the rate of genetic change20 and the balance of drift versus selection1. The classical setting of a well-mixed population is the complete graph.

Of particular note is the evolution of social behaviour, which can be studied using evolutionary game theory21,22,23. Evolutionary game dynamics, which are tied to ecological dynamics22, arise whenever reproductive success is affected by interactions with others.

In evolutionary games on graphs3,4,5,6,7,8,24,25, individuals interact with neighbours according to a game and reproduce on the basis of payoff (Fig. 1). A central question is to determine which strategies succeed on a given graph. In general, there cannot be a closed-form solution or polynomial-time algorithm for this question, unless it is unexpectedly found that P = NP (polynomial time = nondeterministic polynomial time)9. To make progress, one can consider weak selection, meaning that the game has only a small effect on reproductive success. Weak selection results are known for regular graphs, where each individual has the same number of neighbours3,4,5,6,7,8. Evolutionary games on heterogenous (non-regular) graphs have only been investigated using computer simulations3,24,25, approximations3,26 and special cases25,27,28.

Figure 1: Evolutionary games on weighted heterogeneous graphs.
figure 1

a, Population structure is represented by a graph with edge weights wij, which are shown next to the edges for this example. b, Each individual i plays a game (equation (3) in the Methods) with each neighbour, and retains the edge-weighted average payoff fi. The reproductive rate of i is Fi = 1 + δfi, where δ represents the strength of selection. c, For death–birth updating, a random individual i is selected to be replaced (indicated by a ‘?’); then a neighbour j is chosen with a probability proportional to wijFj to reproduce into the vacancy. d, The coalescence time10,11,12,13 τij is the expected meeting time of random walks from i and j, representing time to a common ancestor (yellow circle).

PowerPoint slide

Full size image

We consider games on any weighted graph (Fig. 1a), with edge weights wij. Individuals are of two types, A and B. The game is specified by a payoff matrix (see Methods). Each individual i plays the game with each neighbour, receiving an edge-weighted average payoff of fi (Fig. 1b). The reproductive rate of i is Fi = 1 + δfi, where δ > 0 is the strength of selection. Weak selection means ; neutral drift, δ = 0, is a baseline.

At each time step, an individual is chosen uniformly at random to be replaced. Its neighbours compete for the vacancy proportionally to their reproductive rates (Fig. 1c). Offspring inherit the type of their parent. This update rule, called death–birth3, also translates into social settings: a random individual resolves to update its strategy, and adopts one of its neighbours’ strategies proportionally to their payoff.

Over time, the population will reach the state of all A or all B. Suppose we introduce a single A at a vertex chosen uniformly at random in a population of B individuals. The fixation probability, ρA, is the probability of reaching all A from this initial condition. Likewise, ρB is the probability of reaching all B when starting with a single B individual in a population otherwise of A. Selection favours A over B if ρA > ρB.

The outcome of selection depends on the spatial assortment of types, which can be studied using coalescent theory10,11. Ancestral lineages are represented as random walks12. A step from i to j occurs with probability pij = wij/wi, where wi = ∑kwik is the weighted degree of vertex i. The coalescence time τij is the expected meeting time of independent random walks started at vertices i and j (Fig. 1d), which can be obtained by solving a system of linear equations (see Methods). We show in the Supplementary Information that, if T is the time to absorption (fixation or extinction), then T − τij is the expected time during which i and j have the same type. Of particular note is the expected coalescence time, tn, from the two ends of an n-step random walk, with the initial vertex chosen proportionally to weighted degree.

Our main result holds for any payoff matrix, but we first study a donation game. Cooperators pay a cost, c, and provide a benefit, b. Defectors (that is, those who do not cooperate) pay no cost and provide no benefit. For b > c > 0, this game is a Prisoners’ Dilemma. We find that cooperation is favoured over defection for weak selection if and only if:

Intuitively, the above condition states that a cooperator must have a higher payoff than a random individual two steps away. These two-step neighbours compete with the cooperator for opportunities to reproduce3,5 (Fig. 1b). The first term, −c(T − t0), is the cost for being a cooperator, which is paid for the entire time, T, because t0 = 0. The second term, b(T − t1), is the average benefit that the cooperator gets from its one-step neighbours, because for expected time T − t1, a one-step neighbour is also a cooperator. The remaining terms, −c(T − t2) + b(T − t3), describe the average payoff of an individual two steps away. That individual pays cost c whenever it is a cooperator (time T − t2) and receives benefit b whenever its one-step neighbours, which are three-step neighbours of the first cooperator, are cooperators (time T − t3).

T cancels itself out in equation (1), leaving −ct2 + b(t3 − t1) > 0. Therefore, cooperation is favoured under weak selection, if t3 > t1 and the benefit-to-cost ratio exceeds the threshold

The critical threshold (b/c)* is obtained for any graph by solving for coalescence times and substituting into equation (2). Although equation (2) is derived in the weak selection limit, Monte Carlo simulations suggest it is accurate for fitness costs up to 2.5% (Extended Data Fig. 1a). Therefore, the result can be used for situations of non-vanishing selection intensity, but one must ensure that selective differences are sufficiently small.

Positive (b/c)* means that cooperation is favoured when it is sufficiently effective. Positive values of (b/c)* always exceed—but can be arbitrarily close to—one, at which point any cooperation that yields a net benefit is favoured (Fig. 2a–c). Negative values arise for t3 < t1; in this case cooperation is not favoured, but spiteful behaviours, b < 0, c > 0, are favoured for b/c < (b/c)*. If t3 = t1, then (b/c)* is infinite, and neither cooperation nor spite are favoured.

Figure 2: Graphs that promote or hinder cooperation.
figure 2

a–c, If each individual has one partner with weight w and all other edges of weight 1, any cooperative behaviour is favoured for sufficiently large w. Examples include a disordered network (a); a weighted regular graph (b), for which (b/c)* = (w + k)2/(w2 + k) for ; and a weighted complete graph (c), for which (b/c)* = (w − 2 + N)2/((w − 2)2 − N); here cooperation is possible only when (dashed vertical lines). d, An island-structured population, with edge weights 1 within islands and m < 1 between islands. e, f, The weighted star (e) and the unweighted complete bipartite graph (f) do not support cooperation, because t3 = t1.

PowerPoint slide

Full size image

Which networks best facilitate evolution of cooperation? We find that cooperation thrives on networks with strong pairwise ties (Fig. 2a–c). To quantify this property, let denote the probability that a random walk from vertex i returns to i on its second step. In other words, pi is the probability that, if i choses a neighbour for interaction, that choice is reciprocated. Cooperation succeeds if the pi are large. For large graphs that satisfy a locality property (see Methods), , where is a weighted average of the pi. If each individual has k neighbours of equal weight, then pi = 1/k for each i, yielding the condition3 b/c > k.

As an application, consider a population divided into islands of arbitrary sizes (Fig. 2d). Edges within an island have weight 1. Edges between islands have weight m < 1. We derive a closed-form expression for (b/c)* for the case of two islands. Cooperation appears to be most favoured for evenly-sized islands and a small m (see Methods and Supplementary Information).

Some population structures are not conducive to cooperation. For example, on a weighted star (Fig. 2e), one-step and three-step neighbours are equivalent; therefore t3 = t1 and cooperation is impossible. A similar argument applies to the complete bipartite graph (Fig. 2f).

In some cases, small changes in graph topology can markedly alter the fate of cooperation (Fig. 3). Stars do not support cooperation, but joining two stars via their hubs allows cooperation for b/c > 5/2. If we modify a star by linking pairs of leaves to obtain a ‘ceiling fan’, cooperation is favoured for b/c > 8. Therefore, targeted interventions in network structure (graph surgery) can facilitate transitions to more cooperative societies. It is also of interest that a ‘dense cluster’ of stars connected by their hubs (Fig. 3f) has a benefit–cost threshold of 3/2, which is less than its average degree of 2.

Figure 3: Rescuing cooperation by graph surgery.
figure 3

a, The star does not support cooperation; the critical benefit–cost threshold is infinite. b, Joining two stars via their hubs gives (b/c)* = 5/2. c, Joining them via two leaves gives (b/c)* = 3. d, A ceiling fan has (b/c)* = 8. e, A wheel has (b/c)* = (429 + 90)/82. f, Joining m stars via their hubs in a complete graph gives (b/c)* = (3m − 1)/(2m − 2), which is approximately 3/2 for large m. The (b/c)* values reported here are for infinite population size; see Supplementary Information for finite size.

PowerPoint slide

Full size image

To explore the evolutionary consequences of graph topology on a large scale, we calculated (b/c)* for various ensembles: (i) 1.3 million graphs of sizes 100–150, generated by ten random graph models (Fig. 4); (ii) 40,000 graphs of sizes 300–1,000 generated by four random graph models (Extended Data Fig. 1b); (iii) every simple graph of size up to seven (Extended Data Figs 2, 3, 4); and (iv) seven empirical human and animal social networks (Extended Data Fig. 5). In general, as the average degree, , increases, cooperation becomes increasingly difficult and eventually impossible. However, there is considerable variance in (b/c)* for each value of . The propensity of a graph to support cooperation is neither determined by its average degree, nor by its entire degree sequence (Extended Data Fig. 4).

Figure 4: Conditions for cooperation on 1.3 million random graphs.
figure 4

a, Scatter plot of critical threshold (b/c)* versus mean degree . 71% of graphs have positive (b/c)* and have the possibility of cooperation; negative (b/c)* indicates that spite (b < 0, c > 0) can be favoured. b, Scatter plot of (b/c)* versus , the expected degree of a random neighbour of a randomly chosen vertex, which is a proposed approximation for (b/c)* on heterogeneous graphs26. Although this approximation is reasonable for many graphs, there is substantial variation in (b/c)* for each value of . The success of cooperation depends on features of graph topology beyond the summary statistics and . See Methods for graph models and parameters.

PowerPoint slide

Full size image

So far we have discussed the donation game, but our theory extends to any pairwise interaction; see equation (3) in the Methods. The condition for strategy A to be favoured over B, under weak selection, can be written27 as σa + b > c + σd. Our result implies that σ = (−t1 + t2 + t3)/(t1 + t2 − t3), from which one can evaluate the success of any strategy on any graph, under weak selection. The structure coefficient σ quantifies the extent to which a graph supports cooperation in a social dilemma, or the Pareto-efficient equilibrium in a coordination game2,27 (Extended Data Fig. 1c, d).

Our model can be extended in various ways. Birth–death updating3 can be studied. Total instead of average payoff can be used25. Different graphs can specify interaction and replacement4,7,29. Mutations can be introduced7,30. For each of these variations, we obtain the conditions for success in terms of coalescence times (see Methods).

In summary, we have obtained a condition for how natural selection chooses between two competing strategies on any graph for weak selection. Our framework applies to strategic interactions among humans, as well as ecological interactions among other organisms, in any population of fixed structure (Extended Data Fig. 5). Our result helps to elucidate which population structures promote certain behaviours, such as cooperation. We find that cooperation flourishes most in the presence of strong pairwise ties, which is an intriguing argument for the importance of stable partnerships in forming the backbone of cooperative societies.

Methods

Here we summarize our model and mathematical methods; see Supplementary Information for complete derivations. No experiments were performed for this study, and no empirical data were collected.

Model

Population structure is represented by a weighted, connected graph of size N. Consistent with standard mathematical terminology, a ‘graph’ is understood to be undirected. The edge weight between vertices i and j is denoted wij = wji. Self-loops (wii > 0) are allowed, representing self-interaction and replacement by one’s own offspring. The weighted degree of vertex i is .

Individuals are one of two types, corresponding to strategies in a game. The payoff matrix of a 2 × 2 game can be written as

For the donation game, the payoff matrix is

The state of the process is given by the vector (s1.…, sN), where si ∈ {0,1} indicates the type occupying each vertex: 1 for A and 0 for B in the game of equation (3); 1 for C and 0 for D in the donation game of equation (4). In each state, each individual i retains the edge-weighted average, fi, of the payoff received from each neighbour. For the donation game of equation (4), we have . The reproductive rate of i is Fi = 1 + δfi, where is the intensity of selection.

For death–birth updating, after the game interaction, an individual is selected, uniformly at random, to be replaced. A neighbour is then chosen, with probability proportional to reproductive rate times edge weight, to reproduce into the vacancy. Thus, if i is chosen to be replaced, the probability that j reproduces is . Offspring inherit the type of the parent, resulting in a new state.

Coalescence times

The coalescence times12,31 τij are the solution to the system of linear equations

Equation (5) can be solved for any graph, in polynomial time, using standard methods. From the coalescence times, pairwise statistics of assortment can be obtained using the formula

Above, the brackets indicate an expectation over states arising under neutral drift, δ = 0.

The n-step coalescence time is defined as , where is the probability that an n-step random walk starting at i terminates at j and is the relative weighted degree of vertex i.

Derivation of equation (1)

Applying recent results on perturbations of voter models6, we express the fixation probability of cooperation in the donation game of equation (4) as

Above, is the expected type at the end of an n-step random walk from i. Combining equations (6) and (7), we obtain

Equations (1) and (2) of the main text follow immediately.

Derivation of

From equation (5) we obtain the recurrence relation

Above, is the re-meeting time of two independent random walks from vertex i. For graphs with no self-loops ( for each i), equation (9) gives t2 = ∑iπiτi − 2 and t3 − t1 = ∑iπipiτi − 2, where pi is shorthand for . Equation (2) then becomes

For a regular graphs of degree k, we find that pi = 1/k for each vertex i and ∑iπiτi = N, yielding the condition4,6,7 b/c > (N − 2)/(N/k − 2).

We say that a large graph has the ‘locality property’ if for each vertex i. This condition asserts that the (global) probability πi of choosing i from among all vertices, proportionally to weighted degree, is eclipsed by the (local) probability pi of reaching i by a random step from a random neighbour. We prove in the Supplementary Information that for graphs with this property, the 2’s in the numerator and denominator of equation (10) are negligible. This leads to , where is the weighted average of the pi with weights πiτi.

Islands

In the island model, edge weights are wij = 1 if i and j are on the same island and wij = m < 1 otherwise. For two islands with we obtain

Above, N is the total population size and D is the difference in island sizes. The critical b/c ratio is minimized when D = 0; that is, when the islands have equal size. The result for arbitrary m is given in the Supplementary Information, and results for up to five islands are discussed there as well. These results suggest that, for any fixed number n of islands, cooperation is most favoured when the islands have equal size, in which case (b/c)* = (N − 2)(N − n)/(Nn − 2N + 2n).

Arbitrary games

We extend to the general 2 × 2 matrix game of equation (3) using the Structure Coefficient Theorem27. This theorem states that the condition for A to be favoured over B (in the sense that ρA > ρB under weak selection) takes the form σa + b > c + σd. The structure coefficient σ can be calculated as σ = ((b/c)* + 1)/((b/c)* − 1), leading to σ = (−t1 + t2 + t3)/(t1 + t2 − t3) as stated in the main text. We prove in the Supplementary Information that the numerator and denominator of σ are always positive.

Accumulated payoffs

Accumulated payoff means that the reproductive rate is based on the edge-weighted total payoff received from neighbours (instead of the edge-weighted average). For the donation game of equation (4), the accumulated payoff to vertex i is . A similar derivation leads to

Different interaction and replacement graphs

We can also suppose that individuals interact according to one graph I and reproduce according to another graph G. Equation (2) then generalizes to

Above, tn,m is the expected coalescence time between two ends of a random walk, where the initial vertex is chosen with probability πi, then n steps are taken in the replacement graph, and finally m steps are taken in the interaction graph. The relative weighted degree πi and the coalescence times are computed according to the replacement graph.

Birth–death updating

For birth–death updating3, first an individual i is chosen to reproduce proportionally to its reproductive rate Fi. The offspring replaces a neighbour j chosen proportionally to wij. Birth–death requires a modified coalescent process, in which steps from i to j occur at rate wij/wj. We denote the modified coalescence times by ; these are again the unique solution to a system of linear equations (see Supplementary Information). The critical benefit-cost ratio for birth–death is

Mutation

We introduce mutations with arbitrary probability u per reproduction. Mutations are equally likely to result in either type (including that of the parent). Spatial assortment is analysed using identity-by-descent4,7,30,32,33. Two individuals are identical-by-descent (IBD) if no mutation separates either from their common ancestor. The stationary probability that individuals i and j are IBD is denoted qij. The IBD probabilities qij satisfy the linear recurrence relations7,30:

From equation (14), all IBD probabilities can be computed for any mutation rate on any graph in polynomial time. Let denote the expected IBD probability for the two ends of an n-step random walk, with initial vertex i chosen with probability πi. We show in the Supplementary Information that cooperation is favoured, in the sense of having stationary frequency >50%, when b/c exceeds the critical ratio of

Random graph investigations

For Fig. 4 we computed (b/c)* for 1.3 million unweighted graphs, generated from 10 different random graph models. Parameter values were sampled from a uniform distribution on the specified ranges (see below). Initial graph sizes were uniformly sampled in the range 100 ≤ N ≤ 150; if the random graph model produced a disconnected graph, the largest connected component was used. The critical (b/c)* ratio was computed by solving equation (5) for coalescence times and substituting into equation (10). (No Monte Carlo simulations were used for these investigations.)

Random graph models and parameter ranges (see Fig. 4 and Extended Data Fig. 1) are as follows: 100,000 Erdös–Rényi (ER)34 with edge probability 0 < p < 1; 100,000 small world (SW)35 with initial connection distance 1 ≤ d ≤ 5 and edge creation probability 0 < p < 0.05; 100,000 Barabási–Albert (BA)36 with linking number 1 ≤ m ≤ 10; 100,000 random recursive (RR)37 (like Barabási–Albert except that edges are added uniformly instead of preferentially) with linking number 2 ≤ m ≤ 8; 200,000 Holme–Kim (HK)38 with linking number 2 ≤ m ≤ 4 and triad formation parameter 0 < p < 0.15; 200,000 Klemm–Eguiluz (KE)39 with linking number 3 ≤ m ≤ 5 and deactivation parameter 0 < μ < 0.15; 200,000 shifted-linear preferential attachment40 with linking number 1 ≤ m ≤ 7 and shift 0 < θ < 40; 100,000 forest fire (FF)41 with parameters 0 < pf < pb < 0.15; 100,000 Island Barabási–Albert; and 100,000 Island Erdös–Rényi. Island Barabási–Albert is a meta-network of islands42, in which each island is a shifted-linear preferential attachment network with the same parameters as above. The number of islands varies from 2 to 5. Considering the islands as meta-nodes, the meta-network among the islands is an Erdös–Rényi graph with edge probability 0 < pinter < 1. Island Erdös–Rényi is the same as Island Barabási–Albert, except that each island is an Erdös–Rényi graph with edge probability 0 < pintra < 1.

Code availability

Code that supports the findings of this study is available in Zenodo with the identifier http://dx.doi.org/10.5281/zenodo.276933.

Data availability

This study analysed publicly available datasets from the Stanford Large Network Dataset Collection, http://snap.stanford.edu/data/, and the Koblenz Network Collection, http://konect.uni-koblenz.de/, as well as datasets provided by S. R. Sundaresan and D. I. Rubenstein, which are available upon request from D. I. Rubenstein (dir@princeton.edu).