Statistical inference algorithms for epidemic processes on complex networks

doctoral thesis

• Title (croatian): Algoritmi za statističko zaključivanje o epidemijskim procesima na kompleksnim mrežama
• Author: Nino Antulov-Fantulin; MBZ: 330710
• Mentor: Mile Šikić (mentor)
• Mentor: Tomislav Šmuc (komentor)
• Committee member: Mile Šikić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronic Systems and Information Processing); Zagreb
• Defense date and country: 2015, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing; Data Processing
• Universal decimal classification (UDC): 621.3 - Electrical engineering

Abstract

The main topics of this dissertation are novel methods and algorithms for the modelling and the statistical inference about epidemic processes based on the Susceptible-Infected-Recovered (SIR) model on arbitrary network structures. Two types of problems are solved: (i) estimation of the final epidemic outcome ("forward in time" statistical estimate) and (ii) estimation of epidemic initial conditions from a single epidemic realization ("backward in time" statistical inference). In order to estimate the final epidemic outcome on arbitrary networks without following the temporal dynamics, a novel FastSIR algorithm is constructed. The FastSIR algorithm is using a probability distribution of the number of infected nodes in a first neighbourhood in a limit of time to speed up the simulation. In the backward statistical inference, we solve two problems: (a) the detection of a single epidemic source from a realization and (b) the recognition that a realization has multiple initial sources. A number of different statistical estimators are presented for determining the likelihood for potential source producing the observed epidemic realization. The estimates are based on the Monte Carlo simulations of an epidemic spreading process on a network from a set of potential source candidates, which were infected in the observed realization. This statistical inference framework is applicable to arbitrary networks and different dynamical spreading processes. The problem of multiple-source epidemic recognition from a single realization is solved by constructing a statistical outlier detection algorithm, which is based on the Kolmogorov-Smirnov statistics over realization similarity distributions.

Abstract (croatian)

