Dimension reduction of dynamics on networks using graph automorphisms (Part 1)

Jonathan Ward, University of Leeds. Part of the applied nonlinear dynamics seminars series.

In this talk I will discuss an algorithm to implement "lumping" of the Kolmogorov equations for a general class of continuous-time Markov chains on graphs. For such processes, it is possible in principle to write down a system of ODEs that exactly describe the evolution of the probability distribution of the system being in a given state. However, the size of this system is typically $2^N$, where $N$ is the number of vertices in the graph, and so it is therefore numerically intractable for even modest values of $N$ (e.g. $N>30$).

The presence of graph automorphisms however can significantly reduce the size of the system, in some cases making it numerically tractable to solve. I will propose an algorithm that does this that builds on those used to determine automorphism group generators for sparse graphs. This is work in progress and I\'m looking to get feedback, criticism and suggestions.

Jonathan Ward, University of Leeds