nature.com

Evolutionary dynamics on any population structure - Nature

  • ️Nowak, Martin A.
  • ️Wed Mar 29 2017

References

  1. Lieberman, E., Hauert, C. & Nowak, M. A. Evolutionary dynamics on graphs. Nature 433, 312–316 (2005)

    Article  CAS  ADS  Google Scholar 

  2. Nowak, M. A., Tarnita, C. E. & Antal, T. Evolutionary dynamics in structured populations. Phil. Trans. R. Soc. B 365, 19–30 (2010)

    Article  Google Scholar 

  3. Ohtsuki, H., Hauert, C., Lieberman, E. & Nowak, M. A. A simple rule for the evolution of cooperation on graphs and social networks. Nature 441, 502–505 (2006)

    Article  CAS  ADS  Google Scholar 

  4. Taylor, P. D., Day, T. & Wild, G. Evolution of cooperation in a finite homogeneous graph. Nature 447, 469–472 (2007)

    Article  CAS  ADS  Google Scholar 

  5. Grafen, A. & Archetti, M. Natural selection of altruism in inelastic viscous homogeneous populations. J. Theor. Biol. 252, 694–710 (2008)

    Article  MathSciNet  Google Scholar 

  6. Chen, Y.-T. Sharp benefit-to-cost rules for the evolution of cooperation on regular graphs. Ann. Appl. Probab. 23, 637–664 (2013)

    Article  MathSciNet  Google Scholar 

  7. Allen, B. & Nowak, M. A. Games on graphs. EMS Surv. Math. Sci. 1, 113–151 (2014)

    Article  MathSciNet  Google Scholar 

  8. Débarre, F., Hauert, C. & Doebeli, M. Social evolution in structured populations. Nat. Commun. 5, 3409 (2014)

    Article  ADS  Google Scholar 

  9. Ibsen-Jensen, R ., Chatterjee, K . & Nowak, M. A. Computational complexity of ecological and evolutionary spatial dynamics. Proc. Natl Acad. Sci. USA 112, 15636–15641 (2015)

    CAS  ADS  PubMed  Google Scholar 

  10. Kingman, J. F. C. The coalescent. Stochastic Process. Appl. 13, 235–248 (1982)

    MathSciNet  MATH  Google Scholar 

  11. Wakeley, J. Coalescent Theory: an Introduction. (Roberts and Company Publishers, 2009)

  12. Cox, J. T. Coalescing random walks and voter model consensus times on the torus in Zd. Ann. Probab. 17, 1333–1366 (1989)

    Article  MathSciNet  Google Scholar 

  13. Durrett, R. & Levin, S. The importance of being discrete (and spatial). Theor. Popul. Biol. 46, 363–394 (1994)

    Article  Google Scholar 

  14. Hassell, M. P., Comins, H. N. & May, R. M. Species coexistence and self-organizing spatial dynamics. Nature 370, 290–292 (1994)

    Article  ADS  Google Scholar 

  15. Nowak, M. A. & May, R. M. Evolutionary games and spatial chaos. Nature 359, 826–829 (1992)

    Article  ADS  Google Scholar 

  16. Allen, B., Gore, J. & Nowak, M. A. Spatial dilemmas of diffusible public goods. eLife 2, e01169 (2013)

    Article  Google Scholar 

  17. Nowak, M. A ., Michor, F . & Iwasa, Y. The linear process of somatic evolution. Proc. Natl Acad. Sci. USA 100, 14966–14969 (2003)

    Article  CAS  ADS  Google Scholar 

  18. Santos, F. C., Santos, M. D. & Pacheco, J. M. Social diversity promotes the emergence of cooperation in public goods games. Nature 454, 213–216 (2008)

    Article  CAS  ADS  Google Scholar 

  19. Rand, D. G ., Nowak, M. A ., Fowler, J. H . & Christakis, N. A. Static network structure can stabilize human cooperation. Proc. Natl Acad. Sci. USA 111, 17093–17098 (2014)

    Article  CAS  ADS  Google Scholar 

  20. Allen, B. et al. The molecular clock of neutral evolution can be accelerated or slowed by asymmetric spatial structure. PLoS Comput. Biol. 11, e1004108 (2015)

    Article  Google Scholar 

  21. Maynard Smith, J. Evolution and the Theory of Games (Cambridge Univ. Press, 1982)

  22. Hofbauer, J . & Sigmund, K. Evolutionary Games and Replicator Dynamics (Cambridge Univ. Press, 1998)

  23. Broom, M . & Rychtár, J. Game-Theoretical Models in Biology. (Chapman and Hall/CRC, 2013)

  24. Santos, F. C. & Pacheco, J. M. Scale-free networks provide a unifying framework for the emergence of cooperation. Phys. Rev. Lett. 95, 098104 (2005)

    Article  CAS  ADS  Google Scholar 

  25. Maciejewski, W., Fu, F. & Hauert, C. Evolutionary game dynamics in populations with heterogenous structures. PLOS Comput. Biol. 10, e1003567 (2014)

    Article  ADS  Google Scholar 

  26. Konno, T. A condition for cooperation in a game on complex networks. J. Theor. Biol. 269, 224–233 (2011)

    Article  MathSciNet  Google Scholar 

  27. Tarnita, C. E., Ohtsuki, H., Antal, T., Fu, F. & Nowak, M. A. Strategy selection in structured populations. J. Theor. Biol. 259, 570–581 (2009)

    Article  MathSciNet  Google Scholar 

  28. Hadjichrysanthou, C., Broom, M. & Rychtárˇ, J. Evolutionary games on star graphs under various updating rules. Dyn. Games App. 1, 386–407 (2011)

    Article  MathSciNet  Google Scholar 

  29. Ohtsuki, H., Nowak, M. A. & Pacheco, J. M. Breaking the symmetry between interaction and replacement in evolutionary dynamics on graphs. Phys. Rev. Lett. 98, 108106 (2007)

    Article  ADS  Google Scholar 

  30. Allen, B., Traulsen, A., Tarnita, C. E. & Nowak, M. A. How mutation affects evolutionary games on graphs. J. Theor. Biol. 299, 97–105 (2012)

    Article  MathSciNet  Google Scholar 

  31. Liggett, T. M. Interacting Particle Systems (Springer Science and Business Media, 2006)

  32. Malécot, G. Les Mathématiques de l’Hérédité. (Masson et Cie, 1948)

  33. Slatkin, M. Inbreeding coefficients and coalescence times. Genet. Res. 58, 167–175 (1991)

    Article  CAS  Google Scholar 

  34. Erdös, P. & Rényi, A. On random graphs I. Publ. Math. (Debrecen) 6, 290–297 (1959)

    MathSciNet  MATH  Google Scholar 

  35. Newman, M. E. J. & Watts, D. J. Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341–346 (1999)

    Article  CAS  ADS  MathSciNet  Google Scholar 

  36. Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999)

    Article  ADS  MathSciNet  Google Scholar 

  37. Dorogovtsev, S. N., Goltsev, A. V. & Mendes, J. F. F. Critical phenomena in complex networks. Rev. Mod. Phys. 80, 1275 (2008)

    Article  ADS  Google Scholar 

  38. Holme, P. & Kim, B. J. Growing scale-free networks with tunable clustering. Phys. Rev. E 65, 026107 (2002)

    Article  ADS  Google Scholar 

  39. Klemm, K. & Eguíluz, V. M. Highly clustered scale-free networks. Phys. Rev. E 65, 036123 (2002)

    Article  ADS  Google Scholar 

  40. Krapivsky, P. L. & Redner, S. Organization of growing random networks. Phys. Rev. E 63, 066123 (2001)

    Article  CAS  ADS  Google Scholar 

  41. Leskovec, J ., Kleinberg, J . & Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proc. 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining 177–187 (ACM, 2005)

  42. Lozano, S., Arenas, A. & Sánchez, A. Mesoscopic structure conditions the emergence of cooperation on social networks. PLoS One 3, e1892 (2008)

    Article  ADS  Google Scholar 

  43. Gore, J., Youk, H. & van Oudenaarden, A. Snowdrift game dynamics and facultative cheating in yeast. Nature 459, 253–256 (2009)

    Article  CAS  ADS  Google Scholar 

  44. Lusseau, D. et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54, 396–405 (2003)

    Article  Google Scholar 

  45. Sade, D. S. Sociometrics of Macaca mulatta. I. Linkages and cliques in grooming matrices. Folia Primatol. (Basel) 18, 196–223 (1972)

    Article  CAS  Google Scholar 

  46. Sundaresan, S. R., Fischhoff, I. R., Dushoff, J. & Rubenstein, D. I. Network metrics reveal differences in social organization between two fission–fusion species, Grevy’s zebra and onager. Oecologia 151, 140–149 (2007)

    Article  ADS  Google Scholar 

  47. Hill, A. L., Rand, D. G., Nowak, M. A. & Christakis, N. A. Infectious disease modeling of social contagion in networks. PLoS Comput. Biol. 6, e1000968 (2010)

    Article  ADS  MathSciNet  Google Scholar 

  48. Christakis, N. A. & Fowler, J. H. The spread of obesity in a large social network over 32 years. N. Engl. J. Med. 357, 370–379 (2007)

    Article  CAS  Google Scholar 

  49. McAuley, J. J. & Leskovec, J. Learning to discover social circles in ego networks. Adv. Neural Inf. Process. Syst. 25, 548–556 (2012)

    Google Scholar 

  50. Leskovec, J., Kleinberg, J. & Faloutsos, C. Graph evolution: densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 2 (2007)

    Article  Google Scholar 

  51. Hauert, C., Michor, F., Nowak, M. A. & Doebeli, M. Synergy and discounting of cooperation in social dilemmas. J. Theor. Biol. 239, 195–202 (2006)

    Article  MathSciNet  Google Scholar 

  52. Nowak, M. A. Evolving cooperation. J. Theor. Biol. 299, 1–8 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was supported by Office of Naval Research grant N00014-16-1-2914, the John Templeton Foundation, a gift from B. Wu and E. Larson, AFOSR grant FA9550-13-1-0097 (G.L.), the James S. McDonnell Foundation (B.F.), and the Center for Mathematical Sciences and Applications at Harvard University (B.A., Y.-T.C). We are grateful to S. R. Sundaresan and D. I. Rubenstein for providing data on zebra and wild ass networks, and for discussions.

