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

Maria Cameron; Maria Cameron

doi:10.3934/nhm.2014.9.383

Networks and Heterogeneous Media

2014, Volume 9, Issue 3: 383-416. doi: 10.3934/nhm.2014.9.383

Previous Article Next Article

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

Maria Cameron ^{1
,}

1.
University of Maryland, Department of Mathematics, College Park, MD 20742-4015

Received: 01 February 2014 Revised: 01 June 2014
Primary: 65C50, 60J27; Secondary: 60J28.

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.
- Minimum spanning tree,
- optimal $W$-graph,
- asymptotic spectrum,
- Freidlin's cycle,
- metastability,
- Lennard-Jones cluster
Citation: Maria Cameron. Computing the asymptotic spectrum for networks representing energy landscapesusing the minimum spanning tree[J]. Networks and Heterogeneous Media, 2014, 9(3): 383-416. doi: 10.3934/nhm.2014.9.383

Related Papers:

Abstract

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.

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]	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]	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]	http://www-wales.ch.cam.ac.uk/examples/PATHSAMPLE/.
[33]	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.

Reader Comments

Your name:*

Email:*
© 2014 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)