[PDF] Pertinence dune page web

12 mai 2015 · fameux liens Essayons de déterminer la pertinence d'une page web 2 Un exemple Soit le graphe suivant qui relie 4 pages Web : 3 2 1 4

[PDF] Pertinence dune page Web (TS spécialité) - Maths ac-creteil

Université d'été de Mathématiques Août 2012 Pertinence d'une page Web (TS spécialité) Exercice 1 Un groupe de musique a mis en place un site internet

[PDF] Modèle mathématique - TOURNON

Terminale S1- Spécialité mathématiques Corrigé du devoir maison N°7 Pertinence d'une page web Partie A : Etude asymptotique du surf « sans saut »

On a représenté ci-dessous cinq pages Internet comprenant des articles sur le sujet « les élèves de terminales S font-ils des études scientifiques ? » Sur certaines

[PDF] Pertinence dune page WEB

à fournir la liste de pages contenant le (ou les) mots clés de la requête Mais il y en a des dizaines de milliers Aussi l'ordre alphabétique n'apparaît pas le

[PDF] Pertinence dune page Web Lalgorithme PageRank

Pertinence d'une page Web L'algorithme PageRank Exercice 1 On s'intéresse au graphe orienté ci-dessous, représentant un ensemble de 5 pages internet et

[PDF] Amérique du sud Novembre 2013 Enseignement - Maths-francefr

Le gestionnaire d'un site web, composé de trois pages web numérotées de 1 à 3 et Bn : « Après la n-ième navigation, l'internaute est sur la page no 2 » et on

[PDF] on considère une pyramide régulière sabcd de sommet s

[PDF] les types de serveurs

[PDF] qu'est ce qu'un poste client

[PDF] extrait texte autobiographique

[PDF] un institut effectue un sondage pour connaitre

[PDF] marche aléatoire terminale s

[PDF] soustraction matrice

[PDF] matrice puissance 2

[PDF] matrice nulle

[PDF] tableau entrée sortie exercice corrigé

[PDF] question a poser a un auteur de livre

[PDF] matrice nilpotente exemple

[PDF] matrice nilpotente propriété

[PDF] on ne badine pas avec l'amour

[PDF] cours graphes tes pdf

DERNIÈRE IMPRESSION LE12 mai 2015 à 14:54

Pertinence d"une page web

PAUL MILAN

Lycée d"Adultes de la ville de Paris :

http://www.lyceedadultes.fr/index.html

1 Que fait un moteur de recherche

Contrairement à une base de données structurée dont on peut facilement extraire des informations, le Web est une immense collection de textes de toutes natures qui évolue en permanence. Le moteur de recherche copie préalablement les pages sur des milliers d"ordina- teurs (60 000 pour Google!) et les trie par ordre alphabétique (selon les mots clé). Lors d"une requête relative à un mot clé, le moteur répond par la liste des pages contenant ce mot clé. Mais il y en a des dizaines de milliers en général. C"est ici qu"intervient l"innovation de Larry Page (fondateur avec Serguei Brin de Google) connue sous le nom dePagerank(to rank : classer). L"idée est de répondre à la requête en citant les pages par ordre de pertinence. Le Web a une structure de graphe due au fait que les pages se citent mutuelle- ment. C"est le principe de l"hypertexte : les pages se citent mutuellement par les fameux liens. Essayons de déterminer la pertinence d"une page web.

2 Un exemple

Soit le graphe suivant qui relie 4 pages

Web : 3 214

3 Mesurer la pertinence

3.1 Comptage pondéré

Il est clair qu"une page importante reçoit de nombreux liens. Cependant certaines pages émettent beaucoup de liens ce qui d"une certaine façon diminue leur poids. On pondère alors les liens qui relient les pages. La page 1 pointe vers 3 pages (2,3,4). Chacun de ces liens sera alors pondéré du coefficient 1 3

PAUL MILAN1TERMINALE S SPÉ

On peut associer à ce graphe la matrice

M= (aij)oùaijreprésente le coefficient

de la pageiqui pointe surj.

M=((((((((((

313131

201
20 0 0 0 1 1 201

20))))))))))

3 214
1 3 0,51 0,5 1 3 0,5 0,5 1 3 On peut alors définir la mesure de pertinenceμide la pageien comptant le nombre de liens pondérés qui pointent vers elle : i=∑ ja ji

