Ce cours portera sur certaines observations empiriques du réseau
Internet en tant que graphe, et présentera des modèles de
son évolution. On supposera les auditeurs familiers avec les notions
de base de la théorie de graphe et de l'algorithmique sur les graphes.
Quelques notions d'algèbre linéaire, bien que facultatives,
faciliteront la compréhension. Nous discuterons de propriétés
telles que : la séquence des degrés, la connectivité
et la stationnarité de marches aléatoires (celles-ci sont
utilisées afin de trier les pages web). Partant de mesures empiriques
de ces quantités sur le réseau Internet, nous concluons que
les familles de graphes aléatoires traditionelles ne donnent pas
d'explications convenables à ces observations. Nous présenterons
alors un panorama des tentatives visant à modéliser le réseau
Internet, et à définir un modèle dit de web-graph.
Abstract:
These lectures will cover a number of empirical observations about the web graph, and present models for the evolution of the web graph. The audience is expected to be familiar with basic graph theory and graph algorithms. Some knowledge of linear algebra and random walks may help, but is not essential. We will discuss degree sequences, connectivity and the stationary distribution of random walks (which is used in ranking pages in web search). From empirical observations of these quantities on the web we point out that traditional random graph models do a poor job of explaining these observations. We then review several recent directions in creating models for "web-like" graphs.
Related papers: