Approximate Master Equations

Âmes is French for souls. AMEs, the acronym for approximate master equations, are almost as powerful and magical.

The biggest issue with master equations is that they scale directly with the number of states available to the system. Complex systems are generally made of large systems of \(N\) interacting parts. Even in simple binary dynamics, this would imply \(2^N\) possible states for the system. In order to use master equations to model real complex systems, we will need to break down these systems in subsystems and coarse-grain the systems of master equations. Of course, doing so means our approach won’t be exact and won’t fully describe the system, but it is still powerful. We call this approach Approximate Master Equations.

We illustrate AMEs with a few examples below.

AMEs for networks

We will quickly cover two general approaches to AMEs on networks:

• Node-based AMEs which compress networks based on the state of nodes and of their neighbors, introduced in Adaptive networks: Coevolution of disease and topology [Marceau et al., 2010]

• Group-based AMEs which compress networks based on the states of nodes within cliques or groups, introduced Propagation dynamics on networks featuring complex topologies [Hébert-Dufresne et al., 2010]. Some say that the approach is better described in Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks [St-Onge et al., 2021].

The two approaches are summarized on the figure below using a simple network where nodes are either blue or red and groups either triangle or simple links.

The node-based approach breaks down a network based on the states available for nodes and the \(k+1\) states available to their neighborhood of \(k\) neighbors. For example, in binary dynamics, a node of degree 2 can have 3 possible neighborhoods: 2 red nodes, 2 blue nodes, or 1 of each. We can thus write master equations covering all possible states for star-motifs, with a different set of master equations for every degree class in the network. In our example above, the node-based approach is summarized in the top right corner of the cartoon, and would require 24 equations to fully describe. That’s 14 for the hub of degree 6 (7 per state of the hub), 6 for the nodes of degree 2, and 4 for the leaves of degree 1.

The group-based approach breaks down a network based on well-defined groups like fully connected cliques and on the states of nodes they contain. For example, the network above contains cliques of size two (edges) and three (triangles). In binary dynamics, a clique of size \(n\) can be in \(n+1\) states. To couple them, the group-based approach also tracks nodes based on their state and the number of groups they belong to. The entire approach is summarized in the bottom corner of the cartoon. So, this simple example would require 7 group equations and 4 member equations to describe with group-based AMEs; 11 equations total.

Implementation of AMEs

Coming soon!