COVID calculations lead to unexpected solution to long-standing problem in theoretical computer science

One of the simplest and most used mathematical models for the spread of infectious diseases is the so-called SIR model. The model considers the population assigned to three compartments: susceptible (S) (that is, healthy individuals), infectious (I), and recovered (R). It further stipulates two possible transitions between these compartments: one occurs when a susceptible individual encounters an infectious, resulting in two infectious individuals; the other transition consists in an infectious individual recovering.

This model can be analysed mathematically via the tool called Petri nets, a class of networks with compartments and transitions, linked up with weighted arrows reflecting the relations between compartments and transitions (see the figure). From a given Petri net, equipped with constants indicating the transition rates of each transition (these constants must be determined experimentally), the model prescribes the evolution of the population compartments, and hence the disease.

^{Relations between compartments and transitions in the SIR model, an example of a Petri net. The circles represent the compatments, the squares represent transitions, and the arrows indicate which compartments are involved in which transitions. The fact that the first transition gives rise to 2 infected individuals is indicated with the weight 2.}

When at the beginning of the pandemic UAB researcher Joachim Kock began to model COVID-19 using Petri nets, he wanted to experiment with the idea of considering actual individuals rather than just compartments, an idea inspired by the use of Petri nets in theoretical computer science.

There Petri nets are considered equipped with a certain number of tokens in each compartment, which move according to the transitions, with the rule that a transition can take place only if there are enough tokens in the input compartments: these tokens are then consumed, and as a result tokens will be produced in the output compartments. The most important use of Petri nets in computer science is as a model for concurrent computation. In that context there is an old problem, open since the 1980s, namely that there exist two different approaches to reasoning mathematically about Petri nets as a model of concurrency, - two semantics, as it is called - which could not be reconciled: one is an algebraic semantics, the other is a geometric semantics, each with its advantages and drawbacks.

“COVID-19 simluation with computer-science-style Petri nets, was not a success from the viewpoint of epidemiology,” Kock explains. “The formalism actually does not allow to trace individuals as tokens. There is an obstruction, and it turned out to be the same obstruction that prevented the reconciliation of the geometric and algebraic semantics, the old problem!"
In order to find a solution, the UAB researcher embarked on a general revision of Petri net theory. He discovered that it was necessary to adjust the very definition of Petri net, so as to allow parallel arrows instead of weights. In other words, pass from a number (the weight of an arrow) to a set of arrows with that number of elements. “In homotopy theory, which is one of my fields of research, this kind of consideration is quite common,” Kock explains. “In this case, the introduction of these sets of arrows leads to the appearance of symmetries which are not visible in the conventional Petri nets, where there is only a number, not a set.” What was missing in the conventional Petri nets was precisely access to this information of symmetries of Petri nets, provided in Kock's new notion. “With a little bit of homotopy theory and category theory, I could prove that the new version of Petri nets allows a reconciliation of the two semantics, the algebraic and the geometric.”

The new definition proposed by Kock has already been used by other researchers (Evan Patterson and his group in Berkeley, USA) to develop Petri-net based software for epidemiological modelling, and in particular for COVID research. “In this way the circle has been closed.

Abstract mathematics allows transfer of knowledge from one field of science to another, in this case quite unexpectedly. I was looking for one thing but ended up finding another. Sometimes it is fruitful to experiment with ideas without knowing in advance where they may lead,” Kock concludes.

Research article:

J. Kock, Whole-grain Petri Nets and Processes, Journal of the ACM. Volume 70 Issue 1 February 2023 Article No.: 1 pp 1–58. DOI: 10.1145/3559103. https://doi.org/10.1145/3559103