2 Wanneer wordt een ziekte een epidemie?

In 1918 en 1919 overleden er wereldwijd tussen de 20 en 40 miljoen mensen door een snel verspreidend virus. Bekend als de ‘Spaanse griep’ staat deze besmettelijke ziekte in de geschiedenis boeken als de meest verwoestende epidemie ooit. Meer mensen overleden in één jaar aan de Spaanse griep dan tijdens de vier jaar durende Eerste Wereldoorlog (1914-1918). De massale bijeenkomsten voor terugkerende soldaten worden gezien als één van de redenen waardoor de Spaanse griep zich zo snel kon verspreiden.

Er is veel geld voor onderzoek naar sociale netwerken om het verspreiden van ziekten beter te kunnen begrijpen, voorspellen en beïnvloeden. In dit hoofdstuk zullen we zien dat netwerken kunnen worden gebruikt om de verspreiding van een ziekte te simuleren en ook om het lange termijn gedrag te voorspellen. Het modelleren van de verspreiding van ziektes op netwerken is een actief onderzoeksgebied. In dit filmpje (Engels) vertelt Professor Alessandro Vespignani over onderzoek op dit gebied.

In dit hoofdstuk komen we een eerste random graaf model tegen. Random grafen zijn grafen waarbij verbindingen tussen knopen op een willekeurige manier worden geplaatst. Zulke grafen worden onder andere gebruikt als simplificatie van echte netwerken, omdat hun gedrag vaak gemakkelijker te begrijpen is. Ondanks deze simpelere weergave van de realiteit, kunnen random grafen ons inzicht geven in de oorzaak van bepaalde fenomenen.

2.1 SIR model

De overdracht van een ziekte van individu op individu is een ingewikkeld biologisch proces waarbij een pathogeen wordt doorgegeven en het immuunsysteem deze ziekteverwekker probeert te verwijderen. Om de verspreiding van een besmettelijke ziekte door een populatie te begrijpen is niet alleen kennis van de eigenschappen van het pathogeen - zoals de besmettelijkheid en de lengte van de besmettingstijd - belangrijk, maar ook de netwerkstructuur van de populatie waarin de ziekte verspreid. De netwerken die worden gebruikt voor het modelleren van besmettelijke ziekten zijn contact netwerken, waar de knopen personen zijn en er een lijn tussen twee personen is wanneer deze op zodanige manier contact met elkaar hebben dat de ziekte van de ene persoon aan de andere kan worden doorgegeven. Dit netwerk is afhankelijk van de manier waarop een pathogeen zich verspreidt, bijvoorbeeld via de lucht (griep) of via muggen (malaria) of via lichaamscontact (handenschudden is de belangrijkste besmettingsroute van verkoudheden).

Opgave 2.1 Welk van de bovenstaande contact netwerken verwacht je dat de meeste lijnen bevat?

Het SIR model is een belangrijk model voor het verspreiden van besmettelijke ziektes. In dit model worden de knopen in een contact netwerk onderverdeeld in drie verschillende groepen: een groep S die vatbaar is voor de ziekte (Susceptibles), een groep I die geïnfecteerd is met de ziekte (Infected) en een groep R die hersteld zijn van het virus (Recovered). Het verloop van een ziekte wordt bepaald door de structuur van het contact netwerk en twee andere variabelen: de kans $\beta$ dat een knoop in groep I de ziekte doorgeeft aan een buur in groep S en $t_I$ de lengte van een infectie. Het model verloopt als volgt:

In het begin zijn een aantal knopen geïnfecteerd (I) en de rest van de knopen is vatbaar voor de ziekte (S).
Elke knoop $v$ in toestand I blijft $t_I$ tijdstappen besmettelijk.
Voor elke tijdstap heeft $v$ kans $\beta$ om de ziekte door te geven aan ieder van zijn vatbare buren.
Na $t_I$ tijdstappen is $v$ niet langer besmettelijk en verandert zijn toestand naar R.

