Dynamiques de Topologies de Graphes – DynGraph

Le but de ce projet est de définir des méthodes et des outils pertinents pour étudier la dynamique des graphes. Nous nous appuyons sur des cas concrets de graphes dynamiques, comme par exemple l'infrastructure de l'internet, les liens entre blogs, ou les réseaux de proximité entre individus. En effet, appliquer les notions que nous introduisons sur des cas concrets permet de s'assurer de leur pertinence. Réciproquement, l'étude de ces cas particuliers soulève naturellement de nouvelles questions, qui peuvent ensuite être formalisées en notions génériques. L'objectif est donc de concevoir des métodes génériques, c'est-à-dire pertinentes pour l'étude de la dynamique de n'importe quel graphe. Ces méthodes doivent être développées selon 4 axes : description et manipulation de graphes dynamiques ; détection d'événements qui s'éloignent de la dynamique normale ; dynamique de la structure en communautés des graphes, et conception de modèles de graphes dynamiques capturant les propriétés observées. Enfin, nous avons également pour but de produire des résultats sur la dynamique de cas particuliers de première importance.

Nous avons obtenu des résultats importants selon quatre axes : nouvelles notions pour caractériser la dynamique d'un graphe ; nouvelles méthodes permettant de détecter des anomalies ; nouvelles méthodes permettant de découper le graphe en communautés, c'est-à-dire des groupes de noeuds proches dans le graphe, et de suivre ces communautés au fil du temps ; nouveaux modèles permettant de faire des simulations. Enfin, nous comprenons mieux la dynamique d'objets sociétaux cruciaux. Le projet a également contribué à la mise en place de deux nouveaux partenariats académiques/industriels.

Plusieurs perspectives émergent de ce projet. Tout d'abord, notre meilleure compréhension des objets étudiés nous a fait introduire le concept de flot de liens, concept extrêmement prometteur. Nous avons fait une demande de projet ANR lors du dernier appel. Même si elle n'a malheureusement pas passé la première phase, nous avons confiance dans le fait que, une fois murie, cette approche donnera lieu à des résultats de tout premier plan. Ensuite, certaines des notions que nous avons introduites se prêtent à des calculs distribués, notamment la notion de coeur de communautés. Calculer de manière efficace ces notions sur des clusters de calcul nous permettra de gagner un ordre de grandeur sur la taille des graphes que nous pouvons gérer. Il s'agit d'une de nos perspectives importantes et entre dans le cadre du projet Request financé par les investissements d'avenir, dont nous sommes partenaires et qui vient de débuter. Enfin, le projet a mené à l'introduction de notions extrêmement prometteuses concernant la dynamique des communautés, qui n'ont pas pu être finalisées pendant la durée du projet. Cette question est l'un des aspects principaux du projet ANR CONTINT CODDDE, porté par Jean-Loup Guillaume, l'un des membres de ce projet, qui démarre en 2014.

Les résultats du projet ont conduit d'une part à des implémentations logicielles des différentes méthodes développées, et d'autre part à des publications dans les moyens traditionnels de diffusion académique : journaux internationaux (4 publications dont Complex Systems) et conférences internationales (12 publications dont MobiCom). Nous avons pris soin de viser les différentes communautés scientifiques concernées afin de maximiser l'impact du projet.

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.