research-article

The influence of scaling and assortativity on takeover times in scale-free topologies

Authors:

Joshua L. Payne,

Margaret J. EppsteinAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 241 - 248

https://doi.org/10.1145/1389095.1389133

Published: 12 July 2008 Publication History

Abstract

In evolving systems, the topological characteristics of population structure have a pronounced impact on the rate of spread of advantageous alleles, and therefore affect selective pressure. One common method for quantifying the influence of population structure on selective pressure is through the analysis of the expected number of generations required for a single favorable allele to saturate an entire population (a.k.a. takeover time analysis). While takeover times have been thoroughly investigated in regular population structures, the selective pressures induced by irregular interaction topologies, such as scale-free graphs, have received much less attention. In this study, we systematically investigate the influence of scaling and assortativity, two frequently overlooked topological properties, on takeover times in scale-free population structures. Our results demonstrate that the scaling parameter and the magnitude and sign of assortativity have profound and unexpected nonlinear influences on takeover times in scale-free interaction topologies. We explore the reasons behind these results and suggest ways in which they may be exploited in future studies.

References

[1]

Albert, R., Jeong, H., & Barabààsi, A.L. Diameter of the World-Wide Web. Nature, 401 (1999), 130--131.

[2]

Alba, E., & Dorronsoro, B. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Transactions on Evolutionary Computation, 9, 2 (2005), 126--142.

Digital Library

[3]

Barabàsi, A.L. & Albert, R. Emergence of scaling in random networks. Science, 286 (1999), 509--512.

[4]

Clauset, A., Shalizi, C.S., & Newman, M.E.J. Power-law distributions in empirical data. arXiv:0706.1062v1, (2007).

[5]

Ebel, H., Mielsch, L., & Bornholdt, S. Scale--free topology of e-mail networks. Physical Review E, 66 (2002), 035103(R).

[6]

Giacobini, M., Tomassini, M., & Tettamanzi, A. Takeover time curves in random and small-world structured populations. In Proc. Genetic and Evolutionary Computation Conference. ACM Press, New York, NY, 2005, 1333--1340.

Digital Library

[7]

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.

Digital Library

[8]

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.

[9]

Gómez-Gardeñes, J., & Moreno, Y. From scale-free to Erdos-Réényi networks. Physical Review E, 73 (2006), 056124.

[10]

Gorges-Schleuter, M. An analysis of local selection in evolution strategies. In Proc. Genetic and Evolutionary Computation Conference. Morgan Kaufmann, San Francisco, CA, 1999, 847--854.

[11]

Hauert, C., & Doebeli, M. Spatial structure often inhibits the evolution of cooperation in the snowdrift game. Nature, 428 (2004), 643--646.

[12]

Jeong, H., Mason, S.P., Barabàsi, A.L., & Oltvai, Z.N. Lethality and centrality in protein networks. Nature, 411 (2001), 41--42.

[13]

Keeling, M. J. The effects of local spatial structure on epidemiological invasions. Proceedings of the Royal Society of London B, 266, (1999), 859--867.

[14]

Krapivsky, P.L., Redner, S., & Leyvraz, F. Connectivity in growing random networks. Physical Review Letters, 85, 21 (2000), 4629.

[15]

Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanely, H.E., & ÅÅberg, Y. The web of human sexual contacts. Nature, 411 (2001), 907--908.

[16]

Maslov, S., & Sneppen, K. Specificity and stability in topology of protein networks. Science, 296 (2002), 910--913.

[17]

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).

[18]

Newman, M.E.J. Assortative mixing in networks. Physical Review Letters, 89, 20 (2002), 208701.

[19]

Nowak, M.A., & May, R.M. Evolutionary games and spatial chaos. Nature, 359 (1992), 826--829.

[20]

Pastor-Satorras, R. & Vespignani, A. Epidemic spreading in scale-free networks. Physical Review Letters, 86, 14 (2001), 3200.

[21]

Payne, J.L., & Eppstein, M.J. Takeover times on scale-free topologies. In Proc. Genetic and Evolutionary Computation Conference. ACM Press, New York, NY, 2007, 308--315.

Digital Library

[22]

Poncela, J., Gómez-Gardeñes, J., Floría, L.M., & Moreno, Y. Robustness of cooperation in the evolutionary prisoner's dilemma on complex networks. New Journal of Physics, 9 (2007), 184.

[23]

