CAREER: Computational tools for the analysis of large stochastic networks

当代通信、信息技术和强大的计算资源的发展使网络成为数据组织、表示和解释的流行工具。网络允许我们创建数学上易于处理的模型，这些模型保留了底层系统的重要特征，并避免了与高维和复杂几何结构相关的问题。特别是，网络作为复杂物理过程的建模和分析工具，如蛋白质折叠、相互作用粒子簇的自组装和分子马达的行走，已经显示出了强大的前景。用于分析和构建复杂网络的计算方法的发展有可能促进对晶体生长的理解，并导致基于工业自组装的由相互作用的粒子组成的结构设计。建议的工作将有助于本科生、研究生和博士后学生的科学发展，并有助于加强PI所在机构的课程。该项目还将通过一个网站将原始开发的软件提供给公众使用。提出的研究计划是关于计算工具的发展，用于分析和构建具有指数小成对转移率的随机网络。两两转变速率公式中的参数是物理环境中的绝对温度，相对于所考虑的系统中存在的重要能垒，绝对温度通常很小。通常，来自复杂物理系统建模的网络是大型的（例如一百万个状态），稀疏和非结构化的，并且它们的成对转换速率变化几十个数量级。因此，由于其复杂性和与浮点运算相关的严重问题，它们的分析很困难。本研究计划的目标是发展以下四个问题的计算方法：(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.