COmpression de REseaux et de GRAPHes pour une Informatique Efficace – COREGRAPHIE

Les graphes sont omniprésents. Également appelés réseaux, les graphes servent à modéliser de nombreux problèmes et données du monde réel : réseaux sociaux, réseaux routiers, assemblage de fragments de génomes, images et objets 3D (pour la reconnaissance et la classification de formes), etc. De nos jours, bon nombre de ces applications, sont confrontées à un problème majeur : le volume de données augmente à tel point que même les solutions polynomiales ne suffisent plus. Les plateformes distribuées ou parallèles, comme MapReduce, qui sont des approches efficaces pour traiter les données massives, ne sont pas nécessairement adaptées aux traitement de grands graphes, principalement à cause de la structure inhérente des données de type graphe et à la nature itérative de leurs algorithmes.

Dans ce projet, nous plaçons la compression au cœur de la problématique du traitement des grands graphes de données. Notre objectif est de définir un cadre de réduction de graphes qui permet de construire des représentations plus simples et plus petites des graphes, i.e., des résumés, que l’on peut utiliser à la place des graphes initiaux. Pour cela, nous proposons de développer des algorithmes qui permettent d’effectuer de telles compressions, et de les affiner en fonction de la qualité des résumés obtenus, ainsi que des traitements qu’ils permettent d’entreprendre.
L’avantage d’une telle approche est de traiter les données massives de type graphe en temps linéaire ou quasi-linéaire. Notre méthodologie se base sur la recherche de régularité dans les graphes afin de les réduire et de les analyser.

Ainsi, le défi que nous abordons est de définir, prototyper et tester une telle approche pour proposer un outil efficace, évolutif et opérationnel pour l’analyse de graphes qui peut être étendu à toutes les données structurées de type graphe. Nous appliquerons principalement nos travaux à Software Heritage, la plus grande archive de logiciels, avec code source et historique de développement, fondée par l’INRIA. Le modèle de données de cette archive est un graphe en plein expansion consistant de 15 milliards de nœuds et 200 milliards de liens.

Les nouveaux outils et algorithmes produits par le projet, dont le code source sera ouvert, créeront une base pour le développement de nouveaux types d’algorithmes d’analyse de données et de recherche d’informations pour les données de type graphe et trouveront des applications dans divers domaines et disciplines utilisant des graphes ou des réseaux.