An algebraic framework for structured epidemic modelling

(a) Structured multicospans of Petri nets for compartmental models

In this section, we exemplify the categorical approach to compositional modelling by giving the three components of such a framework: (i) a model semantics, for specifying concrete mathematical models of systems, (ii) a composition syntax, for specifying interactions between systems and (iii) a composition rule, for specifying how to compose chosen concrete models according to a given syntactic term. We emphasize that the composition syntax is a logical syntax, in that the composition syntax axiomatizes the rules of well-formed expressions that define a composition of models. By contrast, the model semantics is a denotational semantics that assigns mathematical meaning to the models in a composition. We do not mean semantics in the sense of observed, real-world phenomena and such an interpretation is outside of the scope of this work.

For the model semantics, we use Petri nets in a form called whole-grain Petri nets [11], defined by the diagram of finite sets and functions shown in figure 1c. Thus, a whole-grain Petri net consists of a finite set of places or species $S$, a finite set of transitions $T$, and spans $S\stackrel{is}{\leftarrow }I\stackrel{it}{\to }T$ and $S\stackrel{os}{\leftarrow }O\stackrel{ot}{\to }T$ defining the input and output arcs between states and transitions. A span is similar to a ‘multirelation’ in that pairs of elements may be related with multiplicity. Multiplicity is important for transitions that input or output multiple tokens of the same species, such as an infection transition that yields two infected individuals as output. As an example, consider the susceptible–infected–recovered (SIR) model in figure 1b. This Petri net has three places $S=\{S,I,R\}$ corresponding to susceptible, infected and recovered populations and two transitions corresponding to infection and recovery. The infection transition is the target of two input arcs—one whose source is the place $S$ and one whose source is the place $I$—and the source of two output arcs—both whose target is the place $I$. The recovery transition is the target of a single input arc and the source of a single output arc.

• Download figure
• Open in new tab
• Download PowerPoint

Petri nets are closed systems, meaning that they are isolated from interaction with other systems. Non-compositional modelling approaches focus on explicitly defining and implementing closed systems. However, Petri nets arising in practice can comprise hundreds [12] or thousands [13] of states and transitions, making them unwieldy both to conceptualize and to implement. By contrast, our compositional modelling approach capitalizes on the tendency of real-world systems to coexist in richly structured ecosystems and enables the development and assembly of open-system models.

Structured cospans [14] and decorated cospans [15] are formalisms for turning closed model semantics into open model semantics, in which systems can interact along specified interfaces. Although structured cospans are applicable to a variety of systems, mathematically and in our implementation, we restrict our discussion to the important case of Petri nets. A structured multicospan of Petri nets, or open Petri net (cf. [16]), is a whole-grain Petri net [11] together with a list of finite sets $A_1,\dots ,A_n$ and functions $A_1\to S,\dots ,A_n\to S$. The sets $A_i$, called the feet of the structured multicospan, define an interface for the open Petri net. The functions $A_i\to S$, called the legs of the structured multicospan, select the places of the Petri net which are exposed through the interface. The more standard notion of structured cospan is the special case of $n=2$ legs. The extra flexibility afforded by multicospans is useful in practice. In particular, open Petri nets with arbitrary numbers of legs can be composed using the graphical syntax of UWDs [17], which are a generic graphical syntax for composing relations, database tables, structured multicospans and other undirected systems. A UWD consists of a set of boxes, a set of ports and a set of junctions. Each port is assigned to a box and wired to a junction. Figure 2a depicts a UWD with three boxes, 10 ports and five junctions. A port assigned to the SIR box and a port assigned to the VIvR box are both wired to the top-most junction. Likewise, two junctions connect two ports assigned to the SIR box with two ports assigned to the cross exposure box, and two junctions connect two ports assigned to the VIvR box with two ports assigned to the cross exposure box.

• Download figure
• Open in new tab
• Download PowerPoint

In figure 2, we present a compartmental model for viral dynamics that accounts for vaccination as the composition of three concrete submodels corresponding to (i) a disease spread model for unvaccinated people, (ii) a disease spread model for vaccinated people and (iii) a cross exposure model of the interactions between the two populations. The open Petri nets for these three primitive subsystems are shown in figure 2b. The composition syntax is given by the UWD in figure 2a, which has three boxes, 10 ports and five junctions. The systems compose by identifying places that are connected in the UWD. For example, the recovered populations, labelled $R$, in the SIR and VIvR models are identified in the composite model. The resulting composite model is shown in figure 2c.

