Teorie epidemií
Modelování a teorie sítí
Petr Liška
http://networksciencebook.com/
22.04.2024
Petr Liška
Teorie epidemií
Petr Liška
Teorie epidemií
Co je to síť?
Síť má dva základní parametry:
Počet uzlů, nebo-li N, reprezentující počet bodů v systému.
K rozeznání jednotlivých uzlů si je značíme pomocí / = 1, 2,N.
Tento parametr často nazýváme velikost sítě.
Počet vazeb, nebo-li L, reprezentující celkový počet interakcí mezi uzly. Vazby zpravidla nebývají označené.
Síť se nazývá orientovaná, jestliže všechny její vazby jsou orientované, tzn. že mají mezi uzly pevně daný směr. V opačném případě mluvíme o síti neorientované, čili nerozlišujeme směr jejích vazeb.
Graf je uspořádána dvojice G = (V, E), kde V je množina vrcholů,
E Q {[*>y] I x,y £ v^x + y}-
Petr Liška		Teorie epidemií	22.04.2024       4 / 25
Reálné sítě
Síi	Uzly	Vazby	Ori	N	L
Herecká	herci	společný film	N	702 388	29 397 908
Vědecká	vědci	společný článek	N	23 133	93 437
WWW (část)	stránky	URL adresy	A	325 729	1 497 134
Citační	články	citace	A	449 673	4 689 479
Petr Liška		Teorie epidemií	22.04.2024       5 / 25
Základní charakteristiky
• stupeň kj - vyjadřuje počet vazeb, které daný uzel / má k ostatním uzlům; v případě orientované sítě rozlišujeme vstupní'k'" a výstupní stupeň kfut.
celkový počet vazeb
průměrný stupeň
1 N
i=l
N N
i=l i=l
N 2L
N ^ ' N
i=i
N . N
i=i i=i
Petr Liška		Teorie epidemií	22.04.2024       6 / 25
Základní charakteristiky
rozložení stupňů p^ - označuje pravděpodobnost, že náhodně vybraný uzel v síti má stupeň k, tedy platí
oo
5>/c = i.
k=0
Označíme-li počet uzlů mající stupeň k v sítí o N uzlech, obdržíme:
Nk
Pk =
N
Potom máme jiný vztah pro pk
co
k=0
kNk N
OO
k=0
Petr Liška	Teorie epidemií		22.04.2024       7 / 25
Náhodná sít
Náhodná síť - definice podle Gilberta
Každý pár z N uzlů je spojen s pravděpodobností p
Náhodnou síť sestrojíme pomocí následujících kroků:
• začneme s N izolovanými uzly
• vybereme náhodnou dvojici uzlů a vygenerujeme náhodné číslo mezi 0 a 1, pak v případě, že toto číslo překročí hodnotu p, spojíme dané uzly vazbou, v opačném případě je necháme nespojené
• předchozí krok opakujeme pro každou z N(N~^ dvojic uzlů
Petr Liška		Teorie epidemií	22.04.2024       8 / 25
Pravděpodobnost, že má náhodná síť přesně L vazeb, je součinem tří výrazů:
• pL, což vyjadřuje pravděpodobnost, že L pokusů o připojení N (A/ — l)/2 dvojic uzlů skončí úspěšným připojením
• (1 — p)~^2 ~~L1 což je pravděpodobnost, že zbývajících A/^~1^
I O I v/    / w      / v ■ /
pokusu neskonči úspešným pripojením
A/(A/-1)\
^    j, což je kombinační číslo, které nám vyjadřuje, kolika způsoby můžeme L vazeb rozmístit mezi N (A/ — l)/2 dvojic uzlů
pí. =
Petr Liška
Teorie epidemií
22.04.2024
Očekávaný počet hran
N(N-l)
L)= £ LpL = p
L=0
N(N-l)
je tedy součin pravděpodobnosti p (vyjadřující, že dva uzly jsou spojeny Lmax =     2     (vyjadřující počet párů, které chceme spojit).
Odsud průměrný stupeň uzlu je
2(0
(k) =-y-= p(N - 1)
22.04.2024
Distribuce uzlů
Pravděpodobnost, že uzel / v náhodné síti má přesně k vazeb je součinem tří výrazů:
pk, což je pravděpodobnost, že k vazeb daného uzlu existuje
(1 — p)N~1~k, což je pravděpodobnost, že (A/ — 1 — k) zbývajících vazeb chybí
nám říká, kolika způsoby můžeme z potenciálních N — 1
TV - 1 k
vazeb (které uzel může mít) vybrat k z nich
Distribuce uzlů tedy je
TV - 1
Pk =
P*(l " P)
N-l-k
(k)
(kŕ k\
Petr Liška		Teorie epidemií	22.04.2024        11 / 25
Svět je malý
N{d)^l + {k) + {k)2 + --- + {k)d ={ '
(k)-l
N{dmax) ^N^{k)
In N
a
'max
'max
(d)
ln(/c) In N
In/V _ ln(8 • 109) _
{d} ~ 1^) "    In 103    " 3'3
Reálna data
Sít	(k)	(d)	dmax	In N/ In (k)
Herecká	83,71	3,91	14	3,04
Vědecká	8,08	5,35	15	4,81
WWW (cast)	4,60	11,27	93	8,31
Citační	10,43	11,21	42	5,55
Kde je problém?
Petr Liška		Teorie epidemií	22.04.2024        14 / 25
Bezškálová síť
Definice
Bezškálová sít je taková síť, jejíž rozložení stupňů se řídí mocninným zákonem, tj.
Pk ~ k~7 •
p(/r) = (7-l)^"7
U      — U ■ A/7-1
min
Petr Liška		Teorie epidemií	22.04.2024        15 / 25
Momenty
kn) =
00 POO
J2knPk~ / knP{k)ák
Nižší momenty mají důležitou interpretaci:
• n = 1: První moment odpovídá průměrnému stupni, čili (k).
• n = 2: Druhý moment , (k2), je důležitý při výpočtu rozptylu
a2 = (k2) — (k)2. Jeho druhá odmocnina, a, se nazývá směrodatná odchylka.
• /7 = 3: Třetí moment, (/c3), určuje šikmost rozložení a říká nám, jak symetrické je     kolem průměru (/c).
Petr Liška
Teorie epidemií
22.04.2024       16 /
Význam bezškálovosti
kn) = c
, A7-7+1 _   , A7-7+1
* max A__:.
A77/A7
r? — 7 + 1
Pro kmax —>> oo dostaneme
Pokud n — 7 + 1 < 0, potom s rostoucím kmax jde člen /c
A7-7+1
max
do
nuly. Proto jsou všechny momenty, které splňují n < 7 — 1, konečné.
Pokud n — 7 + 1 > 0, potom s kmax —> 00 jde i (kn) do nekonečna Proto všechny momenty větší než 7 — 1 divergují.
Petr Liška
Teorie epidemií
22.04.2024
17 /
Bezškálová síť, Barabási-Albert model Růst - v každém kroku přidáme uzel s m novými spojeními Preferential attachment - pravděpodobnost n(^)' ^e spojení nového uzlu bude navázáno na starý uzel / je dána
ki
j
Petr Liška		Teorie epidemií	22.04.2024       18 / 25
Jaký je stupeň uzlu?
Jaká je distribuce stupňů uzlů?
Kolik uzlů má stupeň menší než kl
Dohromady máme N — itiq + t « t uzlů. Pravděpodobnost, že vybereme uzel stupně menšího než k
Distribuce pak je
_ dP(k) _ 2m2 Pk ~ ~dk~ ~ ~W
Petr Liška		Teorie epidemií	22.04.2024       20 / 25
Friendship paradox
kn(ki) = {k2
(k)
Pro náhodné site platí
M,> = |> = WÍ1±M = 1 + {k}
Pro bezškálovou sít platí
<-\
(k } —>> oo   pro   N —> oo
Síť	N	Z.	(k)	(k2)
Internet	192 244	609 066	6,34	240,1
Vědci	23 133	93439	8,08	178,2
Herci	702 388	29 397 908	83,71	47 353
Jednoduchý SIS model
^ = P(k)S{t)l(t) - fil(t) = P(k)l(t)(i - l(t)) - M/(ŕ),     '(O) = h
/     jí_\    CeVW-rt i0
M) ť 1 - /n__ÍL.
; 1     '° /3(k)
Dvě možnosti: • Endemický stav (/j, < /3(/c))
/(oo) = 1 -
Nemoc je vyhlazena (/j, > /3{k))
/(oo) = 0
Petr Liška		Teorie epidemií	22.04.2024       22 / 25
SUSCEPTIBLE (HEALTHY)
RECOVERY <-
Q LU I— O LU Ll_
- 0.5
o
i— o <
0
~i-1-1-1-1-1-1-1-1-1-i-i-1-i-i-1-1 i
0
Í
4 t
exponential outbreak
If i is small,
8
endemic state
10
/(<»)= 1 -
Petr Liška		Teorie epidemií	22.04.2024       23 / 25
Charakteristický čas a reprodukční číslo
Charakteristický čas /(r) = ^
1 1
Nemoc	Ro	
spalničky	12-	-18
černý kašel	12-	-17
záškrt	6-	-7
neštovice	5-	-7
dětská obrna	5-	-7
zarděnky	5-	-7
příušnice	4-	-7
HIV/AIDS	2-	-5
SARS	2-	-5
chřipka	2-	-3
Petr Liška		Teorie epidemií	22.04.2024        24 / 25
Model epidemie na síti
_ _ w__
E kPk   ~ (k)
	k	
	r= W D(k2) - u,(k)	
Petr Liška	Teorie epidemií	22.04.2024        25 / 25