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).

[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.

[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.

[4]

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

[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.

[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.

[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.

[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.

[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.

[10]

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

[11]

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

[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.

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[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., ().

[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.

[20]

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

[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.

[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.

[23]

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

[24]

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

[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.

[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.

[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.

[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.

[29]

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

[30]

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

[31]

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

[32]

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

[33]

, Wales group web site, , ().

[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.

[35]

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

[36]

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

[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.

[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.

[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.

show all references

References:
[1]

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

[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.

[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.

[4]

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

[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.

[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.

[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.

[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.

[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.

[10]

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

[11]

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

[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.

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[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., ().

[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.

[20]

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

[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.

[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.

[23]

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

[24]

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

[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.

[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.

[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.

[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.

[29]

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

[30]

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

[31]

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

[32]

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

[33]

, Wales group web site, , ().

[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.

[35]

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

[36]

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

[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.

[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.

[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.

[1]

Mathias Schäffner, Anja Schlömerkemper. On Lennard-Jones systems with finite range interactions and their asymptotic analysis. Networks & Heterogeneous Media, 2018, 13 (1) : 95-118. doi: 10.3934/nhm.2018005

[2]

Andrea Braides, Anneliese Defranceschi, Enrico Vitali. Variational evolution of one-dimensional Lennard-Jones systems. Networks & Heterogeneous Media, 2014, 9 (2) : 217-238. doi: 10.3934/nhm.2014.9.217

[3]

Irina Berezovik, Wieslaw Krawcewicz, Qingwen Hu. Dihedral molecular configurations interacting by Lennard-Jones and Coulomb forces. Discrete & Continuous Dynamical Systems - S, 2019, 12 (7) : 1879-1903. doi: 10.3934/dcdss.2019124

[4]

Thomas Hudson. Gamma-expansion for a 1D confined Lennard-Jones model with point defect. Networks & Heterogeneous Media, 2013, 8 (2) : 501-527. doi: 10.3934/nhm.2013.8.501

[5]

Sergei Avdonin, Jonathan Bell. Determining a distributed conductance parameter for a neuronal cable model defined on a tree graph. Inverse Problems & Imaging, 2015, 9 (3) : 645-659. doi: 10.3934/ipi.2015.9.645

[6]

Paweł Góra, Abraham Boyarsky. Stochastic perturbations and Ulam's method for W-shaped maps. Discrete & Continuous Dynamical Systems - A, 2013, 33 (5) : 1937-1944. doi: 10.3934/dcds.2013.33.1937

[7]

Michael Khanevsky. Hofer's length spectrum of symplectic surfaces. Journal of Modern Dynamics, 2015, 9: 219-235. doi: 10.3934/jmd.2015.9.219

[8]

Mario Roy. A new variation of Bowen's formula for graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2533-2551. doi: 10.3934/dcds.2012.32.2533

[9]

Wen-ming He, Jun-zhi Cui. The estimate of the multi-scale homogenization method for Green's function on Sobolev space $W^{1,q}(\Omega)$. Communications on Pure & Applied Analysis, 2012, 11 (2) : 501-516. doi: 10.3934/cpaa.2012.11.501

[10]

John Leventides, Iraklis Kollias. Optimal control indicators for the assessment of the influence of government policy to business cycle shocks. Journal of Dynamics & Games, 2014, 1 (1) : 79-104. doi: 10.3934/jdg.2014.1.79

[11]

Donghui Yang, Jie Zhong. Optimal actuator location of the minimum norm controls for stochastic heat equations. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1081-1095. doi: 10.3934/mcrf.2018046

[12]

Yi Cao, Dong Li, Lihe Wang. The optimal weighted $W^{2, p}$ estimates of elliptic equation with non-compatible conditions. Communications on Pure & Applied Analysis, 2011, 10 (2) : 561-570. doi: 10.3934/cpaa.2011.10.561

[13]

Inês Cruz, M. Esmeralda Sousa-Dias. Reduction of cluster iteration maps. Journal of Geometric Mechanics, 2014, 6 (3) : 297-318. doi: 10.3934/jgm.2014.6.297

[14]

Valentin Ovsienko, MichaeL Shapiro. Cluster algebras with Grassmann variables. Electronic Research Announcements, 2019, 26: 1-15. doi: 10.3934/era.2019.26.001

[15]

Lluís Alsedà, David Juher, Pere Mumbrú. Minimal dynamics for tree maps. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 511-541. doi: 10.3934/dcds.2008.20.511

[16]

Andrei V. Dmitruk, Nikolai P. Osmolovskii. Necessary conditions for a weak minimum in optimal control problems with integral equations on a variable time interval. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4323-4343. doi: 10.3934/dcds.2015.35.4323

[17]

Andrei V. Dmitruk, Alexander M. Kaganovich. Quadratic order conditions for an extended weak minimum in optimal control problems with intermediate and mixed constraints. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 523-545. doi: 10.3934/dcds.2011.29.523

[18]

Zhenwei Luo, Jinting Wang. The optimal price discount, order quantity and minimum quantity in newsvendor model with group purchase. Journal of Industrial & Management Optimization, 2015, 11 (1) : 1-11. doi: 10.3934/jimo.2015.11.1

[19]

Andrei V. Dmitruk, Nikolai P. Osmolovski. Necessary conditions for a weak minimum in a general optimal control problem with integral equations on a variable time interval. Mathematical Control & Related Fields, 2017, 7 (4) : 507-535. doi: 10.3934/mcrf.2017019

[20]

Hyeon Je Cho, Ganguk Hwang. Optimal design for dynamic spectrum access in cognitive radio networks under Rayleigh fading. Journal of Industrial & Management Optimization, 2012, 8 (4) : 821-840. doi: 10.3934/jimo.2012.8.821

2018 Impact Factor: 0.871

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]