CAREER: Computational tools for the analysis of large stochastic networks

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

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.