Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

L’algorithme de Google

Posté par
refaw
15-05-22 à 15:05

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.

Posté par
GBZM
re : L’algorithme de Google 15-05-22 à 15:22

Bonjour,

Note p_{i,j} les coefficients de la matrice associée au graphe et x_i les importances des pages.
Traduit en équations la phrase "La page i a
une importance x_i ; 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. "

Posté par
refaw
re : L’algorithme de Google 15-05-22 à 20:36

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.

Posté par
GBZM
re : L’algorithme de Google 15-05-22 à 22:47

Non, tu n'as pas correctement traduit la phrase. Relis-la soigneusement pour mieux la comprendre.

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 09:21

Bonjour,

Je suis vraiment désolé mais je n'arrive pas à voir mon erreur.
Une aide?

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 10:20

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?

Posté par
GBZM
re : L’algorithme de Google 16-05-22 à 10:22

Lisons la phrase car ta difficulté n'est pas mathématique, c'est une difficulté de compréhension de la phrase en français :

Citation :
La page i a une importance x_i ; une page transfère son importance en parties égales aux pages auxquelles elle pointe,
Ça veut dire que la page j contribue à l'importance de la page i pour ???

Citation :
et son importance doit être égale à la somme des importances qu'elle reçoit.
Ça veut dire que l'importance de la page i est x_i={???}.

Remplis les ??? en utilisant les x_j et les coefficients p_{i,j} de la matrice associée au graphe ; ces coefficients ont été explicités dans l'énoncé.

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 10:24

Je viens de faire de poster un message juste avant avec le sytème. Est-ce que c'est mieux comme ça?

Posté par
GBZM
re : L’algorithme de Google 16-05-22 à 10:34

La formule que tu as utilisée est x_i={???}

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 14:33

Je ne comprends pas.
Voici la matrice que j'ai :

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

C'est ça que tu veux que j'utilise?

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 14:41

C'est ça peut-être, je ne comprends pas trop :
x_i = \sum_{j=0}^{3}{p_{i,j}}

Posté par
GBZM
re : L’algorithme de Google 16-05-22 à 16:22

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.

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 16:32

Je ne vois pas ce qu'il manque. Pour moi, on retrouve tous les coefficients.

Posté par
GBZM
re : L’algorithme de Google 16-05-22 à 17:54

Regarde mieux ! Compare avec

Citation :
xA = xC + (1/2)*xD

Tu ne vois pas ce qui manque dans x_i=\sum_{i=1}^4p_{i,j} ?
Rappel : les p_{i,j} sont les coefficients de la matrice associée au graphe.

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 21:51

C'est ça :


 \\ x_i=\sum_{i=1}^4p_{i,j} *x_j
 \\

Posté par
refaw
re : L’algorithme de Google 16-05-22 à 21:55

Et donc :

 \\  \\ \begin{pmatrix}
 \\  \\ 0 & 0 & 1 & 1/2\\
 \\  \\ 1/3 & 0 & 0 & 0\\
 \\  \\ 1/3 & 1/2 & 0 & 1/2\\
 \\  \\ 1/3 & 1/2 & 0 & 0
 \\  \end{pmatrix}
 \\   *
 \\  \begin{pmatrix}
 \\  \\ x_1\\
 \\  \\ x_2\\
 \\  \\ x_3\\
 \\  \\ x_4 \end{pmatrix}
 \\ =
 \\  \begin{pmatrix}
 \\  \\ x_1\\
 \\  \\ x_2\\
 \\  \\ x_3\\
 \\  \\ x_4 \end{pmatrix}
 \\ 
 \\ 
 \\

C'est ça?

Posté par
refaw
re : L’algorithme de Google 17-05-22 à 07:36

Quelqu'un pour m'aider SVP?
Je patine...

Posté par
Mateo_13
re : L’algorithme de Google 17-05-22 à 08:01

Pas de multi-post : https://www.maths-forum.com/superieur/algorithme-google-t260731.html#p1517227

Posté par
GBZM
re : L’algorithme de Google 17-05-22 à 10:26

En notant P la matrice associée au graphe et X le vecteur colonne des importances, tu es arrivé à X=PX.
Il te reste une information à prendre en compte :

Citation :
On normalisede sorte que la somme de toutes les importances soit 1.
Avec ça, tu obtiens un système linéaire que tu peux résoudre.
Prends des initiatives, n'attends pas qu'on fasse tout pour toi en allant voir sur plusieurs forums !



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1541 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !