September  2014, 9(3): 383-416. doi: 10.3934/nhm.2014.9.383

Computing the asymptotic spectrum for networks representing energy landscapes using the minimum spanning tree

1. 

University of Maryland, Department of Mathematics, College Park, MD 20742-4015, United States

Received  February 2014 Revised  June 2014 Published  October 2014

The concept of metastability has caused a lot of interest in recent years. The spectral decomposition of the generator matrix of a stochastic network exposes all of the transition processes in the system. The assumption of the existence of a low lying group of eigenvalues separated by a spectral gap has become a popular theme. We consider stochastic networks representing potential energy landscapes whose states and edges correspond to local minima and transition states respectively, and the pairwise transition rates are given by the Arrhenuis formula. Using the minimal spanning tree, we construct the asymptotics for eigenvalues and eigenvectors of the generator matrix starting from the low lying group. This construction gives rise to an efficient algorithm suitable for large and complex networks. We apply it to Wales's Lennard-Jones-38 network with 71887 states and 119853 edges where the underlying energy landscape has a double-funnel structure. Our results demonstrate that the concept of metastability should be applied with care to this system. For the full network, there is no significant spectral gap separating the eigenvalue corresponding to the exit from the wider and shallower icosahedral funnel at any reasonable temperature range. However, if the observation time is limited, the expected spectral gap appears.
Citation: Maria Cameron. Computing the asymptotic spectrum for networks representing energy landscapes using the minimum spanning tree. Networks & Heterogeneous Media, 2014, 9 (3) : 383-416. doi: 10.3934/nhm.2014.9.383
References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications,, Prentice Hall, (1993).   Google Scholar

[2]

O. M. Becker and M. Karplus, The topology of multidimensional potential energy surfaces: theory and application to peptide structure and kinetics,, J. Chem. Phys., 106 (1997), 1495.  doi: 10.1063/1.473299.  Google Scholar

[3]

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability and low lying spectra in reversible Markov chains,, Comm. Math. Phys., 228 (2002), 219.  doi: 10.1007/s002200200609.  Google Scholar

[4]

A. Bovier, Metastability,, in Methods of Contemporary Statistical Mechanics, 1970 (2009), 177.  doi: 10.1007/978-3-540-92796-9.  Google Scholar

[5]

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability in reversible diffusion processes I. Sharp estimates for capacities and exit times,, J. Eur. Math. Soc., 6 (2004), 399.  doi: 10.4171/JEMS/14.  Google Scholar

[6]

A. Bovier, V. Gayrard and M. Klein, Metastability in reversible diffusion processes. II. Precise estimates for small eigenvalues,, J. Eur. Math. Soc., 7 (2005), 69.  doi: 10.4171/JEMS/22.  Google Scholar

[7]

M. K. Cameron, Computing Freidlin's cycles for the overdamped Langevin dynamics,, J. Stat. Phys., 152 (2013), 493.  doi: 10.1007/s10955-013-0770-4.  Google Scholar

[8]

M. Cameron, R. V. Kohn, and E. Vanden-Eijnden, The string method as a dynamical dystem,, J. Nonlin. Sc., 21 (2011), 193.  doi: 10.1007/s00332-010-9081-y.  Google Scholar

[9]

M. K. Cameron and E. Vanden-Eijnden, Flows in complex networks: Theory, algorithms, and application to Lennard-Jones cluster rearrangement,, J. Stat. Phys., 156 (2014), 427.  doi: 10.1007/s10955-014-0997-8.  Google Scholar

[10]

J. W. Demmel, Applied Numerical Linear Algebra,, SIAM, (1997).  doi: 10.1137/1.9781611971446.  Google Scholar

[11]

E. W. Dijkstra, A note on two problems in connexion with graphs,, Numerische Mathematic, 1 (1959), 269.  doi: 10.1007/BF01386390.  Google Scholar

[12]

