L'algorithme de Google

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
refaw
Messages: 1
Enregistré le: 17 Mai 2022, 08:42

L'algorithme de Google

par refaw » 17 Mai 2022, 08:47

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
Membre Relatif
Messages: 306
Enregistré le: 30 Oct 2013, 06:08

Re: L'algorithme de Google

par Mateo_13 » 17 Mai 2022, 08:59


 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 81 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite