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
Andamento nell’ultimo anno
[comStore Media Matrix]
[google-watch.org]
I Numeri di
Revenue Sources
Revenue, Expenses &
Profits
120%
12.000
100%
10.000
94%
97%
99%
99%
99%
80%
8.000
6.000
Other Revenue
60%
4.000
Ad. Revenue
40%
2.000
0
20%
2002
2003
2004
2005
2006
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
[Google’s IPO Sec Filing]
0%
6%
2002
3%
2003
1%
2004
1%
2005
1%
2006
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
Page Repository
Collection
Indexer
Analysis
Queries
Query Engine
Spiders
Text
Spider Control
Structure
Indexes
Utility
Results
Ranking
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
Si guarda la struttura dei link
p

q
L’autore della pagina p da’ un voto alla
pagina q
Idea: Se una pagina ha un contenuto interessante ci
saranno molte pagine che la riferiscono.
Grafo Web
Il Web è visto come un grafo:
 Ogni pagina web è un NODO
 Ogni link è un ARCO
D1
D2
D1
D3
D1
D2
G= D3
D4
D5
D4
D5
0
0

0

1
 1
D2
D3
D4
D5
0 1 0 0
0 0 0 0

1 0 0 1

0 1 0 0
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
hub
(i)
(icome
1)
h  Ga
(i)
Se p è riferita da molteapagine
 G Tche
h(i )hanno un alto punteggio
come hub, allora deve ricevere un alto punteggio come autority
HITS
h
(i )
a
(i )
 Ga
(i 1)
G h
T
(i )
p
h1 q1
a1
1
q
h2 q
hq=a
2 1+a2
h3 q3
pp
a2
2
ap=h1+h2+h3
Proprietà delle matrici



GTG e GGT sono matrici non negative
GTG e GGT sono semidefinite positive
Hanno autovalori reali e non negativi
h(i )  GGT h(i 1)  h* autovettore principale di GGT
 *
(i )
T
(i 1) 
T
a  G Ga
a
autovettore
principale
di
G
G


Per Perron-Frobenius

L’autovettore associato all’autovalore massimo è positivo
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
PR
casa
doc3
doc1
doc2
doc3
casa
doc1
doc2
1. doc 3
2. doc1
3. doc 2
PageRank


Una pagina è importante se
è votata da pagine importanti
Il voto si esprime “linkando”
una pagina
A differenza di HITS non ho pagine hub!
PageRank di Google

o Una pagina trasmette la propria importanza suddivisa
Random
surfer model: Il navigatore della
in parti ugiuali tra tutte le pagine a cui essa punta
rete
salta da una pagina ad una ad essa collegata
ocon
L’importanza
di una pagina è la somma delle importanze
probabilità
delle pagine che ad essa puntano
pij  1 outdeg(i)
D2
D3
D1
D5
D4
0
0

0

1
 1
0 1 0 0
0 0 0 0

1 0 0 1  P 

0 1 0 0
1 0 1 0 
0
1
0
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 di Google

A partire da un vettore z(0)
z P z
(k)

T (k1)
p1
q
z1
Equivale al calcolo dell’autovettore relativo
p
T
z2
all’autovalorez =1/oudeg(p
1 di P )z +1/oudeg(p )z
2
q
1
1
2
2
PageRank

Due problemi:

0
1
0
0
0
0
1/ 2 0 0
0 1/ 2 0
1/ 3 0 1/ 3
Nodi “Dangling”



0
0

0

1/ 2
1/ 3
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/ 2 

0
0 
PageRank

Dangling nodes
P  P  dv
di =1 se la pagina i è “dangling”
v=(1/n, 1/n, …1/n)T
T
0
1
0
0 
 0
1 / 5 1 / 5 1 / 5 1 / 5 1 / 5 


0 1 / 2
P   0 1/ 2 0


1
/
2
0
1
/
2
0
0


1 / 3 1 / 3 0 1 / 3 0 
Google’s PageRank

Cicli. Si forza l’irriducibilià mettendo degli archi
artificiali che con “bassa probabilità” saltano da ogni
nodo verso ogni altro
c probabilità di saltare a caso
c
P  P  dv
D2
D3
c
D1
P  (1  c)P  c ev T
c
c
c=0.15
D5
T
D4
e=(1,1, …, 1)T;
v=(1/n, 1/n, …, 1/n)T
PageRank
0
0

P 0

1/ 2
1/ 3
0
1
0
0
0
0
1/ 2 0 0
0 1/ 2 0
1/ 3 0 1/ 3
0 
0 

2 / 2
P

0 
0 
0
1
0
0 
 0
1 / 5 1 / 5 1 / 5 1 / 5 1 / 5 


0 1 / 2
P   0 1/ 2 0
 ed irriducibile! 
è stocastica
0 
1 / 2 0 1 / 2 0
1 / 3 1 / 3 0 1 / 3 0 
Possiamo applicare Perron-Frobenius
 0 0 1 0 0  1 / 5
1 / 5 1 / 5 1 / 5 1 / 5 1 / 5  1 / 5

 
P  (1 c)  0 1 / 2 0 0 1 / 2   c 1 / 5

 
1
/
2
0
1
/
2
0
0

 1 / 5
1 / 3 1 / 3 0 1 / 3 0  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 
Riassumendo …



Il calcolo di PageRank viene fatto su tutto il grafo
Web
Si calcola l’autoevettore relativo all’autovalore 1
della matrice P
A tempo di query si prendono I documenti
pertinenti e si restituiscono in ordine di PageRank
decrescente
Personalizzazione di PageRank
Biased Rank
a
[Hawelivala 02]
b
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
Spamming di PageRank
Spam Farm: Insieme di pagine web costruito per far
crescere il PageRank di una pagina t
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
[Garcia-Molina et al., 04]
“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-perclick” 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?”
Grazie!