CR-12 : Grands graphes de terrain

Programme de l’UE

Dans de nombreux contextes des grands graphes jouent un rôle essentiel ; citons par exemple la topologie de l’Internet, les graphes du Web ou les échanges Pair-à-Pair, mais aussi les réseaux sociaux, réseaux de contact, biologiques ou linguistiques. La disponibilité de données massives, de capacités de traitement adéquates, et l’observation de diverses propriétés en commun ont récemment donné naissance à un vaste effort de recherche sur ces objets. Son originalité réside dans le fait qu’on part de graphes issus d’observations, et non définis formellement. C’est en ce sens que ce sont des « graphes de terrain« .

Ce cours abordera les différentes problématiques soulevées par ce domaine que l’on peut regrouper en quatre familles complémentaires :

  • Mesure et Métrologie Mener des mesures fiables, de qualité et à grande échelle est une problématique de recherche en soi, qu’il ne faut pas ignorer. savoir ce que l’on mesure, comment et pourquoi est l’un des points de départ crucial de l’analyse des grands graphes de terrain.
  • Analyse : On abordera les outils et les formalismes pour décrire les grands graphes de terrain afin d’en extraire les principales propriétés.
  • Modélisation. Une fois les principales propriétés d’un graphe identifiées, les capturer dans un
    modèle formel est crucial notamment pour les expliquer, obtenir des résultats formels, et mener
    des simulations.
  • Algorithmique. La taille des graphes considérés interdit l’utilisation d’algorithmes quadratiques ou plus ; de nombreux problèmes pour lesquels des solutions habituellement satisfaisantes sont connues doivent donc être retravaillés. Par ailleurs, la présence de propriétés caractéristiques des graphes de terrain ouvre la voie au développement d’algorithmes efficaces dans ces cas.

Intervenants

  • Alain Barrat, CR CNRS, Centre de Physique Théorique, Marseille, France
  • Eric Fleury, Professeur ENS Lyon
  • Christophe Crespelle, Maître de conférences, Université de Lyon 1

Support de cours