• Previous Article
    Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments
  • DCDS-B Home
  • This Issue
  • Next Article
    Persistent two-dimensional strange attractors for a two-parameter family of Expanding Baker Maps
February  2019, 24(2): 671-694. doi: 10.3934/dcdsb.2018202

Invasion fronts on graphs: The Fisher-KPP equation on homogeneous trees and Erdős-Réyni graphs

1. 

Franklin W. Olin College of Engineering, Needham, MA 02492, USA

2. 

Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030, USA

Received  June 2017 Revised  January 2018 Published  June 2018

We study the dynamics of the Fisher-KPP equation on the infinite homogeneous tree and Erdős-Réyni random graphs. We assume initial data that is zero everywhere except at a single node. For the case of the homogeneous tree, the solution will either form a traveling front or converge pointwise to zero. This dichotomy is determined by the linear spreading speed and we compute critical values of the diffusion parameter for which the spreading speed is zero and maximal and prove that the system is linearly determined. We also study the growth of the total population in the network and identify the exponential growth rate as a function of the diffusion coefficient, α. Finally, we make predictions for the Fisher-KPP equation on Erdős-Rényi random graphs based upon the results on the homogeneous tree. When α is small we observe via numerical simulations that mean arrival times are linearly related to distance from the initial node and the speed of invasion is well approximated by the linear spreading speed on the tree. Furthermore, we observe that exponential growth rates of the total population on the random network can be bounded by growth rates on the homogeneous tree and provide an explanation for the sub-linear exponential growth rates that occur for small diffusion.

Citation: Aaron Hoffman, Matt Holzer. Invasion fronts on graphs: The Fisher-KPP equation on homogeneous trees and Erdős-Réyni graphs. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 671-694. doi: 10.3934/dcdsb.2018202
References:
[1]

A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512.  doi: 10.1126/science.286.5439.509.  Google Scholar

[2]

V. Batagelj and U. Brandes, Efficient generation of large random networks, Phys. Rev. E, 71 (2005), 036113. doi: 10.1103/PhysRevE.71.036113.  Google Scholar

[3]

A. Bers, Space-time evolution of plasma instabilities-absolute and convective, in Basic Plasma Physics: Selected Chapters, Handbook of Plasma Physics, Volume 1 eds. A. A. Galeev & R. N. Sudan, (1984), 451-517. Google Scholar

[4]

B. Bollobás, Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, second edition, 2001. doi: 10.1017/CBO9780511814068.  Google Scholar

[5]

M. Bramson, Convergence of solutions of the Kolmogorov equation to travelling waves, Mem. Amer. Math. Soc., 44 (1983), iv+190pp. doi: 10.1090/memo/0285.  Google Scholar

[6]

L. Brevdo and T. J. Bridges, Absolute and convective instabilities of spatially periodic flows, Philos. Trans. Roy. Soc. London Ser. A, 354 (1996), 1027-1064.  doi: 10.1098/rsta.1996.0040.  Google Scholar

[7]

R. J. Briggs, Electron-Stream Interaction with Plasmas, MIT Press, Cambridge, 1964. Google Scholar

[8]

D. Brockmann and D. Helbing, The hidden geometry of complex, network-driven contagion phenomena, Science, 342 (2013), 1337-1342.  doi: 10.1126/science.1245200.  Google Scholar

[9]

R. Burioni, S. Chibbaro, D. Vergni and A. Vulpiani, Reaction spreading on graphs, Phys. Rev. E, 86 (2012), 055101. doi: 10.1103/PhysRevE.86.055101.  Google Scholar

[10]

X. Chen, Existence, uniqueness, and asymptotic stability of traveling waves in nonlocal evolution equations, Adv. Differential Equations, 2 (1997), 125-160.   Google Scholar

[11]

G. ChintaJ. Jorgenson and A. Karlsson, Heat kernels on regular graphs and generalized Ihara zeta function formulas, Monatsh. Math., 178 (2015), 171-190.  doi: 10.1007/s00605-014-0685-4.  Google Scholar

[12]