In mathematical terms, UWDs form an operad constituting the composition syntax, and the structured multicospans of Petri nets (strictly speaking, their isomorphism classes) form an operad algebra of the UWD syntax. This operadic framework has many advantages. In addition to the modular model specification strategy exemplified in figure 2, the algebra enables a hierarchical model specification strategy in which a submodel may itself be the composite of still more primitive submodels. A syntax for hierarchical modelling is given later in figure 3f. The operadic framework also enables a mathematically rigorous divide-and-conquer workflow by designating subsystems that can be developed and refined in parallel. Updates to submodels do not affect others except through explicitly represented changes to the composition syntax. Furthermore, the syntax provides an opportunity to build assumptions and domain-specific knowledge directly into models and can be used to identify properties or appropriate sampling algorithms of the composite model. These advantages are discussed further in §2d.

• Download figure
• Open in new tab
• Download PowerPoint

The Julia packages AlgebraicPetri and AlgebraicDynamics directly implement the operadic approach described in this section and its extensions in §2c. These packages enable modellers to create executable code for composite models that reflect the modular and hierarchical structure of real-world systems [3].

(b) Mass action kinetics for open Petri nets

A Petri net is a combinatorial description of a dynamical process. The graphical representation and network topology of Petri nets can be analysed to infer structural properties of the system. However, behavioural analyses often require explicit model simulations. These simulations can be computed using discrete sampling algorithms, such as Gillespie’s direct method or tau-leaping, or by interpreting a Petri net as an ordinary differential equation (ODE) and applying standard numerical integration techniques. In this section, we focus on the latter method, which allows for integration with the calibration and analysis toolkits described in §4.

Following Baez & Pollard ([18], Definition 13), we associate an ODE to a Petri net by applying the law of mass action, which states that transitions consume inputs and produce outputs at rates proportional to the product of their input concentrations. To illustrate, define the function $p:S\to {\mathbb{N}}^T$ so that $p(s)$ is the multiset of transitions producing the species $s$. Likewise, define $r:T\to {\mathbb{N}}^S$ so that $r(t)$ is the multiset of species that are inputs to the transition $t$. Its weighted preimage $r^{-1}:S\to {\mathbb{N}}^T$ maps a species $s$ to the multiset of transitions for which it is an input. Each species $s$ in the Petri net is assigned a variable $u_s$ in the ODE. The transitions define the following vector field on the state space ${\mathbb{R}}^S$:

and ${\beta }_t$ is the rate constant associated with transition $t$. These equations define the standard interpretation of Petri nets as systems of ODEs governing chemical reaction networks. Note that the multiset multiplicities represent the stoichiometric coefficients in the chemical reaction interpretation of the Petri net.

When applicable, defining ODEs by Petri nets or composites of Petri nets has significant software advantages. Meaningful, local changes to a Petri net, such as substituting submodels in a composition or adding a single species or transition, often lead to non-trivial, global changes to the corresponding ODE that affect many variables and terms. For example, analysis tools that observe, report and calculate properties of state variables throughout a simulation often refer to a single variable in many places. Therefore, adding or removing a state variable to the system requires making many coordinated changes to the code. This design pattern results in software where local changes to the mathematical model require global changes to the software implementation. By contrast, local changes to a Petri net model requires only local changes to its software implementation in AlgebraicPetri. The transformation of a Petri net into an ODE via the law of mass action automatically and accurately translates these local changes to the Petri net model into global changes to the corresponding ODE. This automation can accelerate the modelling cycle—such as for making modifications in response to new information or testing for policy robustness—which is critical when responding to urgent situations.

(c) Composition of general differential equation models

Mass action kinetics are often insufficient to simulate complex dynamical processes like those found in biology, ecology and epidemiology. In this section, we show how the composition method for Petri nets generalizes to composition methods for models of different types, in particular to models explicitly defined by ODEs or delay differential equations (DDEs).

The composition of Petri nets described in §2a is an example of the categorical formalism of operads and operad algebras, which equip visual grammars with the rigour of algebraic equations. The theme of the operadic approach is to explicitly and independently describe the syntax of composition—how subsystems interact—and the semantics of composition—particular choices of component models for each subsystem. The example of composing Petri nets, in which the syntax is given by a UWD and the semantics by open Petri nets, is one of many examples of the operadic approach to modelling.

Modelling vector-borne pathogens, such as malaria, is an exemplar context for the operadic approach because the pathogen dynamics naturally decompose into distinct scientific domains such as epidemiology and entomology. The Ross–Macdonald class of equational models highlights the decomposition of a vector-borne pathogen epidemic into three subsystems: pathogen dynamics in the vector (mosquito) population, pathogen dynamics in the host (human) population and the dynamics of pathogen transference in the bloodmeal [19]. Syntactically, this composition is defined by a UWD with three boxes corresponding to the three subsystems and with junctions corresponding to populations involved in multiple processes. Figure 3a defines this UWD. To this composition pattern, we apply submodels of increasing complexity and of different types, namely Petri nets in figure 3b, ODEs in figure 3c,d and DDEs in figure 3e. The composition for Petri nets was defined in §2a. The ODE and DDE submodels compose by identifying variables connected in the UWD and summing the rates of change for identified variables. For example, the result of composing the three ODE submodels in figure 3d according to the given composition pattern is

