Soutenance de thèse

La soutenance de thèse de Maximilien Dreveton aura lieu le 6 avril 2022 à 14:00 CET dans la salle Euler violet de l’Inria Sophia Antipolis. Elle sera aussi retransmise sur Zoom.

Titre: « Détection de communautés dans des réseaux non-binaires, temporels et géométriques, et en régime semi-supervisé »


Composition du jury

Directeur de thèse :

  • Konstantin Avrachenkov , Directeur de Recherche, (Inria)

Rapporteurs :

  • Catherine Matias , Directrice de Recherche, CNRS-Sorbonne Université-Université de Paris
  • Dieter Mitsche , Professor, Institut Camille Jordan

Examinateurs :

  • Frédéric Havet , Directeur de Recherche, Institut National de Recherche en Informatique et en Automatique (INRIA)
  • Varun Jog , Assistant Professor, University of Cambridge
  • Marc Lelarge , Directeur de Recherche, ENS/Inria
  • Lasse Leskelä , Associate Professor, Aalto University

Invité :

  • Gérard Bunrside , Research scientist, Nokia Bell Labs

Résumé :

La multiplication des données collectées a occasionné un intérêt multi-disciplinaire autour de l’étude statistique de systèmes complexes où les individus interagissent en pairs. Dans de tels réseaux, des individus similaires ont tendance à interagir similairement. Un important problème d’inférence statistique consiste donc à regrouper les individus similaires en communautés (aussi appelées clusters) en se basant uniquement sur l’observation des interactions entre individus. Ce problème d’apprentissage non-supervisé qui consiste à placer chaque nœud dans un groupe est appelé détection des communautés.

Cette thèse a pour but d’étudier différents aspects de la détection de communautés dans des systèmes complexes.

En particulier, nous étudions des modèles de graphes aléatoires où chaque nœud appartient à une communauté (aussi appelé bloc) et où l’interaction entre deux nœuds dépend uniquement des blocs dans lesquels ces deux nœuds appartiennent. Pour ces modèles, nous établissons des résultats théoriques sur la possibilité et l’impossibilité de découverte des communautés. Notre étude autorise des interactions quelconques (non nécessairement binaires), ce qui rend le résultat applicable à de nombreuses situations (interaction pondérées, temporelles, multi-couches, etc.).

Dans le cas particulier où les interactions entre les nœuds varient au cours du temps, nous proposons plusieurs algorithmes. Plus précisément, nous présentons des méthodes spectrales utilisant les interactions persistantes ou des méthodes basées sur un calcul itératif de la vraisemblance.

Nous examinons aussi le problème de la détection semi-supervisées des communautés. Dans ce cas, un oracle nous renseigne sur la communauté d’un petit nombre de nœuds. Ces renseignements s’ajoutent aux interactions observées entre les nœuds, et facilitent le problème initial (l’apprentissage des communautés des nœuds).

Enfin, nous étudions la situation où les nœuds sont positionnés dans un espace métrique. Dans ce cas, nous montrons que les méthodes spectrales classiques (telles que Spectral Clustering) peuvent totalement échouer, et nous analysons une parade basée sur la sélection de vecteurs propres d’ordre supérieur.

Les commentaires sont clos.