F. Chung and S. -T. Yau, Coverings, heat kernels and spanning trees, Electron. J. Combin., 6 (1999), Research Paper 12, 21 pp.  Google Scholar

[13]

V. ColizzaR. Pastor-Satorras and A. Vespignani, Reaction—diffusion processes and metapopulation models in heterogeneous networks, Nat Phys, 3 (2007), 276-282.  doi: 10.1038/nphys560.  Google Scholar

[14]

R. Durrett, Random Graph Dynamics, volume 20 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2007.  Google Scholar

[15]

P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen, 6 (1959), 290-297.   Google Scholar

[16]

R. A. Fisher, The wave of advance of advantageous genes, Annals of Human Genetics, 7 (1937), 355-369.  doi: 10.1111/j.1469-1809.1937.tb02153.x.  Google Scholar

[17]

J. Hindes, S. Singh, C. R. Myers and D. J. Schneider, Epidemic fronts in complex networks with metapopulation structure, Phys. Rev. E, 88 (2013), 012809. Google Scholar

[18]

M. Holzer, A proof of anomalous invasion speeds in a system of coupled Fisher-KPP equations, Discrete Contin. Dyn. Syst., 36 (2016), 2069-2084.  doi: 10.3934/dcds.2016.36.2069.  Google Scholar

[19]

M. Holzer and A. Scheel, Criteria for pointwise growth and their role in invasion processes, J. Nonlinear Sci., 24 (2014), 661-709.  doi: 10.1007/s00332-014-9202-0.  Google Scholar

[20]

A. KolmogorovI. Petrovskii and N. Piscounov, Etude de l'equation de la diffusion avec croissance de la quantite' de matiere et son application a un probleme biologique, Moscow Univ. Math. Bull., 1 (1937), 1-25.   Google Scholar

[21]

N. E. Kouvaris, H. Kori and A. S. Mikhailov, Traveling and pinned fronts in bistable reaction-diffusion systems on networks, PLoS ONE, 7 (2012), e45029. doi: 10.1371/journal.pone.0045029.  Google Scholar

[22]

H. MatanoF. Punzo and A. Tesei, Front propagation for nonlinear diffusion equations on the hyperbolic space, J. Eur. Math. Soc. (JEMS), 17 (2015), 1199-1227.  doi: 10.4171/JEMS/529.  Google Scholar

[23]

B. Mohar and W. Woess, A survey on spectra of infinite graphs, Bull. London Math. Soc., 21 (1989), 209-234.  doi: 10.1112/blms/21.3.209.  Google Scholar

[24]

M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256.  doi: 10.1137/S003614450342480.  Google Scholar

[25]

M. A. Porter and J. P. Gleeson, Dynamical Systems on Networks, volume 4 of Frontiers in Applied Dynamical Systems: Reviews and Tutorials. Springer, Cham, 2016. A tutorial. doi: 10.1007/978-3-319-26641-1.  Google Scholar

[26]

B. Sandstede and A. Scheel, Absolute and convective instabilities of waves on unbounded and large bounded domains, Phys. D, 145 (2000), 233-277.  doi: 10.1016/S0167-2789(00)00114-7.  Google Scholar

[27]

S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276.  doi: 10.1038/35065725.  Google Scholar

[28]

W. van Saarloos, Front propagation into unstable states, Physics Reports, 386 (2003), 29-222.   Google Scholar

[29]

A. Vespignani, Modelling dynamical processes in complex socio-technical systems, Nature Physics, 8 (2012), 32-39.  doi: 10.1038/nphys2160.  Google Scholar

[30]

D. J. Watts and S. H. Strogatz, Collective dynamics of "small-world" networks, nature, 393 (1998), 440-442.   Google Scholar

[31]

H. F. Weinberger, Long-time behavior of a class of biological models, SIAM Journal on Mathematical Analysis, 13 (1982), 353-396.  doi: 10.1137/0513028.  Google Scholar

[32]

B. ZinnerG. Harris and W. Hudson, Traveling wavefronts for the discrete Fisher's equation, J. Differential Equations, 105 (1993), 46-62.  doi: 10.1006/jdeq.1993.1082.  Google Scholar

show all references

References:
[1]

