PyGT.spectral

Spectral analysis for community-based dimensionality reduction

Produce projection matricies in order to reduce a CTMC rate matrix from a given community structure, using the local equilibrium approximation (LEA) or spectral clustering method as investigated in [Swinburne20b].

The LEA method assumes each community is locally metastable, meaning the distribution of states in each community will be approximately proportional to the local Boltzmann distribution \(\pi_j\).

The LEA thus takes a single left and right vector pair per community J, namely

\[\begin{equation} [{\bf 1}_J]_j = \delta(j\in J) ,\quad [\hat{\pi}_J]_j=\delta(j\in J) \frac{\pi_j}{\sum_{j'\in J}\pi_{j'}}, \end{equation}\]

to produce the reduced rate matrix, which corresponds to the local equilibrum distribution projected onto the community.

The spectral clustering method generalizes this approach, performing a local eigendecomposition and projection to generate a set of left and right vector pairs, from which a subset is used to produce the reduced rate matrix. In particular, the set is projected such that the slowest eigenvector pair becomes the LEA pair \(({\bf 1}_J,\hat{\pi}_J)\), allowing interpolation between the LEA and the exact solution

The vector pairs are chosen until the first nmoments moments of the community escape time is reprodued to a relative error of tol. Further details can be found in [Swinburne20b].

PyGT.spectral.project() returns left and right projections matricies \({\bf Y,X}\) such that the reduction operation is given by

\[\begin{equation} {\bf Q}\in\mathbb{R}^{N\times N} \to {\bf Y}{\bf Q}{\bf X}\in\mathbb{R}^{N'\times N'} ,\quad N'\leq N \end{equation}\]

With an error tolerance tol=0 we recover the exact solution, i.e. \(N'\to N, {\bf Y}\to\mathbb{I}_N, {\bf X}\to\mathbb{I}_N\)

PyGT.spectral.reduce() uses these matricies to produce the reduced rate matrix and reduced left and right stationary vectors and initial distribution \(\rho\) given by

\[\begin{equation} \hat{\pi}\in\mathbb{R}^{N} \to {\bf Y}\hat{\pi}\in\mathbb{R}^{N'} ,\quad {\bf1}\in\mathbb{R}^{N} \to {\bf1}{\bf X}\in\mathbb{R}^{N'} ,\quad {\rho}\in\mathbb{R}^{N} \to {\bf Y}{\rho}\in\mathbb{R}^{N'} \end{equation}\]




PyGT.spectral.reduce(communities, pi, Q, initial_dist=None, style='specBP', nmoments=2, tol=0.01)[source]

Returns a reduced rate matrix and initial distribution (optional) using PyGT.spectral.project()

Parameters:
  • communities (dict) – mapping from community ID (0-indexed) to a boolean array of shape (N, ) which selects out the states in that community. Communities must be disjoint.
  • pi ((N,) array-like) – stationary distribution
  • Q ((N, N) array-like) – rate matrix
  • initial_dist ((N,) array-like, optional) – Initial probability distribution for first passage time problems, for example the local Boltzmann distribtion of a community Default=None
  • style (string, optional) –

    Reduction method. Must be one of

    • LEA : Apply local equilibrum approximation.
    • specBP : Perform spectral reduction with mode basis modified such that slowest mode becomes the LEA mode, with all other modes orthogonal to this mode but not mutually orthonormal. (Default)
    • specBPO : Perform spectral reduction with mode basis rotated such that slowest mode becomes the LEA mode, with all other modes mutually orthonormal. Gives similar results to specBP.
  • nmoments (int, optional) – Number of escape time moments to monitor for accuracy. Ignored if style=LEA. Higher number implies less reduction in matrix rank. Default=2.
  • tol (float, optional) – Relative error tolerance for moments. Ignored if style=LEA. Default=0.01
  • communities – mapping from community ID (0-indexed) to a boolean array of shape (N, ) which selects out the states in that community. Communities must be disjoint.
  • pi – stationary Boltzmann distribution for entire system
  • Q – rate matrix
Returns:

  • Q ((N’, N’) array-like) – Reduced rate matrix
  • pi ((N’,2) array-like) – Reduced left and right stationary distribution vectors for calculation of first passage distributions. With no projection pi[0] = vector of ones, pi[1] = Boltzmann distribution.
  • rho ((N’) array-like) – Reduced initial distribution (only if initial_dist is provided)
PyGT.spectral.project(communities, pi, Q, style='specBP', nmoments=2, tol=0.01)[source]

Produce a projection matricies in order to reduce a CTMC rate matrix from a given community structure.

Parameters:
  • communities (dict) – mapping from community ID (0-indexed) to a boolean array of shape (N, ) which selects out the states in that community. Communities must be disjoint.
  • pi ((N,) array-like) – stationary distribution
  • Q ((N, N) array-like) – rate matrix
  • style (string, optional) –

    Reduction method. Must be one of

    • LEA : Apply local equilibrum approximation.
    • specBP : Perform spectral reduction with mode basis modified such that slowest mode becomes the LEA mode, with all other modes orthogonal to this mode but not mutually orthonormal. (Default)
    • specBPO : Perform spectral reduction with mode basis rotated such that slowest mode becomes the LEA mode, with all other modes mutually orthonormal. Gives similar results to specBP.
  • nmoments (int, optional) – Number of escape time moments to monitor for accuracy. Ignored if style=LEA. Higher number implies less reduction in matrix rank. Default=2.
  • tol (float, optional) – Relative error tolerance for moments. Ignored if style=LEA. Default=0.01
Returns:

  • Y ((N’, N) array-like) – left projection matrix
  • X ((N, N’) array-like) – right projection matrix