Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating. (English) Zbl 1519.92149
Summary: The paper deals with two interrelated topics: (1) identifying transient amplifiers in an iterative process, and (2) analyzing the process by its spectral dynamics, which is the change in the graph spectra by edge manipulation. Transient amplifiers are networks representing population structures which shift the balance between natural selection and random drift. Thus, amplifiers are highly relevant for understanding the relationships between spatial structures and evolutionary dynamics. We study an iterative procedure to identify transient amplifiers for death-birth updating. The algorithm starts with a regular input graph and iteratively removes edges until desired structures are achieved. Thus, a sequence of candidate graphs is obtained. The edge removals are guided by quantities derived from the sequence of candidate graphs. Moreover, we are interested in the Laplacian spectra of the candidate graphs and analyze the iterative process by its spectral dynamics. The results show that although transient amplifiers for death-birth updating are generally rare, a substantial number of them can be obtained by the proposed procedure. The graphs identified share structural properties and have some similarity to dumbbell and barbell graphs. We analyze amplification properties of these graphs and also two more families of bell-like graphs and show that further transient amplifiers for death-birth updating can be found. Finally, it is demonstrated that the spectral dynamics possesses characteristic features useful for deducing links between structural and spectral properties. These feature can also be taken for distinguishing transient amplifiers among evolutionary graphs in general.
MSC:
| 92D15 | Problems related to evolution |
| 60J85 | Applications of branching processes |
| 05C90 | Applications of graph theory |
Keywords:
evolutionary dynamics; transient amplifiers; regular graphs; Laplacian spectra; edge manipulationReferences:
| [1] | Adlam, B.; Chatterjee, K.; Nowak, MA, Amplifiers of selection, Proc R Soc A, 471, 20150114 (2015) · Zbl 1371.92093 · doi:10.1098/rspa.2015.0114 |
| [2] | Alcalde Cuesta, F.; González Sequeiros, P.; Lozano Rojo, Á.; Vigara Benito, R.; Rojas, I.; Ortuño, F., An accurate database of the fixation probabilities for all undirected graphs of order 10 or less, Bioinformatics and biomedical engineering. IWBBIO 2017. LNCS 10209, 209-220 (2017), Cham: Springer, Cham |
| [3] | Allen, B.; Lippner, G.; Chen, YT; Fotouhi, B.; Momeni, N.; Yau, ST; Nowak, MA, Evolutionary dynamics on any population structure, Nature, 544, 227-230 (2017) · doi:10.1038/nature21723 |
| [4] | Allen, B.; Lippner, G.; Nowak, MA, Evolutionary games on isothermal graphs, Nat Commun, 10, 5107 (2019) · doi:10.1038/s41467-019-13006-7 |
| [5] | Allen, B.; Sample, C.; Jencks, R.; Withers, J.; Steinhagen, P.; Brizuela, L.; Kolodny, J.; Parke, D.; Lippner, G.; Dementieva, YA, Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs, PLoS Comput Biol, 16, 1 (2020) · doi:10.1371/journal.pcbi.1007529 |
| [6] | Allen, B.; Sample, C.; Steinhagen, P.; Shapiro, J.; King, M.; Hedspeth, T.; Goncalves, M., Fixation probabilities in graph-structured populations under weak selection, PLoS Comput Biol, 17, 2 (2021) · doi:10.1371/journal.pcbi.1008695 |
| [7] | Arvind, V.; Torán, J., Isomorphism testing: perspectives and open problems, Bull Eur Assoc Theor Comput Sci, 86, 66-84 (2005) · Zbl 1169.68440 |
| [8] | Atay, FM; Tuncel, H., On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication, Linear Algebra Appl, 442, 165-177 (2014) · Zbl 1282.05088 · doi:10.1016/j.laa.2013.08.022 |
| [9] | Babai, L.; Sirakov, B.; Ney de Souza, P.; Viana, M., Groups, graphs, algorithms: the graph isomorphism problem, Proceedings of International Congress of Mathematicians (ICM 2018), 3319-3336 (2019), Singapore: World Scientific, Singapore · Zbl 1490.68116 · doi:10.1142/9789813272880_0183 |
| [10] | Banerjee, A.; Jost, J., On the spectrum of the normalized graph Laplacian, Linear Algebra Appl, 428, 3015-3022 (2008) · Zbl 1149.05327 · doi:10.1016/j.laa.2008.01.029 |
| [11] | Banerjee, A.; Jost, J., Graph spectra as a systematic tool in computational biology, Discrete Appl Math, 157, 10, 2425-2431 (2009) · Zbl 1172.92001 · doi:10.1016/j.dam.2008.06.033 |
| [12] | Banerjee, A., Structural distance and evolutionary relationship of networks, Biosystems, 107, 186-196 (2012) · doi:10.1016/j.biosystems.2011.11.004 |
| [13] | Bondy, JA; Murty, USR, Graph theory (2008), Berlin: Springer, Berlin · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [14] | Butler, S.; Grout, J., A construction of cospectral graphs for the normalized Laplacian, Electron J Combin, 18, 1, 231 (2011) · Zbl 1243.05144 · doi:10.37236/718 |
| [15] | Cannataro, VL; McKinley, SA; St Mary, CM, The implications of small stem cell niche sizes and the distribution of fitness effects of new mutations in aging and tumorigenesis, Evol Appl, 9, 4, 565-582 (2016) · doi:10.1111/eva.12361 |
| [16] | Cannataro, VL; McKinley, SA; St Mary, CM, The evolutionary trade-off between stem cell niche size, aging, and tumorigenesis, Evol Appl, 10, 6, 590-602 (2017) · doi:10.1111/eva.12476 |
| [17] | Chan, H.; Akoglu, L., Optimizing network robustness by edge rewiring: a general framework, Data Min Knowl Disc, 30, 1395-1425 (2006) · Zbl 1409.05190 · doi:10.1007/s10618-015-0447-5 |
| [18] | Chen, H.; Zhang, F., Spectral dynamics of graph sequences generated by subdivision and triangle extension, Electron J Linear Algebra, 32, 454-463 (2017) · Zbl 1386.05104 · doi:10.13001/1081-3810.3583 |
| [19] | Chen, G.; Davis, G.; Hall, F.; Li, Z.; Patel, K.; Steward, M., An interlacing result on normalized Laplacians, SIAM J Discrete Math, 18, 353-361 (2004) · Zbl 1079.05054 · doi:10.1137/S0895480103438589 |
| [20] | Eldan, R.; Racz, MZ; Schramm, T., Braess’s paradox for the spectral gap in random graphs and delocalization of eigenvectors, Random Struct Algorithms, 50, 4, 584-611 (2017) · Zbl 1368.05132 · doi:10.1002/rsa.20696 |
| [21] | Ghosh A, Boyd S (2006) Growing well-connected graphs. In: Misra P (ed) Proceedings of 45th IEEE conference on decision and control, 2006, pp 6605-6611 |
| [22] | Ghosh, A.; Boyd, S.; Saberi, A., Minimizing effective resistance of a graph, SIAM Rev, 50, 37-66 (2008) · Zbl 1134.05057 · doi:10.1137/050645452 |
| [23] | Gu, J.; Jost, J.; Liu, S.; Stadler, PF, Spectral classes of regular, random, and empirical graphs, Linear Algebra Appl, 489, 30-49 (2016) · Zbl 1327.05205 · doi:10.1016/j.laa.2015.08.038 |
| [24] | Hindersin, L.; Traulsen, A., Most undirected random graphs are amplifiers of selection for birth-death dynamics, but suppressors of selection for death-birth dynamics, PLoS Comput Biol, 11, 11 (2015) · doi:10.1371/journal.pcbi.1004437 |
| [25] | Hindersin, L.; Werner, B.; Dingli, D.; Traulsen, A., Should tissue structure suppress or amplify selection to minimize cancer risk?, Biol Direct, 11, 1, 41 (2016) · doi:10.1186/s13062-016-0140-7 |
| [26] | Hindersin, L.; Wu, B.; Traulsen, A.; Garcia, J., Computation and simulation of evolutionary game dynamics in finite populations, Sci Rep, 9, 6946 (2019) · doi:10.1038/s41598-019-43102-z |
| [27] | Hoffman, C.; Kahle, M.; Paquette, E., Spectral gaps of random graphs and applications, Int Math Res Not, rnz077, 1-52 (2019) |
| [28] | Jamieson-Lane, A.; Hauert, C., Fixation probabilities on superstars, revisited and revised, J Theor Biol, 382, 44-56 (2015) · Zbl 1402.92315 · doi:10.1016/j.jtbi.2015.06.029 |
| [29] | Komarova, NL; Sengupta, A.; Nowak, MA, Mutation-selection networks of cancer initiation: tumor suppressor genes and chromosomal instability, J Theor Biol, 223, 433-450 (2003) · Zbl 1464.92067 · doi:10.1016/S0022-5193(03)00120-6 |
| [30] | Komarova, NL, Spatial stochastic models for cancer initiation and progression, Bull Math Biol, 68, 7, 1573-1599 (2006) · Zbl 1334.92202 · doi:10.1007/s11538-005-9046-8 |
| [31] | Krieger, MS; Denison, CE; Anderson, TL; Nowak, MA; Hill, AL, Population structure across scales facilitates coexistence and spatial heterogeneity of antibiotic-resistant infections, PLoS Comput Biol, 16, 7 (2020) · doi:10.1371/journal.pcbi.1008010 |
| [32] | Li, G.; Hao, ZF; Huang, H.; Wei, H., Maximizing algebraic connectivity via minimum degree and maximum distance, IEEE Access, 6, 41249-41255 (2018) · doi:10.1109/ACCESS.2018.2857411 |
| [33] | Lieberman, E.; Hauert, C.; Nowak, MA, Evolutionary dynamics on graphs, Nature, 433, 312-316 (2005) · doi:10.1038/nature03204 |
| [34] | McAvoy, A.; Allen, B., Fixation probabilities in evolutionary dynamics under weak selection, J Math Biol, 82, 14 (2021) · Zbl 1460.92144 · doi:10.1007/s00285-021-01568-4 |
| [35] | Mehatari, R.; Banerjee, A., Effect on normalized graph Laplacian spectrum by motif attachment and duplication, Appl Math Comput, 261, 382-387 (2015) · Zbl 1410.05136 |
| [36] | Meringer, M., Fast generation of regular graphs and construction of cages, J Graph Theory, 30, 137-146 (1999) · Zbl 0918.05062 · doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G |
| [37] | Monk, T., Martingales and the fixation probability of high-dimensional evolutionary graphs, J Theor Biol, 451, 10-18 (2018) · Zbl 1397.92507 · doi:10.1016/j.jtbi.2018.04.039 |
| [38] | Monk, T.; Green, P.; Paulin, M., Martingales and fixation probabilities of evolutionary graphs, Proc R Soc A, 470, 20130730 (2014) · doi:10.1098/rspa.2013.0730 |
| [39] | Möller, M.; Hindersin, L.; Traulsen, A., Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time, Commun Biol, 2, 137 (2019) · doi:10.1038/s42003-019-0374-x |
| [40] | Nowak, MA; Michor, F.; Iwasa, Y., The linear process of somatic evolution, Proc Natl Acad Sci, 100, 25, 14966-14969 (2003) · doi:10.1073/pnas.2535419100 |
| [41] | Ohtsuki, H.; Pacheco, JM; Nowak, MA, Evolutionary graph theory: breaking the symmetry between interaction and replacement, J Theor Biol, 246, 681-694 (2007) · Zbl 1451.92229 · doi:10.1016/j.jtbi.2007.01.024 |
| [42] | Ottino-Löffler, B.; Scott, JG, Evolutionary dynamics of incubation periods, eLife (2017) · doi:10.7554/eLife.30212.001 |
| [43] | Ottino-Löffler, B.; Scott, JG; Strogatz, SH, Takeover times for a simple model of network infection, Phys Rev E, 96 (2017) · doi:10.1103/PhysRevE.96.012313 |
| [44] | Pattni, K.; Broom, M.; Silvers, L.; Rychtar, J., Evolutionary graph theory revisited: when is an evolutionary process equivalent to the Moran process?, Proc R Soc A, 471, 20150334 (2015) · Zbl 1371.92098 · doi:10.1098/rspa.2015.0334 |
| [45] | Pavlogiannis, A.; Tkadlec, J.; Chatterjee, K.; Nowak, MA, Amplification on undirected population structures: comets beat stars, Sci Rep, 7, 1-8 (2017) · doi:10.1038/s41598-017-00107-w |
| [46] | Pavlogiannis, A.; Tkadlec, J.; Chatterjee, K.; Nowak, MA, Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory, Commun Biol, 1, 71 (2018) · doi:10.1038/s42003-018-0078-7 |
| [47] | Read, RC; Wilson, RJ, An atlas of graphs (1998), Oxford: Oxford University Press, Oxford · Zbl 0908.05001 |
| [48] | Richter, H.; Engelbrecht, AP, Recent advances in the theory and application of fitness landscapes (2014), Berlin: Springer, Berlin |
| [49] | Richter, H., Dynamic landscape models of coevolutionary games, Biosystems, 153-154, 26-44 (2017) · doi:10.1016/j.biosystems.2017.02.002 |
| [50] | Richter, H., Properties of network structures, structure coefficients, and benefit-to-cost ratios, Biosystems, 180, 88-100 (2019) · doi:10.1016/j.biosystems.2019.03.005 |
| [51] | Richter, H., Fixation properties of multiple cooperator configurations on regular graphs, Theory Biosci, 138, 261-275 (2019) · doi:10.1007/s12064-019-00293-3 |
| [52] | Richter, H., Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs, J Math Biol, 82, 61 (2021) · Zbl 1466.92129 · doi:10.1007/s00285-021-01609-y |
| [53] | Shine, A.; Kempe, D.; Liu, L.; White, R., Generative graph models based on Laplacian spectra?, WWW’19: the world wide web conference, 1691-1701 (2019), New York: ACM, New York · doi:10.1145/3308558.3313631 |
| [54] | Sydney, A.; Scoglio, C.; Gruenbacher, D., Optimizing algebraic connectivity by edge rewiring, Appl Math Comput, 219, 10, 5465-5479 (2013) · Zbl 1280.05072 |
| [55] | Tkadlec, J.; Pavlogiannis, A.; Chatterjee, K.; Nowak, MA, Population structure determines the tradeoff between fixation probability and fixation time, Commun Biol, 2, 138 (2019) · doi:10.1038/s42003-019-0373-y |
| [56] | Tkadlec, J.; Pavlogiannis, A.; Chatterjee, K.; Nowak, MA, Limits on amplifiers of natural selection under death-Birth updating, PLoS Comput Biol, 16, 1 (2020) · doi:10.1371/journal.pcbi.1007494 |
| [57] | Tkadlec, J.; Pavlogiannis, A.; Chatterjee, K.; Nowak, MA, Fast and strong amplifiers of natural selection, Nat Commun, 12, 4009 (2021) · doi:10.1038/s41467-021-24271-w |
| [58] | van den Heuvel, J., Hamilton cycles and eigenvalues of graphs, Linear Algebra Appl, 226-228, 723-730 (1995) · Zbl 0846.05059 · doi:10.1016/0024-3795(95)00254-O |
| [59] | van Nimwegen, E.; Crutchfield, JP, Metastable evolutionary dynamics: crossing fitness barriers or escaping via neutral paths?, Bull Math Biol, 62, 5, 799-848 (2000) · Zbl 1323.92146 · doi:10.1006/bulm.2000.0180 |
| [60] | Vermeulen, L.; Morrissey, E.; van der Heijden, M.; Nicholson, AM; Sottoriva, A.; Buczacki, S.; Kemp, R.; Tavar, S.; Winton, DJ, Defining stem cell dynamics in models of intestinal tumor initiation, Science, 342, 6161, 995-998 (2013) · doi:10.1126/science.1243148 |
| [61] | Wang, J.; Huang, Q.; Belardo, F.; Marzi, EML, A note on the spectral characterization of dumbbell graphs, Linear Algebra Appl, 437, 1707-1714 (2009) · Zbl 1175.05089 · doi:10.1016/j.laa.2009.06.009 |
| [62] | Wills, P.; Meyer, FG, Metrics for graph comparison: a practitioner’s guide, PLoS ONE, 15, 2 (2020) · doi:10.1371/journal.pone.0228728 |
| [63] | WolframMathWorld: regular graphs. https://mathworld.wolfram.com/RegularGraph.html. Accessed 24 Apr 2022 |
| [64] | Zhang, F.; Chen, YC; Chen, Z., Clique-inserted-graphs and spectral dynamics of clique-inserting, J Math Anal Appl, 349, 211-225 (2009) · Zbl 1148.05048 · doi:10.1016/j.jmaa.2008.08.036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