A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512.  doi: 10.1126/science.286.5439.509.  Google Scholar

[2]

V. Batagelj and U. Brandes, Efficient generation of large random networks, Phys. Rev. E, 71 (2005), 036113. doi: 10.1103/PhysRevE.71.036113.  Google Scholar

[3]

A. Bers, Space-time evolution of plasma instabilities-absolute and convective, in Basic Plasma Physics: Selected Chapters, Handbook of Plasma Physics, Volume 1 eds. A. A. Galeev & R. N. Sudan, (1984), 451-517. Google Scholar

[4]

B. Bollobás, Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, second edition, 2001. doi: 10.1017/CBO9780511814068.  Google Scholar

[5]

M. Bramson, Convergence of solutions of the Kolmogorov equation to travelling waves, Mem. Amer. Math. Soc., 44 (1983), iv+190pp. doi: 10.1090/memo/0285.  Google Scholar

[6]

L. Brevdo and T. J. Bridges, Absolute and convective instabilities of spatially periodic flows, Philos. Trans. Roy. Soc. London Ser. A, 354 (1996), 1027-1064.  doi: 10.1098/rsta.1996.0040.  Google Scholar

[7]

R. J. Briggs, Electron-Stream Interaction with Plasmas, MIT Press, Cambridge, 1964. Google Scholar

[8]

D. Brockmann and D. Helbing, The hidden geometry of complex, network-driven contagion phenomena, Science, 342 (2013), 1337-1342.  doi: 10.1126/science.1245200.  Google Scholar

[9]

R. Burioni, S. Chibbaro, D. Vergni and A. Vulpiani, Reaction spreading on graphs, Phys. Rev. E, 86 (2012), 055101. doi: 10.1103/PhysRevE.86.055101.  Google Scholar

[10]

X. Chen, Existence, uniqueness, and asymptotic stability of traveling waves in nonlocal evolution equations, Adv. Differential Equations, 2 (1997), 125-160.   Google Scholar

[11]

G. ChintaJ. Jorgenson and A. Karlsson, Heat kernels on regular graphs and generalized Ihara zeta function formulas, Monatsh. Math., 178 (2015), 171-190.  doi: 10.1007/s00605-014-0685-4.  Google Scholar

[12]

F. Chung and S. -T. Yau, Coverings, heat kernels and spanning trees, Electron. J. Combin., 6 (1999), Research Paper 12, 21 pp.  Google Scholar

[13]

V. ColizzaR. Pastor-Satorras and A. Vespignani, Reaction—diffusion processes and metapopulation models in heterogeneous networks, Nat Phys, 3 (2007), 276-282.  doi: 10.1038/nphys560.  Google Scholar

[14]

R. Durrett, Random Graph Dynamics, volume 20 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2007.  Google Scholar

[15]

P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen, 6 (1959), 290-297.   Google Scholar

[16]

R. A. Fisher, The wave of advance of advantageous genes, Annals of Human Genetics, 7 (1937), 355-369.  doi: 10.1111/j.1469-1809.1937.tb02153.x.  Google Scholar

[17]

J. Hindes, S. Singh, C. R. Myers and D. J. Schneider, Epidemic fronts in complex networks with metapopulation structure, Phys. Rev. E, 88 (2013), 012809. Google Scholar

[18]

M. Holzer, A proof of anomalous invasion speeds in a system of coupled Fisher-KPP equations, Discrete Contin. Dyn. Syst., 36 (2016), 2069-2084.  doi: 10.3934/dcds.2016.36.2069.  Google Scholar

[19]

M. Holzer and A. Scheel, Criteria for pointwise growth and their role in invasion processes, J. Nonlinear Sci., 24 (2014), 661-709.  doi: 10.1007/s00332-014-9202-0.  Google Scholar

[20]

A. KolmogorovI. Petrovskii and N. Piscounov, Etude de l'equation de la diffusion avec croissance de la quantite' de matiere et son application a un probleme biologique, Moscow Univ. Math. Bull., 1 (1937), 1-25.   Google Scholar

[21]

