Takeover times on scale-free topologies

ABSTRACT

The topological properties of a network directly impact the flow of information through a system. In evolving populations, the topology of inter-individual interactions affects the rate of dissemination of advantageous genetic information and thus affects selective pressure. In this study, we investigate the selective pressures induced by several scale-free population structures using takeover time analysis. Previous results have shown that the selective pressures induced by scale-free interaction topologies are at least as strong as those induced by random and panmictic interaction topologies. In contrast, our results show that the selective pressures induced by scale-free interaction topologies are heavily influenced by their underlying topological properties, and can be tuned from a selective pressure close to that of a random or panmictic topology to a selective pressure that is weaker than that of a two-dimensional toroidal lattice with 3x3 rectangular neighborhoods of interactions. We also provide a detailed topological analysis of these population structures and discuss their influence on the observed dynamics in takeover times. We show that the expected takeover times observed on all population structures considered herein can be rapidly estimated using only a few readily computable metrics of the underlying topology, precluding the need to run expensive simulations or recursive probabilistic formulations.

REFERENCES

• 1: Albert, R., Jeong, H., & Barabààsi, A.L. Diameter of the World-Wide Web. Nature, 401 (1999), 130--131.
• 2: Lee Altenberg, Evolvability Suppression to Stabilize Far-Sighted Adaptations, Artificial Life, v.11 n.4, p.427-444, December 2005 [doi>10.1162/106454605774270633]
• 3: Barabàsi, A.L. & Albert, R. Emergence of scaling in random networks. Science, 286 (1999), 509--512.
• 4: Barabàsi, A.L., Ravasz, E., & Vicsek, T. Deterministic scale-free networks. Physica A, 299 (2001), 559--564.
• 5: Caldarelli, G., Capocci, A. De Los Rios, P., & Munoz, M.A. Scale-free networks from varying vertex intrinsic fitness. Physical Review Letters, 89, 25 (2002), 258702.
• 6: Callaway, D.S., Newman, M.E.J., Strogatz, S.H., & Watts, D.J. Network robustness and fragility: percolation on random graphs. Physical Review Letters, 85, 25 (2000), 5468.
• 7: Ebel, H., Mielsch, L., & Bornholdt, S. Scale-free topology of e-mail networks. Physical Review E, 66 (2002), 035103(R).
• 8: Falconer, D.S. & Mackay, T.F.C. Quantitative Genetics. Pearson Education Limited, London, UK, 1996.
• 9: 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]
• 10: 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.
• 11: 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.
• 12: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 13: Holme, P. & Kim, B.J. Growing scale-free networks with tunable clustering. Physical Review E, 65 (2002), 026107.
• 14: Jeong, H., Mason, S.P., Barabàsi, A.L., & Oltvai, Z.N. Lethality and centrality in protein networks. Nature, 411 (2001), 41--42.
• 15: 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.
• 16: Klemm, K. & Eguiluz, V.M. Highly clustered scale-free networks. Physical Review E, 65 (2002), 036123.
• 17: Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanely, H.E., & Aberg, Y. The web of human sexual contacts. Nature, 411 (2001), 907--908.
• 18: Motter, A.E., de Moura, A.P.S., Lai, Y.C., & Dasgupta, P. Topology of the conceptual network of language. Physical Review E, 65 (2002), 065102(R).
• 19: Nathan, R. Long-distance dispersal of plants. Science, 313 (2006), 786--788.
• 20: Newman, M.E.J. The structure and function of complex networks. SIAM Review, 45 (2003), 167--256.
• 21: Ohtsuki, H., Hauert, C., Lieberman, E., & Nowak, M.A. A simple rule for the evolution of cooperation on graphs and social networks. Nature, 441, 25 (2006), 502--505.
• 22: Park, K., Lai, Y.C., & Ye, N. Self-organized scale-free networks. Physical Review E, 72 (2005), 026131.
• 23: Pastor-Satorras, R. & Vespignani, A. Epidemic spreading in scale-free networks. Physical Review Letters, 86, 14 (2001), 3200.
• 24: Payne, J.L., Eppstein, M.J., & Goodnight, C.J. Sensitivity of self-organized speciation to long-distance dispersal. In Proceedings of the IEEE Symposium on Artificial Life, (2007), 1--7.
• 25: Rauch, E.M. & Bar-Yam, Y. Long-range interactions and evolutionary stability in predator-prey systems. Physical Review E, 73 (2006), 020903.
• 26: Ravasz, E., Somera, A.L., Mongru, D.A., Oltvai, Z.N., & Barabààsi, A.L. Hierarchical organization of modularity in metabolic networks. Science, 297 (2002), 1551--1555.
• 27: 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.
• 28: 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
• 29: Sayama, H., Kaufman, L., & Bar-Yam, Y. Spontaneous pattern formation and genetic diversity in habitats with irregular geographical features. Conservation Biology, 17 (2003), 893--900.
• 30: Servedio, V.D.P., Caldarelli, G., & Buttàà, P. Vertex instrinsic fitness: how to produce arbitrary scale-free networks. Physical Review E, 70 (2004), 056126.
• 31: Sprave, J. A Unified model of non-panmictic population structures in evolutionary algorithms. In Proc. of the Congress of Evolutionary Computation Conference. IEEE Press, 1999, 1384--1391.
• 32: Georgos Siganos , Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, Power laws and the AS-level internet topology, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.514-524, August 2003 [doi>10.1109/TNET.2003.815300]
• 33: 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:
scale-free, selective pressure, spatial structure, takeover time