3,μ3=43,μ4=43Les pages 3 et 4 sont donc les plus pertinentes.On pose la matrice ligne des pertinencesPet la matrice ligneJavec que des 1, on

a alors :

P=J×M

Remarque :Mais ce comptage est très facile à manipuler, puisqu"il suffit de créer des "fausses" pages pointant vers la pageipour en augmenter l"importance.

3.2 Comptage récursif

La pertinence d"une page est renforcée par la pertinence des pages qui pointent vers elle et elle est diminuée par la dispersion éventuelle des liens issus de ces dernières. En reprenant la pondération précédente, on peut définir la pertinence d"une page ide la façon suivante : i=∑ ja ji×μj Le risque de manipulation consistant en l"ajout de pages vides de sens est alors ici annulé puisqu"une telle page recevrait une mesure de pertinence nulle.

On a alors :P=P×M

On obtient le système suivant :

1=1

2μ2+12μ3

2=1

3μ1

3=1

3μ1+12μ2+12μ4

4=1

3μ1+μ3D"où les pertinences en fonction deμ1:

2=1

3μ1,μ3=43μ1,μ4=53μ1

Si on fixe la somme des pertinences à 1,

on obtient alors : 1=3

13,μ1=113,μ3=413,μ4=513

Remarque :La page 4 est alors la plus

pertinente.

PAUL MILAN2TERMINALE S SPÉ

4. PERTINENCE ET PROBABILITÉ

4 Pertinence et probabilité

Dans la matrice1M, on peut remarquer que la somme des coefficientsaijsur une ligne est égal à 1. Ces coefficientsaijpeuvent donc s"interpréter comme la probabilité, pour un "sur- feur" qui se trouverait à la pageide suivre le lien qui l"amènerait à la pagej. On suppose que le surfeur est sur une page donné à l"instant 0 et qu"il évolue de page en page en cliquant sur les liens au hasard. En notantUnla matrice ligne admettant pour coefficient à la colonneila probabi- lité que le surfeur se trouve à la pageiau bout denclics, les relations précédentes peuvent se traduire par la relation matricielle suivante : U n+1=Un×M?Un=U0×(M)n On peut montrer que cette suite(Un)converge vers?3

13;113;413;513?

et ce quelque soit l"état d"origine. On a donc bien une probabilité plus grandede se retrouver en page 4 après un grand nombre de clics! Remarque :Toutefois, il peut arriver que certaines pages ne comportent aucun lien vers d"autres pages; dans ce cas, lorsque le surfeur aléatoirearrive sur l"une d"entre elles, il lui est impossible de la quitter.

5 Saut aléatoire

C"est pourquoi Google utilise une astuce : à chaque page, avec une probabilitép le surfeur peut renoncer à suivre les liens et abandonner sa page actuelle pour une autre page choisie au hasard parmi lesnpages du Web.

On obtient alors une nouvelle matriceM?carac-

térisant le nouveau système. M ?=p

4J+ (1-p)M

Si on prendp=1

5, on obtient :

M ?=1

20J+45M=(((((((((((((1

20196019601960

20120920120

201201201720

20120920120)))))))))))))On démontre que les puissances de la matrice

M ?conduisent à une matrice limite et à des in- dices de pertinence qui sont : 135

572,3232860,171572,10072860

à comparer aux indices trouvés précédemment

μ1μ2μ3μ4

Sans saut aléatoire0,230,080,310,38

Avec saut aléatoire0,240,110,300,35

Danslesdeuxcaslapage4demeurelaplusper-

tinente Pour résumer, plus vous aurez de liens de qualité vers votre site, plus votrePage- Ranksera élevé, plus vos chances d"apparaître en bonne position dans le moteur de recherche Google seront accrues.

1. Cette matrice est une matrice de transition d"une chaîne de Markov. Une chaîne de Markov

est un processus aléatoire portant sur un nombre fini d"états, avec des probabilités de transition

sans mémoire

PAUL MILAN3TERMINALE S SPÉ

quotesdbs_dbs8.pdfusesText_14

[PDF] [PDF] Pertinence dune page web - Lycée dAdultes

[PDF] Pertinence dune page web - Lycée dAdultes