Author information

Authors and Affiliations

  1. Department of Mathematics, Emmanuel College, Boston, Massachusetts, USA

    Benjamin Allen

  2. Program for Evolutionary Dynamics, Harvard University, Cambridge, Massachusetts, USA

    Benjamin Allen, Yu-Ting Chen, Babak Fotouhi, Naghmeh Momeni & Martin A. Nowak

  3. Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA

    Benjamin Allen, Gabor Lippner, Yu-Ting Chen & Shing-Tung Yau

  4. Department of Mathematics, Northeastern University, Boston, Massachusetts, USA

    Gabor Lippner

  5. Department of Mathematics, University of Tennessee, Knoxville, Tennessee, USA

    Yu-Ting Chen

  6. Institute for Quantitative Social Sciences, Harvard University, Cambridge, Massachusetts, USA

    Babak Fotouhi

  7. Department of Electrical and Computer Engineering, McGill University, Montreal, Canada

    Naghmeh Momeni

  8. Department of Mathematics, Harvard University, Cambridge, Massachusetts, USA

    Shing-Tung Yau & Martin A. Nowak

  9. Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts, USA

    Martin A. Nowak

Authors

  1. Benjamin Allen

    You can also search for this author in PubMed Google Scholar

  2. Gabor Lippner

    You can also search for this author in PubMed Google Scholar

  3. Yu-Ting Chen

    You can also search for this author in PubMed Google Scholar

  4. Babak Fotouhi

    You can also search for this author in PubMed Google Scholar

  5. Naghmeh Momeni

    You can also search for this author in PubMed Google Scholar

  6. Shing-Tung Yau

    You can also search for this author in PubMed Google Scholar

  7. Martin A. Nowak

    You can also search for this author in PubMed Google Scholar

