Graph transformation and shortest paths algorithms for finite Markov chains

Nanoparticle cluster formation mechanisms elucidated via Markov state modeling: Attraction range effects, aggregation pathways, and counterintuitive transition rates

Nanoparticle clusters are promising candidates for developing functional materials. However, it is still a challenging task to fabricate them in a predictable and controllable way, which requires investigation of the possible mechanisms underlying cluster formation at the nanoscale. By constructing Markov state models (MSMs) at the microstate level, we find that for highly dispersed particles to form a highly aggregated cluster, there are multiple coexisting pathways, which correspond to direct aggregation, or pathways that need to pass through partially aggregated, intermediate states. Varying the range of attraction between nanoparticles is found to significantly affect pathways. As the attraction range becomes narrower, compared to direct aggregation, some pathways that need to pass through partially aggregated intermediate states become more competitive. In addition, from MSMs constructed at the macrostate level, the aggregation rate is found to be counterintuitively lower with a lower free-energy barrier, which is also discussed.

Nearly reducible finite Markov chains: Theory and algorithms

Finite Markov chains, memoryless random walks on complex networks, appear commonly as models for stochastic dynamics in condensed matter physics, biophysics, ecology, epidemiology, economics, and elsewhere. Here, we review exact numerical methods for the analysis of arbitrary discrete- and continuous-time Markovian networks. We focus on numerically stable methods that are required to treat nearly reducible Markov chains, which exhibit a separation of characteristic timescales and are therefore ill-conditioned. In this metastable regime, dense linear algebra methods are afflicted by propagation of error in the finite precision arithmetic, and the kinetic Monte Carlo algorithm to simulate paths is unfeasibly inefficient. Furthermore, iterative eigendecomposition methods fail to converge without the use of nontrivial and system-specific preconditioning techniques. An alternative approach is provided by state reduction procedures, which do not require additional a priori knowledge of the Markov chain. Macroscopic dynamical quantities, such as moments of the first passage time distribution for a transition to an absorbing state, and microscopic properties, such as the stationary, committor, and visitation probabilities for nodes, can be computed robustly using state reduction algorithms. The related kinetic path sampling algorithm allows for efficient sampling of trajectories on a nearly reducible Markov chain. Thus, all of the information required to determine the kinetically relevant transition mechanisms, and to identify the states that have a dominant effect on the global dynamics, can be computed reliably even for computationally challenging models. Rare events are a ubiquitous feature of realistic dynamical systems, and so the methods described herein are valuable in many practical applications.