We examine population structures for their ability to maintain diversity in neutral evolution. We use the general framework of evolutionary graph theory and consider birth-death (bd) and death-birth (db) updating. The population is of size N. Initially all individuals represent different types. The basic question is: what is the time T N until one type takes over the population? This time is known as consensus time in computer science and as total coalescent time in evolutionary biology. For the complete graph, it is known that T N is quadratic in N for db and bd. For the cycle, we prove that T N is cubic in N for db and bd. For the star, we prove that T N is cubic for bd and quasilinear ( N log N ) for db. For the double star, we show that T N is quartic for bd. We derive upper and lower bounds for all undirected graphs for bd and db. We also show the Pareto front of graphs (of size N = 8 ) that maintain diversity the longest for bd and db. Further, we show that some graphs that quickly homogenize can maintain high levels of diversity longer than graphs that slowly homogenize. For directed graphs, we give simple contracting star-like structures that have superexponential time scales for maintaining diversity.

Computer Science Institute Charles University Prague 116 36 Czech Republic

Department of Mathematics Harvard University Cambridge MA 02138 USA

Department of Mathematics University of Illinois at Urbana Champaign Urbana IL 61801 USA

Department of Molecular and Cellular Biology Harvard University Cambridge MA 02138 USA

Department of Organismic and Evolutionary Biology Harvard University Cambridge MA 02138 USA

Institute of Science and Technology Austria Klosterneuburg 3400 Austria

John A Paulson School of Engineering and Applied Sciences Harvard University Boston MA 02134 USA

Zobrazit více v PubMed

Nowak  MA, May  RM. 1992. Evolutionary games and spatial chaos. Nature. 359(6398):826–829.

Nowak  MA, Michor  F, Iwasa  Y. 2003. The linear process of somatic evolution. Proc Natl Acad Sci U S A. 100(25):14966–14969. PubMed PMC

Lieberman  E, Hauert  C, Nowak  MA. 2005. Evolutionary dynamics on graphs. Nature. 433(7023):312–316. PubMed

Nowak  MA. Evolutionary dynamics: exploring the equations of life. Harvard University Press, 2006.

Ohtsuki  H, Hauert  C, Lieberman  E, Nowak  MA. 2006. A simple rule for the evolution of cooperation on graphs and social networks. Nature. 441(7092):502–505. PubMed PMC

Tarnita  CE, Antal  T, Ohtsuki  H, Nowak  MA. 2009. Evolutionary dynamics in set structured populations. Proc Natl Acad Sci U S A. 106(21):8601–8604. PubMed PMC

Allen  B, Nowak  MA. 2012. Evolutionary shift dynamics on a cycle. J Theor Biol. 311(21):28–39. PubMed PMC

Allen  B, Gore  J, Nowak  MA. 2013. Spatial dilemmas of diffusible public goods. Elife. 2:e01169. PubMed PMC

Díaz  J, Mitsche  D. 2021. A survey of the modified Moran process and evolutionary graph theory. Comput Sci Rev. 39(1):100347.

Adlam  B, Chatterjee  K, Nowak  MA. 2015. Amplifiers of selection. Proc R Soc A Math Phys Eng Sci. 471(2181):20150114.

Pavlogiannis  A, Tkadlec  J, Chatterjee  K, Nowak  MA. 2017. Amplification on undirected population structures: comets beat stars. Sci Rep. 7(1):82. PubMed PMC

Pavlogiannis  A, Tkadlec  J, Chatterjee  K, Nowak  MA. 2018. Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory. Commun Biol. 1(1):71. PubMed PMC

Tkadlec  J, Pavlogiannis  A, Chatterjee  K, Nowak  MA. 2020. Limits on amplifiers of natural selection under death-birth updating. PLoS Comput Biol. 16(1):e1007494. PubMed PMC

Allen  B, et al.  2021. Fixation probabilities in graph-structured populations under weak selection. PLoS Comput Biol. 17(2):e1008695. PubMed PMC

Tkadlec  J, Pavlogiannis  A, Chatterjee  K, Nowak  MA. 2021. Fast and strong amplifiers of natural selection. Nat Commun. 12(1):4009. PubMed PMC

Abbara  A, Pagani  L, García-Pareja  C, Bitbol  A-F. 2024. Mutant fate in spatially structured populations on graphs: connecting models to experiments. PLoS Comput Biol. 20(9):e1012424. PubMed PMC

Fruet  C, Müller  EL, Loverdo  C, Bitbol  A-F. 2025. Spatial structure facilitates evolutionary rescue by cost-free drug resistance. PubMed PMC

Svoboda  J, Joshi  S, Tkadlec  J, Chatterjee  K. 2024. Amplifiers of selection for the Moran process with both birth-death and death-birth updating. PLoS Comput Biol. 20(3):e1012008. PubMed PMC

Kopfová  L, Tkadlec  J. 2025. Colonization times in Moran process on graphs. PLoS Comput Biol. 21(5):e1012868. PubMed PMC

Kuo  YP, Carja  O. 2024. Evolutionary graph theory beyond pairwise interactions: higher-order network motifs shape times to fixation in structured populations. PLoS Comput Biol. 20(3):e1011905. PubMed PMC