Dit model is het meest geschikt voor ziektes die je slechts eenmalig kan krijgen, ofwel wanneer je na de ziekte levenslange immuniteit krijgt ofwel doordat de ziekte dodelijk is.

Opgave 2.2 Bekijk het spel VAX!. Hoe verschilt het model dat daar gebruikt wordt voor ziekteverspreiding van het SIR model?

We zullen zien dat de wiskunde die we in dit hoofdstuk bespreken kan helpen bij het bepalen van het lange termijn gedrag van besmettelijke ziektes.

2.2 Erdős-Rényi random grafen

We maken nu kennis met een heel beroemd netwerk model, de Erdős-Rényi random graaf. Dankzij de eenvoudige definitie van dit model kunnen we veel interessante eigenschappen van deze grafen wiskundig bestuderen. De structuur van een Erdős-Rényi random graaf, oftewel de plaatsing van de lijnen in deze grafen, is compleet willekeurig. Wat dat betreft zijn deze grafen een slecht model voor echte netwerken. We zullen in de loop van de webklas zien dat Erdős-Rényi random grafen inderdaad kwalitatief verschillen van echte netwerken. Toch kunnen we op basis van dit simpele model bepaalde fenomenen in echte netwerken beter begrijpen. We zullen zien dat de kwalitatieve verandering van relatief onschuldige ziekte naar epidemie kan worden uitgelegd in termen van dit simpele netwerk model!

Definitie 2.1 Een Erdős-Rényi random graaf $G(n,p)$ is een graaf met $n$ knopen $1, 2, \dots, n$. Elk paar van knopen $\{i,j\}$ heeft kans $p$ om verbonden te zijn door een lijn.

Bovenstaande definitie is in feite niet exact. De precieze definitie van het model $G(n,p)$ is in termen van een kansverdeling over alle grafen met $n$ knopen. Elke graaf $G$ heeft een kans $P(G) = p^m (1-p)^{{n \choose 2} - m}$ om gekozen te worden, waar $m$ zoals gebruikelijk het aantal lijnen in de graaf $G$ voorstelt. Definitie 2.1 geeft nu een procedure om deze grafen te “maken” volgens de kansverdeling $P(G)$.

Opgave 2.3 In deze opgaven bekijken we het Erdős-Rényi graaf model voor $n=3$.

Teken de acht verschillend grafen met $n$ knopen.
Bereken voor de in a. gevonden grafen de kans dat deze gekozen worden voor $p=0$, $p=0.1$, $p=0.5$ en $p=1$.
Leg met een combinatorisch argument uit waarom de uitdrukking $P(G)$ overeenkomt met de kans dat de Erdős-Rényi random graaf $G(n,p)$ in Definitie 2.1 het netwerk $G$ genereert.

Bovenstaand model draagt de namen van Paul Erdős en Alfréd Rényi dankzij een beroemde reeks artikelen die zij eind jaren 50 en begin jaren 60 publiceerden en waarin zij vele eigenschappen van dit model bestudeerden. Wij zullen nu één van de belangrijkste eigenschappen van dit model bespreken, de zogenaamde percolatie grens van het model. Allereerst enige intuïtie: in Afbeelding 2.1 zien we vijf verschillende grafen die gegenereerd zijn volgens $G(n,p)$ met $n=200$ en $p$ oplopend van $0.002$ tot $0.01$. Voor lage waarden van $p$ bestaat de graaf uit veel kleine componenten (zie Definitie 2.2) terwijl voor hogere waarden van $p$ naast een aantal kleine componenten ook één “gigantische” component ontstaat. We zullen zien dat er een grenswaarde $p^*$ bestaat zodanig dat de graaf $G(n,p)$ bijna zeker geen gigantische component bevat wanneer $p < p^*$ en bijna zeker wel een gigantische component bevat wanneer $p > p^*$. Deze waarde $p^*$ wordt de percolatie grens genoemd.