Just as the law of mass action defines a transformation from Petri nets to ODEs, there is also a transformation from ODEs to DDEs giving a trivial dependence on the history. These transformations allow modellers to use different model types to specify the submodels of a composite. For example, in figure 3e the submodels for the pathogen dynamics in hosts and vectors are given by ODEs and in contrast the bloodmeal model is given by a DDE. The composite model is derived by translating the ODE submodels into DDE models and then composing the DDE models with the result being akin to the Sharpe–Lotka model [20]. This formal process gives domain experts the freedom to choose model classes that best fit their field.

(d) Discussion of compositional model specification

In this section, we have presented a compositional approach to modelling that is grounded in the mathematics of applied category theory and implemented directly in software. We conclude with a discussion of this framework.

(a) Typed Petri nets

Category theory emphasizes the importance of morphisms or maps between mathematical objects. In this section, we demonstrate how morphisms between Petri nets can be used to define typed Petri nets.

Petri nets can represent domain-specific type systems. For example, the Petri net $P_{\mathsf{i}\mathsf{n}\mathsf{f}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{u}\mathsf{s}}$ in figure 4a defines a type system for an infectious disease model. It consists of a single species type and three transition types corresponding to (i) spontaneous changes in infection status; (ii) spontaneous changes between non-infection-related strata, such as movement between patches or changes in quarantine status; and (iii) interactions between a pair of individuals. By contrast, the Petri net $P_{\mathsf{v}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{o}\mathsf{r}\text{-}\mathsf{b}\mathsf{o}\mathsf{r}\mathsf{n}\mathsf{e}}$ depicted in figure 4c represents a type system for a vector-borne disease model and has two species types corresponding to the vector and host populations.

• Download figure
• Open in new tab
• Download PowerPoint

A morphism between Petri nets is a map of places, transitions, input arcs and output arcs that preserves the arities of the arcs and respects the sources and targets of the arcs.² For example, the source of an input arc $i$ in the domain Petri net must map to the source of the arc to which $i$ is mapped. Given a Petri net $P_{\mathsf{t}\mathsf{y}\mathsf{p}\mathsf{e}}$ defining the type system, a typed Petri net is a Petri net $P$ together with a morphism $\varphi :P\to P_{\mathsf{t}\mathsf{y}\mathsf{p}\mathsf{e}}$. Figures 4b and 5 give examples of Petri nets typed by $P_{\mathsf{i}\mathsf{n}\mathsf{f}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{u}\mathsf{s}}$.

• Download figure
• Open in new tab
• Download PowerPoint

All of the Petri nets typed by a given type system form a slice category of the category of whole-grain Petri nets. The mathematical features of slice categories guarantee important modelling features. First, typed Petri nets are practical for model checking. A Petri net typed by $P_{\mathsf{i}\mathsf{n}\mathsf{f}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{u}\mathsf{s}}$ assigns each transition to be a spontaneous change in infection, a spontaneous change in strata, or an interaction. The type of a transition must be consistent with the number of input and output arcs connected to it. For example, a typing by $P_{\mathsf{i}\mathsf{n}\mathsf{f}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{u}\mathsf{s}}$ ensures that a transition with interaction type has two inputs and two outputs. Second, typed Petri nets facilitate high-level critiques of a model. For example, a model typed by $P_{\mathsf{v}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{o}\mathsf{r}\text{-}\mathsf{b}\mathsf{o}\mathsf{r}\mathsf{n}\mathsf{e}}$ cannot incorporate vertical transmission from parents to offspring or sexual transmission in either hosts or vectors. This property may contradict known transmission pathways for a specific disease and thus motivate a revision of the model and the type system. Third, features of the type system may also directly translate into features of the typed Petri net. For example, because each transition in $P_{\mathsf{i}\mathsf{n}\mathsf{f}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{u}\mathsf{s}}$ has the same number of inputs and outputs, any Petri net typed by $P_{\mathsf{i}\mathsf{n}\mathsf{f}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{u}\mathsf{s}}$ conserves the total population over time.

Typed Petri nets also provide guardrails for composing models. A Petri net typed by $P_{\mathsf{v}\mathsf{e}\mathsf{c}\mathsf{t}\mathsf{o}\mathsf{r}\text{-}\mathsf{b}\mathsf{o}\mathsf{r}\mathsf{n}\mathsf{e}}$ must assign each species to be of either vector-type or of host-type thereby separating the vector and host populations. The type system also ensures that interactions only occur between vectors and hosts and that no vectors spontaneously become hosts and vice versa. For example in figure 4d, the transition $S_H\to S_V$ which turns susceptible hosts into susceptible vectors is forbidden by the type system. When composing open Petri nets typed by the same type system via the process described in §2a, we can add a constraint that identified species must have the same type. With this check in place, a host subpopulation will not be identified with a vector subpopulation during model composition. Furthermore, under this constraint, the composition of typed Petri nets retains a typing.

