Teorie epidemií
Modelování a teorie sítí
Petr Liška
http://networksciencebook.com/
17.04.2023
Petr Liška		Teorie epidemií	17.04.2023 3/21
Co je to sít?
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 C {[x, y] I x,y G V,x^y}.
Petr Liška		Teorie epidemií	17.04.2023 4/21
Reálné sítě
Síť	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í	17.04.2023 5/21
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í ka výstupní stupeň kfut.
celkový počet vazeb
1 N
N N
1 = E kl" = E k°ut
i=i i=i
průměrný stupeň
2L
;=1
N » N
(ň = <o = l E kin = l E kr* =
i=l i=l
Petr Liška		Teorie epidemií	17.04.2023 6/21
Základní charakteristiky
rozložení stupňů pk - označuje pravděpodobnost, že náhodně vybraný uzel v síti má stupeň k, tedy platí
oo
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 (k)
oo   , oo
k=0
k=0
Petr Liška
Teorie epidemií
17.04.2023
Náhodná síť
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í	17.04.2023 8/21
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 /V^~1^ — L 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ů
PL=i      l      \PL{1-P) 2
Petr Liška
Teorie epidemií
Očekávaný/Průměrný počet hran
N(N-l)
L=0
je tedy součin pravděpodobnosti p (vyjadřující, že dva uzly jsou spojeny) a Lmax — N(N~ľ^ (vyjadřující počet párů, které chceme spojit).
Odsud průměrný stupeň uzlu je
2(L)
Petr Liška
Teorie epidemií
17.04.2023
10/21
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~k1 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
Pk =
TV - 1 k
p*(l_p)"-i-*«e-<*>^
K!
Petr Liška		Teorie epidemií	17.04.2023 11/21
Svět je malý
(k\d+1
N(d)^l + {k) + {k)2 + --- + {k)d =K i
(k)-l
N{dmax) « N « (k)
In N
d
'max
'max
(d)
ln(/c) In N
In N _ ln(8 • 109) _ (d) ~ K/č) "    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
Petr Liška		Teorie epidemií	17.04.2023 13/21
Kde je problém?
Petr Liška		Teorie epidemií	17.04.2023 14/21
Bezškálová síť
Definice
Bezškálová sít je taková síť, jejíž rozložení stupňů se řídí mocninným zákonem, tj.
p{k) = (7-Cr
kITI3X - km in l\l ^ ^
mm
Petr Liška
Teorie epidemií
17.04.2023
15/21
Momenty
kn) =
00 roo
J2knPk~ / knp(k)dk
L   . J kmjn
^min
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.
• n = 3: Třetí moment, (k3), určuje šikmost rozložení a říká nám, jak symetrické je     kolem průměru (k).
Petr Liška
Teorie epidemií
17.04.2023
16/
Význam bezškálovosti
kn) = c
m/r?
r? - 7 + 1
Pro /cmax —>> oc dostaneme
Pokud n — 7 + 1 < 0, potom s rostoucím kmax jde člen k
n—7+1
do
nuly. Proto jsou všechny momenty, které splňují n < 7 — 1, konečné.
Pokud n — 7 + 1 > 0, potom s kmax oc jde i (kn) do nekonečna Proto všechny momenty větší než 7 — 1 divergují.
Petr Liška
Teorie epidemií
17.04.2023
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
IK*')
J
Petr Liška
Teorie epidemií
17.04.2023
18/
Jaký je stupeň uzlu?
Jaká je distribuce stupňů uzlů?
Kolik uzlů má stupeň menší než kl
m —
t ti
1
2 , im < k =4> ti < t
1
2
Dohromady máme N = niQ + t & t uzlů. Pravděpodobnost, že vybereme uzel stupně menšího než k
Distribuce pak je
Pk =
dP(k) 2m-
dk
k3
Petr Liška		Teorie epidemií	17.04.2023 20/21
Friendship paradox
k2
kn(ki) = '
(k)
Pro náhodné sítě platí Pro bezškálovou síť platí
7c2} —>> oo   pro   N —> oo
Síť	N	L	(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