Thesis of Louis Duvivier

Automatic detection of the structure of interactions within complex systems using graph modelling and compression


Graphs are a widely used tool to model and analyze systems made of a large number of entities in mutual interaction. One can find such systems in fields as divers as computer science (the internet), sociology (virtual or real social networks), biology (protein interaction networks), and many others. The main point of such a model is that, beyond each entity's individual behaviour, the overall organisation of their interactions can have a strong impact on the system's behaviour as a whole (one common example is the study of an epidemic spread within a population). Many models have been developed to explain the structure of interactions in different networks. More specificaly, one can think of the Erdos-Renyi and configuration model, which describe random interactions, various flavour of community-based models, and spacial models (gravity or radiation), among others. For many networks there is more than one possible model, but as they are very different in nature, it is difficult to compare and choose between them. The main objective of this thesis is to develop methods to do so, leveraging in particular information theory.

Advisor: Céline Robardet
Coadvisor: Rémy Cazabet