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 and 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, New Jersey, 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-1517. 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-255. doi: 10.1007/s002200200609.

[4]

A. Bovier, Metastability, in Methods of Contemporary Statistical Mechanics, (ed. R. Kotecky), Lecture Notes in Math., Springer, 1970 (2009), 177-221. 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-424. 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-99. doi: 10.4171/JEMS/22.

[7]

M. K. Cameron, Computing Freidlin's cycles for the overdamped Langevin dynamics, J. Stat. Phys., 152 (2013), 493-518. 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-230. 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-454. arXiv:1402.1736. 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-271. 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-6906. doi: 10.1063/1.478595.

[13]

W. J. Ewens, Mathematical Population Genetics 1: Theoretical Introduction, 2nd Ed., Springer Science+Business Media, Inc., 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-46. 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-1118.

[16]

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, 3rd ed, Springer-Verlag Berlin Heidelberg, 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-352. 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-458. 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-50. 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), 204511. 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, arXiv:1305.1352.

[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), 10340. 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), 034108. 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) (In Press). 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-81. doi: 10.1007/978-94-010-0179-3_6.

[29]

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

[30]

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

[31]

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

[32]

, The database for the Lennard-Jones-38 cluster, http://www-wales.ch.cam.ac.uk/examples/PATHSAMPLE/.

[33]

, Wales group web site http://www-wales.ch.cam.ac.uk.

[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-5116. doi: 10.1021/jp970984n.

[35]

D. J. Wales, M. A. Miller and T. R. Walsh, Archetypal energy landscapes, Nature , 394 (1998), 758-760. 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-622. 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], Dokl. Akad. Nauk SSSR, 202 (1972), 19-21.

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

show all references

References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 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-1517. 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-255. doi: 10.1007/s002200200609.

[4]

A. Bovier, Metastability, in Methods of Contemporary Statistical Mechanics, (ed. R. Kotecky), Lecture Notes in Math., Springer, 1970 (2009), 177-221. 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-424. 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-99. doi: 10.4171/JEMS/22.

[7]

M. K. Cameron, Computing Freidlin's cycles for the overdamped Langevin dynamics, J. Stat. Phys., 152 (2013), 493-518. 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-230. 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-454. arXiv:1402.1736. 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-271. 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-6906. doi: 10.1063/1.478595.

[13]

W. J. Ewens, Mathematical Population Genetics 1: Theoretical Introduction, 2nd Ed., Springer Science+Business Media, Inc., 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-46. 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-1118.

[16]

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, 3rd ed, Springer-Verlag Berlin Heidelberg, 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-352. 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-458. 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-50. 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), 204511. 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, arXiv:1305.1352.

[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), 10340. 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), 034108. 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) (In Press). 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-81. doi: 10.1007/978-94-010-0179-3_6.

[29]

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

[30]

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

[31]

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

[32]

, The database for the Lennard-Jones-38 cluster, http://www-wales.ch.cam.ac.uk/examples/PATHSAMPLE/.

[33]

, Wales group web site http://www-wales.ch.cam.ac.uk.

[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-5116. doi: 10.1021/jp970984n.

[35]

D. J. Wales, M. A. Miller and T. R. Walsh, Archetypal energy landscapes, Nature , 394 (1998), 758-760. 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-622. 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], Dokl. Akad. Nauk SSSR, 202 (1972), 19-21.

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

[1]

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

[2]

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

[3]

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

[4]

Thomas Hudson. Gamma-expansion for a 1D confined Lennard-Jones model with point defect. Networks and 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 and Imaging, 2015, 9 (3) : 645-659. doi: 10.3934/ipi.2015.9.645

[6]

Xiaomin Huang, Yanpei Jiang, Wei Liu. Freidlin-Wentzell's large deviation principle for stochastic integral evolution equations. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022091

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

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

[9]

Jinmei Fan, Yanhai Zhang. Optimal quinary negacyclic codes with minimum distance four. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021043

[10]

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

[11]

Juan Cao, Fengli Ren, Dacheng Zhou. Asymptotic and finite-time cluster synchronization of neural networks via two different controllers. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022005

[12]

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

[13]

Sergei A. Nazarov, Rafael Orive-Illera, María-Eugenia Pérez-Martínez. Asymptotic structure of the spectrum in a Dirichlet-strip with double periodic perforations. Networks and Heterogeneous Media, 2019, 14 (4) : 733-757. doi: 10.3934/nhm.2019029

[14]

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

[15]

Shi'an Wang, N. U. Ahmed. Optimal control and stabilization of building maintenance units based on minimum principle. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1713-1727. doi: 10.3934/jimo.2020041

[16]

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

[17]

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 and Applied Analysis, 2012, 11 (2) : 501-516. doi: 10.3934/cpaa.2012.11.501

[18]

Peigen Cao, Fang Li, Siyang Liu, Jie Pan. A conjecture on cluster automorphisms of cluster algebras. Electronic Research Archive, 2019, 27: 1-6. doi: 10.3934/era.2019006

[19]

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

[20]

Shuichi Jimbo, Yoshihisa Morita. Asymptotic behavior of entire solutions to reaction-diffusion equations in an infinite star graph. Discrete and Continuous Dynamical Systems, 2021, 41 (9) : 4013-4039. doi: 10.3934/dcds.2021026

2020 Impact Factor: 1.213

Metrics

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

Other articles
by authors

[Back to Top]