Evolutionary graph theory

Evolutionary graph theory is an area of research lying at the intersection of graph theory, probability theory, and mathematical biology. Evolutionary graph theory is an approach to studying how topology affects evolution of a population. That the underlying topology can substantially affect the results of the evolutionary process is seen most clearly in a paper by Erez Lieberman, Christoph Hauert and Martin Nowak.^[1]

In evolutionary graph theory, individuals occupy vertices of a weighted directed graph and the weight w_{i j} of an edge from vertex i to vertex j denotes the probability of i replacing j. The weight corresponds to the biological notion of fitness where fitter types propagate more readily. One property studied on graphs with two types of individuals is the fixation probability, which is defined as the probability that a single, randomly placed mutant of type A will replace a population of type B. According to the isothermal theorem, a graph has the same fixation probability as the corresponding Moran process if and only if it is isothermal, thus the sum of all weights that lead into a vertex is the same for all vertices. Thus, for example, a complete graph with equal weights describes a Moran process. The fixation probability is

$\begin{align} \rho_M = \frac{1-r^{-1}} { 1-r^{-N} } \end{align}$

where r is the relative fitness of the invading type.

Graphs can be classified into amplifiers of selection and suppressors of selection. If the fixation probability of a single advantageous mutation $\rho_G$ is higher than the fixation probability of the corresponding Moran process $\rho_M$ then the graph is an amplifier, otherwise a suppressor of selection. One example of the suppressor of selection is a linear process where only vertex i-1 can replace vertex i (but not the other way around). In this case the fixation probability is $\rho_G = 1/N$ (where N is the number of vertices) since this is the probability that the mutation arises in the first vertex which will eventually replace all the other ones. Since $\rho_G < \rho_M$ for all r greater than 1, this graph is by definition a suppressor of selection.

Evolutionary graph theory may also be studied in a dual formulation, as a coalescing random walk.

Also evolutionary games can be studied on graphs where again an edge between i and j means that these two individuals will play a game against each other.

Closely related stochastic processes include the voter model, which was introduced by Clifford and Sudbury (1973) and independently by Holley and Liggett (1975), and which has been studied extensively.

Bibliography

• Holley, R. A.; Liggett, T. M. (1975). "Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model". The Annals of Probability 3 (4): 643–663. doi:10.1214/aop/1176996306.
• Liggett, Thomas M. (1999). Stochastic interacting systems: contact, voter, and exclusion processes. Berlin: Springer. ISBN 3-540-65995-1.
• Clifford, P.; Sudbury, A. (1973). "A model for spatial conflict". Biometrika 60 (3): 581–588. doi:10.1093/biomet/60.3.581.
• Martin A. Nowak (2006). Evolutionary dynamics: exploring the equations of life. Cambridge: Belknap Press of Harvard University Press. ISBN 0-674-02338-2.

References

1. Lieberman, E.; Hauert, C.; Nowak, M. A. (2005). "Evolutionary dynamics on graphs". Nature 433 (7023): 312–316. doi:10.1038/nature03204. PMID 15662424.

External links

A virtual laboratory for studying evolution on graphs:

Further reading

• Allen, Benjamin; Nowak, Martin A. (2014). "Games on graphs". EMS Surveys in Mathematical Sciences 1 (1): 113–151. doi:10.4171/EMSS3.