Vijf grafen gegenereerd met het $G(n,p)$ model. Voor alle vijf de grafen is $n$ gelijk aan $200$. De waarde voor $p$ verschilt, van links naar rechts is deze gelijk aan $0.002, 0.004, 0.006, 0.008$ en $0.01$

Afbeelding 2.1: Vijf grafen gegenereerd met het $G(n,p)$ model. Voor alle vijf de grafen is $n$ gelijk aan $200$. De waarde voor $p$ verschilt, van links naar rechts is deze gelijk aan $0.002, 0.004, 0.006, 0.008$ en $0.01$

Definitie 2.2 Een component van een graaf $G=(V,E)$ is een verzameling knopen $C \subseteq V$ zodaning dat tussen alle knopen in $C$ minstens één pad bestaat én er geen knoop bestaat in $V \backslash C$ die kan worden toegevoegd aan $C$ en deze eigenschap bewaart.

Opgave 2.4 Hoeveel componenten heeft een samenhangende graaf?

Voordat we de percolatie grens bepalen, beginnen we met een makkelijker af te leiden eigenschap, om de smaak te pakken te krijgen. We gaan het verwachte aantal lijnen in $G(n,p)$ uitrekenen. Het totaal aantal verschillende grafen met $n$ knopen en $m$ lijnen is gelijk aan ${{n \choose 2} \choose m}$.

Opgave 2.5 Leg uit waarom het aantal verschillende grafen met $n$ knopen en $m$ lijnen gelijk is aan ${{n \choose 2} \choose m}$.

Al deze grafen komen voor met kans $P(G)$ en dus is de kans om een graaf met $m$ lijnen te genereren gelijk aan \[P(m) = {{n \choose 2} \choose m} p^m(1-p)^{{n \choose 2} - m}.\] Dit is de standaard binomiale verdeling en de gemiddelde waarde voor $m$ is gegeven door ${n \choose 2}p$.

Opgave 2.6 Leid de gemiddelde waarde voor het aantal lijnen $m$ af door directe berekening: \[E(m) = \sum_{m=0}^{{n \choose 2}} m {{n \choose 2} \choose m} p^m(1-p)^{{n \choose 2} - m} \] (je mag dit Googlen). Om de notatie iets te vereenvoudigen volstaat het om te bewijzen dat voor een willekeurig natuurlijk getal $n$ geldt \[\sum_{m=0}^{n} m {n \choose m} p^m(1-p)^{n - m} = np. \] Hint: Laat eerst zien dat $m {n \choose m} = n {n-1 \choose m-1}$ voor $m \geq 1$ en herinner het binomium van Newton.

Het is niet zo verrassend dat het gemiddelde aantal lijnen in een Erdős-Rényi random graaf $G(n,p)$ gelijk is aan ${n \choose 2}p$ aangezien ${n \choose 2}$ het totaal aantal mogelijke lijnen is voor een graaf met $n$ knopen en elke lijn met kans $p$ aanwezig is.

We kunnen nu ook gemakkelijk de gemiddelde graad van de knopen in $G(n,p)$ uitrekenen: \[E(k) = \sum_{m=0}^{{n \choose 2}} \frac{2m}{n} P(m)\]

Opgave 2.7 Reken E(k) uit. Geef ook een heuristisch argument voor deze uitkomst.

2.3 Percolatie voor Erdős-Rényi grafen