J. P. K. Doye, M. A. Miller and D. J. Wales, The double-funnel energy landscape of the 38-atom Lennard-Jones cluster,, J. Chem. Phys., 110 (1999), 6896.  doi: 10.1063/1.478595.  Google Scholar

[13]

W. J. Ewens, Mathematical Population Genetics 1: Theoretical Introduction,, 2nd Ed., (2004).  doi: 10.1007/978-0-387-21822-9.  Google Scholar

[14]

F. C. Frank, Supercooling of liquids,, Proc. R. Soc. Lond. A Math. Phys. Sci., 215 (1952), 43.  doi: 10.1098/rspa.1952.0194.  Google Scholar

[15]

M. I. Freidlin, Sublimiting distributions and stabilization of solutions of parabolic equations with small parameter,, Soviet Math. Dokl., 18 (1977), 1114.   Google Scholar

[16]

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems,, 3rd ed, (2012).  doi: 10.1007/978-3-642-25847-3.  Google Scholar

[17]

M. I. Freidlin, Quasi-deterministic approximation, metastability and stochastic resonance,, Physica D, 137 (2000), 333.  doi: 10.1016/S0167-2789(99)00191-8.  Google Scholar

[18]

J. C. Hamilton, D. J. Siegel, B. P. Uberuaga and A. F. Voter, Isometrization rates and mechanisms for the 38-atom Lennard-Jones cluster determined using molecular dynamics and temperature accelerated molecular dynamics,, preprint., ().   Google Scholar

[19]

W. Huisinga, S. Meyn and Ch. Schuette, Phase transitions and metastability in Markovian and molecular systems,, Ann. Appl. Prob., 14 (2004), 419.  doi: 10.1214/aoap/1075828057.  Google Scholar

[20]

M. Kimura, The Neutral Theory of Molecular Evolution,, Cambridge University Press, (1985).  doi: 10.1017/CBO9780511623486.  Google Scholar

[21]

J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,, Proc. Amer. Math. Soc., 7 (1956), 48.  doi: 10.1090/S0002-9939-1956-0078686-7.  Google Scholar

[22]

V. A. Mandelshtam and P. A. Frantsuzov, Multiple structural transformations in Lennard-Jones clusters: Generic versus size-specific behavior,, J. Chem. Phys., 124 (2006).  doi: 10.1063/1.2202312.  Google Scholar

[23]

J. H. Gillespie, Population Genetics: A Concise Guide,, 2nd Ed. John Hopkins University Press, (2004).   Google Scholar

[24]

M. Manhart and A. V. Morozov, Statistical Physics of Evolutionary Trajectories on Fitness Landscapes,, preprint, ().   Google Scholar

[25]

J. P. Neirotti, F. Calvo, D. L. Freeman and J. D. Doll, Phase changes in 38-atom Lennard-Jones clusters. I. A parallel tempering study in the canonical ensemble,, J. Chem. Phys., 112 (2000).  doi: 10.1063/1.481671.  Google Scholar

[26]

M. Picciani, M. Athenes, J. Kurchan and J. Taileur, Simulating structural transitions by direct transition current sampling: the example of $LJ_{38}$,, J. Chem. Phys., 135 (2011).  doi: 10.1063/1.3609972.  Google Scholar

[27]

M. Sarich, N. Djurdjevac, S. Bruckner, T. O. F. Conrad and Ch. Schuette, Modularity revisited: a novel dynamics-based concept for decomposing complex networks,, Journal of Computational Dynamics, (2013).  doi: 10.3934/jcd.2014.1.191.  Google Scholar

[28]

Ch. Schuette, W. Huisinga and S. Meyn, Metastability of diffusion processes,, IUTAM Symposium on Nonlinear Stochastic Dynamics Solid Mechanics and Its Applications, 110 (2003), 71.  doi: 10.1007/978-94-010-0179-3_6.  Google Scholar

[29]

D. J. Wales, Discrete Path Sampling,, Mol. Phys., 100 (2002), 3285.  doi: 10.1080/00268970210162691.  Google Scholar

[30]