N. E. Kouvaris, H. Kori and A. S. Mikhailov, Traveling and pinned fronts in bistable reaction-diffusion systems on networks, PLoS ONE, 7 (2012), e45029. doi: 10.1371/journal.pone.0045029.  Google Scholar

[22]

H. MatanoF. Punzo and A. Tesei, Front propagation for nonlinear diffusion equations on the hyperbolic space, J. Eur. Math. Soc. (JEMS), 17 (2015), 1199-1227.  doi: 10.4171/JEMS/529.  Google Scholar

[23]

B. Mohar and W. Woess, A survey on spectra of infinite graphs, Bull. London Math. Soc., 21 (1989), 209-234.  doi: 10.1112/blms/21.3.209.  Google Scholar

[24]

M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256.  doi: 10.1137/S003614450342480.  Google Scholar

[25]

M. A. Porter and J. P. Gleeson, Dynamical Systems on Networks, volume 4 of Frontiers in Applied Dynamical Systems: Reviews and Tutorials. Springer, Cham, 2016. A tutorial. doi: 10.1007/978-3-319-26641-1.  Google Scholar

[26]

B. Sandstede and A. Scheel, Absolute and convective instabilities of waves on unbounded and large bounded domains, Phys. D, 145 (2000), 233-277.  doi: 10.1016/S0167-2789(00)00114-7.  Google Scholar

[27]

S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276.  doi: 10.1038/35065725.  Google Scholar

[28]

W. van Saarloos, Front propagation into unstable states, Physics Reports, 386 (2003), 29-222.   Google Scholar

[29]

A. Vespignani, Modelling dynamical processes in complex socio-technical systems, Nature Physics, 8 (2012), 32-39.  doi: 10.1038/nphys2160.  Google Scholar

[30]

D. J. Watts and S. H. Strogatz, Collective dynamics of "small-world" networks, nature, 393 (1998), 440-442.   Google Scholar

[31]

H. F. Weinberger, Long-time behavior of a class of biological models, SIAM Journal on Mathematical Analysis, 13 (1982), 353-396.  doi: 10.1137/0513028.  Google Scholar

[32]

B. ZinnerG. Harris and W. Hudson, Traveling wavefronts for the discrete Fisher's equation, J. Differential Equations, 105 (1993), 46-62.  doi: 10.1006/jdeq.1993.1082.  Google Scholar

Figure 1.  The linear spreading speed for (5), calculated numerically as a function of $\alpha$ for $k = 3$ (red), $k = 4$ (black) and $k = 5$ (blue). Note the critical values $\alpha_2(k)$ for which the spreading speed is zero and $\alpha_1(k)$ where the speed is maximal. Also note that as $\alpha\to 0$, these spreading speeds appear to approach a common curve
Figure 2.  Critical rates of diffusion for period trees with period $m = 2$. On the left, we plot $\alpha_1$ as a function of $k_1$ with $k_2$ fixed to preserve the mean degree. On the right, we plot $\alpha_2$ as a function of $k_1$. Note that in both case the periodic heterogeneity increases the critical diffusion rates
Figure 3.  Numerical simulations of (2) with $k = 3$ and for $\alpha = 0.2$ (left), $\alpha = 0.8$ (middle) and $\alpha = 2.2$ (right). The blue curves are $u_n(t)$ while the red curves depict the normalized population at each level, i.e. $w_n(t)/\max_n(w_n(t))$. Note that $0.2 < \alpha_1(3) < 0.8 < \alpha_2(3) < 2.2$. For $\alpha = 0.2$, we observe that the maximal population is concentrated at the front interface. For $\alpha = 0.8$, the maximal population is concentrated ahead of the front interface. Finally, for $\alpha = 2.2$ the local population at any fixed node converges to zero, but the total population grows and eventually is concentrated at the final level of the tree
Figure 4.  On the left, we compare predictions for the exponential growth rate of the maximum of $w_n(t)$ as a function of $\alpha$ (blue line) against the exponential growth rates of $M(t)$ observed in direct numerical simulations (asterisks) for $k = 5$. On the right, we compare numerically observed spreading speeds for $w_n(t)$ (asterisks) versus linear spreading speeds determined numerically from the pinched double root criterion applied to $\tilde{d}_s(\gamma,\lambda)$ (blue line). Here we have taken $k = 5$
Figure 5.  Arrival times for an Erdős-Réyni graph with $N = 60,000$ and expected degree $k_{ER} = 2$. Various values of $\alpha$ are considered. In green is the best fit linear approximation for the mean arrival times for nodes with distance between $3$ and $12$ from the initial location
Figure 6.  Speed associated to the mean arrival times in numerical simulations on an Erdős-Réyni graph with $N = 60,000$ and expected degree $k_{ER} = 2$ are shown in asterisks. The blue curve is the spreading speed predicted by the analysis in Section 2 for the homogeneous tree with $k = 2.54$, found by numerically computing roots of (6). This value is chosen since it is one less than the mean degree of the network over those nodes with distance between $3$ and $12$ from the original location
Figure 7.  Growth rate of the total population for Erdős-Rényi graph. On the left, $N = 500,000$ and $\alpha = 0.1,0.35,0.6,0.85$. Larger values of $\alpha$ correspond to faster growth rates. On the right is the case of $N = 60,000$ with the same values of $\alpha$
Figure 8.  Numerically calculated exponential growth rate for the Erdős-Rényi graph. On the left, $N = 500,000$ and observed growth rates are plotted as circles. The asterisks are the corresponding growth rates in the homogeneous tree with depth $13$. The lower curve is degree $k = 3$ while the larger curve is degree $k = 4$. On the right are the same computations, but for the Erdős-Rényi graph with $N = 60,000$ and for homogeneous trees with $k = 2$ and $k = 3$
[1]

