Offre en lien avec l’Action/le Réseau : – — –/– — –

Laboratoire/Entreprise : DVRC / Pôle Léonard de Vinci
Durée : 5 mois
Contact : sonia.djebali@devinci.fr
Date limite de publication : 2021-02-15

Contexte :
La compréhension du comportement et de la mobilité touristique requiert de prendre en compte les informations sur les lieux visités, les données sur le touriste ainsi que leurs interactions. Il est possible de représenter les interactions intrinsèques entre les lieux par un graphe. Un graphe représente un groupe de touristes selon un paramètre donné, par exemple la nationalité. Le laboratoire DVRC est spécialisé dans l’analyse de comportement touristique et a développé des études sur la circulation des touristes sur le territoire grâce à des représentations sous forme de graphes [1, 2]. Toutefois, les graphes générés demandent une analyse encore plus fine avec l’extraction de caractéristiques communes entre ces graphes.
Afin d’extraire des caractéristiques identiques entre groupes, il est nécessaire de se focaliser sur les similitudes entre les deux graphes. Leur comparaison se fait par une application mathématique appelée isomorphisme. Historiquement, pour prouver l’isomorphisme entre deux graphes, il convient de comparer leur matrice d’adjacence, à condition d’avoir le même nombre de sommets et le même nombre d’arêtes [3].
Cependant, la comparaison de deux graphes contenant de nombreux sommets, ou de tailles différentes requiert donc une autre méthodologie. L’isomorphisme de deux graphes peut être effectué sur les composantes fortement connexes de ces graphes [4]. Une autre approche serait de réduire un des deux graphes dans le deuxième [5]. Dans cette dernière approche, l’isomorphisme fait appel à un mapping entre les deux graphes. Dans ces deux approches, il est envisageable d’utiliser l’isomorphisme de matrices.
D’autre part, les graphes manipulés dans le contexte de la circulation touristique sont variables et peuvent devenir conséquents, surtout en nombre d’arêtes. Il est donc nécessaire que cette méthode soit améliorée afin d’être efficace sur des matrices de grande taille, et possiblement non symétrique dans le cadre d’un graphe orienté. Une approche de stockage reposant sur une base de données orientée graphe, telle que Néo4j1 permet de gérer l’accès aux données et faciliter la gestion des ressources pour de telles manipulations.

Sujet :
L’objectif du stage est d’effectuer un état de l’art sur la problématique de l’isomorphisme de graphe, de similarité de sous-composantes et de mapping de graphe. Une méthodologie pour comparer de graphes de structures différentes devra être établie avec une complexité en temps et en mémoire moindre. L’étudiant devra donc :
• Développer un état de l’art sur l’isomorphisme de graphe et d’étudier les spécificités du contexte de graphes de circulation touristique ;
• Intégrer une approche de la littérature dans la base de données orientée graphe Neo4j utilisé dans ce contexte ;
• Proposer une nouvelle méthodologie de comparaison de graphes capable de passer à l’échelle

Profil du candidat :
Étudiante ou étudiant de niveau M2 en informatique (Master ou école d’ingénieurs).

Formation et compétences requises :
Les candidat.e.s sont invité.e.s à nous envoyer un mail à sonia.djebali@devinci.fr avec : CV indiquant leurs expériences et compétences
Une lettre de motivation
Les bulletins de notes des deux dernières années.

Adresse d’emploi :
Laboratoire de recherche De Vinci Research Center au sein de l’École Supérieure d’Ingénieurs Léonard de Vinci ; Paris, la Défense.

Document attaché : 202101061625_SUJET_ISOMORPHISME.pdf