IDEAS home Printed from https://ideas.repec.org/a/plo/pcbi00/1008402.html
   My bibliography  Save this article

The Moran process on 2-chromatic graphs

Author

Listed:
  • Kamran Kaveh
  • Alex McAvoy
  • Krishnendu Chatterjee
  • Martin A Nowak

Abstract

Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where “properly colored” means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring.Author summary: Heterogeneity in environmental conditions can have profound effects on long-term evolutionary outcomes in structured populations. We consider a population evolving on a colored graph, wherein the color of a node represents the resources at that location. Using a combination of analytical and numerical methods, we quantify the effects of background heterogeneity on a population’s dynamics. In addition to considering the notion of an “optimal” coloring with respect to mutant invasion, we also study the effects of dynamic spatial redistribution of resources as the population evolves. Although the effects of static background heterogeneity can be quite striking, these effects are often attenuated by the movement (or “flow”) of the underlying resources.

Suggested Citation

  • Kamran Kaveh & Alex McAvoy & Krishnendu Chatterjee & Martin A Nowak, 2020. "The Moran process on 2-chromatic graphs," PLOS Computational Biology, Public Library of Science, vol. 16(11), pages 1-18, November.
    • Handle: RePEc:plo:pcbi00:1008402
    DOI: 10.1371/journal.pcbi.1008402
    as

    Download full text from publisher

    File URL: https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1008402
    Download Restriction: no
    File URL: https://journals.plos.org/ploscompbiol/article/file?id=10.1371/journal.pcbi.1008402&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pcbi.1008402?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Suzan Farhang-Sardroodi & Amir H Darooneh & Moladad Nikbakht & Natalia L Komarova & Mohammad Kohandel, 2017. "The effect of spatial randomness on the average fixation time of mutants," PLOS Computational Biology, Public Library of Science, vol. 13(11), pages 1-22, November.
    2. Benjamin Allen & Christine Sample & Robert Jencks & James Withers & Patricia Steinhagen & Lori Brizuela & Joshua Kolodny & Darren Parke & Gabor Lippner & Yulia A Dementieva, 2020. "Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs," PLOS Computational Biology, Public Library of Science, vol. 16(1), pages 1-20, January.
    3. Bartlomiej Waclaw & Ivana Bozic & Meredith E. Pittman & Ralph H. Hruban & Bert Vogelstein & Martin A. Nowak, 2015. "A spatial model predicts that dispersal and cell turnover limit intratumour heterogeneity," Nature, Nature, vol. 525(7568), pages 261-264, September.
    4. Cullen, Julie Berry & Jacob, Brian A. & Levitt, Steven D., 2005. "The impact of school choice on student outcomes: an analysis of the Chicago Public Schools," Journal of Public Economics, Elsevier, vol. 89(5-6), pages 729-760, June.
    5. Josef Tkadlec & Andreas Pavlogiannis & Krishnendu Chatterjee & Martin A Nowak, 2020. "Limits on amplifiers of natural selection under death-Birth updating," PLOS Computational Biology, Public Library of Science, vol. 16(1), pages 1-13, January.
    6. Benjamin Allen & Gabor Lippner & Yu-Ting Chen & Babak Fotouhi & Naghmeh Momeni & Shing-Tung Yau & Martin A. Nowak, 2017. "Evolutionary dynamics on any population structure," Nature, Nature, vol. 544(7649), pages 227-230, April.
    7. Erez Lieberman & Christoph Hauert & Martin A. Nowak, 2005. "Evolutionary dynamics on graphs," Nature, Nature, vol. 433(7023), pages 312-316, January.
    8. Alex McAvoy & Benjamin Allen & Martin A. Nowak, 2020. "Social goods dilemmas in heterogeneous societies," Nature Human Behaviour, Nature, vol. 4(8), pages 819-831, August.
    9. Laura Hindersin & Arne Traulsen, 2015. "Most Undirected Random Graphs Are Amplifiers of Selection for Birth-Death Dynamics, but Suppressors of Selection for Death-Birth Dynamics," PLOS Computational Biology, Public Library of Science, vol. 11(11), pages 1-14, November.
    10. V S K Manem & K Kaveh & M Kohandel & S Sivaloganathan, 2015. "Modeling Invasion Dynamics with Spatial Random-Fitness Due to Micro-Environment," PLOS ONE, Public Library of Science, vol. 10(10), pages 1-20, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Benjamin Allen & Christine Sample & Robert Jencks & James Withers & Patricia Steinhagen & Lori Brizuela & Joshua Kolodny & Darren Parke & Gabor Lippner & Yulia A Dementieva, 2020. "Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs," PLOS Computational Biology, Public Library of Science, vol. 16(1), pages 1-20, January.
    2. Mark Broom & Igor V. Erovenko & Jan Rychtář, 2021. "Modelling Evolution in Structured Populations Involving Multiplayer Interactions," Dynamic Games and Applications, Springer, vol. 11(2), pages 270-293, June.
    3. Josef Tkadlec & Andreas Pavlogiannis & Krishnendu Chatterjee & Martin A Nowak, 2020. "Limits on amplifiers of natural selection under death-Birth updating," PLOS Computational Biology, Public Library of Science, vol. 16(1), pages 1-13, January.
    4. Lv, Shaojie & Song, Feifei, 2022. "Particle swarm intelligence and the evolution of cooperation in the spatial public goods game with punishment," Applied Mathematics and Computation, Elsevier, vol. 412(C).
    5. Xu Chen & Xuan Di & Zechu Li, 2023. "Social Learning for Sequential Driving Dilemmas," Games, MDPI, vol. 14(3), pages 1-12, May.
    6. McAvoy, Alex & Fraiman, Nicolas & Hauert, Christoph & Wakeley, John & Nowak, Martin A., 2018. "Public goods games in populations with fluctuating size," Theoretical Population Biology, Elsevier, vol. 121(C), pages 72-84.
    7. Liu, Xuesong & Pan, Qiuhui & He, Mingfeng & Liu, Aizhi, 2019. "Promotion of cooperation in evolutionary game dynamics under asymmetric information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 521(C), pages 258-266.
    8. Thomas Graham & Maria Kleshnina & Jerzy A. Filar, 2023. "Where Do Mistakes Lead? A Survey of Games with Incompetent Players," Dynamic Games and Applications, Springer, vol. 13(1), pages 231-264, March.
    9. Suzan Farhang-Sardroodi & Amir H Darooneh & Moladad Nikbakht & Natalia L Komarova & Mohammad Kohandel, 2017. "The effect of spatial randomness on the average fixation time of mutants," PLOS Computational Biology, Public Library of Science, vol. 13(11), pages 1-22, November.
    10. Benjamin Allen & Christine Sample & Patricia Steinhagen & Julia Shapiro & Matthew King & Timothy Hedspeth & Megan Goncalves, 2021. "Fixation probabilities in graph-structured populations under weak selection," PLOS Computational Biology, Public Library of Science, vol. 17(2), pages 1-25, February.
    11. Hendrik Richter, 2020. "Evolution of Cooperation for Multiple Mutant Configurations on All Regular Graphs with N ≤ 14 Players," Games, MDPI, vol. 11(1), pages 1-18, February.
    12. Jorge Peña & Bin Wu & Jordi Arranz & Arne Traulsen, 2016. "Evolutionary Games of Multiplayer Cooperation on Graphs," PLOS Computational Biology, Public Library of Science, vol. 12(8), pages 1-15, August.
    13. Fabio Della Rossa & Fabio Dercole & Anna Di Meglio, 2020. "Direct Reciprocity and Model-Predictive Strategy Update Explain the Network Reciprocity Observed in Socioeconomic Networks," Games, MDPI, vol. 11(1), pages 1-28, March.
    14. Sarkar, Bijan, 2021. "The cooperation–defection evolution on social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 584(C).
    15. Li, Bin-Quan & Wu, Zhi-Xi & Guan, Jian-Yue, 2022. "Critical thresholds of benefit distribution in an extended snowdrift game model," Chaos, Solitons & Fractals, Elsevier, vol. 157(C).
    16. Wang, Chaoqian & Szolnoki, Attila, 2023. "Inertia in spatial public goods games under weak selection," Applied Mathematics and Computation, Elsevier, vol. 449(C).
    17. Yunming Xiao & Bin Wu, 2019. "Close spatial arrangement of mutants favors and disfavors fixation," PLOS Computational Biology, Public Library of Science, vol. 15(9), pages 1-20, September.
    18. Fernando Alcalde Cuesta & Pablo González Sequeiros & Álvaro Lozano Rojo, 2018. "Evolutionary regime transitions in structured populations," PLOS ONE, Public Library of Science, vol. 13(11), pages 1-18, November.
    19. Wang, Chaoqian & Lin, Zongzhe & Rothman, Dale S., 2022. "Public goods game on coevolving networks driven by the similarity and difference of payoff," Chaos, Solitons & Fractals, Elsevier, vol. 162(C).
    20. Xiaochen Wang & Lei Zhou & Alex McAvoy & Aming Li, 2023. "Imitation dynamics on networks with incomplete information," Nature Communications, Nature, vol. 14(1), pages 1-11, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pcbi00:1008402. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ploscompbiol (email available below). General contact details of provider: https://journals.plos.org/ploscompbiol/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.