PyGT  Graph transformation and reduction in Python¶
Graph transformation is designed for the analysis of highly metastable (illconditioned) Markov chains, where linear algebra methods fail. [Wales09]
PyGT
produces stable coarsegrained models with exact branching probabilities and mean first passage times, in discrete or continuous time. [Swinburne20a]
Note
You can install PyGT
using the pip
package manager (preferably in a virtual environment):
pip install PyGT
 Simplest possible usage in continuous time with transition rates \(k_{ij}\):
 Vector
tau
of mean state waiting times \(\tau_j=1/\left(\sum_ik_{ij}\right)\)  Sparse or dense matrix
B
of branching probabilities \(B_{ij}=k_{ij}\tau_j\)  Boolean vector
rm_vec
selecting nodes to remove
import PyGT # Removes nodes in blocks of <=50 whilst retaining numerical stability gt_B, gt_tau = PyGT.GT.blockGT(rm_vec,B,tau,block=50,screen=True)
 Vector
Note
Tutorials (see menu) can be run online with binder:
The notebooks can also be cloned from the PyGT
github repo:
# clone entire source code and examples
git clone https://github.com/tomswinburne/PyGT.git
# go to examples folder
cd PyGT/examples
# run notebook
jupyternotebook basicfunctions.ipynb
Graph transformation [Wales09] is a deterministic dimensionality reduction algorithm that iteratively removes nodes from a Markov Chain while preserving the mean first passage time (MFPT) and branching probabilites between the retained nodes. The original Markov chain does not need to satisfy detailed balance.
This package provides an efficient implementation of the graph transformation algorithm, accelerated via partial block matrix inversions [Swinburne20a] for abitrary discretetime or continuoustime Markov chains [Kannan20a]. Code is also provided for the calculation of first passage time statistics and phenomenological rate constants between endpoint macrostates [Wales09] [Swinburne20b].
We also include code for two different approaches to the dimensionality reduction of Markov chains using the graph transformation algorithm. In the first approach, we consider the problem of estimating a reduced Markov chain given a partitioning of the original Markov chain into communities of microstates (nodes) [Kannan20a]. Various implementations of the intercommunity rates are provided, including the simplest expression given by the local equilibrium approximation, as well as the optimal rates originally derived by Hummer and Szabo. In the second approach, which we call partial graph transformation [Swinburne20a] [Kannan20b], select nodes that contribute the least to global dynamics are renormalized away with graph transformation. The result is a smallerdimensional Markov chain that is betterconditioned for further numerical analysis.
All methods are discussed in detail in the following manuscripts, which should also be cited when using this software:
References
[Wales09]  (1, 2, 3) D.J. Wales, Calculating rate constants and committor probabilities for transition networks by graph transformation, J. Chemical Physics (2009), https://doi.org/10.1063/1.3133782 
[Swinburne20a]  (1, 2, 3) T.D. Swinburne and D.J. Wales, Defining, Calculating, and Converging Observables of a Kinetic Transition Network, J. Chemical Theory and Computation (2020), https://doi.org/10.1021/acs.jctc.9b01211 
[Swinburne20b]  T.D. Swinburne, D. Kannan, D.J. Sharpe and D.J. Wales, Rare Events and First Passage Time Statistics From the Energy Landscape, Submitted to J. Chemical Physics (2020) 
[Kannan20a]  (1, 2)

[Kannan20b] 

 PyGT.io
 PyGT.GT
 PyGT.stats
 PyGT.mfpt
 PyGT.spectral
 PyGT.tools
 Basic Tutorial
 Load in matrix and vectors selecting \(\mathcal{A,B}\) regions using the KTN format
 Remove a set of nodes in \(\mathcal{I}\) using graph transformation
 Find full MFPT matrix
 Find communitity MFPT matrix via full MFPT calculation or metastability approx
 Plot ratio of exact to approximate MFPT matrix
 First passage time distribution between \(\mathcal{A}\) and \(\mathcal{B}\)
 MFPTs and Phenomenological Rate Constants
 Coarsegraining Tutorial
 Model 32state network
 GT setup
 Matrix of intermicrostate MFPTs with GT vs. linear algebra methods
 Compute intercommunity weightedMFPTs
 Different routes to obtain the optimal coarsegrained CTMC
 Numerical comparison of coarsegrained Markov chains
 Plot KKRA, HS against exact, LEA and GT systems at high temperature
 Plot KKRA, HS against exact, LEA and GT systems at slightly lower temperature