De graaf $G(n,p)$ voor $p$ gelijk aan $0$ bevat geen enkele lijn en bestaat dus uit $n$ geïsoleerde knopen. Wanneer $p$ daarentegen gelijk is aan $1$ bevat $G(n,p)$ alle ${n \choose 2}$ mogelijke lijnen, oftewel $G(n,1)$ is de volledige graaf met $n$ knopen. Voor beide grafen kunnen we de grootte van de grootste component bepalen. De graaf $G(n,0)$ bestaat uit $n$ componenten van grootte $1$ en dus is de grootte van de grootste component ook gelijk aan 1. De graaf $G(n,1)$ daarentegen bestaat uit één component van grootte $n$, in dit geval is de grootte van de grootste component dus $n$. Behalve het feit dat de grootste component in $G(n,1)$ veel groter is dan die in $G(n,0)$ is er ook een kwalitatief verschil. Voor $G(n,0)$ is de grootte van de grootste component onafhankelijk van $n$, terwijl deze voor $G(n,1)$ proportioneel is ten opzichte van $n$. Natuurkundigen noemen de grootte omvangrijk, wanneer deze proportioneel is ten opzichte van $n$.

We bestuderen nu hoe de grootte van de grootste component verandert naarmate $p$ toeneemt. Zoals eerder genoemd en geïllustreerd in Afbeelding 2.1 is er een plotselinge overgang van constante grootte naar omvangrijke grootte.

Opgave 2.8 Geef een schatting voor de waarde van $p^*$ in $G(200,p)$ waar de grootte van de grootste component veranderd van constante grootte naar omvangrijke grootte.

Definitie 2.3 We noemen een component waarvan de grootte proportioneel groeit ten opzichte van $n$ een gigantische component, m.a.w. de grootte van de component $|C| \approx k n$ voor een zeker getal $k$.

Opgave 2.9 Laat $u$ de fractie van knopen zijn die geen deel uitmaken van een gigantische component.

Leg uit waarom $u$ gelijk is aan $1$ voor $G(n,0)$.
Wat is $u$ voor $G(n,1)$?
Wat kun je zeggen over $u$ in relatie tot de grootte $n$ van het netwerk voor een netwerk dat een gigantische component bevat.

We kunnen $u$ ook beschouwen als de kans dat een knoop geen deel uitmaakt van de gigantische component. Wanneer $i$ een knoop is die geen deel uitmaakt van de gigantische component, dan kunnen we voor alle andere knopen $j \neq i$ onderscheid maken tussen de volgende twee situaties. Of (a) er is geen lijn tussen de knopen $i$ en $j$ of (b) de lijn $\{i,j\}$ bestaat wel en de knoop $j$ maakt ook geen deel uit van de gigantische component. We kunnen de kans dat $i$ niet via $j$ verbonden is met de gigantische component nu schatten als $(1-p)$ (de kans dat $i$ en $j$ niet verbonden zijn) + $pu$ (de kans dat $i$ en $j$ verbonden zijn maal de kans dat $j$ geen deel uitmaakt van de gigantische component). De kans dat $i$ niet verbonden is met de gigantische component via ieder van de andere $n-1$ knopen is dus gelijk aan $u = (1-p+pu)^{n-1}$.

Opgave 2.10 Maak gebruik van de schatting $\ln(1 + x) \simeq x$ om de volgende vergelijking af te leiden:

\[u \simeq e^{-p(n-1)(1-u)}\]

Om een idee te krijgen waarom de schatting $\ln(1 + x) \simeq x$ klopt, bekijk eens de grafiek van de functie $\frac{\ln(1+x)}{x}$ in je grafische rekenmachine rond $x=0$.

Deze vergelijking wordt exact in de limiet voor $n \rightarrow \infty$. Laat nu $S$ de fractie van knopen zijn die wel deel uitmaken van de gigantische component, oftewel $S = 1 - u$. We vinden dus de volgende vergelijking voor $S$ voor de limiet van grote netwerken

\[S = 1 - e^{-p(n-1)S} = 1 - e^{-cS},\] met $c := p(n-1)$ de gemiddelde graad van knopen in $G(n,p)$ (zie Opgave 2.7). Deze vergelijking geeft een relatie tussen de grootte van de gigantische component en de gemiddelde graad van knopen. We kunnen deze vergelijking niet gemakkelijk exact oplossen, maar we kunnen wel een goed idee krijgen over het gedrag van $S$ voor verschillende waarden van $c$ door naar de grafiek van de functie $y(S) = 1 - e^{-cS}$ te kijken.

