Thèse de François Pitois


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

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.


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