Durée du projet

Décembre 2010 -- Novembre 2013

Participants

Anciens participants

Description

Les graphes dynamiques apparaissent dans de nombreux contextes : réseaux informatiques dans lesquels des machines ou des liens peuvent subir des pannes, réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Jusqu'à récemment ces objets étaient principalement étudiés sous un angle statique, c'est-à-dire comme des photos du graphe à un instant donné. Un grand nombre de résultats de ces 10 dernières années ont introduit un ensemble d'outils pour l'analyse et la description des graphes statiques. Or, prendre en compte la dynamique de ces graphes est fondamental, tant pour avoir une bonne compréhension de leur structure que pour les applications correspondantes. Il y a donc un fort besoin de développer des outils et méthodes pour l'analyse de la dynamique de graphes, autant d'un point de vue fondamental que pour les applications, et ce dans de nombreux domaines : informatique, biologie, sociologie, économie, etc.

Ce projet poursuit deux objectifs distincts. D'une part nous souhaitons établir les outils nécessaires pour l'étude des graphes dynamiques, en introduisant des notions pertinentes pour décrire et comprendre leur structure. Pour cela, nous commencerons par étudier l'évolution temporelle de propriétés décrivant des graphes statiques, qui permet déjà de donner des résultats intéressants. Ceci n'est cependant pas satisfaisant, car étudier l'évolution de propriétés statiques ne permet pas de prendre pleinement en compte la dynamique du graphe. Par exemple, cette approche ne permet pas d'étudier des notions élémentaires comme le taux d'apparition ou de disparition de noeuds et de liens, ou leurs durées de vie. Nous introduirons donc également des notions prenant intrinsèquement en compte la dynamique des graphes étudiés. Nous nous intéresserons également à des questions particulièrement importantes dans ce contexte : la détection d'événements anormaux, et la détection de communautés dynamiques. Enfin, nous souhaitons également traiter la question de la modélisation des graphes dynamiques, c'est-à-dire de la génération de graphes dynamiques artificiels ayant les mêmes propriétés que des graphes dynamiques réels.

Le second objectif du projet concerne l'utilisation de graphes dynamiques issus d'applications réelles pour fonder et valider nos travaux. Cela assurera la pertinence de nos études fondamentales tout en produisant des résultats sur ces cas d'étude, avec un impact fort sur les domaines correspondants. Nous avons d'ores et déjà accès à de grands ensembles de données issus de trois graphes dynamiques différents : les échanges entre machines sur Internet au niveau IP ; des mesures de l'évolution de la topologie locale autour d'une machine sur Internet ; et des échanges sur des systères peer-to-peer de partage de fichiers. Nous ajouterons d'autres cas au cours du projet si cela s'avère nécessaire ou pertinent.

L'équipe impliquée dans ce projet est constituée des membres permanents de l'équipe Complex Networks du LIP6, centrée sur l'étude des graphes de terrain. Le coordinateur du projet et les autres membres de l'équipe son persuadés que l'étude de la dynamique des graphes constitue un thème émergent fondamental dans le domaine de l'étude des graphes de terrain en général, et souhaitent consacrer une part importante de leur activité au développement de ce thème.