• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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)

View/Open
2019PSLED063.pdf (2.615Mb)
Type
Thèse
Date
2019-12-16
Metadata
Show full item record
Author(s)
Beaujean, Paul
Under the direction of
Bazgan, Cristina; Gourdin, Eric
Abstract (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 Theory

Related items

Showing items related by title and author.

  • Thumbnail
    L'internationalisation des chaînes de valeur dans l'industrie de défense : le cas du naval 
    Hérault, Paul (2018-02-13) Thèse
  • Thumbnail
    Des rencontres dans la mondialisation : réseaux et apprentissages dans un salon de distribution de programmes de télévision en Afrique sub-saharienne 
    Favre, Guillaume (2014-12) Thèse
  • Thumbnail
    Des réseaux, des relations, de l'aide : la création et la maintien de l'engagement dans l'équipe virtuelle mondiale 
    Santistevan, Diana (2015-08) Thèse
  • Thumbnail
    Le Rôle des Réseaux de Production dans la Propagation Domestique et Internationale des Chocs Sectoriels 
    Martinez Garibay, Homero Alberto (2018-11-30) Thèse
  • Thumbnail
    Ethnic gap, household businesses and social networks in Vietnam 
    Nguyen, Phuong (2018-11-29) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo