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

James R. Riehl, Maxwell I. Zimmerman, Matthew F. Singh, Gregory R. Bowman, Shinung Ching

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number20200126
JournalJournal of the Royal Society Interface
Volume17
Issue number170
DOIs
StatePublished - Sep 1 2020

Keywords

  • brain networks
  • energy landscapes
  • fixed points
  • graph partitioning
  • optimization
  • protein folding

Fingerprint

Dive into the research topics of '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'. Together they form a unique fingerprint.

Cite this