D. J. Wales, Some further applications of discrete path sampling to cluster isomerization,, Mol. Phys., 102 (2004), 891.  doi: 10.1080/00268970410001703363.  Google Scholar

[31]

D. J. Wales, Energy landscapes: calculating pathways and rates,, International Review in Chemical Physics, 25 (2006), 237.  doi: 10.1080/01442350600676921.  Google Scholar

[32]

, The database for the Lennard-Jones-38 cluster,, , ().   Google Scholar

[33]

, Wales group web site, , ().   Google Scholar

[34]

D. J. Wales and J. P. K. Doye, Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters containing up to 110 Atoms,, J. Phys. Chem. A, 101 (1997), 5111.  doi: 10.1021/jp970984n.  Google Scholar

[35]

D. J. Wales, M. A. Miller and T. R. Walsh, Archetypal energy landscapes,, Nature , 394 (1998), 758.  doi: 10.1038/29487.  Google Scholar

[36]

D. J. Wales, Energy Landscapes: Applications to Clusters, Biomolecules and Glasses,, Cambridge University Press, (2003).   Google Scholar

[37]

D. J. Wales and P. Salamon, Observation time scale, free-energy landscapes, and molecular symmetry,, Proc. Natl. Acad. Sci. USA, 111 (2014), 617.  doi: 10.1073/pnas.1319599111.  Google Scholar

[38]

A. D. Wentzell, Ob asimptotike naibol'shego sobstvennogo znacheniya ellipticheskogo differentsial'nogo operatora s malym parametrom pri starshikh proizvodnykh,, (Russian) [On the asymptotics of the largest eigenvalue of the elliptic differential operator with a small parameter at the highest derivatives], 202 (1972), 19.   Google Scholar

[39]

A. D. Wentzell, On the asymptotics of eigenvalues of matrices with elements of order $\exp\{-V_{ij}/2 (\epsilon^2)}$,, Soviet Math. Dokl., 13 (1972), 65.   Google Scholar

show all references

References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications,, Prentice Hall, (1993).   Google Scholar

[2]

O. M. Becker and M. Karplus, The topology of multidimensional potential energy surfaces: theory and application to peptide structure and kinetics,, J. Chem. Phys., 106 (1997), 1495.  doi: 10.1063/1.473299.  Google Scholar

[3]

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability and low lying spectra in reversible Markov chains,, Comm. Math. Phys., 228 (2002), 219.  doi: 10.1007/s002200200609.  Google Scholar

[4]

A. Bovier, Metastability,, in Methods of Contemporary Statistical Mechanics, 1970 (2009), 177.  doi: 10.1007/978-3-540-92796-9.  Google Scholar

[5]

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability in reversible diffusion processes I. Sharp estimates for capacities and exit times,, J. Eur. Math. Soc., 6 (2004), 399.  doi: 10.4171/JEMS/14.  Google Scholar

[6]

A. Bovier, V. Gayrard and M. Klein, Metastability in reversible diffusion processes. II. Precise estimates for small eigenvalues,, J. Eur. Math. Soc., 7 (2005), 69.  doi: 10.4171/JEMS/22.  Google Scholar

[7]

M. K. Cameron, Computing Freidlin's cycles for the overdamped Langevin dynamics,, J. Stat. Phys., 152 (2013), 493.  doi: 10.1007/s10955-013-0770-4.  Google Scholar

[8]

M. Cameron, R. V. Kohn, and E. Vanden-Eijnden, The string method as a dynamical dystem,, J. Nonlin. Sc., 21 (2011), 193.  doi: 10.1007/s00332-010-9081-y.  Google Scholar

[9]

M. K. Cameron and E. Vanden-Eijnden, Flows in complex networks: Theory, algorithms, and application to Lennard-Jones cluster rearrangement,, J. Stat. Phys., 156 (2014), 427.  doi: 10.1007/s10955-014-0997-8.  Google Scholar

[10]

