×

Absorption time of the Moran process. (English) Zbl 1344.05135

Summary: The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is \(O(n^4)\) on an \(n\)-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is \(\Omega (n \log n)\) and \(O(n^2)\). We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of P. Shakarian et al. [“A review of evolutionary graph theory with applications to game theory”, Biosystems 107, No. 2, 66–80 (2012)].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
92D15 Problems related to evolution
92D25 Population dynamics (general)

References:

[1] T.Antal, I.Scheuring, Fixation of Strategies for an Evolutionary Game in Finite Populations, Bull Math Biol68(2006) 1923-1944. · Zbl 1296.92238
[2] C.Asavathiratham, S.Roy, B.Lesieutre, and G.Verghese, The Influence Model, IEEE Control Syst21 (2001), 52-64.
[3] E.Berge, Dynamic monopolies of constant size, J Combin Theory Ser B83 (2001), 191-200. · Zbl 1032.05052
[4] B.Bollobás, The isoperimetric number of random regular graphs, Eur J Combin9 (1988), 241-244. · Zbl 0673.05086
[5] M.Broom, C.Hadjicrysanthou, J.Rychtář, Evolutionary games on graphs and the speed of the evolutionary process, Proc R Soc A466 (2010), 1327-1346. · Zbl 1202.91027
[6] M.Broom, J.Rychtář, An analysis of the fixation probability of a mutant on special classes of non‐directed graphs, Proc R Soc A464 (2008), 2609-2627. · Zbl 1152.92341
[7] P.Buser, Cubic graphs and the first eigenvalue of a Riemann surface, Math Z162 (1978), 87-99. · Zbl 0371.53032
[8] M.Cemil Azizoğlu and Ö.Eğecioğlu. The bisection width and the isoperimetric number of arrays, Discrete Appl Math138 (2004), 3-12. · Zbl 1050.05069
[9] J.Díaz, L. A.Goldberg, G. B.Mertzios, D.Richerby, M. J.Serna and P. G.Spirakis, On the fixation probability of superstars, Proc R Soc A469 (2013), 20130193. · Zbl 1371.92097
[10] J.Díaz, L. A.Goldberg, G. B.Mertzios, D.Richerby, M. J.Serna, and P. G.Spirakis, Approximating fixation probabilities in the generalized Moran process, Algorithmica24 (2014), 78-91. · Zbl 1303.92095
[11] R.Durrett, Some features of the spread of epidemics and information on random graphs, Proc Nat Acad Sci107 (2010), 4491-4498.
[12] H.Gintis, Game theory evolving: A problem‐centered introduction to modeling strategic interaction, Princeton University Press, Princeton, 2000. · Zbl 1159.91300
[13] G. R.Grimmett, D. R.Stirzaker, Probability and random processes, 3rd edition, Oxford University Press, Oxford, 2001. · Zbl 1015.60002
[14] B.Houchmandzadeh, M.Vallade, The fixation probability of a beneficial mutation in a geographically structured population, New J Phys13 (2011), 073020. · Zbl 1448.91212
[15] A.Jamieson‐Lane, C.Hauert, Fixation probabilities on superstars, revisited and revised, J Theor Biol382 (2015), 44-56. · Zbl 1402.92315
[16] D.Kempe, J.Kleinberg, and É.Tardos, Maximizing the spread of influence through a social network, In Proceedings of 9th ACM International Conference on Knowledge Discovery and Data Mining, Washington, 2003, pp. 137-146.
[17] E.Lieberman, C.Hauert, M. A.Nowak, Evolutionary dynamics on graphs, Nature433 (2005), 312-316.
[18] T. M.Liggett, Stochastic interacting systems: Contact, voter and exclusion processes, Springer, Berlin, 1999. · Zbl 0949.60006
[19] G. B.Mertzios, S. E.Nikoletseas, C.Raptopoulos, and P. G.Spirakis, Natural models for evolution on networks, Theor Comput Sci477 (2013), 76-95. · Zbl 1261.05117
[20] G. B.Mertzios and P. G.Spirakis, Strong bounds for evolution in networks, In Proceedings of 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Volume 7966 of LNCS, Springer, Latvia, 2013, pp. 657-668. · Zbl 1334.68027
[21] M.Mitzenmacher and E.Upfal, Probability and computing: Randomized algorithms and probabilistic analysis, Cambridge University Press, Cambridge, 2005. · Zbl 1092.60001
[22] B.Mohar, Isoperimetric numbers of graphs, J Combin Theory Ser B47 (1989), 274-291. · Zbl 0719.05042
[23] P. A. P.Moran, Random processes in genetics, Proc Cambridge Philos Soc54 (1958), 60-71. · Zbl 0091.15701
[24] J. R.Norris, Markov chains, Cambridge University Press, Cambridge, 1998. · Zbl 0938.60058
[25] D.Shah, Gossip algorithms, J Foundations and Trends in Networking3 (2009), 1-125. · Zbl 1185.68072
[26] P.Shakarian and P.Roos, Fast and deterministic computation of fixation probability in evolutionary graphs, In Proceedings of 6th International Conference on Computational Intelligence and Bioinformatics, 2011, pp. 753-012.
[27] P.Shakarian, P.Roos, and A.Johnson, A review of evolutionary graph theory with applications to game theory, Biosystems107 (2012), 66-80
[28] C.Taylor, D.Fudenberg, A.Sasaki, and M. A.Nowak, Evolutionary game dynamics in finite populations, Bull Math Biol66 (2004), 1621-1644. · Zbl 1334.92372
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.