Patrick Martinez, Judith Vancostenoble. Lipschitz stability for the growth rate coefficients in a nonlinear Fisher-KPP equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 695-721. doi: 10.3934/dcdss.2020362

[2]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323

[3]

Michiel Bertsch, Danielle Hilhorst, Hirofumi Izuhara, Masayasu Mimura, Tohru Wakasa. A nonlinear parabolic-hyperbolic system for contact inhibition and a degenerate parabolic fisher kpp equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3117-3142. doi: 10.3934/dcds.2019226

[4]

Qian Liu, Shuang Liu, King-Yeung Lam. Asymptotic spreading of interacting species with multiple fronts Ⅰ: A geometric optics approach. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3683-3714. doi: 10.3934/dcds.2020050

[5]

Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329

[6]

Yohei Yamazaki. Center stable manifolds around line solitary waves of the Zakharov–Kuznetsov equation with critical speed. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021008

[7]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[8]

Mia Jukić, Hermen Jan Hupkes. Dynamics of curved travelling fronts for the discrete Allen-Cahn equation on a two-dimensional lattice. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020402

[9]

Shumin Li, Masahiro Yamamoto, Bernadette Miara. A Carleman estimate for the linear shallow shell equation and an inverse source problem. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 367-380. doi: 10.3934/dcds.2009.23.367

[10]

Leanne Dong. Random attractors for stochastic Navier-Stokes equation on a 2D rotating sphere with stable Lévy noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020352

[11]

Van Duong Dinh. Random data theory for the cubic fourth-order nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020284

[12]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, 2021, 14 (1) : 77-88. doi: 10.3934/krm.2020049

[13]

Jong-Shenq Guo, Ken-Ichi Nakamura, Toshiko Ogiwara, Chang-Hong Wu. The sign of traveling wave speed in bistable dynamics. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3451-3466. doi: 10.3934/dcds.2020047

[14]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295

[15]

Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325

[16]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[17]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017

[18]

Timothy Chumley, Renato Feres. Entropy production in random billiards. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1319-1346. doi: 10.3934/dcds.2020319

[19]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033

[20]

Peter H. van der Kamp, D. I. McLaren, G. R. W. Quispel. Homogeneous darboux polynomials and generalising integrable ODE systems. Journal of Computational Dynamics, 2021, 8 (1) : 1-8. doi: 10.3934/jcd.2021001

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (115)
  • HTML views (404)
  • Cited by (1)

Other articles
by authors

[Back to Top]