Environmental Evolutionary Graph Theory

Environmental Evolutionary Graph Theory Gregory Puleo [email protected] Rochester Institute of Technology REU Host: University of Illinois at Urbana-Champaign

MIGHTY XLVII November 8, 2008

Puleo (RIT/UIUC)

Environmental Graphs

MIGHTY XLVII

1 / 14

What Is Evolutionary Graph Theory?

Lieberman, Hauert and Nowak, Nature 2005

Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14


Lieberman, Hauert and Nowak, Nature 2005 Two species, red and blue, occupy the vertices of some graph G .

Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14


Lieberman, Hauert and Nowak, Nature 2005 Two species, red and blue, occupy the vertices of some graph G . Each species has a fixed reproductive fitness.

Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14


Lieberman, Hauert and Nowak, Nature 2005 Two species, red and blue, occupy the vertices of some graph G . Each species has a fixed reproductive fitness. Blue has unit fitness. Red has fitness r (r > 0).

Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14



In each update, an individual is selected to reproduce (replacing a random neighbor) with pr. proportional to its fitness.

Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14




Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14




Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14




Puleo (RIT/UIUC)


MIGHTY XLVII

2 / 14

Fixation This model is a stationary Markov chain.

Puleo (RIT/UIUC)


MIGHTY XLVII

3 / 14

Fixation This model is a stationary Markov chain. The all-blue and all-red states are absorbing.

Puleo (RIT/UIUC)


MIGHTY XLVII

3 / 14

Fixation This model is a stationary Markov chain. The all-blue and all-red states are absorbing. When only one species remains, that species has achieved fixation.

Puleo (RIT/UIUC)


MIGHTY XLVII

3 / 14

Fixation This model is a stationary Markov chain. The all-blue and all-red states are absorbing. When only one species remains, that species has achieved fixation. We will frequently be interested in the pr. that a randomly placed individual of one color achieves fixation:

Puleo (RIT/UIUC)


MIGHTY XLVII

3 / 14

Fixation This model is a stationary Markov chain. The all-blue and all-red states are absorbing. When only one species remains, that species has achieved fixation. We will frequently be interested in the pr. that a randomly placed individual of one color achieves fixation: ρR – the pr. that a single red individual, placed uniformly randomly with everyone else blue, achieves fixation ρB – the pr. that a lone blue individual achieves fixation Puleo (RIT/UIUC)


MIGHTY XLVII

3 / 14

Adding the “Environmental”

We give the vertices background colors.

Puleo (RIT/UIUC)


MIGHTY XLVII

4 / 14


We give the vertices background colors. Fitness is no longer fixed, but environmental:

Puleo (RIT/UIUC)


MIGHTY XLVII

4 / 14


We give the vertices background colors. Fitness is no longer fixed, but environmental: Individual gets unit fitness if its color matches the background color. Individual gets fitness ε (0 < ε < 1) if it doesn’t match.

Puleo (RIT/UIUC)


MIGHTY XLVII

4 / 14


We give the vertices background colors. Fitness is no longer fixed, but environmental: Individual gets unit fitness if its color matches the background color. Individual gets fitness ε (0 < ε < 1) if it doesn’t match.

As before, an individual is picked for reproduction with pr. proportional to its fitness.

Puleo (RIT/UIUC)


MIGHTY XLVII

4 / 14

Cubes and Damaged Cubes

By symmetry, this cube graph must be fair:

Puleo (RIT/UIUC)


MIGHTY XLVII

5 / 14


By symmetry, this cube graph must be fair: Whatever the value of ε, ρR = ρB = 1/8

Puleo (RIT/UIUC)


MIGHTY XLVII

5 / 14


By symmetry, this cube graph must be fair: Whatever the value of ε, ρR = ρB = 1/8 What about a damaged cube?

Puleo (RIT/UIUC)


MIGHTY XLVII

5 / 14


By symmetry, this cube graph must be fair: Whatever the value of ε, ρR = ρB = 1/8 What about a damaged cube? Damaged cubes are also fair: ρR = ρB = 1/7

Puleo (RIT/UIUC)


MIGHTY XLVII

5 / 14

Hangers are Unfair

On the other hand, many graphs give one color an advantage.

Puleo (RIT/UIUC)


MIGHTY XLVII

6 / 14

Hangers are Unfair

On the other hand, many graphs give one color an advantage. This “hanger” graph favors red:

Puleo (RIT/UIUC)


MIGHTY XLVII

6 / 14

Hangers are Unfair

On the other hand, many graphs give one color an advantage. This “hanger” graph favors red: ε .9 .5 .1

Puleo (RIT/UIUC)


ρR .256 .284 .319

ρB .243 .201 .080

MIGHTY XLVII

6 / 14

A Star Graph

This star graph is fair.

Puleo (RIT/UIUC)


MIGHTY XLVII

7 / 14

A Star Graph

This star graph is fair. ρR = ρB = 1/8

Puleo (RIT/UIUC)


MIGHTY XLVII

7 / 14

A Star Graph

This star graph is fair. ρR = ρB = 1/8

Question Can we characterize fair graphs?

Puleo (RIT/UIUC)


MIGHTY XLVII

7 / 14

Properly Two-Colored Graphs

Definition A graph is properly two-colored if no two vertices with the same background color are adjacent.

Puleo (RIT/UIUC)


MIGHTY XLVII

8 / 14



Puleo (RIT/UIUC)


MIGHTY XLVII

8 / 14



Puleo (RIT/UIUC)


MIGHTY XLVII

8 / 14



Theorem Let G be a properly two-colored graph, let S be any state of G , let v be any vertex of G , and let w be any opposite-color neighbor of v . Then φ(v ) = φ(w ).

