Moran graphs: Difference between revisions
From EvoLudo
No edit summary |
mNo 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 mark | Moran graphs mark an 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: | ||
