Fast and asymptotic computation of the fixation probability for Moran processes on graphs

Alcalde Cuesta, F. ; González Sequeiros, P. ; Lozano Rojo, Á.

Resumen: Evolutionary dynamics has been classically studied for homogeneous populations, but now there is a growing interest in the non-homogeneous case. One of the most important models has been proposed in Lieberman et al. (2005), adapting to a weighted directed graph the process described in Moran (1958). The Markov chain associated with the graph can be modified by erasing all non-trivial loops in its state space, obtaining the so-called Embedded Markov chain (EMC). The fixation probability remains unchanged, but the expected time to absorption (fixation or extinction) is reduced. In this paper, we shall use this idea to compute asymptotically the average fixation probability for complete bipartite graphs Kn,m. To this end, we firstly review some recent results on evolutionary dynamics on graphs trying to clarify some points. We also revisit the ‘Star Theorem’ proved in Lieberman et al. (2005) for the star graphs K1,m. Theoretically, EMC techniques allow fast computation of the fixation probability, but in practice this is not always true. Thus, in the last part of the paper, we compare this algorithm with the standard Monte Carlo method for some kind of complex networks.

Idioma: Inglés

DOI: 10.1016/j.biosystems.2015.01.007

Año: 2015

Publicado en: BioSystems 129 (2015), 25-35
ISSN: 0303-2647

Factor impacto JCR: 1.495 (2015)

Categ. JCR: BIOLOGY rank: 40 / 85 = 0.471 (2015) - Q2 - T2
Categ. JCR: MATHEMATICAL & COMPUTATIONAL BIOLOGY rank: 28 / 56 = 0.5 (2015) - Q2 - T2

Factor impacto SCIMAGO: 0.602 - Applied Mathematics (Q2) - Biochemistry, Genetics and Molecular Biology (miscellaneous) (Q2) - Medicine (miscellaneous) (Q2) - Modeling and Simulation (Q2) - Statistics and Probability (Q3)

Financiación: info:eu-repo/grantAgreement/ES/DGA/E15
Financiación: info:eu-repo/grantAgreement/ES/MICINN/MTM2010-15471

Tipo y forma: Article (PostPrint)