Puleo (RIT/UIUC)


MIGHTY XLVII

8 / 14

Notation for the Fixation Probability Vector

Let ~x be a 2n -vector where the entry xs is the pr. red fixates starting from the state S.

Puleo (RIT/UIUC)


MIGHTY XLVII

9 / 14


Let ~x be a 2n -vector where the entry xs is the pr. red fixates starting from the state S. Identify each state S with the set of vertices containing red individuals.

Puleo (RIT/UIUC)


MIGHTY XLVII

9 / 14


Let ~x be a 2n -vector where the entry xs is the pr. red fixates starting from the state S. Identify each state S with the set of vertices containing red individuals. Define the quantity γ by γ=P

1

1 v ∈V (G ) deg(v )

Puleo (RIT/UIUC)


MIGHTY XLVII

9 / 14


Let ~x be a 2n -vector where the entry xs is the pr. red fixates starting from the state S. Identify each state S with the set of vertices containing red individuals. Define the quantity γ by γ=P

1

1 v ∈V (G ) deg(v )

=

Puleo (RIT/UIUC)


1

MIGHTY XLVII

9 / 14


Let ~x be a 2n -vector where the entry xs is the pr. red fixates starting from the state S. Identify each state S with the set of vertices containing red individuals. Define the quantity γ by 1

γ=P

1 v ∈V (G ) deg(v )

=

Puleo (RIT/UIUC)

1 3

1 1


MIGHTY XLVII

9 / 14



γ=P

1 v ∈V (G ) deg(v )

=

Puleo (RIT/UIUC)

1 3

1 1


+3

1 2

MIGHTY XLVII

9 / 14



γ=P

1 v ∈V (G ) deg(v )

=

Puleo (RIT/UIUC)

1 3

1 1


+3

1 2

+1

1 5

MIGHTY XLVII

9 / 14



γ=P

1 v ∈V (G ) deg(v )

=

Puleo (RIT/UIUC)

1 3

1 1


+3

1 2

+1

1 5

=

10 47

MIGHTY XLVII

9 / 14

A Value for the Fixation Probability Vector Theorem For a properly two-colored graph G , xS = γ

X v ∈S

Puleo (RIT/UIUC)


1 deg(v )

MIGHTY XLVII

10 / 14


X v ∈S

1 deg(v )

For the current state of the graph at left, this yields 1 1 10 xS = 1 +2 ≈ .426 47 1 2 Puleo (RIT/UIUC)


MIGHTY XLVII

10 / 14


X v ∈S

1 deg(v )

Corollary All properly two-colored graphs are fair. For the current state of the graph at left, this yields 1 1 10 xS = 1 +2 ≈ .426 47 1 2 Puleo (RIT/UIUC)


MIGHTY XLVII

10 / 14

Proving Two-Colored Graphs are Fair Proof. For each vertex v , let yv = x{v } .

Puleo (RIT/UIUC)


MIGHTY XLVII

11 / 14

Proving Two-Colored Graphs are Fair Proof. For each vertex v , let yv = x{v } . yv =

Puleo (RIT/UIUC)

γ deg(v )


MIGHTY XLVII

11 / 14

Proving Two-Colored Graphs are Fair Proof. For each vertex v , let yv = x{v } . 1

γ deg(v ) yv = =P 1 deg(v ) w ∈V (G ) deg(w )

Puleo (RIT/UIUC)


MIGHTY XLVII

11 / 14


γ deg(v ) yv = =P 1 deg(v ) w ∈V (G ) deg(w ) Now, consider this formula for ρR : ρR =

X 1 yv n

v ∈V (G )

Puleo (RIT/UIUC)


MIGHTY XLVII

11 / 14



1 X yv n v ∈V (G )

Puleo (RIT/UIUC)


MIGHTY XLVII

11 / 14



1 X yv n v ∈V (G )

=

Puleo (RIT/UIUC)

1 n


MIGHTY XLVII

11 / 14



1 X yv n v ∈V (G )

ρR =

Puleo (RIT/UIUC)

1 n


MIGHTY XLVII

11 / 14



1 X yv n v ∈V (G )

ρB = ρR =

Puleo (RIT/UIUC)

1 n


MIGHTY XLVII

11 / 14

Does the Converse Hold?

Proposition All fair graphs are properly two-colored.

Puleo (RIT/UIUC)


MIGHTY XLVII

12 / 14



Puleo (RIT/UIUC)


MIGHTY XLVII

12 / 14



Puleo (RIT/UIUC)


MIGHTY XLVII

12 / 14



Open Question What is the general rule characterizing fair graphs?

Puleo (RIT/UIUC)


MIGHTY XLVII

12 / 14

Future Work Open Question Is there a nice closed-form expression for the entries of ~x on arbitrary graphs?

Puleo (RIT/UIUC)


MIGHTY XLVII

13 / 14


Open Question Is there an efficient algorithm for numerically calculating fixation probabilities?

Puleo (RIT/UIUC)


MIGHTY XLVII

13 / 14


Open Question Is there an efficient algorithm for numerically calculating fixation probabilities?

Generalizations and Extensions Different types of graph Directed graphs Weighted edges

Different “ecology” Species-specific fitness More than two foreground/background colors Puleo (RIT/UIUC)


MIGHTY XLVII

13 / 14

Further Reading

E. Lieberman, C. Hauert, and M.A. Nowak. Evolutionary dynamics on graphs. Nature 433 (2005), no. 7023, 312–316 M.A. Nowak. Evolutionary Dynamics. Cambridge: Belknap Press, 2006.

Puleo (RIT/UIUC)


MIGHTY XLVII

14 / 14