
Défense contre les épidémies dans les réseaux
Defense against epidemics in networks
Beaujean, Paul (2019), Défense contre les épidémies dans les réseaux, doctoral thesis prepared under the supervision of Bazgan, Cristina; Gourdin, Eric, Paris Sciences et Lettres (ComUE)
Under the direction of
Bazgan, Cristina; Gourdin, EricAbstract (FR)
Les 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.Abstract (EN)
The 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.Subjects / Keywords
Optimisation combinatoire; Sécurité des réseaux; Matrices aléatoires; Algorithmes d'approximation; Théorie spectrale des graphes; Combinatorial Optimization; Network Security; Random Matrices; Approximation Algorithms; Spectral Graph TheoryRelated items
Showing items related by title and author.
-
Hérault, Paul (2018-02-13) Thèse
-
Détection de communautés dans les grands réseaux : Application aux réseaux d'interactions de gènes Ben M'Barek, Marwa (2022-10-14) Thèse
-
Bazgan, Cristina; Beaujean, Paul; Gourdin, Eric (2018) Communication / Conférence
-
Bazgan, Cristina; Beaujean, Paul; Gourdin, Eric (2022) Article accepté pour publication ou publié
-
BEAUJEAN, PAUL; Sikora, Florian; Yger, Florian (2022) Communication / Conférence