Seminar


Date : June 4, 2020, 1 p.m. - Room :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.

 

Vous pouvez transférer cette invitation à d'autres personnes.

christophe rey vous invite à rejoindre cette réunion Webex.
 
Numéro de la réunion (code d’accès) : 322 118 361
Mot de passe de la réunion : gYk5YsUH8x3
 
jeudi 4 juin 2020
13:00  |  (UTC+02:00) Bruxelles, Copenhague, Madrid, Paris  |  30 min.
 
rejoindre la réunion
 
Rejoindre par téléphone
Tapez pour appeler à partir d'un périphérique mobile (invités uniquement)
+33-1851-48835 France Toll
+33-1-7091-8646 France Toll 2
Numéros d'appel internationaux
 
Rejoindre à partir d'un système ou d'une application vidéo
Composer le numéro 322118361@univca.webex.com
Vous pouvez également composer 62.109.219.4 et saisir votre numéro de votre réunion.
 
Rejoindre les réunions via Microsoft Lync ou Microsoft Skype Entreprise
Composer le numéro 322118361.univca@lync.webex.com
 
Besoin d’aide ? Allez à l'adresse http://help.webex.com