La compression de graphes, également appelée réduction ou simplification de graphes a pour objectif de construire des résumés de graphes qui sont des graphes plus petits que les graphes de départ ou des représentations plus simples de ces derniers.   Les travaux existants montrent que la compression de graphes n’est pas seulement un outil pour réduire la taille mémoire nécessaire à des graphes massifs, mais aussi une étape de prétraitement intéressante qui peut améliorer la complexité des algorithmes de graphes. La compression trouve également application dans l’apprentissage où trouver un moyen de représenter ou d’encoder la structure du graphe est nécessaire pour exploiter les modèles d’apprentissage automatique existants. Plusieurs méthodes de compression avec ou sans perte sont proposées dans la littérature  mais la plupart des algorithmes de compression proposés dans la littérature ne sont pas incrémentaux et ne peuvent être utilisés pour construire ou mettre à jour le résumé d’un graphe dynamique.

L’objectif de principal de cette thèse est d’explorer les aspects d’incrementalité  dans les algorithmes de compression de graphes  afin de pouvoir construire des résumés pour des graphes dynamiques ou des flux de graphes.