# Evolutionary dynamics on graphs

@article{Lieberman2005EvolutionaryDO, title={Evolutionary dynamics on graphs}, author={Erez Lieberman and Christoph Hauert and Martin A. Nowak}, journal={Nature}, year={2005}, volume={433}, pages={312-316} }

Evolutionary dynamics have been traditionally studied in the context of homogeneous or spatially extended populations. Here we generalize population structure by arranging individuals on a graph. Each vertex represents an individual. The weighted edges denote reproductive rates which govern how often individuals place offspring into adjacent vertices. The homogeneous population, described by the Moran process, is the special case of a fully connected graph with evenly weighted edges. Spatial… Expand

#### 1,052 Citations

Evolutionary regime transitions in structured populations

- 2018

The evolutionary dynamics of a finite population where resident individuals are replaced by mutant ones depends on its spatial structure. Usually, the population adopts the form of an undirected… Expand

Evolutionary Dynamics on Graphs - the Effect of Graph Structure and Initial Placement on Mutant Spread

- Mathematics
- 2011

We study the stochastic birth-death process in a finite and structured population and analyze how the fixation probability of a mutant depends on its initial placement. In particular, we study how… Expand

Natural Models for Evolution on Networks

- Mathematics, Computer Science
- WINE
- 2011

In the new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals, and it is proved that the new model of mutual influences admits a potential function, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Expand

Phase transitions in evolutionary dynamics

- Mathematics, Biology
- 2018

The analysis of all graphs from order 8 to order 10 reveals a complex and rich evolutionary dynamics, which have not been examined in detail until now, and poses some new challenges in computing fixation probabilities and times of evolutionary graphs. Expand

Evolutionary games on isothermal graphs

- Mathematics, Medicine
- Nature Communications
- 2019

It is shown that when spatial structure is represented by an isothermal graph, the effective number of neighbors per individual determines whether or not cooperation can evolve, thereby linking evolutionary dynamics to the theory of expander graphs. Expand

Martingales and fixation probabilities of evolutionary graphs

- Mathematics
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- 2014

Evolutionary graph theory is the study of birth–death processes that are constrained by population structure. A principal problem in evolutionary graph theory is to obtain the probability that some… Expand

Games on graphs

- Mathematics
- 2014

Evolution occurs in populations of reproducing individuals. The trajectories and outcomes of evolutionary processes depend on the structure of the population. Evolutionary graph theory is a powerful… Expand

Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs

- Computer Science, Mathematics
- MFCS
- 2017

Faster polynomial-time Monte-Carlo algorithms for finidng the fixation probability on undirected graphs and lower bounds showing that the upper bound on the expected number of effective steps the authors present is asymptotically tight for undirecting graphs are presented. Expand

The complexity of evolution on graphs

- Mathematics
- 2014

Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study… Expand

The complexity of evolutionary games on graphs

- 2015

Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study… Expand

#### References

SHOWING 1-10 OF 63 REFERENCES

The Evolution of Cooperation in a Lattice-Structured Population

- 1996

The evolution of cooperation among unrelated individuals is studied in a lattice-structured habitat, where individuals interact locally only with their neighbors. The initial population includes… Expand

THE SPATIAL DILEMMAS OF EVOLUTION

- Mathematics
- 1993

Evolutionary game theory can be extended to include spatial dimensions. The individual players are placed in a two-dimensional spatial array. In each round every individual “plays the game” with its… Expand

Dynamical organization of cooperation in complex topologies.

- Computer Science, Physics
- Physical review letters
- 2007

In this Letter, we study how cooperation is organized in complex topologies by analyzing the evolutionary (replicator) dynamics of the prisoner's dilemma, a two-player game with two available… Expand

Fastest Mixing Markov Chain on a Graph

- Mathematics, Computer Science
- SIAM Rev.
- 2004

The Lagrange dual of the fastest mixing Markov chain problem is derived, which gives a sophisticated method for obtaining (arbitrarily good) bounds on the optimal mixing rate, as well as the optimality conditions. Expand

On the evolution of random graphs

- Mathematics
- 1984

(n) k edges have equal probabilities to be chosen as the next one . We shall 2 study the "evolution" of such a random graph if N is increased . In this investigation we endeavour to find what is the… Expand

Emergence of scaling in random networks

- Computer Science, Physics
- Science
- 1999

A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems. Expand

Evolutionary Games and Population Dynamics

- Biology, Computer Science
- 1998

In this book the authors investigate the nonlinear dynamics of the self-regulation of social and economic behavior, and of the closely related interactions among species in ecological communities. Expand

Species coexistence and self-organizing spatial dynamics

- Geography
- Nature
- 1994

IN a patchy environment, dispersal between neighbouring local populations can allow the total (regional) population to persist1–5; even where all patches are identical and the within-patch dynamics… Expand

The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem

- Mathematics, Computer Science
- SIAM Rev.
- 2006

A dual of the FMMP problem is formulated and it is shown that it has a natural geometric interpretation as a maximum variance unfolding (MVU) problem, the problem of choosing a set of points to be as far apart as possible, measured by their variance, while respecting local distance constraints. Expand

Spatial structure often inhibits the evolution of cooperation in the snowdrift game

- Computer Science, Medicine
- Nature
- 2004

The results caution against the common belief that spatial structure is necessarily beneficial for cooperative behaviour, and show that no such general predictions can be made for the effects of spatial structure in the snowdrift game. Expand