Glavna tema ove disertacije su nove metode i algoritmi za modeliranje i statističku procjenu epidemijskih procesa bazirani na stohastičkom modelu Podložan-Zaražen-Oporavljen (engl. Susceptible-Infected-Recovered - SIR), na proizvoljnim mrežnim strukturama. Algoritmi i metode posvećeni su rješavanju dva tipa problema: (i) procjena ishoda epidemije ("unaprijed u vremenu") te (ii) procjena početnih uvjeta epidemije iz jedne realizacije epidemijskog procesa ("unatrag u vremenu"). Podložan-Zaražen-Oporavljen (SIR) model parametriziran je s dva osnovna parametra: parametar p - vjerojatnost da zaraženi čvor prenese zarazu na podložnog susjednog čvora u mreži u diskretnoj jedinici vremena i parametar q - vjerojatnost da zaraženi čvor se oporavi u diskretnoj jedinici vremena. Za procjenu ishoda epidemije na mrežnoj strukturi konstruiran je osnovni Naive SIR algoritam. Naive SIR algoritam slijedi vremensku dinamiku stohastičkog procesa na mreži koristeći Monte-Carlo simulaciju. Isti algoritam koristi sljedeće strukture podataka: lista susjedstva - za konstantni pristup susjedima u mreži, struktura red - za pohranu zaraženih čvorova te indikatorsku strukturu polja za provjeru podložnosti i oporavljenosti čvora. Vremenska složenost Naive SIR algoritma proporcionalna je umnošku prosječnog broja zaraženih čvorova, prosječnom stupnju čvora te prosječnom vremenu oporavka. Na regularnim m-arnim stablima moguće je dobiti analitičku gornju granicu za prosječno vremensku složenost. Radi ubrzanja vremenske složenosti Naive SIR algoritma konstruiran je FastSIR algoritam koji ne slijedi vremensku dinamiku epidemije. FastSIR algoritam koristi distribuciju vjerojatnosti broja zaraženih u prvom susjedstvu u limesu vremena kako bi ubrzao simulaciju. Vremenska složenost FastSIR algoritma proporcionalna je umnošku prosječnog broja zaraženih čvorova i prosječnom stupnju čvora. Rekurzivna definicija za računanje distribucije vjerojatnosti broja zaraženih u prvom susjedstvu u limesu vremena je dana u disertaciji. Eksperimenti na realnim i sintetskim mrežama pokazuju ubrzanje (proporcionalno prosječnom vremenu oporavka) FastSIR algoritma u odnosu na Naive SIR algoritam. Predložena je inačica FastSIR algoritma za neprekinuto vrijeme koristeći analitički izvod za distribuciju vjerojatnosti broja zaraženih u prvom susjedstvu u limesu vremena za SIR model u neprekinutom vremenu. Procjenom unazad u vremenu rješavamo dva problema: (a) detekcija izvora zaraze i (b) prepoznavanje realizacija koje dolaze iz više izvora. U tezi je predstavljeno više različitih procjenitelja izglednosti da zaraza iz određenog izvora reproducira promatranu realizaciju. Estimatori se temelje na Monte Carlo simulacijama zaraze iz skupa potencijalnih izvora, koji su bili zaraženi u promatranoj realizaciji i mogu se podijeliti na dvije kategorije: heuristički (Naive Bayes, AvgTopK, AUCDF) i aproksimacijski (Direct Monte-Carlo, Soft Margin) estimatori. Naive Bayes estimator pretpostavlja nezavisnost između čvorova što omogućuje faktorizaciju združene vjerojatnosti realizacije na umnožak vjerojatnosti stanja čvorova u promatranoj realizaciji. Algoritmi AUCDF i AvgTopK estimiraju izglednost izvora na temelju empirijske kumulativne distribucije sličnosti između promatrane realizacije i realizacija generiranih iz potencijalnih izvora. Direct Monte-Carlo algoritam estimira izglednost izvora na temelju frekvencije generiranja promatrane realizacije iz određenog izvora koristeći tehniku podrezivanja krivo generiranih realizacija pomoću Monte-Carlo metode. Važno je napomenuti da tehnika podrezivanja ne unosi grešku u estimaciju izglednosti izvora. Soft Margin estimator relaksira kriterij prihvaćanja realizacija koristeći težinsku funkciju nad sličnostima generiranih realizacija. Soft Margin estimator prelazi u Direct Monte-Carlo estimator kada širina težinske funkcije teži u nulu. Testiranje na sintetskim mrežama pokazuje da Soft Margin estimator ima najbolje karakteristike (točnost rangiranja izvora i procjena izglednosti izvora) u odnosu na druge konkurentske estimatore iz literature. Također je pokazana primjenjivost Soft Margin estimatora u određivanju izvora zaraze na simuliranim epidemijama na realnim mrežama: temporalna mreža seksualnih kontakata i težinska mreža avionskih letova. Soft Margin estimator također omogućuje relaksaciju poznavanja parametara epidemije, strukture mreže ili stanja svih čvorova. Sustavno prepoznavanje realizacija iz više mogućih izvora dovodi do eksponencijalnog porasta broja članova za analizu. Stoga se problem prepoznavanja realizacija koje dolaze iz više izvora prebacio na problem detekcije statističkih iznimki. Realizacije koje dolaze iz više izvora smatraju se iznimkama s obzirom na skup realizacija koje dolaze iz jednog izvora. Konstruiran je algoritam koji koristi Kolmogorov-Smirnov statistiku nad distribucijama sličnosti realizacija jednog prema jednom izvoru te sličnosti između promatrane realizacije prema realizacijama iz jednog izvora. Radi smanjenja vremenske složenosti implementirane su sljedeće optimizacijske tehnike: paralelizacija algoritma, poduzorkovanje potencijalnih izvora, kompresija realizacija u skup cjelobrojnih vrijednosti te brzo binarno računanje sličnosti. Metoda prepoznavanja realizacija iz više izvora testirana je na simuliranim zarazama na mrežama.

• Keywords: complex networks; epidemic spreading algorithms; statistical inference
• Keywords (croatian): kompleksne mreže; algoritmi za širenje epidemija; statistička procjena
• Language: english
• URN:NBN: urn:nbn:hr:168:713850
• Study programme: Title: Electrical Engineering and Computing; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti elektrotehnike i računarstva (Doktor znanosti elektrotehnike i računarstva)
• Type of resource: Text
• Extent: 107 str. ; 30 cm.
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-04-15 16:27:35