Thèse de François Pitois


Sujet :
Recherche de régularités et représentations succinctes de graphes

Date de soutenance : 10/07/2024

Encadrant : Hamida Seba
Co-encadrant : Mohammed Haddad
Co-direction : Olivier Togni

Résumé :

Les graphes sont des outils utilisés dans de nombreux domaines afin de représenter toutes sortes de données réelles. Cependant, avec la taille sans cesse croissante de ces données, il devient de plus en plus difficile d'analyser ces graphes. La compression de graphes a pour but de réduire et de résumer des graphes afin que les algorithmes standards puissent les traiter en un temps raisonnable. Il y a actuellement plusieurs algorithmes avec ou sans perte qui permettent de compresser un graphe, comme Shrink par Sadri et al. ou Slashburn par Kang et Faloustos. Un framework notable est WebGraph par Boldi et Vigna, qui compresse le graphe du web en utilisant des propriétés de localité et des similarités dans les hyperliens. D'autres approches sont basées sur la décomposition modulaire, qui permet de trouver des régularités à l'intérieur d'un graphe. De manière générale, de nombreuses méthodes de compression sont basées sur le fait de trouver des régularités dans le graphe telles que des motifs récurrents. Le principal objectif de cette thèse est d'explorer les régularités des grands graphes de données et d'utiliser ces régularités pour résumer ces graphes efficacement. Ainsi, la première question que l'on se posera est comment trouve-t-on efficacement des régularités dans un grand graphe. Ensuite, une fois les régularités trouvées, il sera crucial de trouver une façon de représenter intelligemment ce graphe en s'appuyant sur ces régularités. Une autre question à laquelle cette thèse essayera de répondre est quel genre de paramètres de graphe est-il possible d'estimer en utilisant le résumé d'un graphe.


Jury :
M. Gavoille CyrilProfesseur(e)Université de BordeauxRapporteur(e)
M. Paul ChristopheDirecteur(trice) de rechercheCNRS au LIRMMRapporteur(e)
M. Crespelle ChristopheProfesseur(e)Université Côte d’AzurExaminateur​(trice)
M. De Montgolfier FabienMaître de conférenceUniversité Paris CitéExaminateur​(trice)
Mme Parreau AlineChargé(e) de RechercheLIRIS CNRS UMR 5205 - Université Claude Bernard Lyon 1Examinateur​(trice)
M. Togni OlivierProfesseur(e)Université de BourgogneDirecteur(trice) de thèse
Mme Seba HamidaProfesseur(e)LIRIS Université Claude Bernard Lyon 1Co-directeur (trice)
M. Haddad MohammedMaître de conférenceLIRIS Université Claude Bernard Lyon 1Co-encadrant(e)