Google et l’algèbre linéaire

Ophir Lojkine

Description

Présentation de l’algorithme Pagerank de Google

Informations

• Publié par: Force_IT
• Nombre de lectures: 27
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

GÉnÉralitÉs Qu’est-cequ’un graphe ?IdÉes d’algorithmesRÉsolution d’un systÈme d’Équations linÉairesMarche alÉatoire, chanes de Markov

Google et l’algÈbre linÉaire
PrÉsentation de l’algorithme Pagerank de Google

Ophir LOJKINE

Mai 

GÉnÉralitÉs Qu’est-cequ’un graphe ?IdÉes d’algorithmesRÉsolution d’un systÈme d’Équations linÉairesMarche alÉatoire, chanes de Markov

GÉnÉralitÉs
1
Qu’est-ce qu’un graphe?
2
IdÉes d’algorithmes
3
Compter le nombre de liens
Une idÉe simple
Des rÉsultats perfectibles
Partage du poids des liens
On complexifie un peu les choses
C’est toujours pas Ça
RÉsolution d’un systÈme d’Équations linÉaires
4
L’idÉe gÉniale
Et l’algÈbre linÉaire apparat
5
Marche alÉatoire, chanes de Markov
Suite des puissances de M
Terme correctif
L’algorithme, enfin!
Pour aller plus loin
6

GÉnÉralitÉsMarche alÉatoire, chanes de MarkovQu’est-ce qu’un graphe ?IdÉes d’algorithmesRÉsolution d’un systÈme d’Équations linÉaires
Objet de l’exposÉ
Objectifs de l’algorithme pagerank

Pagerank
L’unique but de cet algorithme est d’attribuer une note À chaque page du
web, qui correspond À sonimportance.

Pagerank ne fait pas tout...
L’algorithme pagerank ne sert pas À :
Analyser les requtes des utilisateurs
Analyser le contenu des pages web
Trouver les pages qui correspondent À une requte

GÉnÉralitÉsQu’est-ce qu’un graphe ?RÉsolution d’un systÈme d’Équations linÉairesMarche alÉatoire, chanes de MarkovIdÉes d’algorithmes
Qu’est-ce qu’un graphe?
Qu’est-ce qu’un graphe ?

DÉfinition
Un graphe est un ensemble de nœuds reliÉs entre eux par des artes
(cas gÉnÉral) ou par des arcs (graphes orientÉs).
Les graphes que nous allons Étudier sont des graphes orientÉs, c’est À
dire que leurs artes ont une direction : il peut y avoir un arc de A vers B,
mais aucun arc de B vers A.

GÉnÉralitÉsQu’est-ce qu’un graphe ?IdÉes d’algorithmesRÉsolution d’un systÈme d’Équations linÉairesMarche alÉatoire, chanes de Markov
Qu’est-ce qu’un graphe?
Qu’est-ce qu’un graphe ?

DÉfinition
Un graphe est un ensemble de nœuds reliÉs entre eux par des artes
(cas gÉnÉral) ou par des arcs (graphes orientÉs).
Les graphes que nous allons Étudier sont des graphes orientÉs, c’est À
dire que leurs artes ont une direction : il peut y avoir un arc de A vers B,
mais aucun arc de B vers A.

Exemple de graphe orientÉ :

Qu’est-ce qu’un graphe?- Exemple

Les graphes
nœuds
arcs

Le web
pages web
liens hypertexte

GÉnÉralitÉs Qu’est-cequ’un graphe ?IdÉes d’algorithmesMarche alÉatoire, chanes de MarkovRÉsolution d’un systÈme d’Équations linÉaires

IdÉes d’algorithmes- Compter le nombre de liens

Compter le nombre de liens
IdÉe simple : compter le nombre de liens. Le score d’un nœud sera alors
lenombre total d’arcspointant vers lui.
Le score d’une page web sera alors proportionnel au nombre de liens
vers cette page.

IdÉes d’algorithmes- Exemple

ProblÈmes
Facile À
dÉtourner : il
suffit de faire
une page qui va
faire des liens
vers toutes les
autres pages
d’un site pour
augmenter
artificiellement le
score de
certaines pages.
Ne donne pas
assez
d’importance À
la ae
gÉnÉrale.

GÉnÉralitÉs Qu’est-cequ’un graphe ?IdÉes d’algorithmesMarche alÉatoire, chanes de MarkovRÉsolution d’un systÈme d’Équations linÉaires

IdÉes d’algorithmes- Partage du poids des liens

Partage du poids des liens
On veut dÉvaluer les liens faits par des pages qui font trop de liens.
Si on appelleil’importance du nœud i etλjle nombre d’arcs venant du
nœudj, on a :

1
∑
i=
λj
j

IdÉes d’algorithmes- Exemple

ProblÈmes
Donne trop
d’importance À
la partie 3 du
deuxiÈme article.
Sous-estime
toujours
l’importance de
la premiÈre
page.
On peut toujours
le dÉtourner.
Comment ?