PyGT.GT

Iteratively remove nodes from a Markov chain with graph transformation

This module implements the graph transformation algorithm to eliminate nodes from a discrete- or continuous-time Markov chain. When the removed nodes are chosen judiciously, the resulting network is less sparse, of lower dimensionality, and is generally better-conditioned. See PyGT.tools for various tools which help select nodes to eliminate, namely, ranking nodes based on their mean waiting times and equilibrium occupation probabilities. [Kannan20b]

The graph transformation algorithm requires a branching probability matrix \(\textbf{B}\) with elements \(B_{ij}=k_{ij}{\tau}_j\) where \(k_{ij}\) is the \(i \leftarrow j\) inter-microstate transition rate and \(\tau_j\) is the mean waiting time of node \(j\). In a discrete-time Markov chain, \(\textbf{B}\) is replaced with the discrete-time transition probability matrix \(\textbf{T}(\tau)\) and the waiting times of all nodes are uniform, equal to the lag time \(\tau\).

In each iteration of GT, a single node \(x\) is removed, and the branching probabilities and waiting times of the neighboring nodes are updated according to

\[\begin{split}\begin{eqnarray} B_{ij}^{\prime} &\leftarrow B_{ij} + \frac{B_{ix}B_{xj}}{1-B_{xx}} \\ \tau_j^\prime &\leftarrow \tau_j + \frac{B_{xj}\tau_j}{1-B_{xx}} \end{eqnarray}\end{split}\]

A matrix version of the above equations permits the removal of blocks of nodes simulatenously. The code monitors for stability in the inversion algorithm, to allow for for one-by-one node removal instead if a block is ill-conditioned. [Swinburne20a]

PyGT.GT.blockGT(rm_vec, B, tau, block=20, order=None, rates=False, Ndense=50, screen=False, cond_thresh=10000000000000.0)[source]

Main function for GT code, production of a reduced matrix by graph transformation.

Parameters:
  • rm_vec ((N,) array-like, bool) – Boolean array of which nodes to remove
  • B ((N,N) dense or sparse matrix) – Matrix of branching probabilities (CTMC) or transition probabilities (DTMC)
  • tau ((N,) array-like) – Array of waiting times (CTMC) or lag times (DTMC)
  • block (int, optional) – Number of node to attempt to remove simultaneously. Default = 20
  • order ((N,) array-like, optional) – Order in which to remove nodes. Default ranks on node connectivity. Modify with caution: large effect on performance
  • rates (bool, optional) – Whether to return the GT-reduced rate matrix in addition to B and tau. Only vaid for CTMC case. Default = False
  • Ndense (int, optional) – Force switch to dense representation if N<Ndense. Default = 50
  • screen (bool, optional) – Whether to print progress of GT. Default = False
  • cond_thresh (float, optional) – Threshold condition number below which block matrix inversion is attempted. If block condition number is too high, conventional GT is used to remove nodes, which is less efficient but more stable. Default= 1e13
Returns:

  • B ((N’,N’) dense or sparse matrix) – Matrix of N’<N renormalized branching probabilities. Will be returned as same type (sparse/dense) as input
  • tau ((N’,) array-like) – Array of N’<N renormalized waiting times
  • K ((N’,N’) dense or sparse matrix (same type as B)) – Matrix of N’<N renormalized transition rates. Only if rates=True
PyGT.GT.singleGT(rm_vec, B, tau, cond_thresh=10000000000000.0)[source]

Single iteration of GT algorithm used by main GT function. Either removes a single node with float precision correction [Wales09] or attemps node removal via matrix inversion [Swinburne20a]. In the latter case, if an error is raised by np.linalg.inv this is communicated through success

Parameters:
  • rm_vec ((N,) array-like, bool) – Boolean array of which nodes to remove
  • B ((N,N) dense or sparse matrix) – Matrix of branching probabilities
  • tau ((N,) array-like) – Array of waiting times
  • cond_thresh (float, optional) – Threshold condition number below which matrix inversion is attempted. If condition number is higher than cond_thresh, singleGT() returns success=False. Default= 1.0e13
Returns:

  • B ((N’,N’) dense or sparse matrix) – Matrix of N’<N renormalized branching probabilities
  • tau ((N’,) array-like) – Array of N’<N renormalized waiting times
  • success (bool) – False if estimated condition number is too high or LinAlgError raised by np.linalg.inv