Algoritmi di Ranking per i Motori di Ricerca

Gianna M. Del CorsoDipartimento InformaticaUniversità 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: Aprile 2009

Aprile 2009

[Market Share]

QuickTime™ and a decompressor

are needed to see this picture.

Trend

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

D1D3

D4D5

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 autorityhi 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 autoritydeve 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(i−1)

a(i ) =GTh(i )

HITS

h(i ) =Ga(i−1)

a(i ) =GTh(i )h1

h2

h3

p

ap=h1+h2+h3q3

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(i−1)

a(i ) =GTGa(i−1)

⎫⎬⎭⇒

h* autovettore principale di GGT

a* autovettore principale di GTG

Teorema di Perron-Frobenius

A>=0 e irriducibile

• (A)>0, esiste = (A) con molteplicita’ algebrica 1•Esiste x>0, autovettore corrispondente a (A)

A>=0 e riducibile

(A)>=0, esiste = (A) con molteplicita’ algebrica 1•Esiste x>=0, autovettore corrispondente a (A)

HITS

AuthorityHubness

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Authority and hubness weights

Riassumendo HITSA 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

AuthorityHubness

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 32. doc13. 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 paginauna 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à

pij = 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 00 0 0 0 00 1 / 2 0 0 1 / 2

1 / 2 0 1 / 2 0 01 / 3 1 / 3 0 1 / 3 0

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

D1D3

D4D5

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 ) =PTz(k−1)

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 01 / 5 1 / 5 1 / 5 1 / 5 1 / 50 1 / 2 0 0 1 / 2

1 / 2 0 1 / 2 0 01 / 3 1 / 3 0 1 / 3 0

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

P =P +dvT

Google’s PageRank

Cicli. Si forza l’irriducibilià mettendo degli archi artificiali che con “bassa probabilità” saltano da ogni nodo verso ogni altro

D1D3

D4D5

D2

c probabilità di saltare a caso

c

c

P =P +dvT

P =(1−c)P + cevTc

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 01 / 5 1 / 5 1 / 5 1 / 5 1 / 50 1 / 2 0 0 1 / 2

1 / 2 0 1 / 2 0 01 / 3 1 / 3 0 1 / 3 0

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

+ c

1 / 5 1 / 5 1 / 5 1 / 5 1 / 51 / 5 1 / 5 1 / 5 1 / 5 1 / 51 / 5 1 / 5 1 / 5 1 / 5 1 / 51 / 5 1 / 5 1 / 5 1 / 5 1 / 51 / 5 1 / 5 1 / 5 1 / 5 1 / 5

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

P =

0 0 1 0 01 / 5 1 / 5 1 / 5 1 / 5 1 / 50 1 / 2 0 0 1 / 2

1 / 2 0 1 / 2 0 01 / 3 1 / 3 0 1 / 3 0

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

P =

0 0 1 0 00 0 0 0 00 1 / 2 0 0 2 / 2

1 / 2 0 1 / 2 0 01 / 3 1 / 3 0 1 / 3 0

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

è stocastica ed irriducibile!P

Possiamo applicare Perron-Frobenius

Personalizzazione di PageRank

Biased Rank

ab

[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?”

Grazie!