Évènements

05 sep
05/09/2019 14:30

Sciences & Société

Soutenance de thèse : Ahmed Anes BENDIMERAD

Mining useful patterns in attributed graphs

Doctorant : Ahmed Anes BENDIMERAD

Laboratoire INSA : LIRIS
Ecole doctorale : ED512 : InfoMaths

Le graphe est une structure qui permet de modéliser efficacement une large variété de données. Par exemple, un réseau social peut être représenté avec un graphe où les personnes sont les sommets, et leurs liens d'amitiés sont les arêtes. Ces graphes peuvent être augmentés avec des attributs décrivant ses sommets. Dans un réseau social, chaque personne peut être décrite par son âge, ses centres d'intérêts, etc. C'est ce qu'on appelle un graphe attribué. L'analyse de ce type de graphes peut offrir une grande opportunité pour extraire des informations utiles et actionnables. Cela permet d'identifier des communautés ayant des centres d'intérêts particuliers dans un réseau social, de détecter des évènements à partir des tweets partagés, etc. Dans cette thèse, nous adressons le problème de fouille de graphes attribués. Plus précisément, nous proposons des méthodes qui analysent un graphe pour identifier des motifs : des sous- graphes ayant des caractéristiques particulières. Bien que ce problème a intéressé un grand nombre de chercheurs depuis des années, il reste encore plusieurs défis à relever. Nous adressons la question : quand est-ce qu'un motif est intéressant pour l'utilisateur ? plusieurs facteurs entrent en jeu. Nous considérons qu'un motif est intéressant : (1) s'il montre une exceptionnalité par rapport au reste du graphe, (2) s'il donne une nouvelle information à l'utilisateur (il est imprévu), (3) s'il communique une information qui fait partie du centre d'intérêt de l'utilisateur (préférences). Pour mesurer la qualité d'un motif, nous proposons des modèles qui prennent en compte un ou plusieurs de ces trois facteurs. Nous définissons des algorithmes qui déterminent les meilleurs motifs selon chaque modèle proposé, et nous effectuons des études empiriques pour évaluer l'efficacité de chacun de ces algorithmes.

Informations complémentaires

  • Amphi Chappe (Bâtiment Claude Chappe, TC) - Villeurbanne