COmpression de REseaux et de GRAPHes pour une Informatique Efficace (COREGRAPHIE)

Type of project: ANR
Contract dates: 2021 - 2025
Équipe(s): GOAL
Responsable scientifique LIRIS: Hamida Seba
Partenaire(s): Centre de Recherche Inria de Paris, Institut de Recherche en Informatique Fondamentale, Laboratoire d’Informatique de Bourgogne
URL du projet: https://coregraphie.projet.liris.cnrs.fr/

Description:
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, 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, 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 le projet COREGRAPHIE, 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 simplification et 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.