Ultimately, a domain-specific typing can guarantee meaningful properties of a model and prevent novice users or automated systems from generating models that contradict common sense or domain expertise.

(b) Stratified compartmental models

A recurring theme in scientific modelling is the importance of stratified models, in which local dynamics are reproduced in multiple strata and strata interact according to a specified scheme. For example, Pooley et al. [23] consider age-stratified models, and Citron et al. [22] compare stratified models defined by a choice of local epidemiological dynamics (SIR, SIS or Ross–Macdonald) and a choice of stratification by location (the flux or simple trip models of metapopulation dynamics). Typed Petri nets offer a general methodology for stratifying models, which contrasts with the by-hand approach taken in [22].

Consider two typed Petri nets, the unstratified disease model $\varphi :P\to P_{\mathsf{t}\mathsf{y}\mathsf{p}\mathsf{e}}$ and a stratification scheme ${\varphi }^{\prime }:P^{\prime }\to P_{\mathsf{t}\mathsf{y}\mathsf{p}\mathsf{e}}$. The stratification of $P$ by $P^{\prime }$ is defined to be the Petri net with places (resp. transitions, input arcs and output arcs) consisting of pairs of places (resp. transitions, input arcs and output arcs) in $P$ and $P^{\prime }$ which have the same type. Because the morphisms $\varphi$ and ${\varphi }^{\prime }$ respect the source and target maps from arcs to species and transitions, the source and target maps in the stratified model are well-defined. Figure 6b gives an example of stratifying the SIR model by a model of quarantine/isolation status. In the stratified model, the place $(S,Q)$ represents the susceptible and quarantining population while $(S,\sim Q)$ represents the susceptible and not quarantining population. The transition mediating the places $(S,\sim Q)$ and $(I,\sim Q)$ represents the infection transition in the SIR model and the interaction between non-quarantining people in the stratification scheme. Because these transitions are both of interaction type and mediate species of the same type, they are paired in the stratified model. Figure 5 gives a palette of additional epidemiological models (SIS and SVIIvR) and stratification schemes (quarantine status, age, the flux model of spatial dynamics and the simple trip model of spatial dynamics).

• Download figure
• Open in new tab
• Download PowerPoint

The categorical abstraction standardizes the definition of model stratification, and its implementation in AlgebraicPetri automates the construction of stratified models under the constraints of the expert-chosen type system. Because the size of stratified models grows quadratically with respect to the sizes of the component models, this framework streamlines the accurate implementation of stratified models as well as the clear communication and critique of stratified models via their components. Many of the advantages described in §2d also apply to the categorical representation of model stratification.

Comparison with [22] highlights the clarity and efficiency that our approach brings to the modelling workflow. Citron et al. [22] investigate the choice of applying candidate models of movement between subpopulations to disease models when calibrated to real-world datasets. They combine three standard disease models (SIR, SIS and Ross–Macdonald) with two choices of movement dynamics (flux and simple trip). In the flux model, people relocate to different patches at fixed rates. In the simple trip model, people are assigned a home patch and temporarily visit other patches. The flux and simple trip models on two patches are expressed as Petri nets in figure 5b(iii)(iv). In [22], the adjustments to the disease models are done manually and do not express a formal relationship between the adjusted models and their component disease and movement models. By contrast, our approach to model stratification formalizes this construction. In particular, the stratification of the Petri nets for the SIR and SIS disease models (figures 4b and 5a(i)) by the Petri nets for the flux and simple trip movement models mirror the differential equation models defined in ([22], eqns 6, 7, 9 and 10). Our software implementation of the mathematical ideas presented in this section can then be applied to automatically generate the stratified models from the palette of component models. As shown in the electronic supplementary material, this implementation greatly reduces the size of the Petri nets that must be encoded by hand. Additionally, this approach makes it easier to extend the methods of Citron et al. [22], since new stratification schemes, once defined and typed, can be seamlessly integrated into the model construction, calibration and analysis pipeline, instead of requiring experts to manually adjust each candidate disease model by each candidate movement model.

Mathematically, a stratified model is a pullback of whole-grain Petri nets, or equivalently a product in the slice category over the given type system. Properties of these well-studied categorical formalisms immediately verify useful properties of stratified Petri nets. For example, consider stratifying a disease model by quarantine status and by spatial dynamics. Since pullback is an associative and commutative binary operation, the order of stratification does not affect the final model. That is, the following procedures are equivalent: stratifying the disease model by spatial dynamics and then by quarantine status, stratifying the disease model by quarantine status and then by spatial dynamics, and stratifying the disease model by the stratification of spatial dynamics by quarantine status (or vice versa).