Contributions

B.A., G.L., Y.-T.C. and M.A.N. conceived the project. B.A., G.L., Y.-T.C. and S.-T.Y. performed mathematical analysis. N.M., B.F. and G.L. performed numerical experiments and Monte Carlo simulations. B.A. and M.A.N. wrote the paper. All authors contributed to all aspects of the project.

Corresponding author

Correspondence to Benjamin Allen.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Additional information

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Extended data figures and tables

Extended Data Figure 1 Further numerical and simulation results.

a, To assess accuracy of our results for empirically plausible selection strength, we performed Monte Carlo simulations with δ = 0.025 and c = 1. This corresponds to a fitness cost of 2.5%, which was determined to be the cost of cooperative behaviour in yeast43. Markers indicate population size times frequency of fixation for a particular value of b on a particular graph. Dashed lines indicate (b/c)* as calculated from equation (2). All graphs have size N = 100. Graphs are: Barabási–Albert (BA) with linking number m = 3, small world35 (SW) with initial connection distance d = 3 and edge creation probability p = 0.025, Klemm–Eguiluz39 (KE) with linking number m = 5 and deactivation parameter μ = 0.2, and Holme–Kim38 (HK) with linking number m = 2 and triad formation parameter P = 0.2. b, We computed (b/c)* for 4 × 104 large random graphs (sizes 300–1,000) using four random graph models: Erdös–Rényi34 (ER) with edge probability 0 < p < 0.25, Klemm–Eguiluz with linking number 3 ≤ m ≤ 5 and deactivation parameter 0 < μ < 0.15, Holme–Kim with linking number 2 ≤ m ≤ 4 and triad formation parameter 0 < P < 0.15, and a meta-network42 of shifted-linear preferential attachment networks40 (Island Barabási–Albert) with 0 < pinter < 0.25; see Methods for details. c, d, We computed the structure coefficient27 σ = ((b/c)* + 1)/((b/c)* − 1) for the same ensemble of random graphs as in Fig. 4 of the main text. Strategy A is favoured over strategy B under weak selection if σa + b > c + σd; see equation (3) of Methods. c, Plot of σ versus , which is the σ-value for a regular graph of the same mean degree . d, Plot of σ versus , which is the σ-value one would expect if the condition (as described in ref. 26) were exact. Here, is the expected degree of a neighbour of a randomly chosen vertex.

