Voici mon exercice :
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 www.pageA.fr (A), www.pageB.fr(B), www.pageC.fr (C), et 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 m'aiguiller?
Merci beaucoup.
Bonjour,
Note les coefficients de la matrice associée au graphe et les importances des pages.
Traduit en équations la phrase "La page a
une importance ; 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. "
Si je résume
- les fléches sortantes :
- A -> B, C, D
- B -> D
- C -> A
- D -> A, C
- les fléches entrantes :
- A <- C, D
- B <- A
- C <- A, B, D
- D <- A, B
Si je ne me suis pas trompé dans les fléches, et si je traduis pour :
- les fléches sortantes :
(1/3) * xB + (1/3) * xC + (1/3) * xD = xA
xD = xB
xC = xA
(1/2) * xA + (1/2) * xC = xD
- les fléches entrantes :
xA = xC + xD
xB = xA
xC = xA + xB + xD
xD = xA + xB
C'est comme ça pour le système linéaire?
Merci beaucoup pour votre aide.
C'est pas plutôt juste ça :
xA = xC + (1/2)*xD
xB = (1/3)*xA
xC = (1/3)*xA+(1/2)*xB+(1/2)*xD
xD=(1/2)*xB+(1/3)*xA
Ou il y a une erreur?
Lisons la phrase car ta difficulté n'est pas mathématique, c'est une difficulté de compréhension de la phrase en français :
On numérote de 1 à 4, d'habitude, et si tu compares avec ton message de 10:20 tu peux voir qu'il manque des choses.
Regarde mieux ! Compare avec
En notant la matrice associée au graphe et le vecteur colonne des importances, tu es arrivé à .
Il te reste une information à prendre en compte :
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :