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.