# American Institute of Mathematical Sciences

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] 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] 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 [10] 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 [11] 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 & Heterogeneous Media, 2019, 14 (4) : 733-757. doi: 10.3934/nhm.2019029 [12] 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 [13] 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 [14] 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 [15] Jean Dolbeault, Marta García-Huidobro, Rául Manásevich. Interpolation inequalities in $\mathrm W^{1,p}( {\mathbb S}^1)$ and carré du champ methods. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 375-394. doi: 10.3934/dcds.2020014 [16] 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 [17] 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 [18] 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 [19] 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 [20] 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

2018 Impact Factor: 0.871

## Metrics

• HTML views (0)
• Cited by (0)

• on AIMS