Source-linked AI summary
Evolutionary dynamics on any population structure
Benjamin Allen, Gabor Lippner, Yu-Ting Chen, Babak Fotouhi, Naghmeh Momeni, Martin A. Nowak, Shing-Tung Yau
TL;DR
The paper addresses the open problem of identifying favored traits on heterogeneous population structures, where arbitrary-selection analysis lacks an efficient general solution. It derives a weak-selection formula using coalescent theory and random-walk meeting times, finding that cooperation is favored under graph-dependent conditions and especially in structures with strong pairwise ties.
Problem
Determining which trait selection favors on heterogeneous graphs remained open, while the arbitrary-selection problem is computationally difficult.
Method
The paper uses coalescent theory, random-walk meeting times, and evolutionary Markov-chain analysis to derive weak-selection fixation conditions.
Results
Under weak selection, cooperation is favored when its fixation probability exceeds 1/N, with the condition determined by graph structure.
Takeaways & Limitations
The formula enables evaluation of diverse heterogeneous population structures and analysis of how graph surgery changes evolutionary outcomes.
Abstract
from arXiv · showhide
Evolution occurs in populations of reproducing individuals. The structure of a biological population affects which traits evolve. Understanding evolutionary game dynamics in structured populations is difficult. Precise results have been absent for a long time, but have recently emerged for special structures where all individuals have the same number of neighbors. But the problem of determining which trait is favored by selection in the natural case where the number of neighbors can vary, has remained open. For arbitrary selection intensity, the problem is in a computational complexity class which suggests there is no efficient algorithm. Whether there exists a simple solution for weak selection was unanswered. Here we provide, surprisingly, a general formula for weak selection that applies to any graph or social network. Our method uses coalescent theory and relies on calculating the meeting times of random walks. We can now evaluate large numbers of diverse and heterogeneous population structures for their propensity to favor cooperation. We can also study how small changes in population structure---graph surgery---affect evolutionary outcomes. We find that cooperation flourishes most in societies that are based on strong pairwise ties.
D.4 Recurrence relations for coalescence times
The paper models evolutionary dynamics on weighted connected graphs using random walks and coalescent times, with weak selection analyzed as a perturbation of neutral drift.
- D.4 Recurrence relations for coalescence times: Random-walk steps follow edge-weight proportions, producing a stationary distribution proportional to weighted degree and a reversibility relation.The framework also averages quantities over random-walk endpoints, including the two ends of a walk started from stationarity.
- D.4 Recurrence relations for coalescence times: Under Death-Birth updating, reproduction rates are Fi(s) = 1 + δfi(s), and replacement events copy a reproducer’s type into a replaced vertex.The evolutionary process is a continuous-time Markov chain with two absorbing fixation states.
- D.4 Recurrence relations for coalescence times: Weak selection is analyzed by expanding fixation probabilities to first order in δ around the neutral process.The analysis focuses biologically on a new type initially occupying one uniformly chosen vertex.
- D.4 Recurrence relations for coalescence times: Neutral drift makes degree-weighted type frequency a martingale, so a single neutral mutation at vertex i fixes with probability πi.The weighting πi is interpreted as the reproductive value of vertex i.
- D.4 Recurrence relations for coalescence times: Coalescence times are expected meeting times of two independent random walks and can be computed by solving a linear system.For connected graphs, the system has a unique solution and all coalescence times are obtainable in polynomial time.
E.1 General case
The general weak-selection condition expresses cooperation’s success through coalescence-time combinations, yielding a graph-specific critical benefit-to-cost ratio.
- E.1 General case: Cooperation is favored under weak selection precisely when its fixation probability exceeds the neutral benchmark 1/N.The resulting condition is equivalent to the main text’s general criterion and also determines when defectors fall below neutrality.
- E.1 General case: For graph families satisfying the locality property, the critical benefit-to-cost ratio becomes (b/c)∗ = 1/¯p.The result follows from asymptotic behavior of the coalescence-time sums.
E.3 Weighted regular graphs
For weighted regular graphs, fixation and cooperation conditions simplify because vertices share the same weighted neighborhood distribution. In loopless graphs, the relevant return probability is determined by the Simpson degree.
- Weighted regular graphs have identical outgoing weight distributions, giving π_i = 1/N for every vertex.
- In loopless weighted regular graphs, the one-step return probability is zero and the two-step return probability is p^(2) = 1/κ.
- For unweighted regular graphs, the Simpson degree κ equals the topological degree k.
- Under weak selection, strategy A is favored in an arbitrary pairwise game when σa + b > c + σd, with σ computed from meeting times.
- For equal gains from switching, the condition σa + b > c + σd implies ρA > 1/N > ρB; otherwise it only establishes ρA > ρB.
H Bounds on (b/c)∗and σ
Meeting-time inequalities yield universal bounds on the structure coefficient and critical benefit-cost ratio for connected weighted graphs. The two-vertex case is exceptional, while ratios can approach one in larger graphs.
- These bounds follow from inequalities among the meeting times τ^(1), τ^(2), and τ^(3), which ensure positivity of σ’s numerator and denominator.
- The proof uses a variational argument that fixes weights adjacent to one vertex while varying nonadjacent edge weights, including directed nonadjacent edges.
- Equality in the meeting-time bounds is restricted to graphs of size two, with self-loops excluded for some inequalities.
- For every connected weighted graph with N ≥ 3, σ > 0 and |(b/c)∗| > 1.
- For N = 2, fixation is determined by the first death event, so ρA = ρB = 1/2 regardless of the game and both σ and (b/c)∗ are undefined.
- The critical ratio (b/c)∗ can approach 1, equivalently allowing σ to become arbitrarily large; whether it can approach −1 is left unclear.
I Arbitrary mutation rates
The analysis extends weak-selection results to arbitrary mutation rates through mutation-selection stationarity and identity-by-descent probabilities. It also generalizes the framework across several model variations.
- Mutation occurs with probability u per reproduction; otherwise offspring inherit the parent’s type, with mutations equally likely to produce either type.
- For u > 0, the evolutionary process has a unique mutation-selection stationary distribution, where A is favored if its degree-weighted abundance exceeds one half.
- Identity-by-descent probabilities q_ij quantify whether two occupants share a common ancestor without mutation and are obtained from equations on arbitrary weighted connected graphs.
- For the donation game and arbitrary 2 × 2 games, weak-selection success conditions can be expressed using identity-by-descent probabilities and the structure coefficient.
- In the low-mutation limit, identity-by-descent conditions are equivalent to the coalescence-time condition for weak-selection fixation.
- The methods also extend to accumulated payoffs, distinct interaction and replacement graphs, and Birth-Death updating.
J.1 Accumulated payoffs
The framework is adapted to accumulated payoffs, separate interaction and replacement graphs, and Birth-Death updating. Each variation yields conditions expressed through appropriately modified random walks or coalescence times.
- J.1 Accumulated payoffs: Accumulated payoffs sum edge-weighted neighbor payoffs without normalization, and their fixation probabilities produce a corresponding critical benefit-cost ratio.
- J.1 Accumulated payoffs: When interaction and replacement graphs differ, the population structure is represented by weighted graphs (G, I), with G connected and I not necessarily connected.
- J.1 Accumulated payoffs: An (n, m)-random walk takes n steps on the replacement graph G followed by m steps on the interaction graph I.
- J.1 Accumulated payoffs: The resulting fixation analysis carries over with replacement-graph weights defining π_i, and yields a critical benefit-cost ratio for the two-graph setting.
- J.1 Accumulated payoffs: Under Birth-Death updating, an individual reproduces in proportion to reproductive rate and replaces a random neighbor selected by edge weight.
- J.1 Accumulated payoffs: Birth-Death analysis uses inverse degree as reproductive value and a continuous-time coalescing random walk with transition rate w_ij/w_j.
- J.1 Accumulated payoffs: The modified coalescence-time equations have a unique solution when G is connected, obtainable in polynomial time.
J.3.3 Condition for success
The fixation probability of cooperation and the critical benefit-to-cost ratio are obtained from coalescence-time equations for weighted island structures.
- J.3.3 Condition for success: The fixation probability of cooperation is obtained by combining Eqs. (20), (64), and (66).
- J.3.3 Condition for success: The critical benefit-cost ratio is then derived from the resulting fixation analysis.
- J.3.3 Condition for success: Coalescence times for pairs of vertices on the same or different islands satisfy recurrence relations used to derive the success condition.The island structure assigns distinct coalescence times to within-island and between-island pairs.
K.1.1 Two islands
For two islands, the critical benefit-to-cost ratio is derived exactly and analyzed as a function of island-size imbalance and migration weight. Equal island sizes approach a local infimum as between-island weight vanishes.
- K.1.1 Two islands: The exact two-island critical b/c ratio is expressed as a numerator divided by a denominator depending on total size, island-size difference, and migration weight.Here N=N1+N2 and D=|N1−N2|.
- K.1.1 Two islands: When islands are evenly sized, D=0, simplifying the critical-ratio expression.
- K.1.1 Two islands: The evenly sized two-island value is at least a local infimum of the critical b/c ratio.
- K.1.1 Two islands: For D=0 and N≥4, the critical b/c ratio approaches an infimum as m→0.
K.1.2 More than two islands
For more than two islands, the analysis finds that equal island sizes minimize the limiting critical benefit-to-cost ratio in the examined cases, with the general equal-size expression minimized as migration becomes very small.
- K.1.2 More than two islands: For three and four islands, the limiting critical b/c ratio as m→0 is minimized when islands are evenly sized.The exact expressions are obtained but are too lengthy to record.
- K.1.2 More than two islands: For five islands, under the assumption that two islands have equal size, the remaining three minimize the limiting ratio when they also share one size.
- K.1.2 More than two islands: For any number of evenly sized islands, the critical b/c ratio is minimized as m→0.The result applies to arbitrary migration for Ni=N/n.
- K.1.2 More than two islands: The limiting value is approached when m≪1/n, and is conjectured to be a global infimum under Ni≥2.The conjecture covers fixed N≥4, n≥2, positive m<1, and arbitrary island-size distributions.
- K.1.2 More than two islands: The appendix also derives coalescence-based results for several star-graph connections and a ceiling-fan graph.These cases include hub-hub, leaf-hub, and leaf-leaf connections between stars.
K.4 Wheel
The wheel analysis derives coalescence times for leaf pairs at different separations and for leaf-hub pairs, then uses them to calculate the critical benefit-to-cost ratio.
- K.4 Wheel: In a wheel graph, leaf-pair coalescence times are indexed by their separation j, while τLH denotes the leaf-hub coalescence time.The boundary cases are τL,0=τL,n=0.
- K.4 Wheel: The wheel recurrence relates τL,j to neighboring leaf-pair times and τLH for 1≤j≤n−1.
- K.4 Wheel: An ansatz is substituted into the recurrence to obtain the solutions for the coalescence times.
- K.4 Wheel: The parameter γ can be chosen as (3−√5)/2 without affecting the result, after which b is solved from the recurrence equations.
- K.4 Wheel: The resulting expressions provide τLH and leaf-pair coalescence times, including τL,1, before the critical b/c ratio is calculated.
- K.4 Wheel: The success conditions are based on fixation probability and, with mutation, expected degree-weighted abundance; fitness and inclusive-fitness interpretations are also calculated.Inclusive fitness is considered specifically for the donation game.
L.1 Fitness
This section formulates fitness for heterogeneous graph populations using reproductive values and weak-selection effects. General games require triplet identity-by-descent probabilities for explicit evaluation, whereas the donation game requires only pairwise probabilities.
- Heterogeneous vertices have different reproductive values because their expected contributions to the future gene pool differ even under neutral drift.
- An individual’s fitness is defined from survival, its reproductive value, and the reproductive values of offspring produced over a short interval.
- The fitness expression separates neutral fitness, equal to reproductive value π_i, from the weak-selection effect on individual i.
- For arbitrary matrix games, explicit overall direct-fitness effects require triplet identity-by-descent probabilities and are beyond the work’s scope.
- For the donation game, overall direct-fitness effects can instead be computed using only pairwise identity-by-descent probabilities.
L.2 Inclusive fitness
Inclusive fitness is well-defined here for the donation game because cooperation’s effects separate by individual and are symmetric across vertices. For general games, the quadratic fitness effect prevents assigning an inclusive-fitness effect to one individual.
- Inclusive fitness combines an individual’s effect on its own fitness with weighted effects on others, using genetic relatedness as the weights.
- For general games, the quadratic direct-fitness effect does not separate into contributions from particular individuals, so no single-individual inclusive-fitness effect exists.
- For the donation game, the direct-fitness effect is linear and separates into distinct contributions from particular individuals.
- Reversibility makes fitness effects symmetric, with cooperation at i affecting j equally to cooperation at j affecting i.
- The donation game therefore has equal direct and inclusive fitness effects in every state, but this result is idiosyncratic to the model’s reversibility property.
M Computational issues
Computing coalescence times requires solving large linear systems, but symmetric diagonally dominant solvers improve scalability and permit analysis of many graphs. Experiments combine large graph ensembles, empirical networks, and Monte Carlo validation.
- Coalescence-time computation by Gaussian elimination takes O(N^6) steps, while block-wise inversion with fast matrix multiplication reduces this to O(N^4.75).
- The coalescence-time system is symmetric diagonally dominant, allowing approximate solutions in nearly linear time in the number of non-zero matrix entries.
- A MATLAB implementation required 12 seconds for N = 1000 with average degree 4, and 120 seconds for N = 2000 with average degree 4.
- The study computed critical b/c ratios for 1.3 million unweighted graphs from 10 random graph models and for several large real-world networks.
- The Framingham Study graph had N = 5253, average degree 6.5, critical b/c ratio 7.96, and a running time of around 3.5 hours.
- Monte Carlo simulations tested weak-selection results beyond their exact regime using 5×10^5 trials per graph and finite absorption time T = 400000.