Kuo  YP, Carja  O. 2024. Evolutionary graph theory beyond single mutation dynamics: on how network-structured populations cross fitness landscapes. Genetics. 227(2):iyae055. PubMed PMC

Tkadlec  J, Pavlogiannis  A, Chatterjee  K, Nowak  MA. 2019. Population structure determines the tradeoff between fixation probability and fixation time. Commun Biol. 2(1):138. PubMed PMC

Bhaumik  J, Masuda  N. 2024. Constant-selection evolutionary dynamics on weighted networks.

Adlam  B, Nowak  MA. 2014. Universality of fixation probabilities in randomly structured populations. Sci Rep. 4(1):6692. PubMed PMC

Díaz  J, Goldberg  LA, Richerby  D, Serna  M. 2016. Absorption time of the Moran process. Random Struct Algo. 49(1):137–159.

Brewster  DA, Nowak  MA, Tkadlec  J. 2024. Fixation times on directed graphs. PLoS Comput Biol. 20(7):e1012299. PubMed PMC

Iwamasa  Y, Masuda  N. 2014. Networks maximizing the consensus time of voter models. Phys Rev E. 90(1):012816. PubMed

McAvoy  A, Adlam  B, Allen  B, Nowak  MA. 2018. Stationary frequencies and mixing times for neutral drift processes with spatial structure. Proc R Soc A Math Phys Eng Sci. 474(2218):20180238.

Gao  S, Liu  Y, Wu  B. 2024. The speed of neutral evolution on graphs. J R Soc Interface. 21(214):20230594. PubMed PMC

Kaveh  K, McAvoy  A, Nowak  MA. 2019. Environmental fitness heterogeneity in the Moran process. R Soc Open Sci. 6(1):181661. PubMed PMC

Kaveh  K, McAvoy  A, Chatterjee  K, Nowak  MA. 2020. The Moran process on 2-chromatic graphs. PLoS Comput Biol. 16(11):e1008402. PubMed PMC

Nowak  MA, May  RM. 1993. The spatial dilemmas of evolution. Int J Bifur Chaos. 03(01):35–78.

Nakamaru  M, Matsuda  H, Iwasa  Y. 1997. The evolution of cooperation in a lattice-structured population. J Theor Biol. 184(1):65–81. PubMed

Hauert  C, Doebeli  M. 2004. Spatial structure often inhibits the evolution of cooperation in the snowdrift game. Nature. 428(6983):643–646. PubMed

Nowak  MA. 2006. Five rules for the evolution of cooperation. Science. 314(5805):1560–1563. PubMed PMC

Ohtsuki  H, Nowak  MA. 2006. Evolutionary games on cycles. Proc R Soc Lond B Biol Sci. 273(1598):2249–2256. PubMed PMC

Taylor  PD, Day  T, Wild  G. 2007. Evolution of cooperation in a finite homogeneous graph. Nature. 447(7143):469–472. PubMed

Ohtsuki  H, Nowak  MA. 2008. Evolutionary stability on graphs. J Theor Biol. 251(4):698–707. PubMed PMC

Nathanson  CG, Tarnita  CE, Nowak  MA. 2009. Calculating evolutionary dynamics in structured populations. PLoS Comput Biol. 5(12):e1000615. PubMed PMC

Tarnita  CE, Ohtsuki  H, Antal  T, Fu  F, Nowak  MA. 2009. Strategy selection in structured populations. J Theor Biol. 259(3):570–581. PubMed PMC

Fu  F, Nowak  MA, Hauert  C. 2010. Invasion and expansion of cooperators in lattice populations: prisoner’s dilemma vs. snowdrift games. J Theor Biol. 266(3):358–366. PubMed PMC

Van Veelen  M, García  J, Rand  DG, Nowak  MA. 2012. Direct reciprocity in structured populations. Proc Natl Acad Sci U S A. 109(25):9929–9934. PubMed PMC

Allen  B, Nowak  MA. 2014. Games on graphs. EMS Surv Math Sci. 1(1):113–151.

Allen  B, et al.  2017. Evolutionary dynamics on any population structure. Nature. 544(7649):227–230. PubMed

Donnelly  P, Welsh  D. Finite particle systems and infection models. In:

Nordborg  M, Krone  SM. Separation of time scales and convergence to the coalescent in structured populations. In:

Nordborg  M. Coalescent theory. In:

Allen  B, McAvoy  A. 2024. The coalescent in finite populations with arbitrary, fixed structure. Theor Popul Biol. 158(208):150–169. PubMed

Arora  S, Barak  B. Computational complexity: a modern approach. Cambridge University Press, 2009.

Broom  M, Hadjichrysanthou  C, Rychtář  J. 2010. Evolutionary games on graphs and the speed of the evolutionary process. Proc R Soc A Math Phys Eng Sci. 466(2117):1327–1346.

Goldberg  LA, Roth  M, Schwarz  T. 2024. Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process. Theor Comput Sci. 1016(11):114785.

Cooper  C, Rivera  N. The linear voting model. In:

McKay  BD, Piperno  A. 2014. Practical graph isomorphism, II. J Symb Comput. 60(3):94–112.