Description
Date depot: 1 janvier 1900
Titre: Analyse stochastique des graphes aléatoires
Directeur de thèse:
Laurent DECREUSEFOND (LTCI (EDMH))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
{{Contexte}}
La théorie des graphes est bien établie de façon rigoureuse et ancienne. Elle s’applique à de très nombreux problèmes dans toutes sortes de domaines. Les applications à l’épidémiologie, aux réseaux de télécommunications, à l’informatique, à la physique statistique invitent à envisager une extension de cet apparatus au cas aléatoire.
Prenons d’abord l’exemple de l’épidémiologie, c’est-à-dire l’étude de la diffusion de maladies chez les humains, les animaux ou celle des virus informatiques. Des modèles déterministes de diffusion d’épidémie existent depuis longtemps. Ils sont basés notamment sur « la loi d’action de masse » qui stipule que tous les individus susceptibles sont indifférentiables : non seulement leur propension intrinsèque à être infecté est identique mais leurs liens avec les infectés sont statistiquement égaux. Les équations de diffusion d’épidémie ainsi obtenues sont parfaitement étudiables mais les résultats obtenus ne correspondent pas toujours aux observations. Cela révèle qu’à trop homogénéiser les interfaces entre individus, l’on aboutit à des contradictions. En effet, un virus ne peut se propager que par des contacts que l’on ne saurait donc résumer à une loi universelle et uniforme. Un serveur informatique contaminé a plus de chances de favoriser la dissémination d’un virus qu’un ordinateur personnel. Un virus apparaissant en Asie concernera d’abord ce continent puis ultérieurement les autres de par la mondialisation des échanges. Les mathématiques et notamment les structures de graphes semblent l’outil idéal pour représenter les interactions entre agents susceptibles et agents pathogènes mais la méconnaissance que nous avons de ces échanges rendent nécessaires une modélisation aléatoire. Les questions qui se posent sont alors de savoir ce que sera l’évolution de la maladie, restera-t-elle au stade d’endémie ou diffusera-t-elle jusqu’à créer une épidémie ? Le cas échéant, quelle sera sa vitesse de diffusion ? Comment diffuser les médicaments de façon à limiter la diffusion de la maladie le plus efficacement possible ?
Dans les réseaux de télécommunications sans fil, tels que les réseaux ad-hoc, les réseaux Wifi, les réseaux cellulaires, les principaux problèmes sont ceux de la gestion des interférences et de la couverture. Plus les terminaux sont proches, plus leurs émissions-réceptions respectives se brouillent mutuellement. Mais si les mobiles sont trop distants, notamment dans un réseau ad-hoc, ils ne peuvent communiquer et les messages ne peuvent être échangés correctement entre tous les terminaux. Comme les positions des mobiles tout comme les conditions radio sont éminemment aléatoires, les graphes représentant les interférences ne peuvent être que des graphes pondérés aléatoires. Il s’agit maintenant de calculer les chances de pouvoir établir un chemin entre deux points donnés ou de calculer les valeurs possibles d’une fonction qui implique tous les sommets du graphe. En informatique, on peut mentionner l’utilisation des graphes pour les réseaux pairs à pairs : les données sont réparties sur plusieurs clients, le comportement de ces clients étant lui-même hautement incertain (défaillances du réseau support, déconnexion, etc.); les graphes à considérer sont éminemment aléatoires.
Le réseau Internet, les réseaux sociaux ont été l’objet de multiples investigations pour déterminer la nature du graphe des connexions entre serveurs ou entre individus (voir [2,12] et leurs références). Il a été montré qu’existaient des noeuds en nombre restreint dont la bonne marche conditionnait la bonne marche du réseau dans le cas d’Internet ou la bonne diffusion de l’information dans le cas des réseaux sociaux. L’étude du nombre, de la robustesse des noeuds est particulièrement importante tant pour parer à une cyber-attaque que pour optimiser l’effet des publicités virales [9].
{{Etat de l’art}}
La littérature sur les graphes aléatoires est riche notamment du côté de la physique car ces outils sont depuis longtemps utilisés en physique statistique. Le modèle le plus simple est le graphe d’Erdös Renyi, construit par effacement aléatoire des arêtes d’un graphe complet. Cette construction simple et d’une structure parmi les plus simples à analyser, ne peut malheureusement pas être utilisée pour représenter des graphes « réels » tels que les réseaux sociaux, Internet, etc. Pour pallier cet inconvénient majeur, de nombreuses autres constructions ont été proposées. De cette zoologie, ressortent principalement les graphes à attachement préférentiel et les graphes dits de configuration. Dans le premier cas, les nœuds sont ajoutés les uns après les autres à un graphe existant et chaque nouveau sommet s’attache à un autre sommet avec une probabilité proportionnelle au degré d’icelui. Ce phénomène connu sous le nom de « les riches deviennent plus riches » semble refléter un grand nombre de situations pratiques notamment celles citées ci-dessus (voir [10]). L’autre al
Doctorant.e: Ferraz Eduardo