Evolutionary Dynamics on Small-World Networks

Authors: Jan Rychtar, Brian Stadler

Abstract:

We study how the outcome of evolutionary dynamics on graphs depends on a randomness on the graph structure. We gradually change the underlying graph from completely regular (e.g. a square lattice) to completely random. We find that the fixation probability increases as the randomness increases; nevertheless, the increase is not significant and thus the fixation probability could be estimated by the known formulas for underlying regular graphs.

Keywords: evolutionary dynamics, small-world networks

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070807

References:

[1] Metz, J.A.J., Geritz, S.A.H., Mesza, G., Jacobs, F.J.A., van Heerwaarden, J.S., 1995. Adaptive dynamics, a geometrical study of the consequences of nearly faithful reproduction. Stochastic and spatial structures of dynamical systems (Amsterdam, 1995), 183- 231, Konink. Nederl. Akad. Wetensch. Verh. Afd. Natuurk. Eerste Reeks, 45, North-Holland, Amsterdam, 1996.
[2] Durrett, R., Levin, S., 1994. The importance of being discrete (and spatial). Teor. Pop. Biol. 46 (3), 363-394.
[3] Taylor, C., Fudenberg, D., Sasaki, A., et al., 2004. Evolutionary game dynamics in finite populations. Bull. Math. Biol. 66 (6), 1621-1644.
[4] Lieberman, E., Hauert, C. Nowak, M.A., 2005. Evolutionary Dynamics on Graphs, Nature 433, 312-316.
[5] Nowak, M.A., 2006. Evolutionary Dynamics: exploring the equations of life. Harward University Press.
[6] Ebel, H., Bornholdt, S., 2002. Coevolutionary games on networks. Phys. Rev. E 66 (5): Art. No. 056118.
[7] Ohtsuki, H., Lieberman, E., Hauert, C. Nowak, M.A., 2006. A simple rule for the evolution of cooperation on graphs and social networks, Nature 433, 502-505.
[8] Watts, D.J., 1999. Small Worlds, Princeton University Press.
[9] Watts, D.J., Strogatz, S.H., 1998. Collective dynamics of ÔÇÿsmall world- networks, Nature 393, 440-442.
[10] Erd¨os, P., Renyi, A., 1960. On the evolution of random graphs, Publ. Math. Inst. Hungarian Acad. Sci. 5, 17-61.
[11] Barabasi, A., Albert, R., 1999. Emergence of scaling in random networks, Science 286, 509-512.
[12] Norris, J.R. 1997. Markov Chains, Cambridge University Press.
[13] Broom, M., 2007. Personal communication.
[14] Moran, P.A.P., 1958. Random processes in genetics, Proc. Camb. Phil. Soc. 54, 60-71.
[15] Broom, M., Rycht'aˇr, J., Stadler, B., 2007. In preparation.
[16] Smith, A.F.M., Roberts, G.O., 1993. Bayesian computation via the Gibbs sampler and related Markov chain Monte Carlo methods. J. Roy. Statist. Soc. Ser. B 55, no. 1, 3-23.