Teorie epidemií Modelování a teorie sítí Petr Liška http://networksciencebook.com/ 26.04.2022 Petr Liška Teorie epidemií 26.04.2022 Petr Liška Teorie epidemií 26.04.2022 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í 26.04.2022 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í 26.04.2022 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 (ň = = Ett = 5>- k=0 k=0 Petr Liška Teorie epidemií 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í 26.04.2022 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í 26.04.2022 9/21 Očekávaný počet hran N(N-l) N(N-l) lpl = p l=0 L)= ]t LpL = p 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í 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 = [ , p"(i-P) k\ Petr Liška Teorie epidemií 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í 13/21 Kde je problém? Petr Liška Teorie epidemií 26.04.2022 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. kITI3X - km in l\l ^ ^ mm Petr Liška Teorie epidemií 26.04.2022 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í 26.04.2022 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í 26.04.2022 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í Jaký je stupeň uzlu? Jaká je distribuce stupňů uzlů? Kolik uzlů má stupeň menší než kl m[i,y