Institut de Recherche sur l'Enseignement des Mathématiques de Paris

Les graphes ou réseaux d'interactions apparaissent naturellement en télécommunication (Internet, graphe du Web, réseaux pairs-à-pairs, Facebook, ...), dans les interactions sociales (communautés d'intérêts, systèmes de recommandations, ...), bibliométrie (citations, co-auteurs), ou encore en biologie (propagation d'épidémies, interactions entre protéines). Ces réseaux sont souvent de grande taille, et il faut donc des algorithmes très performants pour les analyser. Surtout ils permettent de comprendre les liens structurels entre les entités modélisées par ces réseaux. A l'aide de plusieurs exemples issus d'applications dans des domaines différents, je montrerai que leur connaissance en tant que graphe permet d'en déduire des informations importantes sur les individus (sommets du graphe)... Enfin, je présenterai en détail l'algorithme de PageRank (Google) qui permet à partir du graphe d'interaction des pages Web, d'attribuer de manière récursive un coefficient d'importance à une page Web donnée. Cet algorithme est un très bel exemple d'application de mathématiques simples (algèbre linéaire, chaînes de Markov) à notre vie quotidienne car il est très utilisé par tous les moteurs de recherche afin de classer les réponses à vos questions.