Transcript ppt

Evolvable by Design
How topology affects network evolution
Panos Oikonomou
Philippe Cluzel
NetSci07
James Franck Institute
Institute of Biophysical Dynamics
The University of Chicago
Introduction
• Some features are ubiquitous in nature and artificial systems
• Which are the consequences/advantages of such organizations?
• How do such systems evolve?
Internet map
US Human Genome Project
Yeast protein net, Jeong et al (2001)
Is there an evolutionary advantage in topological features?
Random Topology
P(k )  e  K K k / k!
Scale-free Topology
P(k )  Ck 
Outline
• Dynamical rules for each node
• Dynamics of network
• Evolutionary Game:
Genotype, Phenotype, Fitness,
Mutations & Selection
• Results:
Random vs. scale-free
• Interpretation and heuristic explanation
Boolean Threshold Dynamics

1


 i (t  1)   0


  i (t )

Ki
if
w 
j 0
ij
(t )  hi  0
j
Ki
if
w 
j 0
ij
j
(t )  hi  0
j
(t )  hi  0
Ki
if
w 
j 0
ij
Network Dynamics
• N nodes in two states:
ON/OFF
• Updated according to
boolean rules
• Starting from random
initial conditions
• Performs Cycle of
length L
Target “Phenotype”
Output Signal:
Boolean time series
The target
Perform robustly a
cycle behavior of
length Lc
The fitness
average hamming
distance over time
Parameters
Net. Size~500 nodes
Lc= 1-50
μ= 0.001-0.1
Evolutionary Algorithm
Parameters
Pop. Size ~50 nets
Net. Size~500 nodes
Lc= 1-50
μ= 0.001-0.1
Evolutionary Path
Random networks
Discontinuous evolution:
• Long fitness plateaus &
sudden advantageous jumps
• Networks change by neutral
mutations
• Convergence depends on rare
advantageous mutative events.
Each independent population
converges differently from the
average.
Scale-free networks
Continuous evolution:
• Diversity: the population
consists of many different
phenotypes
• Evolvability capacity to
produce many different
heritable phenotypes.
• All populations follow the same
trend and are able to converge
Continuous vs. Discontinuous Evolutionary paths
Probability that a mutation affects an output node:
 P   Pdyn 
x
 Pdyn    ps (ki ) P(ki )
1
1
0.1
0.8
0.01
0.6
‹P›
‹P›
Random
0.001
Scale-free
0.4
0.2
0.0001
2.5
5
7.5
10
‹K›
12.5
15
17.5
2.5
5
7.5
10
‹K›
12.5
15
17.5
Different topologies give different
evolutionary behaviors!
evolution "at the edge of chaos“?
random networks exhibit chaotic behavior for K > Kc= 3.83 and scaleTopology
pre-determines the evolutionary paths of networks
free networks exhibit chaotic behavior for exponents γ < γc= 2.42.
Conclusions
Homogeneous random networks and scale-free
networks exhibit drastically different
evolutionary paths.
Topology pre-determines
paths of networks.
the
evolutionary
Possible implications in design and evolutionary
strategies…
Oikonomou et al, Nature Physics, 2 (8), 2006.
Acknowledgements
Philippe Cluzel
(Univ. of Chicago)
Leo Kadanoff
(Univ. of Chicago)
Max Aldana
(UNAM)