Antoine Channarond
Clustering dans un modèle de graphe aléatoire à positions latentes
On dispose d’un réseau d’interactions, c’est-à dire d’un ensemble d’individus (noeuds du graphe), et l’ensemble de leurs interactions inter-individuelles (les arêtes du graphe). La question posée est celle de la classification (ou clustering) des noeuds. Il existe de très nombreuses méthodes reposant sur des points de vue différents, telles que la classification par communautés, le clustering spectral, ou encore le model-based clustering, qui consiste à se placer dans une famille de modèles de graphes aléatoires, où chaque noeud appartient à une classe non-observée, et la probabilité de connexion entre deux noeuds dépend de leurs classes d’appartenance. Le challenge statistique de classification est d’inférer les classes latentes à partir de l’observation du graphe seulement.
On se propose ici de considérer un modèle de graphe où les variables latentes ne sont pas des classes, mais des positions dans un espace qui n’est pas observé, suivant une densité de probabilité f inconnue. Les clusters correspondent aux composantes connexes d’un ensemble de niveau t (à choisir) de la densité f. Le modèle suppose que la probabilité de connexion entre deux noeuds dépend de la distance entre les positions des noeuds de manière croissante (plus les noeuds sont proches, plus ils ont de chance de se connecter). L’enjeu statistique est de classer les noeuds, selon le cluster auquels ils appartiennent. Pour cela on utilise le lien entre degré d’un noeud (nombre de ses voisins) et densité en la position latente du noeud, puis le fait que le graphe, élagué en ne conservant que les noeuds de degré suffisamment grand, respecte la structure topologique de l’ensemble de niveau. L’analyse du graphe permet alors une analyse indirecte statistique de l’espace latent, et de sa structure de clustering, à la résolution choisie (en lien avec le niveau t).