Thèse de Antoine Castillon


Sujet :
Algorithmes Online pour la compression de graphes

Date de soutenance : 28/10/2024

Encadrant : Hamida Seba
Co-encadrant : Mohammed Haddad
Co-direction : Julien Baste

Résumé :

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.


Jury :
Mme Bazgan CristinaProfesseur(e)Université Paris DauphineRapporteur(e)
M. Liedloff MathieuProfesseur(e)Université d’OrléansRapporteur(e)
M. Guillaume Jean-LoupProfesseur(e)Université de La RochelleExaminateur​(trice)
M. Letocart LucasProfesseur(e)Université Sorbonne Paris NordExaminateur​(trice)
Mme Dhaenens ClarisseProfesseur(e)Université de LilleDirecteur(trice) de thèse
Mme Seba HamidaProfesseur(e)LIRIS Université Lyon 1Co-directeur (trice)
M. Baste Julien BASTE Maître de conférencesMaître de conférenceUniversité de LilleCo-encadrant(e)
M. Haddad MohammedMaître de conférenceLIRIS Université Lyon 1Co-encadrant(e)