Analyse de trajectoires à l'aide de graphes attribués : vers un algorithme d'échantillonnage de sous-graphes exceptionnels

<note>

Thèmes : Machine Learning, Data Mining, Analyse de graphes, Mobilité, Echantillonnage (e.g., Metropolis-Hasting)

Encadrant(s) : Marc Plantevit, Anes Bendimerad

Laboratoire : LIRIS

Equipe : DM2L </note>

Les progrès dans les techniques de localisation et d'informatique mobile ont généré des données de trajectoires spatiales massives, représentant la mobilité d'une diversité d'objets en mouvement, tels que des personnes, des véhicules et des animaux. De nombreuses techniques ont été proposées pour le traitement, la gestion et l'exploitation des données de trajectoires au cours de la dernière décennie, favorisant un large éventail d'applications. Fournir des outils permettant de comprendre ces trajectoire est actuellement un défi.

Il est possible de représenter les déplacements des individus en s'appuyant sur une modélisation sous forme de graphes attribués. Un algorithme permettant la découverte de graphes exceptionnels a été développé. Cet algorithme retourne l'ensemble complet des sous-graphes exceptionnels. Or le problème de découverte de sous-graphes exceptionnels est NP-Complet.

Objectif

L'objectif de ce projet est de développer un algorithme permettant l'échantillonnage des sous-graphes exceptionnels. En d'autres mots, nous ne souhaitons plus obtenir toutes les solutions mais un bon échantillon dans un temps donné.

• compréhension du problème et l'algorithme de découverte de sous-graphes exceptionnels
• étude des méthodes d'échantillonnage
• Proposition et implémentation d'une méthode adaptée
• Etude empirique de la méthode proposée sur différents jeux de données réels

Mehdi Kaytoue, Marc Plantevit, Albrecht Zimmermann, Ahmed Anes Bendimerad, Céline Robardet: Exceptional contextual subgraph mining. Machine Learning 106(8): 1171-1211 (2017)

Ahmed Anes Bendimerad, Rémy Cazabet, Marc Plantevit, Céline Robardet: Contextual Subgraph Discovery with Mobility Models. COMPLEX NETWORKS 2017: 477-489

Ce projet est pertinent pour les étudiants désirant s'orienter vers les parcours de masters 2 DS, TIW, IA.