Komplexní sítě můžeme zkoumat i z pohledu různých procesů, které na nich probíhají, speciálně nás budou zajímat procesy šíření. V síti se můžou šířit viry (ať už biologické, nebo počítačové) anebo třeba informace. Dynamika šíření v sítích je velmi zajímavá z praktického pohledu. Dále se budeme zabývat modelem šíření epidemie.
Rozlišujeme následující stavy osob:
Klasický epidemiologický přístup, který předpokládá pouze stavy S a I. Předpokládá plně homogenní mísení společnosti, neboli každá dvojice jedinců má stejnou šanci se potkat.
Máme populaci velikosti $n$. Nechť $S(t)$ značí počet zranitelných jedinců (susceptible person, SP) a $I(t)$ značí počet nakažených jedinců (infected person, IP) v čase $t$.
Počáteční podmínky:
Co když $I(0) = 1$, jak se bude infekce šířit?
Označíme $\beta$ pravděpodobnost přenosu infekce $\text{IP} \rightarrow \text{SP}$ a $\langle k \rangle$ počet kontaktů typického jedince.
Pozorování:
Zavedeme $$s(t) = \frac{S(t)}{n}$$ a $$i(t) = \frac{I(t)}{n}.$$ Vynecháním časové závislosti získáváme standardní formu SI modelu $$\frac{\textrm{d}i}{\textrm{d}t} = \beta\langle k \rangle si = \beta\langle k \rangle i(1 - i).$$ Jelikož $s + i = 1$, nepotřebujeme rovnici pro $s$.
Úpravami získáváme řešení $$i = \frac{i_0 e^{\beta\langle k \rangle t}}{1 - i_0 + i_0e^{\beta\langle k \rangle t}}.$$
Charakteristický čas je čas kdy počet SP dosáhne $1/e ~ 40\%$ populace. Značíme $\tau = \frac{1}\beta\langle k \rangle$.
Tento model je nerealistický kvůli nezohledňování přírozené imunity získané poražením nemoci.
Přidává stav uzdravený (recovered) (R): $$\text{SP} \rightarrow \text{IP} \rightarrow \text{RP}$$ Dalším novým parametrem je $\gamma$, neboli časový interval $\tau$ po který IP zůstává nakažený. $$\text{P}[\text{uzdravení v časovém intervalu $\delta\tau$}] = \gamma \delta\tau$$ což implikuje $$\text{P}[\text{jedinec není uzdraven po uplynutí $\delta\tau$}] = 1- \gamma \delta\tau.$$ Dále $$\text{P}[\text{IP je stále nakažený po celkovém čase $\tau$}] = \lim_{\delta\tau\rightarrow 0} (1- \gamma \delta\tau)^{\frac{\tau}{\delta\tau}} = e^{-\gamma\tau}.$$
což je nerealistické, protože u nemocí bývá doba potřebná k uzdravení téměř konstantní pouze s několika vybočujícími hodnotami.
SIR model můžeme popsat následující soustavou diferenciálních rovnic: $$\frac{\textrm{d}s}{\textrm{d}t} = -\beta si$$ $$\frac{\textrm{d}i}{\textrm{d}t} = \beta si - \gamma i$$ $$\frac{\textrm{d}r}{\textrm{d}t} = \gamma i$$
Dá se odvodit, že celkový počet nakažených je $$r = 1 - s_0 e^{\beta \frac{r}{\gamma}},$$ kde $s_0$ je počet nakažených na začátku. Pro konstantní počet nakažených a $n$ jdoucí k nekonečnu dostáváme $$r = 1 - e^{\beta \frac{r}{\gamma}}.$$ Zajímavostí je, že to odpovídá velikosti velké komponenty v Erdös-Rényi náhodném grafu s pravděpodobností hrany $\frac{\beta}{\gamma}$. Přechod mezi exponenciálním šířením viru a jeho postupným vymřením je okolo $\beta = \gamma$.
Reprodukční číslo $R_0$ udává, kolik lidí v průměru nakazí jeden nemocný. Za čas $\tau$ jeden nakažený (IP) v průměru potká $\beta \tau$ dalších osob a v modelu předpokládáme, že jsou tyto osoby zranitelné (SP) (nerealistické). $$\text{P}[\text{IP zůstává nakažlivý po čas $\tau$ a uzdraví se v čase $\tau +\mathrm{d}\tau$}] = \gamma e^{-\gamma\tau}\mathrm{d}\tau$$ Průměr přes distribuci všech $\tau$ dává $$R_0 = \beta\gamma \int_0^{\infty} \tau e^{-\gamma\tau}\mathrm{d}\tau.$$
rozšiřuje SI model o možnost reinfekce, tj. možné přechody mezi stavy jsou $\text{SP} \rightarrow \text{IP} \rightarrow \text{SP}$ a přechod $\text{IP} \rightarrow \text{SP}$ reprezentuje uzdravení. Nepředpokládáme získání imunity.
rozšiřuje SIR model o možnost reinfekce po nějaké době, což odpovídá stavu, kdy imunita je pouze omezená či dočasná. Zavádí nový parametr $\delta$ odpovídající průměrné rychlosti ztráty imunity. Přechody mezi stavy jsou $\text{SP} \rightarrow \text{IP} \rightarrow \text{RP} \rightarrow \text{SP}$. SIRS model je určený následujícími rovnicemi $$\frac{\textrm{d}s}{\textrm{d}t} = \delta r - \beta si$$ $$\frac{\textrm{d}i}{\textrm{d}t} = \beta si - \gamma i$$ $$\frac{\textrm{d}r}{\textrm{d}t} = \gamma i - \delta r$$ Poznámka: Není řešitelné analyticky, používají se numerické metody.
modely dosud předpokládaly homogenní šíření, které nezachycuje reálný stav, kdy máme kontakty především s lidmi, které známe. Jelikož síť lidských kontaktů má scale-free vlastnost, není odhad pomocí průměrného počtu známých dostatečně přesný. Vrcholy stejného stupně považujeme za ekvivalentní. Značíme $I_k$ počet infikovaných se stupněm $k$ a $N_k$ počet všech vrcholů stupně $k$. Potom $$ i_k = \frac{I_k}{N_k}.$$ Celkový počet nakažených odpovídá $i = \sum_k p_k i_k$.
Funkce hustoty udává zlomek nakažených mezi sousedy zranitelného vrcholu. Záleží na typu sítě:
Pro $k_{\max}$ vrcholů máme systém rovnic $$\frac{\textrm{d}i_k}{\textrm{d}t} = \beta (1 - i_k) k \Theta_k \quad \forall k \in \{1, \dots, k_{\max}\}.$$ Rovnice jsou podobné jako ve standardním SI modelu, jen $\langle k \rangle$ nahrazujeme za $k$ a místo zlomku nakažených $i$ používáme funkci hustoty $\Theta_k$. Když nepředpokládáme žádnou korelaci mezi hranami a stupni vrcholů, neboli $\text{P}[\text{hrana spojuje vrchol $v$ s vrcholem stupně $k$}]$ je nezávislá na $k$, můžeme odvodit, že $$\Theta(t) = Ce^{t/\tau},$$ kde $$\tau = \frac{\langle k \rangle}{\beta(\langle k^2 \rangle - \langle k \rangle)}.$$ Když uvážíme úvodní podmínku, dostáváme $$\Theta(t) = i_0\frac{\langle k \rangle - 1}{\langle k \rangle} e^{t/\tau}$$ a při substituci do $$\frac{\textrm{d}i_k}{\textrm{d}t} = \beta (1 - i_k) k \Theta_k$$ dostáváme $$\frac{\textrm{d}i_k}{\textrm{d}t} \approx \beta ki_0 \frac{\langle k \rangle - 1}{\langle k \rangle}e^{t/\tau^{\text{SI}}},$$ kde $\tau^{\text{SI}} = \frac{\langle k \rangle}{\beta(\langle k^2 \rangle - \langle k \rangle)}$ je charakteristický čas pro šíření patogenu.
Pro modelování systémů diferenciálních rovnic můžeme použít například knihovnu scipy a její modul integrate.
K numerickému řešení soustav diferenciálních rovnic můžeme konkrétně použít funkci solve_ivp,
které je potřeba předat tři základní parametry:
Ukážeme si použití funkce na příkladu exponenciálního poklesu.
Pro vytvoření časového intervalu s vybraně nahuštěnými mezihodnotami, který se bude hodit pro vykreslení výsledku, využijeme funkci linspace z knihovny numpy:
https://numpy.org/doc/stable/reference/generated/numpy.linspace.html
from scipy.integrate import solve_ivp
import numpy as np
import matplotlib.pyplot as plt
def exponential_decay(t, x):
dxdt = -0.5 * x
return dxdt
sol = solve_ivp(exponential_decay, [0, 100], [1000], dense_output=True)
t = np.linspace(0, 100, 100)
z = sol.sol(t)
plt.plot(t, z.T)
plt.xlabel('t')
plt.legend(['decay'], shadow=True)
plt.show()
Úloha 1: Simulujte situaci, kdy máme populaci velikosti 2 500 000 lidí, na začátku je 100 nakažených, průměrný nakažený má 40 kontaktů denně a nakažlivost nemoci je 1.5%. Doba, po kterou je nakažený člověk nakažlivý trvá 4 dny. Po prodělání nemoci získá osoba imunitu na týden. Vykreslete křivky počtu zranitelných, nakažlivých (a uzdravených) v modelech SI, SIR a SIRS.
Úloha 2: Na chlapecké internátní škole se rozšířila chřipka. Na internátě bydlelo 763 chlapců a v průběhu dvoutýdenní epidemie byly počty nakažených následující:
{3, 7, 25, 72, 222, 282, 256, 233, 189, 123, 70, 25, 11, 4}
Postavte SIR model, který bude co nejpřesněji simulovat průběh této epidemie.
Jaké jsou jeho parametry?
(Na začátku udělejte nějaký předběžný odhad a postupně jej upravujte, abyste se přiblížili k zadaným datům.)