Projet ANR-10-JCJC-0202 – DynGraph : Dynamiques de Topologies de Graphes
Programme : JCJC : Sciences de l'information, de la matière et de l'ingénierie : Sciences de l’information, simulation (JCJC SIMI 2)
Année de financement : 2010
Coordinateur du projet : Madame Clémence Magnien (UNIVERSITE PARIS VI [PIERRE ET MARIE CURIE])
Partenaires : Laboratoire d'Informatique de Paris 6
Montant : 170760.0 euros
Durée : 40 mois
Résumé : Comprendre les graphes qui évoluent au fil du tempsLes graphes permettent d'étudier de nombreux objets comme les réseaux d'amitié, l'infrastructure de l'internet, le Web, les réseaux routiers, etc. Leur étude est cruciale pour de nombreuses applications : moteurs de recherche, réseaux sociaux en ligne, robustesse de l'internet, etc. La plupart de ces graphes évoluent au fil du temps, mais ce n'est cependant pas pris en compte en général. Il y a donc un fort besoin de méthodes d'étude de cette dynamique.
Des graphes dynamiques apparaissent dans de nombreux contextes et il est important de comprendre leur dynamique pour de nombreuses applicationsLes graphes (c'est-à-dire des ensembles de noeuds reliés deux à deux) apparaissent dans de nombreux contextes. On peut citer les résesaux d'amitié, l'infrastructure de l'internet, le Web, les chaînes alimentaires, les réseaux routiers, etc. Depuis la fin des années 90, de nombreux travaux ont montré que l'étude de la structure de ces graphes, c'est-à-dire uniquement des liens entre les noeuds, en oubliant les informations sur les noeuds telles que par exemple l'âge ou le sexe de la personne considérée, permet d'obtenir des résultats cruciaux pour de nombreuses applications sociétales et/ou industrielles : moteurs de recherche, réseaux sociaux en ligne, robustesse de l'internet, etc. La plupart de ces graphes sont dynamiques : les relations d'amitiés changent, des machines sont ajoutées sur l'internet, etc. La plupart des travaux avant le début du projet n'ont cependant pas pris en compte cette dynamique. L'objectif du projet est donc de mettre au point des techniques permettant de comprendre la dynamique de ces graphes, ce qui est crucial pour les applications citées ci-dessus.
Notre approche : des allers-retours permanents     entre des cas particuliers d'intérêt et des questions générales.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.
Résumé de la soumission : 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.
Résultats : 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.
Perspectives : 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.
Publications et brevets : 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.