Promotion Ranking

Défault des Méthodes de ranking

• Les pages nouvellement créées ne sont pas tout de suite référencées pas les méthodes de ranking traditionnelles.

• Exemple : PageRank, HITS

Pourquoi

• Les nouvelles page font partie du « IN » dans le WebGraph. Elles ne possèdent pas de liens qui les référencent.

• Il est donc très difficiles de connaître leurs « qualité ».

• Il faut attendre qu’elles fassent partie du « core » du « WebGraph ». Ceci demande un facteur temps important.

Objectif

• Trouver un moyen d’inclure les nouvelles pages (de qualité) dans les résultats des moteurs de recherches avant qu’elles ne fassent parties du « core » du « WebGraph »

Idée : Rank Promotion

• Promouvoir les pages lointaines de la liste des résultats d’un moteur de recherche

• Pour cela on les fait artificiellement grimper au sommet de la liste.

Résultat 11

Résultat 22

Résultat 33

Résultat 44

Résultat 55

Résultat 66

Résultat 500500

Expérience

• Site Internet dans lequel se trouve plusieurs milliers de pages au contenu amusant ou comique.

• Presque un millier de « surfeurs », qui n’avaient aucune connaissance préalable du sujet d’expérience.

Expérience : pages du site

• Les pages ont été créées dynamiquement à partir d’une base de données contenant des blagues.

• La qualité des pages est le degré de « funniness ».• Des pages contenant des citations ont été ajoutées

pour que l’ensemble des pages du site ait une distribution par PageRank normale. C’est à dire, que la distribution ressemble à celle de n’importe quel autre site Internet.

Expérience : la page principale du site

• La homepage du site présente les blagues et citations à la manière d’une moteur de recherche, par groupe de dix et en ordre descendant de « funniness ».

• Le niveau de « funniness » est établi par les utilisateurs. Ils ont le choix de cliquer sur les boutons « drôle », « neutre » et « pas drôle ».

• Pour limiter la fraude, une fois que l’utilisateur a cliqué sur un bouton, ils disparaissent.

Expérience : les utilisateurs

• La publicité faite pour le site a attiré un total de 962 visiteurs pendant 45 jours.

• Chaque surfeur qui visite le site pour la première fois se voit attribué un numéro de groupe: 1 ou 2.

• Pour le 1er groupe, les blagues sont présentées en ordre descendant de popularité.

• Pour le 2ième groupe, les blagues sont également présentées en ordre descendant de popularité. Mais les pages qui n’ont pas été évaluées sont insérées dans la page principale par Rank Promotion.

Expérience : rotation du contenu

• Pour chaque visiteur, le maximum de pages accessibles est fixé à mille.

• La durée de vie des page est fixée au hasard de 1 à 30 jours.

• Pour simuler un état stationnaire dans lequel chaque page a une durée de vie réelle de 30 jours, chaque page qui disparaît est remplacée par une page de même qualité avec une durée de vie fixée à 30 jours et une popularité de zéro.

Evaluation

• Le site est capable de « monitorer » l’activité de 10% des utilisateurs.

• Ceci permet d’utiliser deux indices pour évaluer les effets du promotion ranking.

• TBP => Time To Become Popular

• QPC => Quality Per Click

TBP

• Temps que met une page de bonne qualité à devenir populaire dans un moteur de recherche.

• C’est à dire, qu’elle va figurer au début de la liste des résultats pour un mot clef donné.

QPC

• Mesure la qualité moyenne des pages visionnées par les « surfeurs » sur une grande période de temps.

t

tl Pp

t

tl Pp

t tlpVu

pQtlpVuQPC

0

