IV124 Komplexní sítě Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 17. května 2018 Modely nákazy: epidemie Minule: komplexní šírení • rozšírení „přehlasováním" • sociologické aplikace Dnes: jednoduché šírení • stochastický model • aplikace v biologických a technických sítích 2 of 18 Poznámka ke stochastickým modelům Jednoduché deterministické modely lze komplikovat (přidávat pravidla) • rozšiřuje se repertoár možných chování • stále náročnější analýza • v jistý moment je jednodušší velké množství reálných dějů shrnout do jedné náhodné veličiny 3 of 18 Větvící se procesy Nej prostší model: • do populace p přichází pacient 0 a potká k osob • pravděpodobnost přenosu při setkání je p • v každé další vlně zůstává k i p stejné • výsledkem je strom kontaktů mezi potenciálně nakaženými a podstrom skutečné nákazy 4 of 18 (a) The contact network for a branching process O" a a a Q, Q 0 ÖOOÖOOOOOOOO (b) With high contagion probability, the infection spreads widely Ö Ö OÖOtiOOOOÖOOÖOaOQOOÖOÖOOÖOÜO (c) With low contagion probability, the infection is likely to die out quickly ^Easley and Kleinberg 2010 5 of Větvící se procesy Možné výsledky: • nákaza se po chvíli zastaví (zanikne) • rozsáhlá epidemie Reprodukční číslo /?o: • očekávaný počet nově nakažených jedním jedincem • popisuje životaschopnost a agresivitu nákazy • zde Rq = pk 6 of 18 Větvící se procesy Vývoj v závislosti na Rq: • /?o 1: agresivní epidemie • /?o ~ 1: rozsah nákazy se může výrazně lišit mezi běhy; i malé změny v mechanismu šíření rozhodují o vypuknutí epidemie Doposud jsme ignorovali: • konečnost populace • topologii kontaktní sítě 7 of 18 SIR model Tři sousledné stavy uzlu: 1. Susceptible: náchylný k nákaze od sousedů 2. Infectious: nemocný uzel šířící nákazu po t\ kroků 3. Removed: imunní/mrtvý uzel V každém kroku uzly ve stavu / rozšíří nemoc do všech svých sousedů s pravěpodobností p. 8 of 18 Klasické epidemiologické modely Předpokládají možnost kontaktu s libovolným členem populace, formulovány pomocí diferenciálních rovnic: SIR vs. sítě proportion infectious, / (%) o 5 £ £ § g S f proportion infectious, / (%) I-1-1-1- proportion infectious, / (%) ^ K) W A LA ft -J (B proportion infectious, / (%) _l_I_I_I_I_I_I_I_L_ proportion infectious, / (%) — — — — —1 r. c4- _l_I_I_I_I_I_I_I_L_ SIR model: rozšírení Dynamika je jednoduchá (větvící se proces na síti) Možná rozšírení: • ohodnocený graf - nehomogenní pravděpodobnost rozšírení p • nehomogenní lt • rozdělení / na více podrobných - infekční inkubace, méně infekční období se symptomy, ... 12 of 18 SIS model Umožníme opětovnou nákazu 1. Susceptible: náchylný k nákaze od sousedů 2. Infectious: nemocný uzel šířící nákazu po t\ kroků 3. Susceptible Narozdíl od SIR modelu umožňuje velmi dlouhé běhy na konečné síti. 13 of 18 SIRS model Ve výskytu reálných chorob pozorujeme výrazné oscilace, ty ani v SIS nedostaneme. Přidáme časově omezenou imunitu 1. Susceptible: náchylný k nákaze od sousedů 2. Infectious: nemocný uzel šířící nákazu po t\ kroků 3. Recovery: uzdravený a uzel imunní po ír kroků 4. Susceptible 14 of 18 Globální vs. lokální oscilace SIRS vykazuje na obecné síti oscilace na lokální úrovni. Oscilace na globální úrovni • vyžadují homofilní (lokální) vazby a daleko dosahující zkratky • odpovídá charakteristice malých světů • konkrétní dynamika je úzce svázaná s topologií sítě 15 of 18 SIRS a malé světy Model sítě Watts-Strogatz (připomenutí): • kruh s lokálními vazbami; s pravděpodobností c přepojeny hrany do náhodného cíle SIRS dynamika • globální oscilace (synchronizace) závisí na počtu „zkratek" - slabých vazeb • malé c - lokální infekce, velké c - globální oscilace 16 of 18 SIRS a malé světy ^iperman et al. 2001 Dema 18 of 18