CAREER: Computational tools for the analysis of large stochastic networks

University Of Maryland, College Park, College Park MD

Investigators

Abstract

The contemporary development of communications, information technologies and powerful computing resources has made networks a popular tool for data organization, representation and interpretation. Networks allow us to create mathematically tractable models that preserve important features of the underlying systems and avoid problems associated with high dimensionality and complex geometry. In particular, networks have demonstrated a strong promise as a modeling and analysis tool of complex physical processes such as protein folding, self-assembly of clusters of interacting particles, and walks of molecular motors. The development of computational methods for analysis and construction of complex networks has a potential to advance the understanding of crystal growth and lead to industrial self-assembly based design of structures consisting of interacting particles. The proposed work will help in the scientific development of undergraduate, graduate and post-doctoral students as well as help in the enhancement of the curriculum at the PI's home institution. The project will also make originally developed software through a website for public use. The proposed research program is concerned with the development of computational tools for analysis and construction of stochastic networks with exponentially small pairwise transition rates. The parameter in the formula for the pairwise transition rates is the absolute temperature in the physical context which is usually small relative to important energetic barriers present in the system under consideration. Typically, networks coming from modeling complex physical systems are large (e.g. a million states), sparse and unstructured, and their pairwise transition rates vary by tens of orders of magnitude. As a result, their analysis is difficult due to their complexity and severe issues associated with the floating point arithmetic. The goal of the research program is the development of computational methods for the following four problems: (1) asymptotic analysis of large stochastic networks (in particular, finding asymptotic estimates for the eigenvalues and eigenvectors, extracting quasi-invariant and metastable subsets of states, and building coarse-grained models); (2) finite temperature continuation of specific eigenpairs describing particular transition processes of interest in the considered network; (3) building stochastic networks representing aggregation processes of interacting particles; and (4)finding the quasi-potential, the function quantifying the dynamics of time-irreversible systems driven by small thermal noise and allowing to convert continuous non-gradient systems with multiple attractors to stochastic networks. The analytical components of the proposed research lie in the interface of the Large Deviation theory and the graph theory. The numerical components involve network algorithms, numerical linear algebra, optimization methods, methods for finding saddle points, Monte-Carlo methods, and solvers for the Hamilton-Jacobi type equations.