Evolutionary dynamics on any population structure
Open accessThe DOI matches its Crossref record; 76 of the 76 references it cites were found in a registry or an index.
Abstract
Evolution occurs in populations of reproducing individuals. The structure of a population can affect which traits evolve. 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 neighbours. 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 algorithm. 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 times of random walks. 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
The genetical theory of natural selection
Fisher, R. A. (1930) · doi:10.5962/bhl.title.27468 · Cited by 17,617
The genetical evolution of social behaviour. I
Hamilton, W. D. (1964) · Journal of Theoretical Biology · doi:10.1016/0022-5193(64)90038-4 · Cited by 15,725 · cited 1×
“˝(3) i ˝ (1) i i + O(u2) (u!0): Above, we have dened q(n) i = P j2Gp (n) ij q ij and ˝ (n) i = P p(n) ij ˝ ij. The second equality above uses Eq. (60). L.2 Inclusive tness Inclusive tness theory [68, 56, 4] analyzes the evolution of social behavior using a quantity called the inclusive tness eect. This quantity is den…”
BackgroundStrogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
Evolution and the Theory of Games
Smith, J. M. (1988) · Did Darwin Get It Right? · doi:10.1007/978-1-4684-7862-4_22 · Cited by 7,906
Evolution and the Theory of Games
Smith, J. M. (1982) · Cambridge University Press eBooks · doi:10.1017/cbo9780511806292 · Cited by 6,922
The algebraic eigenvalue problem
Wilkinson, J. H. (1965) · Cited by 5,833
Evolutionary Games and Population Dynamics
Hofbauer, J., & Sigmund, K. (1998) · doi:10.1017/cbo9781139173179 · Cited by 5,502
Wright, S. (1943) · Genetics · doi:10.1093/genetics/28.2.114 · Cited by 5,479
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
The Spread of Obesity in a Large Social Network over 32 Years
Christakis, N. A., & Fowler, J. H. (2007) · New England Journal of Medicine · doi:10.1056/nejmsa066082 · Cited by 5,007
Evolutionary games and spatial chaos
Nowak, M. A., & May, R. M. (1992) · Nature · doi:10.1038/359826a0 · Cited by 4,463
Self-citationSzabó, G., & Fáth, G. (2007) · Physics Reports · doi:10.1016/j.physrep.2007.04.004 · Cited by 2,974
Competition and Biodiversity in Spatially Structured Habitats
Tilman, D. (1994) · Ecology · doi:10.2307/1939377 · Cited by 2,780
Learning to Discover Social Circles in Ego Networks
Leskovec, J., & McAuley, J. (2012) · neural information processing systems · Cited by 2,491
Graph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Graphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-003-0651-y · Cited by 2,277
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220
A simple rule for the evolution of cooperation on graphs and social networks
Ohtsuki, H., Hauert, C., Lieberman, E., & Nowak, M. A. (2006) · Nature · doi:10.1038/nature04605 · Cited by 2,208 · cited 6×
“Evolution proceeds according to Death-Birth (DB) updating [5]: A random individual dies and a neighbor is chosen, with probability proportional to reproductive rate, to reproduce into the vacancy.”
BackgroundMethodInfluentialSelf-citationScale-Free Networks Provide a Unifying Framework for the Emergence of Cooperation
Santos, F. C., & Pacheco, J. M. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.098104 · Cited by 1,804
Renormalization group analysis of the small-world network model
Newman, M. E. J., & Watts, D. J. (1999) · Physics Letters A · doi:10.1016/s0375-9601(99)00757-4 · Cited by 1,448
Social diversity promotes the emergence of cooperation in public goods games
Santos, F. C., Santos, M. D., & Pacheco, J. M. (2008) · Nature · doi:10.1038/nature06940 · Cited by 1,442
Evolutionary dynamics on graphs
Lieberman, E., Hauert, C., & Nowak, M. A. (2005) · Nature · doi:10.1038/nature03204 · Cited by 1,337
Self-citationScaling and percolation in the small-world network model
Newman, M. E. J., & Watts, D. J. (1999) · Physical Review E · doi:10.1103/physreve.60.7332 · Cited by 1,202
Evolutionary Dynamics of Biological Games
Nowak, M. A., & Sigmund, K. (2004) · Science · doi:10.1126/science.1093411 · Cited by 1,184
Self-citationGrowing scale-free networks with tunable clustering
Holme, P., & Kim, B. J. (2002) · Physical Review E · doi:10.1103/physreve.65.026107 · Cited by 1,088
The Importance of Being Discrete (and Spatial)
Durrett, R., & Levin, S. (1994) · Theoretical Population Biology · doi:10.1006/tpbi.1994.1032 · Cited by 1,085
Moran, P. A. P. (1958) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100033193 · Cited by 1,065
Organization of growing random networks
Krapivsky, P. L., & Redner, S. (2001) · Physical Review E · doi:10.1103/physreve.63.066123 · Cited by 871
Generation of uncorrelated random scale-free networks
Catanzaro, M., Boguñá, M., & Pastor-Satorras, R. (2005) · Physical Review E · doi:10.1103/physreve.71.027103 · Cited by 739
Les mathématiques de l'hérédité
Malécot, G. (1948) · Masson eBooks · Cited by 676
Snowdrift game dynamics and facultative cheating in yeast
Gore, J., Youk, H., & van Oudenaarden, A. (2009) · Nature · doi:10.1038/nature07921 · Cited by 668
Inbreeding coefficients and coalescence times
Slatkin, M. (1991) · Genetical Research · doi:10.1017/s0016672300029827 · Cited by 615
Coalescent Theory: An Introduction
Wakeley, J. (2008) · Cited by 603
Ortmann, A., & Weibull, J. W. (1997) · Southern Economic Journal · doi:10.2307/1061129 · Cited by 588
How to Make a Kin Selection Model
Taylor, P. D., & Frank, S. A. (1996) · Journal of Theoretical Biology · doi:10.1006/jtbi.1996.0075 · Cited by 581
Genetic Structure and Selection in Subdivided Populations
Rousset, F. (2004) · Cited by 554
Liggett, T. M. (2005) · Classics in Mathematics · doi:10.1007/b138374 · Cited by 538
Evolutionary dynamics in structured populations
Nowak, M. A., Tarnita, C. E., & Antal, T. (2010) · Philosophical Transactions of the Royal Society B: Biological Sciences · doi:10.1098/rstb.2009.0215 · Cited by 512
Self-citationHighly clustered scale-free networks
Klemm, K., & Eguíluz, V. M. (2002) · Physical Review E · doi:10.1103/physreve.65.036123 · Cited by 395
Species coexistence and self-organizing spatial dynamics
Hassell, M. P., Comins, H. N., & May, R. M. (1994) · Nature · doi:10.1038/370290a0 · Cited by 363
Theoretical Numerical Analysis: A Functional Analysis Framework
Han, W., & Atkinson, K. E. (2009) · Texts in Applied Mathematics · doi:10.1007/978-1-4419-0458-4 · Cited by 352
Growing scale-free networks with small-world behavior
Klemm, K., & Eguíluz, V. M. (2002) · Physical Review E · doi:10.1103/physreve.65.057102 · Cited by 339
Synergy and discounting of cooperation in social dilemmas
Hauert, C., Michor, F., Nowak, M. A., & Doebeli, M. (2006) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2005.08.040 · Cited by 335
Self-citationEvolution of cooperation in a finite homogeneous graph
Taylor, P. D., Day, T., & Wild, G. (2007) · Nature · doi:10.1038/nature05784 · Cited by 302
Static network structure can stabilize human cooperation
Rand, D. G., Nowak, M. A., Fowler, J. H., & Christakis, N. A. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1400406111 · Cited by 290
Self-citationStrategy selection in structured populations
Tarnita, C. E., Ohtsuki, H., Antal, T., Fu, F., & Nowak, M. A. (2009) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2009.03.035 · Cited by 281 · cited 3×
“1) that on any graph, the condition for natural selection to favor A over B, in the sense that ρA > ρB for weak selection, can be written [43] as σa + b > c + σd with σ = (−t1 + t2 + t3)/(t1 + t2 − t3).”
BackgroundMethodInfluentialSelf-citationBreaking the Symmetry between Interaction and Replacement in Evolutionary Dynamics on Graphs
Ohtsuki, H., Nowak, M. A., & Pacheco, J. M. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.108106 · Cited by 271
Self-citationSundaresan, S. R., Fischhoff, I. R., Dushoff, J., & Rubenstein, D. I. (2007) · Oecologia · doi:10.1007/s00442-006-0553-6 · Cited by 269
Allele-Frequency Change in a Class-Structured Population
Taylor, P. D. (1990) · The American Naturalist · doi:10.1086/285034 · Cited by 255
Nowak, M. A. (2012) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2012.01.014 · Cited by 232
Self-citationInfectious Disease Modeling of Social Contagion in Networks
Hill, A. L., Rand, D. G., Nowak, M. A., & Christakis, N. A. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000968 · Cited by 229
Self-citationGame-Theoretical Models in Biology
Broom, M., & Rychtar, J. (2013) · Chapman & Hall/CRC eBooks · doi:10.1201/b14069 · Cited by 227
The linear process of somatic evolution
Nowak, M. A., Michor, F., & Iwasa, Y. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2535419100 · Cited by 227
Self-citationCoalescing Random Walks and Voter Model Consensus Times on the Torus in $\mathbb{Z}^d$
Cox, J. T. (1989) · The Annals of Probability · doi:10.1214/aop/1176991158 · Cited by 219
Evolutionary graph theory: Breaking the symmetry between interaction and replacement
Ohtsuki, H., Pacheco, J. M., & Nowak, M. A. (2007) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2007.01.024 · Cited by 192
Self-citationSociometrics of Macaca mulatta I. Linkages and Cliques in Grooming Matrices
Sade, D. S. (1972) · Folia Primatologica · doi:10.1159/000155480 · Cited by 179
Allen, B., & Nowak, M. A. (2014) · EMS Surveys in Mathematical Sciences · doi:10.4171/emss/3 · Cited by 168
Self-citationMesoscopic Structure Conditions the Emergence of Cooperation on Social Networks
Lozano, S., Arenas, A., & Sánchez, A. (2008) · PLoS ONE · doi:10.1371/journal.pone.0001892 · Cited by 150
Social evolution in structured populations
Débarre, F., Hauert, C., & Doebeli, M. (2014) · Nature Communications · doi:10.1038/ncomms4409 · Cited by 147
Evolutionary stability on graphs
Ohtsuki, H., & Nowak, M. A. (2008) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2008.01.005 · Cited by 137
Self-citationSpatial dilemmas of diffusible public goods
Allen, B., Gore, J., & Nowak, M. A. (2013) · eLife · doi:10.7554/elife.01169 · Cited by 135
Self-citationEvolutionary Game Dynamics in Populations with Heterogenous Structures
Maciejewski, W., Fu, F., & Hauert, C. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003567 · Cited by 129
Approaching Optimality for Solving SDD Linear Systems
Koutis, I., Miller, G. L., & Peng, R. (2014) · SIAM Journal on Computing · doi:10.1137/110845914 · Cited by 127
The probability of fixation of a single mutant in an exchangeable selection model
Lessard, S., & Ladret, V. (2007) · Journal of Mathematical Biology · doi:10.1007/s00285-007-0069-7 · Cited by 105
Dispersal, Kin Competition, and the Ideal Free Distribution in a Spatially Heterogeneous Population
Leturque, H., & Rousset, F. (2002) · Theoretical Population Biology · doi:10.1006/tpbi.2002.1600 · Cited by 94
How mutation affects evolutionary games on graphs
Allen, B., Traulsen, A., Tarnita, C. E., & Nowak, M. A. (2012) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2011.03.034 · Cited by 90
Self-citationNatural selection of altruism in inelastic viscous homogeneous populations
Grafen, A., & Archetti, M. (2008) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2008.01.021 · Cited by 80
Social evolution and genetic interactions in the short and long term
Cleve, J. V. (2014) · Theoretical Population Biology · doi:10.1016/j.tpb.2015.05.002 · Cited by 76
Computational complexity of ecological and evolutionary spatial dynamics
Ibsen-Jensen, R., Chatterjee, K., & Nowak, M. A. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1511366112 · Cited by 66
Self-citationEvolutionary Games on Star Graphs Under Various Updating Rules
Hadjichrysanthou, C., Broom, M., & Rychtář, J. (2011) · Dynamic Games and Applications · doi:10.1007/s13235-011-0022-7 · Cited by 63
A condition for cooperation in a game on complex networks
Konno, T. (2010) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2010.10.033 · Cited by 60
Allen, B., Sample, C., Dementieva, Y. A., Medeiros, R. C., Paoletti, C., & Nowak, M. A. (2015) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1004108 · Cited by 57
Self-citationReproductive value in graph-structured populations
Maciejewski, W. (2014) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2013.09.032 · Cited by 51
Sharp benefit-to-cost rules for the evolution of cooperation on regular graphs
Chen, Y.-T. (2013) · The Annals of Applied Probability · doi:10.1214/12-aap849 · Cited by 42
Self-citation
Research works printed but not linked: 8
- [9] John Frank Charles Kingman. The coalescent. Stochastic Processes and their Applications , 13(3):235-248, 1982. -
- [51] Benjamin Allen and Corina E Tarnita. Measures of success in a class of evolutionary models with fixed population size and structure. Journal of Mathematical Biology , 68(1-2):109-143, 2014. -
- [58] Corina E Tarnita and Peter D Taylor. Measures of relative fitness of social behaviors in finite structured population models. The American Naturalist , 184(4):477-488, 2014. -
- [61] P.D. Taylor, T. Day, and G. Wild. From inclusive fitness to fixation probability in homogeneous structured populations. Journal of Theoretical Biology , 249(1):101-110, 2007. -
- [65] Peter D Taylor and Wes Maciejewski. Hamilton's inclusive fitness in finite-structured populations. Philosophical Transactions of the Royal Society B: Biological Sciences , 369(1642):20130360, 2014. -
- [67] Peter Taylor. Hamilton s rule in finite populations with synergistic interactions. Journal of Theoretical Biology , 397:151-157, 2016. -
- [69] Erol Ak¸ cay and Jeremy Van Cleve. There is no fitness but fitness, and the lineage is its bearer. Phil. Trans. R. Soc. B , 371(1687):20150085, 2016. -
- [71] Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2016, pages 842-850, New York, NY, USA, 2016. ACM.
Cited by
Statistical physics of human cooperation
Perc, M., Jordan, J. J., Rand, D. G., Wang, Z., Boccaletti, S., & Szolnoki, A. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.05.004 · Cited by 1,590
Jusup, M., Holme, P., Kanazawa, K., Takayasu, M., Romić, I., Wang, Z., Geček, S., Lipić, T., Podobnik, B., Wang, L., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2021.10.005 · Cited by 643
Evolutionary dynamics of higher-order interactions in social networks
Alvarez-Rodriguez, U., Battiston, F., de Arruda, G. F., Moreno, Y., Perc, M., & Latora, V. (2021) · Nature Human Behaviour · doi:10.1038/s41562-020-01024-1 · Cited by 576
Evolutionary dynamics of higher-order interactions in social networks
Alvarez-Rodriguez, U., Battiston, F., de Arruda, G. F., Moreno, Y., Perc, M., & Latora, V. (2021) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-214990 · Cited by 403
Evolution of cooperation with asymmetric social interactions
Su, Q., Allen, B., & Plotkin, J. B. (2022) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2113468118 · Cited by 104
Self-citation
Metadata
- Authors
- Allen, B., Lippner, G., Chen, Y.-T., Fotouhi, B., Momeni, N., Yau, S.-T., & Nowak, M. A.
- Affiliations
- Harvard University (US)
- Corresponding author
- Allen, Benjamin
- Venue
- Nature
- Published
- 2017-03-29
- Volume
- 544
- Issue
- 7649
- Pages
- 227-230
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- OpenAlex
- W2401891657
- Cited by
- 534
- References
- 76
- Citations by year
- 2026: 62 · 2025: 69 · 2024: 68 · 2023: 63 · 2022: 51 · 2021: 54 · 2020: 49 · 2019: 51 · 2018: 52 · 2017: 15
- FWCI
- 116.97
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- arXiv (Cornell University)
- Topics
- Social Sciences › Sociology and Political Science › Evolutionary Game Theory and Cooperation
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Evolution and Genetic Dynamics
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical and Theoretical Epidemiology and Ecology Models
- Keywords
- evolutionary game theory, structured populations, weak selection, cooperation, graph topology, coalescence time, random walks, evolutionary dynamics, selection intensity
- MeSH terms
- Algorithms, Animals, Computer Graphics, Cooperative Behavior, Biological Evolution, Game Theory, Genetics, Population, Humans, Models, Biological, Selection, Genetic, Sociology, Ecosystem
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.