J. W. Demmel, Applied Numerical Linear Algebra,, SIAM, (1997).  doi: 10.1137/1.9781611971446.  Google Scholar

[11]

E. W. Dijkstra, A note on two problems in connexion with graphs,, Numerische Mathematic, 1 (1959), 269.  doi: 10.1007/BF01386390.  Google Scholar

[12]

J. P. K. Doye, M. A. Miller and D. J. Wales, The double-funnel energy landscape of the 38-atom Lennard-Jones cluster,, J. Chem. Phys., 110 (1999), 6896.  doi: 10.1063/1.478595.  Google Scholar

[13]

W. J. Ewens, Mathematical Population Genetics 1: Theoretical Introduction,, 2nd Ed., (2004).  doi: 10.1007/978-0-387-21822-9.  Google Scholar

[14]

F. C. Frank, Supercooling of liquids,, Proc. R. Soc. Lond. A Math. Phys. Sci., 215 (1952), 43.  doi: 10.1098/rspa.1952.0194.  Google Scholar

[15]

M. I. Freidlin, Sublimiting distributions and stabilization of solutions of parabolic equations with small parameter,, Soviet Math. Dokl., 18 (1977), 1114.   Google Scholar

[16]

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems,, 3rd ed, (2012).  doi: 10.1007/978-3-642-25847-3.  Google Scholar

[17]

M. I. Freidlin, Quasi-deterministic approximation, metastability and stochastic resonance,, Physica D, 137 (2000), 333.  doi: 10.1016/S0167-2789(99)00191-8.  Google Scholar

[18]

J. C. Hamilton, D. J. Siegel, B. P. Uberuaga and A. F. Voter, Isometrization rates and mechanisms for the 38-atom Lennard-Jones cluster determined using molecular dynamics and temperature accelerated molecular dynamics,, preprint., ().   Google Scholar

[19]

W. Huisinga, S. Meyn and Ch. Schuette, Phase transitions and metastability in Markovian and molecular systems,, Ann. Appl. Prob., 14 (2004), 419.  doi: 10.1214/aoap/1075828057.  Google Scholar

[20]

M. Kimura, The Neutral Theory of Molecular Evolution,, Cambridge University Press, (1985).  doi: 10.1017/CBO9780511623486.  Google Scholar

[21]

J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,, Proc. Amer. Math. Soc., 7 (1956), 48.  doi: 10.1090/S0002-9939-1956-0078686-7.  Google Scholar

[22]

V. A. Mandelshtam and P. A. Frantsuzov, Multiple structural transformations in Lennard-Jones clusters: Generic versus size-specific behavior,, J. Chem. Phys., 124 (2006).  doi: 10.1063/1.2202312.  Google Scholar

[23]

J. H. Gillespie, Population Genetics: A Concise Guide,, 2nd Ed. John Hopkins University Press, (2004).   Google Scholar

[24]

M. Manhart and A. V. Morozov, Statistical Physics of Evolutionary Trajectories on Fitness Landscapes,, preprint, ().   Google Scholar

[25]

J. P. Neirotti, F. Calvo, D. L. Freeman and J. D. Doll, Phase changes in 38-atom Lennard-Jones clusters. I. A parallel tempering study in the canonical ensemble,, J. Chem. Phys., 112 (2000).  doi: 10.1063/1.481671.  Google Scholar

[26]

M. Picciani, M. Athenes, J. Kurchan and J. Taileur, Simulating structural transitions by direct transition current sampling: the example of $LJ_{38}$,, J. Chem. Phys., 135 (2011).  doi: 10.1063/1.3609972.  Google Scholar

[27]

M. Sarich, N. Djurdjevac, S. Bruckner, T. O. F. Conrad and Ch. Schuette, Modularity revisited: a novel dynamics-based concept for decomposing complex networks,, Journal of Computational Dynamics, (2013).  doi: 10.3934/jcd.2014.1.191.  Google Scholar

[28]