0

)),((

))(),((lim

t

tl Pp

t

tl Pp

t tlpVu

pQtlpVuQPC

0

0

)),((

))(),((lim

Qualité intrinsèquede la page « p »

Nombre de visiteursde la page « p » pendant

sa durée de vie « tl »Somme de touteles pages du site

Sur une durée infinie

Normalisation

QPC

Evaluation : Constats

• Le but du du Promotion Ranking est de diminuer TBP et d’augmenter QPC.

• Plus une page est référencée tôt dans un moteur de recherche, plus sa popularité va devenir importante.

• Pour promouvoir une nouvelle page, il faut donc l’insérer au début de la liste des résultats du moteur de recherche.

Promotion Ranking : Méthodes

• Pour le promotion ranking, il existe plusieurs méthodes.

• Ici, il y en a deux :

• 1) Randomized Rank Promotion

• 2) Selective Randomized Rank Promotion.

Randomized Rank Promotion

• Instanciation de 3 listes : L, Ld, et Lp.

• Ld contient l’ensemble des pages de résultats suite à une requête lancée dans un moteur de recherche.

• Lp contient la liste des pages à promouvoir.

• L est la liste finale, présentée à l’utilisateur.

Randomized Rank Promotion suite

• Les k-1 premiers éléments de Ld sont insérés dans L.

• Les k+i éléments de L sont pris soit de Ld, soit de Lp.

• Ce choix dépend de la valeur probabiliste d’une variable aléatoire r.

• Exemple : la variable r peut être le résultat du jet d’une pièce de monnaie (pile ou face).

Selective Randomized Rank Promotion

• Différences avec le modèle précédant :1) Toutes les pages n’ont pas les mêmes chances d’être

choisies. Seul le pages avec une « awareness » de 0 sont promues.

• Méthode :1) Utiliser les informations supplémentaires fournies par

les visiteurs « monitorés » du moteur de recherche.2) Utiliser la relation entre la popularité d’une page et son

nombre attendu de visiteurs.

Selective Randomized Rank Promotion (suite)

• La relation popularité par rapport au nombre de visiteur s’exprime par :

• F2 = nombre de visiteurs attendus.

• F1 = popularité de la page.

xFFxF 12

Selective Randomized Rank Promotion (suite 1)

• F2 est déduite empiriquement par les résultats fournis par le moteur de recherche AltaVista (loi de puissance).

xxF2/3

2

Teta = cte de normalisation

n

i iv

1

2/3 v = nombre de visteurs par unité de temps

Selective Randomized Rank Promotion (suite 2 )

• La popularité F1(x) d’une page s’exprime par la relation :

Pp

m

pQxmi

pQmifxF

/1

1 1

m = nombre d’utilisateurs « monitorés »

Q(p) = Qualité intrinsèque de la page

F1 = 1 + toutes les autres pages dont la popularité surpasse x.

« awareness »

Selective Randomized Rank Promotion (suite 3)

• Formule finale:

z

rkxFrxF

xF

xF,

11min 1

1

1

'1

Si F1(x) < k

Autrement

z = pages avec une « awareness » de zéro

F1 = formule précédente

Selective Randomized Rank Promotion (suite 4 )

• F1 étant une formule approximative :1) On ignore les effets de valeurs proches en popularité. 2) On oublie de compter une page.

• On combine F1 avec la formule suivante, par « curve fitting » (simulation par régression non-linéaire):

xxF logloglog 2

x = popularité de la page

Selective Randomized Rank Promotion (suite 5)

• Question :

• Quelles valeurs faut-il donner à k (point d’entrée dans la liste), r (degré de hasard) et Wp (pages à promouvoir).

• Réponse par simulation

Effet sur TBP

-no promotion

- uniform promotion

- selective promotion

k=1 and r=0.2

Ajustement de k et r

Résultats

0

0.2

0.4

0.6

0.8

1

1E+03 1E+04 1E+05 1E+06

# pages

0

0.2

0.4

0.6

0.8

1

1E+02 1E+04 1E+06

# users

0

0.2

0.4

0.6

0.8

1

0.75 2.25 3.75 5.25

page lifetime

qu

alit

y-p

er-c

lick

0

0.2

0.4

0.6

0.8

1

1E+01 1E+04 1E+07

visit rate

qu

alit

y-p

er-c

lick

(par simulation)

Résultat final (réel)