Extended Data Figure 2 The critical benefit–cost threshold for all graphs of size four.

There are six connected, unweighted graphs of size four. Of these, only the path graph has positive (b/c)*. Two others have infinite (b/c)* and three have negative (b/c)*. For size three (not shown), there are only two connected, unweighted graphs: the path, which has (b/c)* = ∞, and the triangle, which has (b/c)* = −2.

Extended Data Figure 3 The critical benefit–cost threshold for all graphs of size five.

There are 21 connected, unweighted graphs of size five. Critical ratios in the range 0 < (b/c)* < 30 are shown. Overall, seven of the (b/c)* values are positive, twelve are negative, and two are infinite.

Extended Data Figure 4 The critical benefit–cost threshold for all graphs of size six.

There are 112 connected, unweighted graphs of size six. Of these, 43 have positive (b/c)*, 65 have negative (b/c)*, and four have (b/c)* = ∞. Notably, there are graphs with the same degree sequence (for example, 3, 2, 2, 1, 1, 1) but different (b/c)*.

Extended Data Figure 5 Results for empirical networks.

The benefit–cost threshold (b/c)*, or equivalently the structure coefficient2,27 σ, gives the propensity of a population structure to support cooperative and/or Pareto-efficient behaviours. These values should be interpreted in terms of specific behaviours occurring in a population, and they depend on the network ontology (that is, the meaning of links). They can be used to facilitate comparisons across populations of similar species, or to predict consequences of changes in population structure. a, Unweighted social network of frequent associations in bottlenose dolphins (Tursiops spp.)44. b, Grooming interaction network in rhesus macaques (Macaca mulatta), weighted by grooming frequency45. c, Weighted network of group association in Grevy’s zebras (Equus grevyi)46. Preferred associations, which are statistically more frequent than random, are given weight 1. Other associations occurring at least once are given weight . d, Weighted network of group association in Asiatic wild asses (onagers)46, with the same weighting scheme as for the zebra network. For both zebra and wild ass, the unweighted networks, including every association ever observed, are dense and behave like well-mixed populations. By contrast, the weighted networks, which emphasize close ties, can promote cooperation. e, Table showing data from a–d as well as a social network of family, self-reported friends, and co-workers as of 1971 from the Framingham Heart Study47,48, a Facebook ego-network49, and the co-authorship network for the General Relativity (gr) and Quantum Cosmology (qc) category of the arXiv preprint server50. Average degree is reported for unweighted graphs only; for weighted graphs it is unclear which notion of degree is most relevant. Note that large (b/c)* ratios, which correspond to σ values close to one, do not mean that cooperation is never favoured. Rather, the implication is that the network behaves similarly to a large well-mixed population, for which cooperation is favoured for any 2 × 2 game with a + b > c + d. The donation game does not satisfy this inequality, but other cooperative interactions do51,52.

Supplementary information

Supplementary Information

This file contains Supplementary Text and Data and additional references (see Contents for more details). (PDF 1669 kb)

PowerPoint slides

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Allen, B., Lippner, G., Chen, YT. et al. Evolutionary dynamics on any population structure. Nature 544, 227–230 (2017). https://doi.org/10.1038/nature21723

Download citation

  • Received: 31 August 2016

  • Accepted: 23 February 2017

  • Published: 29 March 2017

  • Issue Date: 13 April 2017

  • DOI: https://doi.org/10.1038/nature21723