Séminaire

Date : 4 juin 2020 13:00 - Salle :Visio-conférence Recherche de chemin dans des grands graphes Bruno GUILLON - MC LIMOS, Université Clermont Auvergne

Séminaire court de 30 minutes

Les mesures de complexité classiques (temps ≡ nombre d'opérations, espace) ne sont pas adaptées lorsqu'il s'agit d'étudier de très grands graphes, qui ne peuvent être stockés en mémoire centrale. En effet, le coût d'un accès sur disque surpasse largement le coût des opérations effectuées “en mémoire”. Une mesure de complexité plus adaptée pour l'algorithmique des très grands graphes est donc de mesurer le nombre d'accès disque, de requêtes effectuées, ou la taille du sous-graphe exploré si une exploration partielle est suffisante. Dans le cadre du problème de recherche de (plus court) chemin, nous pouvons proposer un algorithme approché, guidé, qui permet de restreindre considérablement l'espace visité par rapport aux algorithmes classiques (e.g., le parcours en largeur bilatéral). En se basant sur des fonctions heuristiques obtenues par des méthodes d'apprentissage du traitement automatique des langues, nous avons obtenu expérimentalement des résultats encourageants sur des graphes sociaux, comme par exemple le graphe des publications extrait de la plateforme DBLP. Ceci est un travail joint avec Charles Paperman.