Habilitation à diriger des recherches

Soutenue le 6 juillet 2010, à l'université Pierre et Marie Curie

Mémoire

Transparents

Jury :
  • Eric D. Kolaczyk, Rapporteur.
    Professeur, Boston University, Dpt of Mathematics and Statistics.
  • Guy Melançon, Rapporteur
    Professeur, Université Bordeaux I, LABRI.
  • Jean-Jacques Pansiot, Rapporteur.
    Professeur, Université de Strasbourg, LSIIT.
  • Patrice Abry, Examinateur.
    DR, CNRS, laboratoire de physique de l'ENS Lyon.
  • Vania Conan, Examinateur.
    Chercheur, Thales communications.
  • Eric Fleury, Examinateur.
    Professeur, ENS Lyon, LIP.
  • Pierre Fraigniaud, Examinateur.
    DR, CNRS, LIAFA.
  • Franck Petit, Examinateur.
    Professeur, UPMC, LIP6.

Résumé

On appelle graphes de terrain les graphes issus d'observations d'objets concrets, tels que la topologie de l'internet (routeurs reliés par des câbles), des réseaux sociaux (réseaux d'amitiés ou de collaborations), des réseaux biologiques (interactions entre protéines), etc. La plupart de ces graphes évoluent au fil du temps, par l'apparition et la disparition de noeuds et de liens. L'étude de cette dynamique est un sujet primordial mais qui a encore reçu relativement peu d'attention.

Ce mémoire est consacré à l'étude de cette dynamique, selon trois axes différents : la mesure, c'est-à-dire l'acquisition d'informations sur quels noeuds et liens sont présents et à quels moments dans un graphe ; la métrologie, c'est-à-dire l'étude du biais induit dans les données par l'opération de mesure ; et l'analyse, c'est-à-dire la description, souvent au moyen de propriétés statistiques ou structurelles, d'un graphe et de sa dynamique.

Nous avons montré que ces problématiques, qui ont été mises en évidence dans les études consacrées aux graphes statiques, sont également pertinentes dans le cas dynamique, et que de nouvelles questions apparaissent. Concernant la mesure, il est apparu qu'il est essentiel d'étudier de manière rigoureuse les paramètres de mesure, afin de certifier la qualité des données obtenues et de favoriser la reproductibilité de ces mesures. Nous avons étudié plusieurs cas où la mesure introduit un biais dans les observations. Nous avons en particulier introduit une méthodologie permettant de savoir si une mesure a duré suffisamment longtemps pour que l'on puisse avoir confiance dans les propriétés observées. Concernant l'analyse, nous nous sommes principalement intéressés à la dynamique de la topologie de l'internet telle qu'observable depuis un unique moniteur. Nous avons notamment mis en évidence le fait que les adresses IP observables depuis un moniteur se renouvellent à un rythme beaucoup plus important que ce qui était auparavant supposé, et que les changements de routage jouent un rôle important dans ce phénomène.