Moteurs de recherche (30 minutes)

Inspiré de Mesure de popularité d'une page web, de Julien Launay.

Matériel nécessaire : un dé à six faces par binôme.

  1. Avant le début de l'activité, le professeur a ouvert sur son ordinateur le fichier permettant de synthétiser les résultats de l'ensemble de la classe.

  2. Le professeur distribue le sujet (source), et lit avec les élèves l'énoncé.

  3. À la main, avec le dé, par binômes, les élèves simulent une marche aléatoire sur le graphe. Le professeur les laisse chercher deux minutes, puis il parcours la salle pour :

    • dire à chaque binôme (dés que la place est libre) qu'il peut aller reporter ses résultats sur l'ordinateur du professeur ;
    • ramasser son dé.

    À la fin de l'activité, sur l'ordinateur du professeur, le score PageRank de l'ensemble du graphe est disponible.

    Remarque : Le score PageRank devrait1 être (arrondi au centième) : $$\begin{array}{cccccc} A & B & C & D & E & F \\ \hline 0,32 & 0,11 & 0,16 & 0,24 & 0,08 & 0,09 \ \end{array}$$

  4. Les élèves répondent d'abord seuls, puis en faisant le bilan en grand groupe avec le professeur, à la suite de l'activité (parties Analyse et Search Engine Optimization).

    La réponse attendue à la dernière question est que l'on peut créer trois nouvelles pages web qui forment une clique avec le sommet F (c'est-à-dire que chaque sommet de F et des trois nouveaux sommets pointe vers les autres). Cela augmente artificiellement la popularité de ces pages, et permet de faire de F la page la plus populaire du graphe.


  1. La matrice de transition du graphe probabiliste (dans lequel les sommets ont été triés par ordre alphabétique) est :

    $$M=\begin{pmatrix} 0 & 1/3 & 1/3 & 1/3 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 1/2 \\ 1/2 & 0 & 0 & 0 & 1/2 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}$$

    Quelqu'un de plus compétent que moi en math pourrait calculer la valeur exacte des états stables de ce graphe. Je me contenterai de supposer que l'état initial n'a aucune incidence sur cet état stable, et de calculer :

    $$\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0\end{pmatrix}\times\begin{pmatrix} 0 & 1/3 & 1/3 & 1/3 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 1/2 \\ 1/2 & 0 & 0 & 0 & 1/2 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}=\begin{pmatrix} 0,32 & 0,11 & 0,16 & 0,24 & 0,08 & 0,09 \end{pmatrix}$$