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.

In evolutionary graph theory, individuals occupy vertices of a weighted directed graph and the weight wi 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. This 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. Thus, a complete graph with equal weights describes a Moran process.

Graphs can be classified into amplifiers of selection and suppressors of selection. If the fixation probability of a single advantageous mutation is higher than the fixation probability of the corresponding Moran process 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 (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 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.

Read more about Evolutionary Graph Theory:  Bibliography

Famous quotes containing the words evolutionary, graph and/or theory:

    The point is, ladies and gentlemen, that greed, for lack of a better word, is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit.
    Stanley Weiser, U.S. screenwriter, and Oliver Stone. Gordon Gekko (Michael Douglas)

    In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.
    W.N.P. Barbellion (1889–1919)

    The things that will destroy America are prosperity-at-any- price, peace-at-any-price, safety-first instead of duty-first, the love of soft living, and the get-rich-quick theory of life.
    Theodore Roosevelt (1858–1919)