Emmanuelle Lebahr (LIAFA)

La navigabilité des réseaux, ou “effet petit monde”, consiste en l’existence de chemins très courts reliant toute paire de points dans des réseaux comportant un très grande nombre d’entités, et dans le fait que ces chemins puissent être découverts localement. Ce phénomène est aussi connu sous le nom des “6 degrés de séparation” depuis l’expérience de Milgram de 1967 sur un réseau social. Les réseaux concernés par ce phénomène sont nombreux et cruciaux: les réseaux sociaux, le réseau des pages web, la plupart des grands réseaux de communication…

Dans cet exposé, nous nous intéresserons aux causes de ce phénomène et aux avancées récentes en termes de modélisation de réseaux pour tenter de les comprendre. Nous verrons comment des modèles de graphes aléatoires augmentés peuvent faire émerger ce phénomène et comment nous pouvons les exploiter pour produire des grands réseaux de communication décentralisés très efficaces. Nous verrons également comment l’étude du phénomène “petit monde” peut nous amener à mieux comprendre la structure du réseau Internet, encore très méconnue.