Algoritmi di Ranking per i Motori di Ricerca
Gianna M. Del Corso
Dipartimento Informatica Università di Pisa
Sommario
Statistiche
Algoritmi di Ranking
HITS
PageRank di Google
Approfondimenti
Statistiche
Statistiche
Dimensione
Miliardi di pagine
5-10K per pagina => decine di terabytes
La dimensione raddoppia ogni 2 anni
Cambiamenti
23% cambia ogni giorno
Tempo medio di durata circa 10 giorni
[Nielsen//NetRatings]
Percentuali: Giugno 2006
Giugno 2006
1.5 M. utenti
[comScore Media Matrix]
Trend
[comStore Media Matrix]
Andamento nell’ultimo anno
[google-watch.org]
I Numeri di
[Google’s IPO Sec Filing]
Revenue, Expenses &
Profits
0 2.000 4.000 6.000 8.000 10.000 12.000
Rev. 439,508 1.465,93 3.189,23 6.138,56 10.604,92 Exp. 253,042 1.123,47 2.549,03 4.121,28 7.054,92 Pro. 99,656 105,648 399,119 1.465,40 3.077,45
2002 2003 2004 2005 2006
Revenue Sources
6% 3% 1% 1% 1%
94% 97% 99% 99% 99%
0%
20%
40%
60%
80%
100%
120%
2002 2003 2004 2005 2006
Other Revenue Ad. Revenue
Motori di Ricerca
I motori di ricerca
Lo scopo (o meglio, il sogno) dei motori di ricerca è quello di poter catalogare tutto ciò che viene pubblicato sul web
Si vuole poter accedere al Web tramite parole chiave (query)
I primi risultati forniti “dovrebbero” essere i più rilevanti
Struttura dei Motori di Ricerca
Spider Control Spiders
Ranking Indexer
Page Repository
Query Engine Collection
Analysis
Text Structure Utility
Queries Results
Indexes
Web Ranking
… In principio …
A metà degli anni ‘90
L’ordinamento delle pagine restituite in seguito ad una query
dipendeva dal “proprietario” della pagina - Keywords - frequenza di un termine
Problema: SPAM
Nel 1998
Due idee simili:
HITS (John Klimberg)
PageRank (S. Brin & L. Page)
L’importanza di una pagina non dipende da colui che “possiede” e scrive la pagina
Idea di base
L’autore della pagina p da’ un voto alla pagina q
p q
Idea: Se una pagina ha un contenuto interessante ci saranno molte pagine che la riferiscono.
Si guarda la struttura dei link
Grafo Web
Il Web è visto come un grafo:
Ogni pagina web è un NODO
Ogni link è un ARCO
D1 D3
D5 D4 D2
G=
D1 D2 D3 D4
D1 D2 D3 D4
D5
D5
0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0
Ranking
L’importanza delle pagine è determinata dalla struttura del grafo web
Questi algoritmi non utilizzano informazioni sul contenuto delle pagine
È il grafo stesso a dirci se la pagina è interessante
HITS (Kleimberg)
Ogni pagina ha due punteggi:
ai punteggio autority hi punteggio hub
Una pagina è una buona “autority” se è riferita da buoni hub.
Una pagina è un buon “hub” se contemporaneamente riferisce buone autority su uno stesso argomento.
Se la pagina p punta a pagine con un alto valore come autority deve ricevere un alto punteggio come hub
Se p è riferita da molte pagine che hanno un alto punteggio come hub, allora deve ricevere un alto punteggio come autority
h(i) Ga(i1) a(i) GTh(i)
HITS
h
(i ) Ga
(i1)a
(i ) G
Th
(i ) h1h2
h3
p
ap=h1+h2+h3
q3 q1
q2 a2
a1
q
hq=a1+a2
p1
p2
Proprietà delle matrici
GTG e GGT sono matrici non negative
GTG e GGT sono semidefinite positive
Hanno autovalori reali e non negativi
Per Perron-Frobenius
L’autovettore associato all’autovalore massimo è positivo
h(i ) GGTh(i1) a(i ) GTGa(i1)
h* autovettore principale di GGT a* autovettore principale di GTG
HITS
Authority Hubness
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Authority and hubness weights
Riassumendo HITS
A tempo di query
Si trovano le pagine pertinenti
Si costruisce il grafo a partire da queste pagine
Si calcola l’autovettore dominante della matrice GTG
Si ordinano le pagine secondo l’ordinamento indotto dall’autovettore principale
HITS
Authority Hubness
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Authority and hubness weights
La pagina 1 e la pagina 10 sono le più autorevoli Sono riferite da buone pagine hub: la 2 e la 12
PageRank (Google)
Ranking “statico”- PageRank
A tempo di query si trovano le pagine pertinenti la query
L’ordinamento delle pagine restituite si basa sul PageRank delle pagine che era stato
precomputato
PageRank
casa
doc1 doc2 doc3
doc1
doc2 doc3 PR
casa
1. doc 3 2. doc1 3. doc 2
PageRank
Una pagina èUna pagina importante se importante se è votata da pagine importanti votata da pagine importanti
Il voto si esprime “linkando” Il voto si esprime “linkando”
una pagina una pagina
A differenza di HITS non ho pagine hub!
PageRank di Google
Random surfer model: Il navigatore della rete salta da una pagina ad una ad essa collegata con probabilità
p
ij 1outdeg(i)
0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0
P
0 0 1 0 0
0 0 0 0 0
0 1 / 2 0 0 1 / 2 1 / 2 0 1 / 2 0 0 1 / 3 1 / 3 0 1 / 3 0
D1 D3
D5 D4 D2
o Una pagina trasmette la propria importanza suddivisa in parti ugiuali tra tutte le pagine a cui essa punta
o L’importanza di una pagina è la somma delle importanze delle pagine che ad essa puntano
PageRank di Google
A partire da un vettore z(0)
z
(k) P
Tz
(k1) Equivale al calcolo dell’autovettore relativo all’autovalore 1 di PT
z1
z2
q
zq=1/oudeg(p1)z1+1/oudeg(p2)z2
p1
p2
PageRank
Due problemi:
Nodi “Dangling”
P può non essere stocastica
P non ha necessariamente l’autovalore 1
Cicli
La matrice è riducibile
L’autovalore massimo può non essere unico
0 0 1 0 0
0 0 0 0 0
0 1/ 2 0 0 1/ 2 1/ 2 0 1/ 2 0 0 1/ 3 1/ 3 0 1/ 3 0
PageRank
Dangling nodes
di =1 se la pagina i è “dangling”
v=(1/n, 1/n, …1/n)T
P
0 0 1 0 0
1 / 5 1 / 5 1 / 5 1 / 5 1 / 5 0 1 / 2 0 0 1 / 2 1 / 2 0 1 / 2 0 0 1 / 3 1 / 3 0 1 / 3 0
P P dv
TGoogle’s PageRank
Cicli. Si forza l’irriducibilià mettendo degli archi
artificiali che con “bassa probabilità” saltano da ogni nodo verso ogni altro
D1 D3
D5 D4 D2
c probabilità di saltare a caso
c
c
P P dv
TP (1 c)P c ev
Tc
e=(1,1, …, 1)T;
v=(1/n, 1/n, …, 1/n)T
c
c=0.15
PageRank
P (1 c)
0 0 1 0 0
1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 0 1/ 2 0 0 1/ 2 1/ 2 0 1/ 2 0 0 1/ 3 1/ 3 0 1/ 3 0
c
1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5 1/ 5
P
0 0 1 0 0
1 / 5 1 / 5 1 / 5 1 / 5 1 / 5 0 1 / 2 0 0 1 / 2 1 / 2 0 1 / 2 0 0 1 / 3 1 / 3 0 1 / 3 0
P
0 0 1 0 0
0 0 0 0 0
0 1/ 2 0 0 2 / 2 1/ 2 0 1/ 2 0 0 1/ 3 1/ 3 0 1/ 3 0
è stocastica ed irriducibile!
P
Possiamo applicare Perron-Frobenius
Riassumendo …
Il calcolo di PageRank viene fatto su tutto il grafo Web
Si calcola l’autoevettore relativo all’autovalore 1 della matrice
A tempo di query si prendono I documenti
pertinenti e si restituiscono in ordine di PageRank decrescente
P
Personalizzazione di PageRank
Biased Rank
a b
[Hawelivala 02]
Eurekester
Permette di creare e di entrare a far parte di “SearchGroups” per focalizzare la ricerca verso I propri interessi
Why we need a fast link- based rank?
“…The link structure of the Web is
significantly more dynamic than the contents on the Web. Every week, about 25% new
links are created. After a year, about 80% of the links on the Web are replaced with new ones. This result indicates that search
engines need to update link-based ranking metrics very often…”
[ Cho et al., 04 ]
Interessi di Ricerca
La matrice associata al grafo web è la più grande matrice esistente
Gli algoritmi di Ranking devono essere in grado di gestire la mole dei dati
Devono essere veloci… Google impiega circa un mese per aggiornare completamente il
vettore di PageRank.
Tecniche per aggiornare il vettore senza ricalcolarlo del tutto
Approfondimenti
Who powers Whom
Spam Farm: Insieme di pagine web costruito per far crescere il PageRank di una pagina t
Spamming di PageRank
[Garcia-Molina et al., 04]
SEO: Search Engines Optimizer
Consulenti che suggeriscono come far crescere il volume dei visitatori di siti web cercando di costruire dei siti che siano più visibili
“Google Bombing”
“Google Bombing”
Alcuni esempi popolari :
weapons of mass destruction - messaggio di errore tipo IE “weapons of mass destruction cannot be found”.
great president - biografia di George W. Bush.
out of touch executives – Pagina di informazione sull’esecutivo di Google
Waffle – sito di John Kerry (candidato democratico avversario di G.W.Bush)
25 Gennaio 2007 è stato annunciato che Goggle ha a disposizione un nuovo algoritmo resistente al Google bombing.
[ wikipedia ]
Risultati curiosi
Jew - uno dei primi siti che vengono restituiti è un sito antisemita. C’è poi un messaggio di
“scuse” da parte di Google
Madonna - sito ufficiale di Madonna,… si inferisce la sua esistenza dal fatto che ha molti link che la riferiscono
Coffee - il primo sito è una pagina di
Starbucks …ma che non contiene mai la parola coffee…
Pubblicità
Per fare pubblicità su un MdR si può
partecipare ad un ASTA per aggiudicarsi una keyword alla quale legare il proprio
messaggio pubblicitario
Su Google c’è anche un servizio “pay-per- click” nel quale il venditore paga solo se l’utente visita il suo sito
Comparing Ranks (Online
Demo)
Finally…the perfect search engine?
Sergei Brin: “It would be the mind of God. Larry says it would know exactly what you want and give you back exactly
what you need.”
Chackabarti: “The web grew exponentially from almost zero to 800 million pages between 1991 and 1999. In comparison, it took 3.5 million years for the human brain to grow linearly from 400 to 1400 cubic centimeters. How do we work with the web without getting overwhelmed? We look for
relevance and quality. Can we design programs to recognize these properties?”