Computing and Optimizing Over All Fixed-Points of Discrete Systems on Large Networks
Computing and Optimizing Over All Fixed-Points of Discrete Systems on Large Networks
复制标题
DOI：
10.1098/rsif.2020.0126
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
James R. Riehl;Maxwell I. Zimmerman;Matthew F. Singh;G. Bowman;ShiNung Ching
中科院分区：
文献类型：
--
作者：
James R. Riehl;Maxwell I. Zimmerman;Matthew F. Singh;G. Bowman;ShiNung Ching
平衡点，或不动点，在各种领域的动力系统中起着重要的作用，然而找到它们在计算上是具有挑战性的。在这里，我们展示了如何有效地计算稀疏网络上离散值、离散时间系统的所有平衡点。使用图划分，我们递归地将原始问题分解为一组更小，更简单的问题，这些问题易于计算，并且其解组合产生完整的平衡集。这使得在任意大的网络上找到满足某些标准的系统固定点成为可能。这种方法也可以在不计算完整平衡集的情况下使用，因为在某些情况下，完整平衡集可能会变得非常大。例如，人们可以使用这种方法来检查平衡点的存在性和总数，或者找到相对于给定成本函数的最优平衡点。我们用两个科学领域的例子证明了这种方法的潜在能力：计算大脑网络中固定点的数量和寻找基于晶格的蛋白质折叠模型的最小能量构象。
Equilibria, or fixed points, play an important role in dynamical systems across various domains, yet finding them can be computationally challenging. Here, we show how to efficiently compute all equilibrium points of discrete-valued, discrete-time systems on sparse networks. Using graph partitioning, we recursively decompose the original problem into a set of smaller, simpler problems that are easy to compute, and whose solutions combine to yield the full equilibrium set. This makes it possible to find the fixed points of systems on arbitrarily large networks meeting certain criteria. This approach can also be used without computing the full equilibrium set, which may grow very large in some cases. For example, one can use this method to check the existence and total number of equilibria, or to find equilibria that are optimal with respect to a given cost function. We demonstrate the potential capabilities of this approach with examples in two scientific domains: computing the number of fixed points in brain networks and finding the minimal energy conformations of lattice-based protein folding models.