860
edits
Moran graphs: Difference between revisions
From EvoLudo
no edit summary
mNo edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
[[Image:Circulation.svg|thumb|300px|Fairly generic sample population structure. Vertices represent individuals and links define their neighbourhood. A directed link indicates that one individual may be another's neighbour but not vice versa. Each link may have a weight, which indicates the propensity to be selected for reproduction. Reproduction occurs in the direction of the link. The depicted graph represents a circulation and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]] | [[Image:Circulation.svg|thumb|300px|Fairly generic sample population structure. Vertices represent individuals and links define their neighbourhood. A directed link indicates that one individual may be another's neighbour but not vice versa. Each link may have a weight, which indicates the propensity to be selected for reproduction. Reproduction occurs in the direction of the link. The depicted graph represents a circulation and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]] | ||
Moran graphs maintain the balance between selection and random drift of the original [[Moran process]]. For those graphs the [[spatial Moran process]] leaves the fixation probabilities of a mutant unchanged and identical to the original [[Moran process]] in unstructured, well-mixed populations. Rather surprisingly it turns out that this applies to a large class of graphs, called circulations. | Moran graphs mark in important reference point in [[evolutionary graph theory]] because they maintain the balance between selection and random drift of the original [[Moran process]]. For those graphs the [[spatial Moran process]] leaves the fixation probabilities of a mutant unchanged and identical to the original [[Moran process]] in unstructured, well-mixed populations. Rather surprisingly it turns out that this applies to a large class of graphs, called circulations. | ||
Mathematically, the structure of the graph is determined by the adjacency matrix \(\mathbf{W} = [w_{ij}]\) where \(w_{ij}\) denotes the strength of the link pointing from vertex \(i\) to vertex \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two vertices \(i\) and \(j\) are not connected. In order to characterize circulations, let us introduce the flux through each vertex. The sum of the weights of the incoming links \(f_i^\text{in}=\sum_j w_{ji}\) denotes the flux entering vertex \(i\). \(f_i^\text{in}\) relates to a temperature because it indicates the rate at which the occupant of vertex \(i\) gets replaced. ‘Hot’ vertices are frequently replaced and ‘cold’ vertices are only rarely updated. In analogy, the sum of the weights of the outgoing links \(f_i^\text{out}=\sum_j w_{ij}\) denotes the flux leaving vertex \(i\). \(f_i^\text{out}\) determines the impact of vertex \(i\) on its neighborhood. All graphs, which satisfy \(f_i^\text{in}=f_i^\text{out}\) for all vertices, are circulations. With this we can state a remarkable theorem: | Mathematically, the structure of the graph is determined by the adjacency matrix \(\mathbf{W} = [w_{ij}]\) where \(w_{ij}\) denotes the strength of the link pointing from vertex \(i\) to vertex \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two vertices \(i\) and \(j\) are not connected. In order to characterize circulations, let us introduce the flux through each vertex. The sum of the weights of the incoming links \(f_i^\text{in}=\sum_j w_{ji}\) denotes the flux entering vertex \(i\). \(f_i^\text{in}\) relates to a temperature because it indicates the rate at which the occupant of vertex \(i\) gets replaced. ‘Hot’ vertices are frequently replaced and ‘cold’ vertices are only rarely updated. In analogy, the sum of the weights of the outgoing links \(f_i^\text{out}=\sum_j w_{ij}\) denotes the flux leaving vertex \(i\). \(f_i^\text{out}\) determines the impact of vertex \(i\) on its neighborhood. All graphs, which satisfy \(f_i^\text{in}=f_i^\text{out}\) for all vertices, are circulations. With this we can state a remarkable theorem: | ||
| Line 14: | Line 14: | ||
==Evolutionary dynamics on Moran graphs== | ==Evolutionary dynamics on Moran graphs== | ||
Even though the [[#Fixation probability on circulation graphs|fixation probability]] is the same for all circulations, the invasion dynamics of mutants depends on structural details of different kinds of circulation graphs. In particular, the local structure of a graph determines or constrains the proliferation opportunities of a mutant and hence affects the spreading of a mutant trait. | |||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
[[Image:Complete graph (N=60).svg|left|200px|link=EvoLudoLab: Moran process on the complete graph]] | [[Image:Complete graph (N=60).svg|left|200px|link=EvoLudoLab: Moran process on the complete graph]] | ||
==== [[EvoLudoLab: Moran process on the complete graph|Evolutionary dynamics on the complete graph]] ==== | ==== [[EvoLudoLab: Moran process on the complete graph|Evolutionary dynamics on the complete graph]] ==== | ||
. | The [https://en.wikipedia.org/wiki/Complete_graph complete graph] is essentially identical to the original [[Moran process]] in an unstructured population. Every vertex is connected to every other one and hence the degree of the complete graph is \(k=N-1\). This means every offspring can replace any other vertex except its parent, which is indeed the only difference between the [[spatial Moran process]] on the complete graph and the original Moran process. Nevertheless, in principle, this could also be implemented in the graph structure by adding loops to each vertex. Because mutants can spread to any part of the graph in a single step, the invasion process progresses quickly and does not exhibit characteristic patterns. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
| Line 24: | Line 26: | ||
[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Moran process on the cycle graph]] | [[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Moran process on the cycle graph]] | ||
==== [[EvoLudoLab: Moran process on the cycle graph|Evolutionary dynamics on the cycle graph]] ==== | ==== [[EvoLudoLab: Moran process on the cycle graph|Evolutionary dynamics on the cycle graph]] ==== | ||
. | On the [https://en.wikipedia.org/wiki/Cycle_graph cycle graph] every vertex is connected to its two neighbours to the left and right. This corresponds to a linear graph or 1D lattice with periodic boundary conditions. The invasion dynamics is highly constrained and mutant proliferation is restricted to the left and right ends of a single connected cluster of mutants. Consequently the invasion speed is much slower than on the complete graph. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
| Line 31: | Line 33: | ||
[[Image:2D lattice (N=51x51, k=4).png|left|200px|link=EvoLudoLab: Moran process on the rectangular lattice]] | [[Image:2D lattice (N=51x51, k=4).png|left|200px|link=EvoLudoLab: Moran process on the rectangular lattice]] | ||
==== [[EvoLudoLab: Moran process on the rectangular lattice|Evolutionary dynamics on the rectangular lattice]] ==== | ==== [[EvoLudoLab: Moran process on the rectangular lattice|Evolutionary dynamics on the rectangular lattice]] ==== | ||
. | [https://en.wikipedia.org/wiki/Lattice_graph#Square_grid_graph Rectangular lattices] or 2D lattices are often used to represent spatial dimensions. However, in order to reduce finite size effects periodic boundary conditions are often assumed, i.e. the rectangular lattice is arranged on a torus. Moreover this is a convenient way to ensure that the lattice is regular, i.e. all vertices have the same number of neighbours (otherwise the lattice would also not qualify as a circulation). In contrast to the 1D lattice or cycle, a cluster of mutants can now split into two or conversely two clusters can merge into one. On rectangular lattices, mutants typically invade by forming a compact, expanding cluster with a frazzled boundary. The width of the frazzled zone increases for decreasing fitness differences between residents and mutants. Smaller fitness differences also increase the chance that the initial cluster of mutants gets split into several smaller ones. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
[[Image:Random regular graph (N=100, k= | [[Image:Random regular graph (N=100, k=4).svg|left|200px|link=EvoLudoLab: Moran process on random regular graphs]] | ||
==== [[EvoLudoLab: Moran process on random regular graphs|Evolutionary dynamics on random regular graphs]] ==== | ==== [[EvoLudoLab: Moran process on random regular graphs|Evolutionary dynamics on random regular graphs]] ==== | ||
. | [https://en.wikipedia.org/wiki/Random_regular_graph Random regular graphs] are random networks where each vertex has the same degree \(k\) (number of neighbours) and approximate [https://en.wikipedia.org/wiki/Cayley_tree Cayley trees] or [https://en.wikipedia.org/wiki/Bethe_lattice Bethe lattices] for finite \(N\). Due to the random structure no distinctive invasion patterns can form and the invasion process is similar to the complete graph despite the far fewer links, albeit a little slower because of the fewer links. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
==Fixation probabilities on Moran graphs== | ==Fixation probabilities on Moran graphs== | ||
The definition of Moran graphs is that those population structures do not affect fixation probabilities of a mutant and actually conserve the fixation probabilities of the original Moran process in unstructured populations. Moreover, the fixation probability is also independent of the location of the initial mutant. The following simulations illustrate this result for rather diverse examples of circulations. | |||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
[[Image:Complete graph (N=60).svg|left|200px|link=EvoLudoLab: Fixation probabilities on the complete graph]] | [[Image:Complete graph (N=60).svg|left|200px|link=EvoLudoLab: Fixation probabilities on the complete graph]] | ||
==== [[EvoLudoLab: Fixation probabilities on the complete graph|Fixation probabilities on the complete graph]] ==== | ==== [[EvoLudoLab: Fixation probabilities on the complete graph|Fixation probabilities on the complete graph]] ==== | ||
. | The fixation probabilities for mutants on any circulation are the same and the same as in the original Moran process. The simulations confirm this result for the complete graph, which is closest to an unstructured population. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
| Line 53: | Line 57: | ||
[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation probabilities on the cycle graph]] | [[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation probabilities on the cycle graph]] | ||
==== [[EvoLudoLab: Fixation probabilities on the cycle graph|Fixation probabilities on the cycle graph]] ==== | ==== [[EvoLudoLab: Fixation probabilities on the cycle graph|Fixation probabilities on the cycle graph]] ==== | ||
. | The invasion dynamics of mutants on the cycle graph is rather different from the invasion on a complete graph. For example, opportunities for the mutant to spread through the population are severely limited. At all times, mutants are confined to a single connected cluster. Nevertheless and in spite of these differences, the fixation probability of a mutant remains unchanged. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
| Line 60: | Line 64: | ||
[[Image:2D lattice (N=51x51, k=4).png |left|200px|link=EvoLudoLab: Fixation probabilities on the rectangular lattice]] | [[Image:2D lattice (N=51x51, k=4).png |left|200px|link=EvoLudoLab: Fixation probabilities on the rectangular lattice]] | ||
==== [[EvoLudoLab: Fixation probabilities on the rectangular lattice|Fixation probabilities on the rectangular lattice]] ==== | ==== [[EvoLudoLab: Fixation probabilities on the rectangular lattice|Fixation probabilities on the rectangular lattice]] ==== | ||
. | In contrast to the cycle graph (or 1D lattice), the initial mutant cluster can split into several disconnected clusters on rectangular (2D) lattices and separate clusters can merge into one. Again this does not affect the fixation probabilities of mutants. Note the rectangular lattice must be regular, i.e. all vertices must have the same number of neighbours - otherwise the graph would not qualify as a circulation. Usually this is implemented by introducing periodic boundary conditions. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
[[Image:Random regular graph (N=100, k= | [[Image:Random regular graph (N=100, k=4).svg|left|200px|link=EvoLudoLab: Fixation probabilities on random regular graphs]] | ||
==== [[EvoLudoLab: Fixation probabilities on random regular graphs|Fixation probabilities on random regular graphs]] ==== | ==== [[EvoLudoLab: Fixation probabilities on random regular graphs|Fixation probabilities on random regular graphs]] ==== | ||
. | The invasion dynamics on random regular graphs is similar to the complete graph in spite of fewer links. Simulations below illustrate that this does affect the ''fixation times'' but again leaves the ''fixation probabilities'' of a mutant unchanged. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
==Fixation times on Moran graphs== | ==Fixation times on Moran graphs== | ||
According to their definition, mutations on Moran graphs maintain the same fixation probabilities as in the original Moran process in unstructured populations. However, this has no implications on the fixation times of a mutant or on the absorption time, i.e. the time until the population reaches either one of the absorbing states with all mutants or all residents. In fact, fixation and absorption times vary greatly even between different circulation graphs, as illustrated with the following simulations for diverse examples of circulations. Even though to date rigorous connections between structural features and fixation times are lacking, the [https://en.wikipedia.org/wiki/Distance_(graph_theory) diameter of a graph] correlates with fixation times. The diameter of a graph \(d\) is defined as the longest shortest path between any two vertices and provides a measure for how many updates are at least required until the progeny of any one particular vertex could occupy any other vertex. Other, related measures such as the [https://en.wikipedia.org/wiki/Distance_(graph_theory) radius of a graph] or the average [https://en.wikipedia.org/wiki/Shortest_path_problem shortest distance] seem to work equally well. | |||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
[[Image:Complete graph (N=60).svg|left|200px|link=EvoLudoLab: Fixation times on the complete graph]] | [[Image:Complete graph (N=60).svg|left|200px|link=EvoLudoLab: Fixation times on the complete graph]] | ||
==== [[EvoLudoLab: Fixation times on the complete graph|Fixation times on the complete graph]] ==== | ==== [[EvoLudoLab: Fixation times on the complete graph|Fixation times on the complete graph]] ==== | ||
. | Since the complete graph is essentially identical to an unstructured population, it is little surprise that the fixation and absorption times also essentially remain the same. In particular, the complete graph is the only graph whose diameter does not depend on its size \(N\) and remains constant \(d=1\). Possibly the fixation times on the complete graph are the shortest on any circulation with undirected links or even on any graph. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
| Line 82: | Line 88: | ||
[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation times on the cycle graph]] | [[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation times on the cycle graph]] | ||
==== [[EvoLudoLab: Fixation times on the cycle graph|Fixation times on the cycle graph]] ==== | ==== [[EvoLudoLab: Fixation times on the cycle graph|Fixation times on the cycle graph]] ==== | ||
. | In contrast to the complete graph, opportunities for mutants to spread on the cycle graph are severely limited. Consequently, fixation times are much longer. The diameter of a cycle graph is \(d=[N/2]\), where \([x]\) denotes the largest integer smaller than \(x\). Quite possibly the fixation times on the cycle graph are the longest for any circulation with undirected links. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
| Line 89: | Line 95: | ||
[[Image:2D lattice (N=51x51, k=4).png |left|200px|link=EvoLudoLab: Fixation times on the rectangular lattice]] | [[Image:2D lattice (N=51x51, k=4).png |left|200px|link=EvoLudoLab: Fixation times on the rectangular lattice]] | ||
==== [[EvoLudoLab: Fixation times on the rectangular lattice|Fixation times on the rectangular lattice]] ==== | ==== [[EvoLudoLab: Fixation times on the rectangular lattice|Fixation times on the rectangular lattice]] ==== | ||
. | On the rectangular lattice fixation times lie between the extremes of the complete graph and the cycle graph. The diameter of rectangular lattice scales as \(d\sim\sqrt{N}\) but the actual value depends on the degree of the vertices, i.e. whether the lattice reflects a ''von Neumann'' neighbourhood, \(k=4\), or a ''Moore'' neighbourhood, \(k=8\), or includes an even larger range of neighbours. | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
<div class="lab_description Moran"> | <div class="lab_description Moran"> | ||
[[Image:Random regular graph (N=100, k= | [[Image:Random regular graph (N=100, k=4).svg|left|200px|link=EvoLudoLab: Fixation times on random regular graphs]] | ||
==== [[EvoLudoLab: Fixation times on random regular graphs|Fixation times on random regular graphs]] ==== | ==== [[EvoLudoLab: Fixation times on random regular graphs|Fixation times on random regular graphs]] ==== | ||
. | Fixations times on random regular graphs are much smaller than on a rectangular lattice of the same size \(N\) and the same degree \(k\). The reason is that it is much easier for mutant offspring to reach distant corners on a random regular graph than on a lattice. Even for small \(k\) every vertex can be reached from every other vertex with relatively few steps. This is also reflected in the diameter of random regular graphs, which scales as \(d\sim\ln N\). | ||
{{-}} | {{-}} | ||
</div> | </div> | ||