Ch. Schuette, W. Huisinga and S. Meyn, Metastability of diffusion processes,, IUTAM Symposium on Nonlinear Stochastic Dynamics Solid Mechanics and Its Applications, 110 (2003), 71.  doi: 10.1007/978-94-010-0179-3_6.  Google Scholar

[29]

D. J. Wales, Discrete Path Sampling,, Mol. Phys., 100 (2002), 3285.  doi: 10.1080/00268970210162691.  Google Scholar

[30]

D. J. Wales, Some further applications of discrete path sampling to cluster isomerization,, Mol. Phys., 102 (2004), 891.  doi: 10.1080/00268970410001703363.  Google Scholar

[31]

D. J. Wales, Energy landscapes: calculating pathways and rates,, International Review in Chemical Physics, 25 (2006), 237.  doi: 10.1080/01442350600676921.  Google Scholar

[32]

, The database for the Lennard-Jones-38 cluster,, , ().   Google Scholar

[33]

, Wales group web site, , ().   Google Scholar

[34]

D. J. Wales and J. P. K. Doye, Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters containing up to 110 Atoms,, J. Phys. Chem. A, 101 (1997), 5111.  doi: 10.1021/jp970984n.  Google Scholar

[35]

D. J. Wales, M. A. Miller and T. R. Walsh, Archetypal energy landscapes,, Nature , 394 (1998), 758.  doi: 10.1038/29487.  Google Scholar

[36]

D. J. Wales, Energy Landscapes: Applications to Clusters, Biomolecules and Glasses,, Cambridge University Press, (2003).   Google Scholar

[37]

D. J. Wales and P. Salamon, Observation time scale, free-energy landscapes, and molecular symmetry,, Proc. Natl. Acad. Sci. USA, 111 (2014), 617.  doi: 10.1073/pnas.1319599111.  Google Scholar

[38]

A. D. Wentzell, Ob asimptotike naibol'shego sobstvennogo znacheniya ellipticheskogo differentsial'nogo operatora s malym parametrom pri starshikh proizvodnykh,, (Russian) [On the asymptotics of the largest eigenvalue of the elliptic differential operator with a small parameter at the highest derivatives], 202 (1972), 19.   Google Scholar

[39]

A. D. Wentzell, On the asymptotics of eigenvalues of matrices with elements of order $\exp\{-V_{ij}/2 (\epsilon^2)}$,, Soviet Math. Dokl., 13 (1972), 65.   Google Scholar

[1]

Evan Greif, Daniel Kaplan, Robert S. Strichartz, Samuel C. Wiese. Spectrum of the Laplacian on regular polyhedra. Communications on Pure & Applied Analysis, 2021, 20 (1) : 193-214. doi: 10.3934/cpaa.2020263

[2]

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

[3]

Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257

[4]

Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321

[5]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[6]

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123

[7]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[8]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266

[9]

Vivina Barutello, Gian Marco Canneori, Susanna Terracini. Minimal collision arcs asymptotic to central configurations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 61-86. doi: 10.3934/dcds.2020218

[10]

Neng Zhu, Zhengrong Liu, Fang Wang, Kun Zhao. Asymptotic dynamics of a system of conservation laws from chemotaxis. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 813-847. doi: 10.3934/dcds.2020301

[11]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271

[12]

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

[13]

Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256

[14]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020450

[15]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[16]

Sergio Conti, Georg Dolzmann. Optimal laminates in single-slip elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 1-16. doi: 10.3934/dcdss.2020302

[17]

Haili Yuan, Yijun Hu. Optimal investment for an insurer under liquid reserves. Journal of Industrial & Management Optimization, 2021, 17 (1) : 339-355. doi: 10.3934/jimo.2019114

[18]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

[19]

Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318

[20]

Yongxiu Shi, Haitao Wan. Refined asymptotic behavior and uniqueness of large solutions to a quasilinear elliptic equation in a borderline case. Electronic Research Archive, , () : -. doi: 10.3934/era.2020119

2019 Impact Factor: 1.053

Metrics

  • PDF downloads (44)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]