Evolution occurs in populations of reproducing individuals. The structure of a population can affect which traits evolve1,2. Understanding evolutionary game dynamics in structured populations remains difficult. Mathematical results are known for special structures in which all individuals have the same number of neighbours3,4,5,6,7,8. The general case, in which the number of neighbours can vary, has remained open. For arbitrary selection intensity, the problem is in a computational complexity class that suggests there is no efficient algorithm9. Whether a simple solution for weak selection exists has remained unanswered. Here we provide a solution for weak selection that applies to any graph or network. Our method relies on calculating the coalescence times10,11 of random walks12. We evaluate large numbers of diverse population structures for their propensity to favour cooperation. We study how small changes in population structure—graph surgery—affect evolutionary outcomes. We find that cooperation flourishes most in societies that are based on strong pairwise ties.
The authors derive a condition for how natural selection chooses between two competing strategies on any graph for weak selection, elucidating which population structures promote certain behaviours, such as cooperation.