Thesis of François Pitois


Subject:
Regularity search and succinct representations of graphs

Defense date: 10/07/2024

Advisor: Hamida Seba
Coadvisor: Mohammed Haddad
Codirection: Olivier Togni

Summary:

Graphs are a tool used in a lot of fields to represent various kinds of concrete data. However, with the expansion in size of those data, it becomes harder and harder to process those graphs. Graph compression aims at shrinking and summarizing graphs so that standard algorithms can process them in a reasonable amount of time. There are currently several lossless and lossy methods to compress a graph, such as Shrink by Sadri et al. or Slashburn by Kang and Faloustos. A notable framework is WebGraph by Boldi and Vigna, which compresses the web graph using locality properties and hyperlinks similarity. Some other approaches are based upon modular decomposition which finds regularities within a graph. Generally, several compression methods are based upon finding regularities within graph such as frequent patterns. The main goal of this thesis is to explore regularities of large data graphs and use those regularities to summarize graphs efficiently. Hence, the first question to answer is how do we find efficiently regularities in a large graph, and what kind of regularities can you find in a reasonable amount of time. Next, once regularities are found, it will be crucial to find efficient ways to represent a graph based on those regularities. Another question this thesis will try to answer is what kind of graph parameters is it possible to estimate using a summarized graph.


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)