https://wiki.evoludo.org/index.php?title=Moran_graphs&feed=atom&action=history Moran graphs - Revision history 2024-03-29T00:44:19Z Revision history for this page on the wiki MediaWiki 1.40.0 https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2706&oldid=prev Hauert at 18:12, 13 October 2023 2023-10-13T18:12:43Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 11:12, 13 October 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l114">Line 114:</td> <td colspan="2" class="diff-lineno">Line 114:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the vertex at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the vertex at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. Moreover, fixation times generally depend on the location of the initial mutant. Only additional [[Graph symmetries|structural symmetries]] can ensure that the fixation times are independent of the location on one graph but not across different graphs. The circulation theorem only ensures that the ''ratio'' of the transition probabilities \(<del style="font-weight: bold; text-decoration: none;">T</del>^+/<del style="font-weight: bold; text-decoration: none;">T</del>^− = r\) remains unchanged, i.e. independent of the number and distribution <del style="font-weight: bold; text-decoration: none;">of residents and mutants</del>, <del style="font-weight: bold; text-decoration: none;">but </del>even on circulation graphs \(<del style="font-weight: bold; text-decoration: none;">T</del>^+\) and \(<del style="font-weight: bold; text-decoration: none;">T</del>^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. Moreover, fixation times generally depend on the location of the initial mutant. Only additional [[Graph symmetries|structural symmetries]] can ensure that the fixation times are independent of the location on one graph but not across different graphs. The circulation theorem only ensures that the ''ratio'' of the transition probabilities \(<ins style="font-weight: bold; text-decoration: none;">T_i</ins>^+/<ins style="font-weight: bold; text-decoration: none;">T_i</ins>^− = r\) remains unchanged, i.e. independent of the number <ins style="font-weight: bold; text-decoration: none;">of mutants \(i\) </ins>and <ins style="font-weight: bold; text-decoration: none;">their </ins>distribution<ins style="font-weight: bold; text-decoration: none;">. However</ins>, even on circulation graphs <ins style="font-weight: bold; text-decoration: none;">both </ins>\(<ins style="font-weight: bold; text-decoration: none;">T_i</ins>^+\) and \(<ins style="font-weight: bold; text-decoration: none;">T_i</ins>^−\) depend not only on the number but also on the distribution of mutants <ins style="font-weight: bold; text-decoration: none;">but those effects cancel for their ratio</ins>. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2484&oldid=prev Hauert: /* Fixation probability on circulation graphs */ 2016-08-31T08:47:25Z <p><span dir="auto"><span class="autocomment">Fixation probability on circulation graphs</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 01:47, 31 August 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l114">Line 114:</td> <td colspan="2" class="diff-lineno">Line 114:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the vertex at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the vertex at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. The circulation theorem only ensures that the ''ratio'' of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem<ins style="font-weight: bold; text-decoration: none;">. Moreover, fixation times generally depend on the location of the initial mutant. Only additional [[Graph symmetries|structural symmetries]] can ensure that the fixation times are independent of the location on one graph but not across different graphs</ins>. The circulation theorem only ensures that the ''ratio'' of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2483&oldid=prev Hauert: /* Fixation times on Moran graphs */ 2016-08-31T04:11:02Z <p><span dir="auto"><span class="autocomment">Fixation times on Moran graphs</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:11, 30 August 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l76">Line 76:</td> <td colspan="2" class="diff-lineno">Line 76:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation times on Moran graphs==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation times on Moran graphs==</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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. <ins style="font-weight: bold; text-decoration: none;">Moreover, even on circulation graphs fixation times in general also depend on the location of the initial mutant. Only sufficiently [[Graph symmetries|symmetrical graphs]] can at least ensure that fixations times do not depend on the location of the initial mutant. However, even then fixation times differ between different graphs.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2480&oldid=prev Hauert at 03:34, 31 August 2016 2016-08-31T03:34:55Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:34, 30 August 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2">Line 2:</td> <td colspan="2" class="diff-lineno">Line 2:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[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&#039;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.]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[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&#039;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.]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Moran graphs mark <del style="font-weight: bold; text-decoration: none;">in </del>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.  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Moran graphs mark <ins style="font-weight: bold; text-decoration: none;">an </ins>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.  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2479&oldid=prev Hauert at 03:34, 31 August 2016 2016-08-31T03:34:08Z <p></p> <a href="//wiki.evoludo.org/index.php?title=Moran_graphs&amp;diff=2479&amp;oldid=2464">Show changes</a> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2464&oldid=prev Hauert at 22:51, 30 August 2016 2016-08-30T22:51:52Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 15:51, 30 August 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l8">Line 8:</td> <td colspan="2" class="diff-lineno">Line 8:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>::&#039;&#039;Circulation Theorem:&#039;&#039; The Moran process on a graph results in the same fixation probability \(\rho_1\) of a single mutant as in an unstructured population if the graph is a circulation.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>::&#039;&#039;Circulation Theorem:&#039;&#039; The Moran process on a graph results in the same fixation probability \(\rho_1\) of a single mutant as in an unstructured population if the graph is a circulation.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>An [[#Fixation probability on circulation graphs|illustrative sketch of the proof]] follows below. In contrast to unstructured (well-mixed) populations, the state of a structured population is not simply determined by just the number of mutants (or residents) but rather needs to take the distribution of mutants and residents into account. Rather surprisingly, however, it turns out that for circulations the spatial distribution of mutants and residents does not affect their fixation probabilities. The observation that fixation probabilities remain unchanged for diverse population structures forms the basis for the conjecture by [[#References|Maruyama (1970)]] and [[#References|Slatkin (1981)]] speculating that population structure does not affect fixation probabilities. Indeed this is true for structures as diverse as [https://en.wikipedia.org/wiki/Complete_graph complete graphs] (every vertex is connected to every other vertex), lattices or [https://en.wikipedia.org/wiki/Random_regular_graph random regular graphs] <del style="font-weight: bold; text-decoration: none;">(see e.g. [[#References|Bollobás, 1995]])</del>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>An [[#Fixation probability on circulation graphs|illustrative sketch of the proof]] follows below. In contrast to unstructured (well-mixed) populations, the state of a structured population is not simply determined by just the number of mutants (or residents) but rather needs to take the distribution of mutants and residents into account. Rather surprisingly, however, it turns out that for circulations the spatial distribution of mutants and residents does not affect their fixation probabilities. The observation that fixation probabilities remain unchanged for diverse population structures forms the basis for the conjecture by [[#References|Maruyama (1970)]] and [[#References|Slatkin (1981)]] speculating that population structure does not affect fixation probabilities. Indeed this is true for structures as diverse as [https://en.wikipedia.org/wiki/Complete_graph complete graphs] (every vertex is connected to every other vertex), lattices or [https://en.wikipedia.org/wiki/Random_regular_graph random regular graphs].</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Last but not least, the circulation theorem indirectly suggests that some population structures &#039;&#039;do&#039;&#039; affect fixation probabilities. Thus, it becomes an intriguing question what population structures may act as [[evolutionary suppressors]] that suppress selection and enhance random drift (\(\rho&lt;\rho_1\) for \(r &gt; 1\)) or, conversely, as [[evolutionary amplifiers]] that enhance selection and suppresses random drift (\(\rho&gt;\rho_1\) for \(r &gt; 1\)).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Last but not least, the circulation theorem indirectly suggests that some population structures &#039;&#039;do&#039;&#039; affect fixation probabilities. Thus, it becomes an intriguing question what population structures may act as [[evolutionary suppressors]] that suppress selection and enhance random drift (\(\rho&lt;\rho_1\) for \(r &gt; 1\)) or, conversely, as [[evolutionary amplifiers]] that enhance selection and suppresses random drift (\(\rho&gt;\rho_1\) for \(r &gt; 1\)).</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l22">Line 22:</td> <td colspan="2" class="diff-lineno">Line 22:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Moran process on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Moran process on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph|Evolutionary dynamics on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph|Evolutionary dynamics on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l51">Line 51:</td> <td colspan="2" class="diff-lineno">Line 51:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation probabilities on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation probabilities on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph|Fixation probabilities on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph|Fixation probabilities on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l80">Line 80:</td> <td colspan="2" class="diff-lineno">Line 80:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation times on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:1D lattice (N=150, k=2).png|left|200px|link=EvoLudoLab: Fixation times on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph|Fixation times on the <del style="font-weight: bold; text-decoration: none;">linear </del>graph]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph|Fixation times on the <ins style="font-weight: bold; text-decoration: none;">cycle </ins>graph]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l113">Line 113:</td> <td colspan="2" class="diff-lineno">Line 113:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===References===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===References===</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">#Bollobás, B. (1995) Random Graphs, New York, Academic.</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#Maruyama, T. (1974) A Simple Proof that Certain Quantities are Independent of the Geographical Structure of Population &#039;&#039;Theor. Pop. Biol.&#039;&#039; &#039;&#039;&#039;5&#039;&#039;&#039; 148-154.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#Maruyama, T. (1974) A Simple Proof that Certain Quantities are Independent of the Geographical Structure of Population &#039;&#039;Theor. Pop. Biol.&#039;&#039; &#039;&#039;&#039;5&#039;&#039;&#039; 148-154.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#Slatkin, M. (1981) Fixation probabilities and fixation times in a subdivided population &#039;&#039;Evolution&#039;&#039; &#039;&#039;&#039;35&#039;&#039;&#039; 477-488.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#Slatkin, M. (1981) Fixation probabilities and fixation times in a subdivided population &#039;&#039;Evolution&#039;&#039; &#039;&#039;&#039;35&#039;&#039;&#039; 477-488.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Evolutionary graph theory]][[Category:Tutorial]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Evolutionary graph theory]][[Category:Tutorial]]</div></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2454&oldid=prev Hauert at 18:39, 29 August 2016 2016-08-29T18:39:21Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 11:39, 29 August 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{InCharge|author1=Christoph Hauert}}__NOTOC__</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{InCharge|author1=Christoph Hauert}}__NOTOC__</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[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 <del style="font-weight: bold; text-decoration: none;">[[#Circulation theorem|</del>circulation<del style="font-weight: bold; text-decoration: none;">]] </del>and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[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.]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l15">Line 15:</td> <td colspan="2" class="diff-lineno">Line 15:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Evolutionary dynamics on Moran graphs==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Evolutionary dynamics on Moran graphs==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Complete graph (N=<del style="font-weight: bold; text-decoration: none;">1000</del>).<del style="font-weight: bold; text-decoration: none;">png</del>|left|200px|link=EvoLudoLab: Moran process on the complete graph]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Complete graph (N=<ins style="font-weight: bold; text-decoration: none;">60</ins>).<ins style="font-weight: bold; text-decoration: none;">svg</ins>|left|200px|link=EvoLudoLab: Moran process on the complete graph]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on the complete graph|Evolutionary dynamics on the complete graph]] ====</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on the complete graph|Evolutionary dynamics on the complete graph]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l22">Line 22:</td> <td colspan="2" class="diff-lineno">Line 22:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Rectangular </del>lattice (N=<del style="font-weight: bold; text-decoration: none;">51x51</del>).png|left|200px|link=EvoLudoLab: Moran process on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">1D </ins>lattice (N=<ins style="font-weight: bold; text-decoration: none;">150, k=2</ins>).png|left|200px|link=EvoLudoLab: Moran process on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>|Evolutionary dynamics on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>|Evolutionary dynamics on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l29">Line 29:</td> <td colspan="2" class="diff-lineno">Line 29:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Random regular graph </del>(N=<del style="font-weight: bold; text-decoration: none;">1000</del>).<del style="font-weight: bold; text-decoration: none;">svg</del>|left|200px|link=EvoLudoLab: Moran process on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">2D lattice </ins>(N=<ins style="font-weight: bold; text-decoration: none;">51x51, k=4</ins>).<ins style="font-weight: bold; text-decoration: none;">png</ins>|left|200px|link=EvoLudoLab: Moran process on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>|Evolutionary dynamics on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>|Evolutionary dynamics on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36">Line 36:</td> <td colspan="2" class="diff-lineno">Line 36:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Linear </del>graph (N=<del style="font-weight: bold; text-decoration: none;">150</del>).<del style="font-weight: bold; text-decoration: none;">png</del>|left|200px|link=EvoLudoLab: Moran process on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">Random regular </ins>graph (N=<ins style="font-weight: bold; text-decoration: none;">100, k=3</ins>).<ins style="font-weight: bold; text-decoration: none;">svg</ins>|left|200px|link=EvoLudoLab: Moran process on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>|Evolutionary dynamics on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Moran process on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>|Evolutionary dynamics on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l44">Line 44:</td> <td colspan="2" class="diff-lineno">Line 44:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation probabilities on Moran graphs==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation probabilities on Moran graphs==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Complete graph (N=<del style="font-weight: bold; text-decoration: none;">100</del>).<del style="font-weight: bold; text-decoration: none;">png</del>|left|200px|link=EvoLudoLab: Fixation probabilities on the complete graph]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Complete graph (N=<ins style="font-weight: bold; text-decoration: none;">60</ins>).<ins style="font-weight: bold; text-decoration: none;">svg</ins>|left|200px|link=EvoLudoLab: Fixation probabilities on the complete graph]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on the complete graph|Fixation probabilities on the complete graph]] ====</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on the complete graph|Fixation probabilities on the complete graph]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l51">Line 51:</td> <td colspan="2" class="diff-lineno">Line 51:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Rectangular </del>lattice (N=<del style="font-weight: bold; text-decoration: none;">9x9</del>).png|left|200px|link=EvoLudoLab: Fixation probabilities on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">1D </ins>lattice (N=<ins style="font-weight: bold; text-decoration: none;">150, k=2</ins>).png|left|200px|link=EvoLudoLab: Fixation probabilities on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>|Fixation probabilities on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>|Fixation probabilities on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l58">Line 58:</td> <td colspan="2" class="diff-lineno">Line 58:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Random regular graph </del>(N=<del style="font-weight: bold; text-decoration: none;">100</del>).<del style="font-weight: bold; text-decoration: none;">svg</del>|left|200px|link=EvoLudoLab: Fixation probabilities on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">2D lattice </ins>(N=<ins style="font-weight: bold; text-decoration: none;">51x51, k=4</ins>).<ins style="font-weight: bold; text-decoration: none;">png </ins>|left|200px|link=EvoLudoLab: Fixation probabilities on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>|Fixation probabilities on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>|Fixation probabilities on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l65">Line 65:</td> <td colspan="2" class="diff-lineno">Line 65:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Linear </del>graph (N=<del style="font-weight: bold; text-decoration: none;">150</del>).<del style="font-weight: bold; text-decoration: none;">png</del>|left|200px|link=EvoLudoLab: Fixation probabilities on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">Random regular </ins>graph (N=<ins style="font-weight: bold; text-decoration: none;">100, k=3</ins>).<ins style="font-weight: bold; text-decoration: none;">svg</ins>|left|200px|link=EvoLudoLab: Fixation probabilities on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>|Fixation probabilities on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation probabilities on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>|Fixation probabilities on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l73">Line 73:</td> <td colspan="2" class="diff-lineno">Line 73:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation times on Moran graphs==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation times on Moran graphs==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Complete graph (N=<del style="font-weight: bold; text-decoration: none;">100</del>).<del style="font-weight: bold; text-decoration: none;">png</del>|left|200px|link=EvoLudoLab: Fixation times on the complete graph]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Complete graph (N=<ins style="font-weight: bold; text-decoration: none;">60</ins>).<ins style="font-weight: bold; text-decoration: none;">svg</ins>|left|200px|link=EvoLudoLab: Fixation times on the complete graph]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on the complete graph|Fixation times on the complete graph]] ====</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on the complete graph|Fixation times on the complete graph]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l80">Line 80:</td> <td colspan="2" class="diff-lineno">Line 80:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Rectangular </del>lattice (N=<del style="font-weight: bold; text-decoration: none;">9x9</del>).png|left|200px|link=EvoLudoLab: Fixation times on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">1D </ins>lattice (N=<ins style="font-weight: bold; text-decoration: none;">150, k=2</ins>).png|left|200px|link=EvoLudoLab: Fixation times on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>|Fixation times on the <del style="font-weight: bold; text-decoration: none;">rectangular lattice</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>|Fixation times on the <ins style="font-weight: bold; text-decoration: none;">linear graph</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l87">Line 87:</td> <td colspan="2" class="diff-lineno">Line 87:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Random regular graph </del>(N=<del style="font-weight: bold; text-decoration: none;">100</del>).<del style="font-weight: bold; text-decoration: none;">svg</del>|left|200px|link=EvoLudoLab: Fixation times on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">2D lattice </ins>(N=<ins style="font-weight: bold; text-decoration: none;">51x51, k=4</ins>).<ins style="font-weight: bold; text-decoration: none;">png </ins>|left|200px|link=EvoLudoLab: Fixation times on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>|Fixation times on <del style="font-weight: bold; text-decoration: none;">random regular graphs</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>|Fixation times on <ins style="font-weight: bold; text-decoration: none;">the rectangular lattice</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l94">Line 94:</td> <td colspan="2" class="diff-lineno">Line 94:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;div class=&quot;lab_description Moran&quot;&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<del style="font-weight: bold; text-decoration: none;">Linear </del>graph (N=<del style="font-weight: bold; text-decoration: none;">150</del>).<del style="font-weight: bold; text-decoration: none;">png</del>|left|200px|link=EvoLudoLab: Fixation times on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Image:<ins style="font-weight: bold; text-decoration: none;">Random regular </ins>graph (N=<ins style="font-weight: bold; text-decoration: none;">100, k=3</ins>).<ins style="font-weight: bold; text-decoration: none;">svg</ins>|left|200px|link=EvoLudoLab: Fixation times on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>|Fixation times on <del style="font-weight: bold; text-decoration: none;">the linear graph</del>]] ====</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==== [[EvoLudoLab: Fixation times on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>|Fixation times on <ins style="font-weight: bold; text-decoration: none;">random regular graphs</ins>]] ====</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{-}}</div></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2448&oldid=prev Hauert at 09:20, 29 August 2016 2016-08-29T09:20:30Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 02:20, 29 August 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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 <del style="font-weight: bold; text-decoration: none;">between vertices </del>\(i\) <del style="font-weight: bold; text-decoration: none;">and </del>\(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two <del style="font-weight: bold; text-decoration: none;">nodes </del>\(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:</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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 <ins style="font-weight: bold; text-decoration: none;">pointing from vertex </ins>\(i\) <ins style="font-weight: bold; text-decoration: none;">to vertex </ins>\(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two <ins style="font-weight: bold; text-decoration: none;">vertices </ins>\(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:</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>::&#039;&#039;Circulation Theorem:&#039;&#039; The Moran process on a graph results in the same fixation probability \(\rho_1\) of a single mutant as in an unstructured population if the graph is a circulation.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>::&#039;&#039;Circulation Theorem:&#039;&#039; The Moran process on a graph results in the same fixation probability \(\rho_1\) of a single mutant as in an unstructured population if the graph is a circulation.</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l102">Line 102:</td> <td colspan="2" class="diff-lineno">Line 102:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation probability on circulation graphs==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Fixation probability on circulation graphs==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Circulation Theorem.svg|thumb|300px|Circulation graph with one connected subset (shaded area) of mutants (orange). For every reproduction event along one of the solid arrows, the subset either shrinks, if a resident (blue) reproduced, or grows, if a mutant reproduces. Reproduction events along dashed arrows do not alter the population configuration.]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Image:Circulation Theorem.svg|thumb|300px|Circulation graph with one connected subset (shaded area) of mutants (orange). For every reproduction event along one of the solid arrows, the subset either shrinks, if a resident (blue) reproduced, or grows, if a mutant reproduces. Reproduction events along dashed arrows do not alter the population configuration.]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>At any point in time during the invasion process of mutants on a circulation graph, it is possible to identify connected subsets of <del style="font-weight: bold; text-decoration: none;">nodes </del>on the graph that are occupied by mutants such that all adjacent <del style="font-weight: bold; text-decoration: none;">nodes </del>of each subset are occupied by residents. Obviously, the state of the population changes only if a replacement occurs along one of the links connecting residents and mutants (see figure). Multiple such subsets may exist and, in fact, the evolutionary process may split large connected subsets of mutants into two smaller ones or may merge two previously unconnected subsets into one larger subset. For each subset, the circulation theorem establishes that the sum of the weights of links pointing out of the subset (connecting a mutant <del style="font-weight: bold; text-decoration: none;">node </del>to an adjacent resident <del style="font-weight: bold; text-decoration: none;">node</del>) equals the sum of the weights of links pointing into the subset (connecting an adjacent resident with a mutant <del style="font-weight: bold; text-decoration: none;">node </del>within the subset). Since the influx is balanced by the outflux, \(f_i^\text{in}=f_i^\text{out}\), for all <del style="font-weight: bold; text-decoration: none;">nodes</del>, increasing the mutant subset by replacing an adjacent resident <del style="font-weight: bold; text-decoration: none;">node </del>with a mutant or decreasing the subset by replacing a mutant with a resident, does not affect the flux balance of the subset. For the same reason, the balance remains unchanged if subsets merge or if one subset splits into two.  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>At any point in time during the invasion process of mutants on a circulation graph, it is possible to identify connected subsets of <ins style="font-weight: bold; text-decoration: none;">vertices </ins>on the graph that are occupied by mutants such that all adjacent <ins style="font-weight: bold; text-decoration: none;">vertices </ins>of each subset are occupied by residents. Obviously, the state of the population changes only if a replacement occurs along one of the links connecting residents and mutants (see figure). Multiple such subsets may exist and, in fact, the evolutionary process may split large connected subsets of mutants into two smaller ones or may merge two previously unconnected subsets into one larger subset. For each subset, the circulation theorem establishes that the sum of the weights of links pointing out of the subset (connecting a mutant <ins style="font-weight: bold; text-decoration: none;">vertex </ins>to an adjacent resident <ins style="font-weight: bold; text-decoration: none;">vertex</ins>) equals the sum of the weights of links pointing into the subset (connecting an adjacent resident with a mutant <ins style="font-weight: bold; text-decoration: none;">vertex </ins>within the subset). Since the influx is balanced by the outflux, \(f_i^\text{in}=f_i^\text{out}\), for all <ins style="font-weight: bold; text-decoration: none;">vertices</ins>, increasing the mutant subset by replacing an adjacent resident <ins style="font-weight: bold; text-decoration: none;">vertex </ins>with a mutant or decreasing the subset by replacing a mutant with a resident, does not affect the flux balance of the subset. For the same reason, the balance remains unchanged if subsets merge or if one subset splits into two.  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the <del style="font-weight: bold; text-decoration: none;">node </del>at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the <ins style="font-weight: bold; text-decoration: none;">vertex </ins>at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. The circulation theorem only ensures that the &#039;&#039;ratio&#039;&#039; of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. The circulation theorem only ensures that the &#039;&#039;ratio&#039;&#039; of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.</div></td></tr> </table> Hauert https://wiki.evoludo.org/index.php?title=Moran_graphs&diff=2443&oldid=prev Hauert: Created page with "{{InCharge|author1=Christoph Hauert}}__NOTOC__ Image:Circulation.svg|thumb|300px|Fairly generic sample population structure. Vertices represent individuals and links define..." 2016-08-29T09:10:00Z <p>Created page with &quot;{{InCharge|author1=Christoph Hauert}}__NOTOC__ Image:Circulation.svg|thumb|300px|Fairly generic sample population structure. Vertices represent individuals and links define...&quot;</p> <p><b>New page</b></p><div>{{InCharge|author1=Christoph Hauert}}__NOTOC__<br /> <br /> [[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&#039;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 theorem|circulation]] and hence a mutant has the same fixation probability as in the original [[Moran process]] for unstructured populations.]]<br /> 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. <br /> <br /> 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 between vertices \(i\) and \(j\). If \(w_{ij} =0\) and \(w_{ji} =0\) then the two nodes \(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:<br /> <br /> ::&#039;&#039;Circulation Theorem:&#039;&#039; The Moran process on a graph results in the same fixation probability \(\rho_1\) of a single mutant as in an unstructured population if the graph is a circulation.<br /> <br /> An [[#Fixation probability on circulation graphs|illustrative sketch of the proof]] follows below. In contrast to unstructured (well-mixed) populations, the state of a structured population is not simply determined by just the number of mutants (or residents) but rather needs to take the distribution of mutants and residents into account. Rather surprisingly, however, it turns out that for circulations the spatial distribution of mutants and residents does not affect their fixation probabilities. The observation that fixation probabilities remain unchanged for diverse population structures forms the basis for the conjecture by [[#References|Maruyama (1970)]] and [[#References|Slatkin (1981)]] speculating that population structure does not affect fixation probabilities. Indeed this is true for structures as diverse as [https://en.wikipedia.org/wiki/Complete_graph complete graphs] (every vertex is connected to every other vertex), lattices or [https://en.wikipedia.org/wiki/Random_regular_graph random regular graphs] (see e.g. [[#References|Bollobás, 1995]]).<br /> <br /> Last but not least, the circulation theorem indirectly suggests that some population structures &#039;&#039;do&#039;&#039; affect fixation probabilities. Thus, it becomes an intriguing question what population structures may act as [[evolutionary suppressors]] that suppress selection and enhance random drift (\(\rho&lt;\rho_1\) for \(r &gt; 1\)) or, conversely, as [[evolutionary amplifiers]] that enhance selection and suppresses random drift (\(\rho&gt;\rho_1\) for \(r &gt; 1\)).<br /> {{-}}<br /> <br /> ==Evolutionary dynamics on Moran graphs==<br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Complete graph (N=1000).png|left|200px|link=EvoLudoLab: Moran process on the complete graph]]<br /> ==== [[EvoLudoLab: Moran process on the complete graph|Evolutionary dynamics on the complete graph]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Rectangular lattice (N=51x51).png|left|200px|link=EvoLudoLab: Moran process on the rectangular lattice]]<br /> ==== [[EvoLudoLab: Moran process on the rectangular lattice|Evolutionary dynamics on the rectangular lattice]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Random regular graph (N=1000).svg|left|200px|link=EvoLudoLab: Moran process on random regular graphs]]<br /> ==== [[EvoLudoLab: Moran process on random regular graphs|Evolutionary dynamics on random regular graphs]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Linear graph (N=150).png|left|200px|link=EvoLudoLab: Moran process on the linear graph]]<br /> ==== [[EvoLudoLab: Moran process on the linear graph|Evolutionary dynamics on the linear graph]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> ==Fixation probabilities on Moran graphs==<br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Complete graph (N=100).png|left|200px|link=EvoLudoLab: Fixation probabilities on the complete graph]]<br /> ==== [[EvoLudoLab: Fixation probabilities on the complete graph|Fixation probabilities on the complete graph]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Rectangular lattice (N=9x9).png|left|200px|link=EvoLudoLab: Fixation probabilities on the rectangular lattice]]<br /> ==== [[EvoLudoLab: Fixation probabilities on the rectangular lattice|Fixation probabilities on the rectangular lattice]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Random regular graph (N=100).svg|left|200px|link=EvoLudoLab: Fixation probabilities on random regular graphs]]<br /> ==== [[EvoLudoLab: Fixation probabilities on random regular graphs|Fixation probabilities on random regular graphs]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Linear graph (N=150).png|left|200px|link=EvoLudoLab: Fixation probabilities on the linear graph]]<br /> ==== [[EvoLudoLab: Fixation probabilities on the linear graph|Fixation probabilities on the linear graph]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> ==Fixation times on Moran graphs==<br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Complete graph (N=100).png|left|200px|link=EvoLudoLab: Fixation times on the complete graph]]<br /> ==== [[EvoLudoLab: Fixation times on the complete graph|Fixation times on the complete graph]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Rectangular lattice (N=9x9).png|left|200px|link=EvoLudoLab: Fixation times on the rectangular lattice]]<br /> ==== [[EvoLudoLab: Fixation times on the rectangular lattice|Fixation times on the rectangular lattice]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Random regular graph (N=100).svg|left|200px|link=EvoLudoLab: Fixation times on random regular graphs]]<br /> ==== [[EvoLudoLab: Fixation times on random regular graphs|Fixation times on random regular graphs]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> &lt;div class=&quot;lab_description Moran&quot;&gt;<br /> [[Image:Linear graph (N=150).png|left|200px|link=EvoLudoLab: Fixation times on the linear graph]]<br /> ==== [[EvoLudoLab: Fixation times on the linear graph|Fixation times on the linear graph]] ====<br /> .<br /> {{-}}<br /> &lt;/div&gt;<br /> <br /> ==Fixation probability on circulation graphs==<br /> [[Image:Circulation Theorem.svg|thumb|300px|Circulation graph with one connected subset (shaded area) of mutants (orange). For every reproduction event along one of the solid arrows, the subset either shrinks, if a resident (blue) reproduced, or grows, if a mutant reproduces. Reproduction events along dashed arrows do not alter the population configuration.]]<br /> At any point in time during the invasion process of mutants on a circulation graph, it is possible to identify connected subsets of nodes on the graph that are occupied by mutants such that all adjacent nodes of each subset are occupied by residents. Obviously, the state of the population changes only if a replacement occurs along one of the links connecting residents and mutants (see figure). Multiple such subsets may exist and, in fact, the evolutionary process may split large connected subsets of mutants into two smaller ones or may merge two previously unconnected subsets into one larger subset. For each subset, the circulation theorem establishes that the sum of the weights of links pointing out of the subset (connecting a mutant node to an adjacent resident node) equals the sum of the weights of links pointing into the subset (connecting an adjacent resident with a mutant node within the subset). Since the influx is balanced by the outflux, \(f_i^\text{in}=f_i^\text{out}\), for all nodes, increasing the mutant subset by replacing an adjacent resident node with a mutant or decreasing the subset by replacing a mutant with a resident, does not affect the flux balance of the subset. For the same reason, the balance remains unchanged if subsets merge or if one subset splits into two. <br /> <br /> Recall that the number of mutants in the population changes only if a replacement occurs along any link that connects residents with mutants or vice versa. Because the Moran process essentially selects links with a probability proportional to the link weight and the fitness of the node at its tail, it follows that for each subset, the probability that another mutant is added is simply given by \(r/(1 + r)\) and the complementary probability to remove one mutant is \(1/(1 + r)\). Since this holds for each subset, it also holds for the entire population and is independent of the number, size, shape and distribution of mutant subsets. This invariance applies only if the circulation theorem is satisfied. Consequentially, the fixation probability on circulation graphs reduces to the recursive equation derived for the original [[Moran process]].<br /> <br /> Note that even though the fixation probabilities remain unchanged on circulation graphs, the corresponding fixation times are very sensitive to the details of the population structure and pose a much harder problem. The circulation theorem only ensures that the &#039;&#039;ratio&#039;&#039; of the transition probabilities \(T^+/T^− = r\) remains unchanged, i.e. independent of the number and distribution of residents and mutants, but even on circulation graphs \(T^+\) and \(T^−\) depend not only on the number but also on the distribution of mutants. Generally, population structures tend to substantially increase the fixation times because the structure limits the possibilities for mutants to conquer new vertices.<br /> {{-}}<br /> <br /> ==Publications==<br /> #Lieberman, E., Hauert, C. &amp; Nowak, M. (2005) Evolutionary dynamics on graphs &#039;&#039;Nature&#039;&#039; &#039;&#039;&#039;433&#039;&#039;&#039; 312-316 [http://dx.doi.org/10.1038/nature03204 doi: 10.1038/nature03204].<br /> <br /> ===References===<br /> #Bollobás, B. (1995) Random Graphs, New York, Academic.<br /> #Maruyama, T. (1974) A Simple Proof that Certain Quantities are Independent of the Geographical Structure of Population &#039;&#039;Theor. Pop. Biol.&#039;&#039; &#039;&#039;&#039;5&#039;&#039;&#039; 148-154.<br /> #Slatkin, M. (1981) Fixation probabilities and fixation times in a subdivided population &#039;&#039;Evolution&#039;&#039; &#039;&#039;&#039;35&#039;&#039;&#039; 477-488.<br /> <br /> [[Category:Evolutionary graph theory]][[Category:Tutorial]]</div> Hauert