CAREER: Computational tools for the analysis of large stochastic networks

通信、信息技术和强大计算资源的当代发展使网络成为数据组织、表示和解释的流行工具。网络使我们能够创建数学上易于处理的模型，这些模型保留了底层系统的重要特征，并避免了与高维和复杂几何形状相关的问题。特别是，网络已经表现出强大的承诺作为一个复杂的物理过程，如蛋白质折叠，相互作用的粒子簇的自组装，和分子马达的行走的建模和分析工具。复杂网络的分析和构建的计算方法的发展有可能促进对晶体生长的理解，并导致基于工业自组装的结构设计，包括相互作用的粒子。拟议的工作将有助于本科生，研究生和博士后学生的科学发展，以及在PI的家乡机构的课程的增强帮助。该项目还将通过网站制作最初开发的软件供公众使用。建议的研究计划是关注的计算工具的发展，分析和建设的随机网络指数小的成对转移率。成对跃迁速率公式中的参数是物理环境中的绝对温度，相对于所考虑的系统中存在的重要能量势垒，绝对温度通常很小。通常，来自复杂物理系统建模的网络是大的（例如，一百万个状态），稀疏和非结构化的，并且它们的成对转移率变化数十个数量级。因此，由于它们的复杂性和与浮点运算相关的严重问题，它们的分析是困难的。研究计画的目标是发展下列四个问题的计算方法：（1）大型随机网路的渐近分析（特别是，找到本征值和本征向量的渐近估计，提取状态的准不变和亚稳态子集，并建立粗粒度模型）;（2）描述所考虑网络中感兴趣的特定跃迁过程的特定本征对的有限温度延拓;（3）建立表示相互作用粒子聚集过程的随机网络;（4）求准势，该函数量化了由小热噪声驱动的时间不可逆系统的动态，并允许将连续的非随机网络具有多个吸引子的梯度系统。所提出的研究的分析组件在于大偏差理论和图论的接口。数值部分涉及网络算法，数值线性代数，优化方法，寻找鞍点的方法，蒙特-卡罗方法，和求解器的哈密尔顿-雅可比型方程。

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.