Show simple item record

Defense against epidemics in networks

dc.contributor.advisorBazgan, Cristina
dc.contributor.advisorGourdin, Eric
hal.structure.identifier
dc.contributor.authorBeaujean, Paul*
dc.date.accessioned2020-10-27T12:59:43Z
dc.date.available2020-10-27T12:59:43Z
dc.date.issued2019-12-16
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21170
dc.description.abstractfrLes théories mathématiques en épidémiologie ont adopté l'usage de réseaux d'interactions pour modéliser la propagation d'une épidémie au sein d'une population de nœuds qui sont en contact s'ils sont reliés par une arête. Bien que des avancées majeures aient été réalisées pour concevoir des contre-mesures efficaces qui agissent directement sur les maladies, peu d'études en comparaison ont été effectuées pour tenter de modifier le réseau d'interaction lui-même. Cette thèse étudie la possibilité de trouver une modification optimale d'un réseau de manière à stopper une épidémie qui s'y propagerait. Ce problème d'optimisation étant difficile du point de vue la théorie de la complexité, nous proposons un algorithme probabiliste d'approximation qui est garanti de produire une modification stoppant l'épidémie en un temps limité. De plus, nous montrons que l'analyse du ratio d'approximation de cet algorithme est la meilleure possible pour un large ensemble d'instances. Pour mesurer l'utilité pratique d'un tel algorithme, nous procédons à une analyse critique des méthodologies actuelles en évaluation expérimentale des algorithmes. En réponse, nous proposons une nouvelle méthodologie pour étudier des implantations d'algorithmes produisant des solutions potentiellement inexactes, sous-optimales et dont le comportement dépend de paramètres.frr
dc.language.isoen
dc.subjectOptimisation combinatoirefr
dc.subjectSécurité des réseauxfr
dc.subjectMatrices aléatoiresfr
dc.subjectAlgorithmes d'approximationfr
dc.subjectThéorie spectrale des graphesfr
dc.subjectCombinatorial Optimizationen
dc.subjectNetwork Securityen
dc.subjectRandom Matricesen
dc.subjectApproximation Algorithmsen
dc.subjectSpectral Graph Theoryen
dc.subject.ddc005.8
dc.titleDéfense contre les épidémies dans les réseauxfr
dc.titleDefense against epidemics in networksen
dc.typeThèse
dc.contributor.editoruniversityParis Sciences et Lettres (ComUE)
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenThe modern mathematical study of epidemics has adopted the concept of contact networks to model a disease spreading among nodes who may interact with each other along edges. While much progress has been made in designing effective countermeasures against epidemics by acting upon the disease, fewer studies have explored the use of modifying the contact network itself. This thesis explores the possibility of finding an optimal modification of a network to stop an epidemic spreading over it. Because this optimization problem is computationally hard to solve, we design a randomized approximation algorithm by combining semidefinite programming together with matrix concentration inequalities which is guaranteed to return a network modification that stops the epidemic in a short amount of time. Furthermore, we give evidence that the analysis of this algorithm is tight in a large regime.To understand the practical applicability of this algorithm, we analyze current practices in the experimental evaluation of algorithms and propose a new methodology to assess algorithms that may fail, may return approximate solutions, and may change behavior based on hyperparameters.en
dc.identifier.theseid2019PSLED063
dc.subject.ddclabelOrganisation des données
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record