Resolen un vell problema de la teoria de computació
Model SIR amb xarxes de Petri 29.01.2023 Divulgació  - 

A l’inici de la pandèmia de COVID-19, el professor del Departament de Matemàtiques de la UAB Joachim Kock va començar a experimentar amb models epidemiològics. No va aconseguir millorar-ne les prediccions, però de manera inesperada va fer un descobriment matemàtic que va portar a la solució d’un vell problema de la informàtica teòrica sobre les xarxes de Petri obert des de la dècada de 1980. La recerca s’ha publicat recentment a la prestigiosa revista Journal of the ACM.


Un dels models matemàtics més simples i més utilitzats per descriure epidèmies és l’anomenat model SIR. El model considera la població compartimentada en tres grups: les persones sanes (S), les persones infectades (I) i les persones recuperades i immunes (R). També estipula que hi ha dues transicions possibles entre aquests grups: una té lloc quan una persona sana esdevé una d’infectada perquè s’ha trobat amb una altra que ho estava –ambdues passen a ser persones infectades– i l’altra transició passa quan una persona infectada es recupera.

Aquest model pot ser analitzat matemàticament mitjançant una eina anomenada xarxa de Petri, un tipus de xarxa que compta amb compartiments (els grups de persones) i transicions (els canvis d’un grup a un altre), amb fletxes ponderades per descriure les relacions entre compartiments i transicions (vegeu la figura). A partir de la xarxa de Petri amb els paràmetres que indiquen amb quina taxa s’efectuen les transicions (i que han de ser estimats experimentalment), el model descriu l’evolució dels compartiments i, per tant, de l’epidèmia.

Quan a l’inici de la pandèmia l’investigador de la UAB Joachim Kock va començar a modelitzar la COVID-19 mitjançant xarxes de Petri, volia experimentar amb la idea de considerar les persones no com a grups estadístics sinó com a individus, una idea inspirada en la informàtica teòrica. En aquest àmbit, les xarxes de Petri consideren un nombre determinat de fitxes a cada compartiment, que es mouen d’acord amb les transicions, de tal manera que una transició pot tenir lloc si hi ha prou fitxes als compartiments d’entrada: es consumeixen fitxes als compartiments d’entrada i se’n produeixen de noves als de sortida.

En la informàtica teòrica, l’ús més important de les xarxes de Petri és com a model de la computació concurrent, però aquest estudi presenta un vell problema encara no resolt des de la dècada de 1980. El problema és que existeixen dues maneres diferents de raonar matemàticament sobre les xarxes de Petri com a model de concurrència, dues «semàntiques», que no s’han pogut reconciliar: una semàntica algebraica i una de geomètrica, amb els seus avantatges i els seus inconvenients.

Simular la COVID-19 amb les xarxes de Petri que s’utilitzen en computació per tal de considerar individus «no va ser una bona idea des del punt de vista de l’epidemiologia», explica Kock, «perquè el formalisme d’aquestes xarxes no permetia traçar les persones individualment. Hi havia una obstrucció, i va resultar ser la mateixa obstrucció que impedia reconciliar les semàntiques algebraica i geomètrica, el vell problema de les xarxes de Petri!».

Per tal de trobar-ne una solució, el professor de la UAB va revisar tota la teoria de les xarxes de Petri i va descobrir que calia modificar-ne lleugerament la mateixa definició per tal que aquestes xarxes admetessin fletxes paral·leles en lloc de pesos, és a dir, passar d’un nombre que representa el pes d’una fletxa a un conjunt de fletxes amb aquest nombre d’elements. «A la teoria d’homotopia, un dels meus camps de recerca, aquest tipus de consideració és habitual», concreta Kock. «En aquest cas, en introduir els conjunts de fletxes apareixen maneres de reordenar-les i simetries que no existeixen si tenim en compte només el pes com a nombre, com la definició convencional». El que faltava a les xarxes de Petri convencionals era exactament l’accés a la informació de les simetries d’una xarxa que proporciona la definició del professor Joachim Kock. «Amb una mica de teoria d’homotopia i teoria de categories, vaig demostrar que la nova versió de les xarxes de Petri admet una reconciliació de les dues semàntiques, l’algebraica i la geomètrica.»

La nova definició proposada per Kock ja ha estat utilitzada per altres investigadors (Evan Patterson i el seu equip a Berkeley, EUA) per desenvolupar un programa informàtic basat en xarxes de Petri per modelitzar epidèmies com la covid. «D’aquesta manera es tanca el cercle. La matemàtica abstracta ha permès transferir coneixements i experiència d’una ciència a una altra, en aquest cas de manera inesperada. Vaig buscar una cosa i he acabat trobant-ne una altra de ben diferent. A vegades és productiu experimentar amb idees que no se sap exactament cap a on et portaran», conclou Kock.

Article de recerca:

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

Figura: Relacions entre els compartiments i les transicions en el model SIR, exemple d’una xarxa de Petri. Els cercles simbolitzen els compartiments, els quadrats representen les transicions possibles i les fletxes indiquen quins compartiments participen en quines transicions. El fet que la primera transició doni lloc a dues persones infectades s’indica a la xarxa de Petri amb el pes 2.

 

Correu electrònic  Departament de Matemàtiques
 
Anar a Notícies

Arxiu de notícies

Des de
Fins a
Paraula clau

Departament de Matemàtiques
Edifici C Facultat de Ciències
08193 Bellaterra (Barcelona)
TEL +34 93 581 13 04
FAX +34 93 581 27 90

d.matematiques@uab.cat
 

 

 

2024 Universitat Autònoma de Barcelona