Afbeelding 2.2: Interactieve app om het gedrag van $S$ te bestuderen voor verschillende waardes van $c$. Als de app niet laad open dan deze link.

Opgave 2.11 In deze opgave bestuderen we het gedrag van $S$ afhankelijk van $c$.

Laat zien dat $S=0$ altijd een oplossing is van de vergelijking $S=1-e^{-cS}$.
Gebruik de interactieve app in Afbeelding 2.2 om te bepalen vanaf welke waarde voor $c$ de vergelijking $S=1-e^{-cS}$ een tweede oplossing heeft. Geef een bewijs hiervoor door de afgeleides van de functies $1 - e^{-cx}$ en $x$ met elkaar te vergelijken.
Voor welke waarden van $c$ kan er dus een gigantische component bestaan?

We hebben nog niet laten zien dat er ook daadwerkelijk een gigantische component bestaat voor waarden van $c$ waar de vergelijking $S=1-e^{-cS}$ een tweede oplossing heeft. Dit kan worden nagegaan door naar de omgeving van een groepje verbonden knopen te kijken. Hier wijden we niet verder over uit. Het punt waarop het gedrag van deze vergelijking van een naar twee oplossingen verandert is de percolatie grens.

2.4 Voorbeelden van percolatie

Hoe kunnen we met wat we geleerd hebben over Erdős-Rényi grafen de verspreiding van besmettelijke ziektes beter begrijpen? Laten we aannemen dat ons contact netwerk in feite de complete graaf is, oftewel alle knopen kunnen alle andere knopen in principe besmetten en dat een knoop precies één tijdseenheid ziek is (oftewel $t_I = 1$). Het SIR model is een dynamische model (veranderend in de tijd), maar verrassend genoeg kunnen we in dit geval direct iets zeggen over het lange termijn gedrag.

Stel je nu voor dat op een gegeven moment in ons model knoop $v$ besmet raakt met de ziekte. In de volgende tijdstap is er een kans $\beta$ dat de ziekte wordt overgedragen voor een buur $w$ die vatbaar is voor de ziekte. We kunnen dit zien als de uitkomst van het opgooien van een oneerlijke munt, die met kans $\beta$ op “kop” landt. Het maakt nu niet uit of we deze munt aan het begin van het model gooien om te beslissen of de ziekte van $v$ aan $w$ wordt doorgegeven wanneer $v$ ziek wordt, of dat we dit doen zodra $v$ ziek wordt.

Als we zo blijven redeneren, kunnen we voor elk paar knopen alvast een munt opgooien, en alleen de lijnen waarvoor we “kop” krijgen toevoegen aan het netwerk. Dit zijn precies de lijnen waar de ziekte wordt doorgegeven als één van de aangrenzende knopen geïnfecteerd wordt. Maar dit is precies een Erdős-Rényi graaf met $p = \beta$! Op lange termijn zal de ziekte zich verspreiden door de gehele componenten waarin de eerste geïnfecteerde knopen zich bevinden. Wanneer $p=\beta$ dusdanig groot is dat $p(n-1) > 1$ is, is er een grote kans dat de eerste geïnfecteerde knopen zich in de gigantische component bevinden, en de ziekte een epidemie veroorzaakt. De percolatie grens voor een besmettelijke ziekte wordt aangeduid met $R_0$. Bekijk dit fragment uit de film Contagion, waarin Kate Winslet uitleg geeft over $R_0$.

Voor een meer realistisch SIR model waarin we gebruik maken van een echt contact netwerk, en dus niet meer aannemen dat elke individu elke andere individu in principe kan besmetten, kunnen we op een algemenere manier over percolatie na denken. We beschrijven dit algemene percolatie model als volgt

