Using pair approximations to predict takeover dynamics in spatially structured populations

ABSTRACT

The topological properties of a network directly impact the flow of information through a system. For example, in natural populations, the network of inter-individual contacts affects the rate of flow of infectious disease. Similarly, in evolutionary systems, the topological properties of the underlying population structure affect the rate of flow of genetic information, and thus affect selective pressure. One commonly employed method for quantifying the influence of the population structure on selective pressure is through the analysis of takeover time. In this study, we reformulate takeover time analysis in terms of the well-known Susceptible-Infectious-Susceptible (SIS) model of disease spread. We then adapt an analytical technique, called the pair approximation, to provide a general model of takeover dynamics. We compare the results of this model to simulation data on a total of six regular population structures and discuss the strengths and limitations of the approximation.

REFERENCES

• 1: Anderson, R. M., & May, R. M. Infectious Diseases of Humans. Oxford University Press, 1995.
• 2: Barabàsi, A. L. & Albert, R. Emergence of scaling in random networks. Science, 286 (1999), 509--512.
• 3: Bryden, K. M., Ashlock, D., Corns S., Wilson, S. Graph based evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 10, 5 (2005), 550--567.
• 4: Mario Giacobini , Marco Tomassini , Andrea Tettamanzi, Takeover time curves in random and small-world structured populations, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068224]
• 5: Giacobini, M., Tomassini, M., Tettamanzi, A., & Alba, E. Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Transactions on Evolutionary Computation, 9, 5 (2005), 489--505.
• 6: Goldberg, D. E., & Deb, K. A comparative analysis of selection schemes used in genetic algorithms. In Proc. Foundations of Genetic Algorithms. Morgan-Kauffman, San Mateo, CA, 1991, 69--93.
• 7: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 8: Keeling, M. J. The effects of local spatial structure on epidemiological invasions. Proc. R. Soc. Lond. B, 266 (1999), 859--867.
• 9: Keeling, M. J., & Eames, K. T. D. Networks and epidemic models. J. R. Soc. Interface, 2 (2005), 295--307.
• 10: Kerr, B., Riley, M. A., Feldman, M. W., & Bohannan, B. J. M. Local dispersal promotes biodiversity in a real life game of rock-paper-scissors. Nature, 418 (2002), 171--174.
• 11: Matsuda, H., Ogita, N., Sasaki, A., & Soto, K. Statistical mechanics of population: the lattice Lotka-Volterra model. Prog. Theor. Phys. 88 (1992), 1035--1049.
• 12: Morris, A. J. Representing spatial interactions in simple ecological models. PhD Thesis. University of Warwick, UK.
• 13: Newman, M. E. J. Spread of epidemic disease on networks. Phys. Rev. E, 66 (2002), 016128.
• 14: Newman, M. E. J. The structure and function of complex networks. SIAM Review, 45 (2003), 167--256.
• 15: Pastor-Satorras, R. & Vespignani, A. Epidemic spreading in scale-free networks. Physical Review Letters, 86, 14 (2001), 3200.
• 16: Joshua L. Payne , Margaret J. Eppstein, Emergent mating topologies in spatially structured genetic algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144032]
• 17: Joshua L. Payne , Margaret J. Eppstein, Takeover times on scale-free topologies, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277018]
• 18: Payne, J. L., Eppstein, M. J., & Goodnight, C. J. Sensitivity of self-organized speciation to long-distance dispersal. Proceedings of the IEEE Symposium on Artificial Life, 2007, 1--7.
• 19: Rudolph, G. On takeover times in spatially structured populations: array and ring. In Proc. 2nd Asia-Pacific Conference on Genetic Algorithms and Applications. Global-Link Publishing Company, Hong Kong, 2000, 144--151.
• 20: Rudolph, G. Takeover times of noisy non-generational selection rules that undo extinction. In Proc. 5th International Conference on Artificial Neural Networks and Genetic Algorithms. Springer-Verlag, Heidelberg, 2001, 268--271.
• 21: Jayshree Sarma , Kenneth A. De Jong, An Analysis of the Effects of Neighborhood Size and Shape on Local Selection Algorithms, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.236-244, September 22-26, 1996
• 22: Satō, K., & Iwasa, Y. Pair approximations for lattice-based ecological models. In The Geometry of Ecological Interactions: Simplifying Spatial Complexity. Cambridge University Press, 2000, 341--358.
• 23: Van Baalen, M. Pair approximations for different spatial geometries. In The Geometry of Ecological Interactions: Simplifying Spatial Complexity. Cambridge University Press, 2000, 359--387.
• 24: Watts, D. J., & Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature, 393 (1998), 440--442.
• 25: Werfel, J. & Bar-Yam, Y. The evolution of reproductive restraint through social communication. PNAS, 101, 30 (2004), 11019--11024.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
networks, pair approximation, selective pressure, spatial structure, takeover time