title: Fast and asymptotic computation of the fixation probability for Moran processes on graphs.
abstract: 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 K(n,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 K(1,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.
authors.affiliation: GeoDynApp - ECSING Group, Spain. Electronic address: fernando.alcaldecuesta@gmail.com.
authors.forename: F
authors.initials: F
authors.lastname: Alcalde Cuesta
authors.affiliation: GeoDynApp - ECSING Group, Spain; Dpto. de Didáctica das Ciencias Experimentais, Facultade de Formación do Profesorado, Universidade de Santiago de Compostela, Avda. Ramón Ferreiro, 10, E-27002 Lugo, Spain. Electronic address: pablo.gonzalez.sequeiros@usc.es.
authors.forename: P
authors.initials: P
authors.lastname: González Sequeiros
authors.affiliation: GeoDynApp - ECSING Group, Spain; Centro Universitario de la Defensa de Zaragoza, Academia General Militar, Ctra. Huesca s/n, E-50090 Zaragoza, Spain; Instituto Universitario de Matemáticas y Aplicaciones, Universidad de Zaragoza, Spain. Electronic address: alvarolozano@unizar.es.
authors.forename: Á
authors.initials: Á
authors.lastname: Lozano Rojo
mesh_terms: D005075:Biological Evolution; D008390:Markov Chains; D008954:Models, Biological; D015233:Models, Statistical; D009010:Monte Carlo Method; D011336:Probability
keywords: Evolutionary dynamics; Expected fixation time; Fixation probability; Markov chain; Monte Carlo methods; Star and bipartite graphs