Laat $G$ een willekeurige graaf zijn en kies een parameter $0 \leq q \leq 1$.
Verwijder elke lijn in $G$ met kans $q$.

Opgave 2.12 Beschouw de graaf $G(n,p)$ in termen van het bovenstaande percolatie model.

Wat is $G$?
Wat is $q$?

Een veel bestudeerd voorbeeld van bovenstaand percolatie model is op het rooster $\mathbb{Z}^d$. In Afbeelding 2.3 zie je een voorbeeld van een klein deel van dit rooster voor $d=2$ en $q=0.5$.

Een voorbeeld van percolatie op een rooster met $q=0.5$, gemaakt met de [software van Robert Fitzner](http://www.fitzner.nl/simulator/index.html). De verschillende kleuren geven de componenten aan.

Afbeelding 2.3: Een voorbeeld van percolatie op een rooster met $q=0.5$, gemaakt met de software van Robert Fitzner. De verschillende kleuren geven de componenten aan.

Voor dit algemenere percolatie model is de vraag of er wederom een percolatie grens bestaat en zo ja wat deze is. Deze vraag is in het algemeen erg lastig te beantwoorden. Voor het rooster $\mathbb{Z}^d$ weten we het volgende. Voor de roosters $\mathbb{Z}^d$ bestaat er een percolatie grens voor alle dimensies $d$. Voor $d=1$ en $d=2$ zijn deze bekend, maar voor $d > 2$ zijn deze waarden onbekend.

Opgave 2.13 a. Teken een deel van het 1-dimensionale `rooster’ $\mathbb{Z}$.

Wat denk je dat de waarde van de percolatie grens is voor $\mathbb{Z}$?
Wat denk je dat de waarde van de percolatie grens is voor $\mathbb{Z}^2$ - bekijk dit eventueel experimenteel met de Applet voor percolatie te vinden op deze website.

Wetenschappers bestuderen percolatietheorie met een grote variatie aan motivaties. Binnen de fundamentele wiskunde zijn er verbanden met random fractals, conformal invariantie, groepentheorie en sensitiviteit voor ruis. Ook binnen de natuurkunde zijn er verschillende theoretische toepassing: het Ising model dat over magnetisme gaat, quantumveldentheorie en quantum zwaartekracht. In meer toegepaste gebieden wordt percolatie theorie gebruikt om stroming door poreuse materialen te bestuderen, het vormen van sterrenstelsels, tandverval en zoals we al eerder hebben gezien, het verspreiden van besmettelijke ziektes.

Bonusopgave 2.1 (technische uitdaging van de week) Schrijf een programma met als input een geheel getal $n$ en een getal $0 \leq p \leq 1$ dat een willekeurige graaf $G(n,p)$ genereert. Je kunt zelf kiezen in welk formaat je deze graaf teruggeeft, bijvoorbeeld als adjacency matrix, als verzamelingen $V$ en $E$, als een lijst van de lijnen of als een afbeelding van de graaf. Laat door middel van simulatie zien dat het gemiddelde aantal driehoeken in een graaf gelijk is aan ${n \choose 3} p^3$ en het dat gemiddelde aantal geïsoleerde knopen gelijk is aan $n(1-p)^{n-1}$. Bedenk zelf eigenschappen van de random graaf waarvan je de gemiddelde waarde kunt benaderen door middel van simulatie.

Bonusopgave 2.2 (creatieve uitdaging van de week) Het verspreiden van social media posts lijkt erg op hoe een virus zich verspreid in een contact netwerk. Een post die door een groot aantal mensen bekeken en gedeeld wordt heet niet voor niets viral. Creëer een interessante/grappige/verrassende/belangrijke post en deel deze via social media. Probeer je post door zoveel mogelijk mensen te laten delen. Vertel op het forum hoeveel likes, shares, retweets, comments je hebt gehad. Kun je een visualisatie maken van de verspreiding van jouw post op een sociaal netwerk?