L'algorithme de Google

[refaw]

Bonjour,

Voici mon exercice de 1ère année de licence :

Au cœur du succès du moteur de recherche Google, l'algorithme PageRank repose, dans son
incarnation la plus simple, sur de l'algèbre linéaire de base. On veut ici étudier une version de cet
algorithme appliquée à des cas concrets.
On modélise notre réseau de pages web avec un graphe orienté, de la façon suivante : chaque
page est un sommet, et on dessine une flèche (arête orientée) allant de i à j si la page i contient un
lien à la page j. On a alors un graphe dont les arêtes sont des couples (i, j) ordonnés. On définit
ainsi une matrice qui a 1/Nj en position (i, j) s'il y a un lien sur la page j qui amène à la page i,
et 0 sinon : ici Nj est le nombre total de lien sortants de la page j.


(1) Les pages http://www.pageA.fr (A), http://www.pageB.fr(B), http://www.pageC.fr (C), et http://www.pageD.fr (D) contiennent les liens suivants : C a un lien entrant de chacune des autres pages, A a un lien
sortant à B et un à D, D contient un lien à A, B a un lien à D, C à A. Dessiner le graphe cor-
réspondant et écrire sa matrice associée. (Ex. : la page A a un lien sortant vers chacune de B, C,
D, donc la première colonne de la matrice associée est (0, 1/3, 1/3, 1/3)T .)

PageRank attribue à chaque page une importance relative x de la façon suivante. La page i a
une importance xi ; une page transfère son importance en parties égales aux pages auxquelles elle
pointe, et son importance doit être égale à la somme des importances qu'elle reçoit. On normalise
de sorte que la somme de toutes les importances soit 1.

(2) Si xA, xB , xC , xD sont les importances des pages de l'exemple, écrire le système linéaire qui
corréspond à la définition ci-donnée et trouver leurs valeurs.

(3) Soit v = (1/4, 1/4, 1/4, 1/4)T . Calculer Av, A2v, A3v. Comparer avec le résultat de la
question précédente : que remarque-t-on ? Que vaudra A100v, à deux chiffres décimaux près ?
Le PageRank consiste alors à calculer l'importance des pages et les classer en importance décrois-
sante. Voyons quelques exemples où cela ne marche pas.

(4) On a trois pages A, B, C. A et B ont chacune un lien à C. Écrire la matrice corréspondante
et trouver le PageRank. Pourquoi le résultat ne peut-il pas être un classement ?

(5) On a cinq pages A, B, C, D, E. A et B ont chacune un lien à l'autre. C et D ont chacune
un lien à l'autre; du même D et E ; et E et C. Quelle est l'importance des pages ? Pourquoi n'y
a-t-il pas un choix univoque du PageRank ?
Pour résoudre un de ces problèmes, si on a une matrice d'adjacence A comme ci-dessus, on
introduit une nouvelle matrice B = 0, 9 · A + 0, 1 · 1
n J (on perturbe A), où J a toutes ses entrées
égales à 1 et n est le nombre de pages à classer.

(6) Refaire les calculs des questions 4 et 5 avec cette nouvelle matrice et trouver le PageRank
corréspondant. Lequel des deux problèmes a été résolu ?
Intuitivement, le PageRank corréspond à un internaute qui choisit au hasard dans chaque page
un des liens qui amène à la prochaine page de son historique : l'importance d'une page est alors
la proportion de temps passé sur cette page.

Je pense être arrivé à la question 1. Mais je n'arrive pas à la question 2. Quelqu'un peut donner la réponse?

Merci beaucoup.

[Mateo_13]

Pas de multi-post : https://www.ilemaths.net/sujet-l-algorithme-de-google-880249.html