Rong, Z., Li, X., & Wang, X. Roles of mixing patterns in cooperation on a scale-free networked game. Physical Review E, 76 (2007), 027101.

[24]

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.

[25]

Santos, F.C., & Pacheco, J.M. Scale--free networks provide a unifying framework for the emergence of cooperation. Physical Review Letters, 95, 9 (2005), 098104.

[26]

Sarma, J., & De Jong, K. An analysis of the effect of the neighborhood size and shape on local selection algorithms. In Proc. Parallel Problem Solving from Nature Conference. Springer-Verlag, Heidelberg, 1996, 236--244.

Digital Library

[27]

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.

[28]

Smith, J.M. Evolution and the Theory of Games. Cambridge University Press, Cambridge, UK, 1982.

[29]

Watts, D.J. A simple model of global cascades on random networks. PNAS, 99, 9 (2002), 5766--5771.

[30]

Xulvi--Brunet, R., & Sokolov, I.M. Reshuffling scale-free networks: from random to assortative. Physical Review E, 70 (2004), 066102.

Cited By

Burguillo JDorronsoro BBurguillo J(2017)Optimization Models with Coalitional Cellular AutomataSelf-organizing Coalitions for Managing Complexity10.1007/978-3-319-69898-4_8(139-169)Online publication date: 14-Dec-2017
https://doi.org/10.1007/978-3-319-69898-4_8
Dorronsoro BBurguillo JPeleteiro ABouvry P(2013)Evolutionary Algorithms Based on Game Theory and Cellular Automata with CoalitionsHandbook of Optimization10.1007/978-3-642-30504-7_19(481-503)Online publication date: 2013
https://doi.org/10.1007/978-3-642-30504-7_19
Green DLiu JAbbass HGreen DLiu JAbbass H(2013)DPE Networks and Evolutionary DynamicsDual Phase Evolution10.1007/978-1-4419-8423-4_5(143-160)Online publication date: 13-Nov-2013
https://doi.org/10.1007/978-1-4419-8423-4_5
Show More Cited By

Index Terms

The influence of scaling and assortativity on takeover times in scale-free topologies
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Evolutionary dynamics on scale-free interaction networks

There has been a recent surge of interest in studying dynamical processes, including evolutionary optimization, on scale-free topologies. While various scaling parameters and assortativities have been observed in natural scale-free interaction networks, ...
Takeover times on scale-free topologies
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

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 ...
Pair approximations of takeover dynamics in regular population structures

In complex adaptive systems, the topological properties of the interaction network are strong governing influences on the rate of flow of information throughout the system. For example, in epidemiological models, the structure of the underlying contact ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
136
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Burguillo JDorronsoro BBurguillo J(2017)Optimization Models with Coalitional Cellular AutomataSelf-organizing Coalitions for Managing Complexity10.1007/978-3-319-69898-4_8(139-169)Online publication date: 14-Dec-2017
https://doi.org/10.1007/978-3-319-69898-4_8
Dorronsoro BBurguillo JPeleteiro ABouvry P(2013)Evolutionary Algorithms Based on Game Theory and Cellular Automata with CoalitionsHandbook of Optimization10.1007/978-3-642-30504-7_19(481-503)Online publication date: 2013
https://doi.org/10.1007/978-3-642-30504-7_19
Green DLiu JAbbass HGreen DLiu JAbbass H(2013)DPE Networks and Evolutionary DynamicsDual Phase Evolution10.1007/978-1-4419-8423-4_5(143-160)Online publication date: 13-Nov-2013
https://doi.org/10.1007/978-1-4419-8423-4_5
Dorronsoro BBouvry P(2012)Study of different small-world topology generation mechanisms for Genetic Algorithms2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6256543(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6256543
De Felice MMeloni SPanzieri SLanzi P(2011)Effect of topology on diversity of spatially-structured evolutionary algorithmsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001789(1579-1586)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001789
Dorronsoro BBouvry P(2011)Improving Classical and Decentralized Differential Evolution With New Mutation Operator and Population TopologiesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.208136915:1(67-98)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1109/TEVC.2010.2081369
Nicolau MSchoenauer MRothlauf F(2009)Evolving specific network statistical properties using a gene regulatory network modelProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570001(723-730)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570001
Payne JEppstein M(2009)Evolutionary dynamics on scale-free interaction networksIEEE Transactions on Evolutionary Computation10.1109/TEVC.2009.201982513:4(895-912)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1109/TEVC.2009.2019825

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten