PageRank

Information Retrieval nel WebHITS

PageRank

PageRank

Simone Rutigliano

Corso di Laurea in Informatica Magistrale

3 dicembre 2014

Simone Rutigliano PageRank


PageRank

Outline

1 Information Retrieval nel Web

2 HITSCaratteristicheImplementazioneVantaggi e svantaggi

3 PageRankDefinizioneIdea di baseFunzionamentoImplementazioneEsempio



PageRank

Caratteristiche del Web

Struttura ad hyperlink

Frequenza elevata nell’aggiornamento e modifica deidocumenti web

Quantita elevata di documenti da considerare

Mancanza di revisione nei documenti

RidondanzaLink di bassa qualitaLink obsoleti



PageRank

IR nel Web . . .

Per garantire qualita ai documenti recuperati e necessariopuntare sull’accuratezza dei risultati incorporandocostantemente gli aggiornamenti

Immunita ai sistemi che falsano l’importanza dei documenti

Personalizzazione dei risultati in base alla profilazione utente



PageRank

. . . IR nel Web

La struttura a hyperlink fornisce informazioni extra per lacostruzione di un metodo di Web-IR

Tale struttura e utilizzata dai piu meccanismi di retrieval

HITS (Hypertext Inducer Topic Search, 1997)PageRank (1998)



PageRank

La struttura ad Hyperlink del Web . . .

Ciascuna pagina/documento del Web e rappresentato comeun nodo di un grafico molto grande

Gli archi diretti che connettono questi nodi rappresentano glihyperlink tra i diversi documenti

inlink: pagine che puntano verso uno specifico documento(link entranti)outlink: pagine collegate ad uno specifico documento (linkuscenti)



PageRank

. . . La struttura ad Hyperlink del Web

Entrambi i sistemi HITS e PageRank sono basati sui concetti diauthority e hub

Authority: documento con numerosi inlink

Hub: documento con diversi outlink

Ad ogni pagina viene assegnato un punteggio authority e hub

Auth Hub



PageRank

CaratteristicheImplementazioneVantaggi e svantaggi

HITS . . .

“Buoni hubs puntano a buone authority e buone authority sonopuntati da buoni hubs”

Indicato con E l’insieme di tutte le connessioni del grafo associatoal web

eij rappresenta la connessione tra il nodo i ed il nodo j

Considerata la pagina i-sima avremo

xi il suo punteggio di authorityyi il suo punteggio di hub



PageRank


. . . HITS . . .

HITS si basa sul raffinamento successivo dei punteggi xi e yi

L’importanza di una pagina come authority dipendedall’importanza dei suoi inlink

x(k)i =

∑j :eji∈E

y(k−1)j

L’importanza di una pagina come hub dipende dall’importanzadei suoi outlink

y(k)i =

∑j :eij∈E

x(k)j



PageRank


. . . HITS

Le precedenti equazioni si possono riscrivere in forma matricialeintroducendo la matrice di adiacenza L = [lij ] del grafo del webdove

lij =

{1 se esiste connessione tra i nodi i e j0 altrimenti

Le colonne di L sono i documenti puntati dalla genericapagina (outlink)

Le righe di L sono i documenti che puntano la generica pagina(inlink)



PageRank


HITS - Implementazione

Data una query q :

Costruire il grafo di vicinanza (neighborhood graph) Nrelativo alla query q

Calcolare i punteggi di authority e hub del grafo N attraversol’ausilio della matrice di adiacenza

Presentare il rank dei documenti authority e hub recuperati



PageRank


HITS - Vantaggi e Svantaggi

Vantaggi

doppio ranking (authority e hub)

uso di matrici di dimensioni ridotte

Svantaggi

Dipendenza dalla query per la costruzione della neighborhoodgraph

Punteggi di hub ed authority alterabili inserendo inlink eoutlink al documento stesso

Possibile indirizzamento a pagine off-topic



PageRank

DefinizioneIdea di baseFunzionamentoImplementazioneEsempio

PageRank - Definizione

Formulato nel 1998 da Larry Page e Sergey Brin

Algoritmo di ricerca di Google : “The heart of our software isPageRank TM. . . it provides the basis for all of our web searchtools.”

Supera gli svantaggi di HITS



PageRank


PageRank - Idea di base

Pesatura dei link in base all’importanza del sito da cui proviene

L’importanza di un link da una qualunque sorgente dovrebbeessere attenuato dal numero dei siti che la sorgente vota



PageRank


PageRank - Formalismo

Indicata con P una generica pagina, il suo punteggio sara

r(P) =∑Q∈BP

r(Q)

|Q|

doveBP = { insieme di tutte le pagine puntanti a P}|Q| = numero degli outlink di Q



PageRank


Calcolo punteggio PageRank . . .

Se abbiamo n pagine P1,P2, . . . ,Pn ed assegniamo a ciascunapagina un arbitrario punteggio iniziale r0(Pi ) = 1

n

Il punteggio r(P) puo essere calcolato mediante la seguenteiterazione:

rj(Pi ) =∑

Q∈BPi

rj−1(Q)

|Q|j = 1, 2, 3, . . .



PageRank


. . . calcolo punteggio PageRank . . .

Ponendo: πᵀj = (rj(P1), rj(P2), . . . , rj(Pn))

Definiamo la matrice di Google per righe P tale che:

pij =

{ 1Pi

se Pi si connette con la pagina Pj

0 altrimenti

La precedente iterazione si puo riscrivere come:

πᵀj = πᵀj−1P



PageRank


. . . calcolo punteggio PageRank

Se il limite esiste, il vettore PageRank e definito

πᵀ = limj→∞

πᵀj

la i-sima componente del vettore PageRank e ilpunteggio(pagerank) della pagina Pi

Per assicurare la convergenza del processo iterativo la matriceP deve essere modificata



PageRank


Esempio di graph web

1 2

3

54

6

Matrice Google per righe P

P =

0 12

12 0 0 0

12 0 1

2 0 0 0

0 12 0 1

2 0 0

0 0 0 0 12

12

0 0 12

12 0 0

0 0 0 0 0 1



PageRank


Matrice Google per righe

La matrice di Google per righe P e

non-negativasomma degli elementi sulle righe pari a zero1 o uno

Se la matrice P ha tutte le righe con somma pari a uno allorasi parla di matrice stocastica:

autovalore dominante uguale a 1iterazione PageRank converge all’autovettore sinistronormalizzato πᵀ = πᵀP t.c. πᵀ1 = 1

1nodi danglingSimone Rutigliano PageRank


PageRank


Esempio nodo dangling

1 2

3

54

6

P =

0 12

12 0 0 0

12 0 1

2 0 0 0

0 12 0 1

2 0 0

0 0 0 0 12

12

0 0 12

12 0 0

0 0 0 0 0 0

sIl nodo 6 e un nodo dangling in quando non ha outlink



PageRank


Trasformazione Matrice di Google per righe . . .

Stocastica

Sostituire ad ogni riga nulla il vettore 1ᵀ

n

La nuova matrice stocastica si indica con P

Irriducibile

Aggiungere una matrice di perturbazione E = 11ᵀ

n

La nuova matrice sara uguale a

¯P = dP + (1− d)E d ∈ [0, 1]



PageRank


. . . Trasformazione Matrice di Google per righe

La matrice di Google attualmente utilizzata e ottenutaconsiderando la matrice di perturbazione E = 1vᵀ dove vᵀ e unvettore di personalizzazione dell’utente

¯P = dP + (1− d)1vᵀ d ∈ [0, 1]



PageRank


Damping factor d

Fattore il cui valore e stabilito da Google

Nella documentazione originale fornita dal Searcher il dampingfactor e pari a 0,85 (puo subire aggiustamenti a discrezione diGoogle)

Attraverso il damping factor, Google puo determinare il valorepercentuale di PageRank che transita da una pagina all’altra estabilire un valore minimo di PageRank attribuito ad ognunadelle pagine presenti nei suoi archivi



PageRank


Magic value d = 0.85

“the smart guys at Google use 0.85 ”

Funziona euristicamente bene

Gli algoritmi iterativi che approssimano il PageRankconvergono velocemente per d = 0.85

valori piu grandi richiederebbero piu iterazioni



PageRank


Energy Balance . . .

Dato un grafo GI , l’energia del grafo EI sara data dallasomma di tutti i PageRank delle pagine contenute nel grafo

EI =∑p∈I

xiᵀ

L’energia del grafo GI corrisponde al livello di authority delgrafo stesso



PageRank


. . . Energy Balance . . .

L’energia totale del grafo GI sara data dalla somma delle quattrocomponenti

EI = |I |+ EIin − EI

out − EIdp

|I | denota la cardinalita di pagine contenute in GI

EIin indica l’energia entrante nel grafo

EIout indica l’energia uscente dal grafo

EIdp indica l’energia persa dai nodi dangling



PageRank


. . . Energy Balance

Nel dettaglio, per calcolare le diverse energie le formule daapplicare saranno

E inI = d

1−d∑

i∈in(I ) fixᵀi

E outI = d

1−d∑

i∈out(I ) (1− fi )xᵀi

EdpI = d

1−d∑

i∈dp(I ) xᵀi

Dove

fi =link di i puntanti a pagine presenti in GI

|link uscenti da i |



PageRank


Energy Balance - Proprieta

Nel caso ottimale quindi, avremo che l’energia EI del grafo GI sara

EI ≤ |I |+ E inI

Piccoli grafi con pochi referenti non possono avere pagine conalti score

Robustezza della misura di authority



PageRank


Implementazione di PageRank

Data una query q

1 Determinare l’insieme di rilevanza della query creando ilsottoinsieme di pagine contenenti i termini della query(indicizzazione inversa)

2 Applicare il PageRank all’insieme di rilevanza di q per ottenereil rank delle pagine considerate (Ogni documento ha unpunteggio PageRank indipendente dalla query)



PageRank


Calcolo del vettore PageRank πᵀ relativo a ¯P

1 Specificare il parametro d

2 Porre πᵀ0 = 1ᵀ

n

3 Fissata la threshold, iterare fino alla convergenza l’equazione

πᵀk+1 = dπᵀk P + (1− d)vᵀ



PageRank


Esempio . . .

Consideriamo l’insieme di rilevanza composto da sei pagine webaventi la seguente struttura ad hyperlink

1 2

3

56

4



PageRank


. . . Esempio . . .

La matrice di Google per righe corrispondente al grafo sara laseguente

P =

0 12

12 0 0 0

0 0 0 0 0 013

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0



PageRank


. . . Esempio . . .

Considerato che il nodo 2 e un nodo dangling allora sara necessariotrasformarla in matrice stocastica

1 2

3

56

4

P =

0 12

12 0 0 0

16

16

16

16

16

16

13

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0

s



PageRank


. . . Esempio . . .

La matrice stocastica ottenuta e una matrice riducibile

P =

0 12

12 0 0 0

16

16

16

16

16

16

13

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0



PageRank


. . . Esempio . . .

Per ottenere una matrice irriducibile settiamo il parametrod = 0.85 da applicare alla formula 2

¯P = 0.85 ∗ P +0.15 ∗ 11ᵀ

6

2 ¯P = dP + (1−d)11ᵀ

n



PageRank


. . . Esempio . . .

6 5

4

2

3

22

2

1

1

11

1 0.85 · 0 + 0.15 · 1/62 0.85 · 1/2 + 0.15 · 1/63 0.85 · 1 + 0.15 · 1/6

0.85 ∗

. . .

......

.... . . 0 1

212

. . . 12 0 1

2

. . . 1 0 0

+ 0.15 ∗

. . .

......

.... . . 1

616

16

. . . 16

16

16

. . . 16

16

16



PageRank


. . . Esempio

Il vettore di PageRank associato alla precedente matrice sara

πᵀ = (0.3721 0.05396 0.0415 0.375 0.206 0.286)

PageRank indipendente dalla query



PageRank


Esempio di raccomandazione . . .

Data una query contenente i termini t1 e t2

Inverted term-document associato sara

t1 −→ doc1, doc4, doc6t2 −→ doc1, doc3...



PageRank


. . . Esempio di raccomandazione

Calcoliamo l’insieme di rilevanza per la query q = (t1, t2)

Insieme di rilevanza {1 3 4 6}

I PageRank dei 4 documenti possono essere confrontati perindividuare quale dei documenti e il piu rilevante

ordinare le componenti del vettore pagerank associate aidocumenti selezionati in modo decrescente

π4 π6 π3 π1

doc4 −→ documento piu rilevanteseguono doc6, doc3, doc1



PageRank

References

Monica Bianchini, Marco Gori, and Franco Scarselli.Inside pagerank.ACM Trans. Internet Technol., 5(1):92–128, February 2005.

Amy N. Langville and Carl D. Meyer.A survey of eigenvector methods for web information retrieval.SIAM Rev., 47(1):135–161, January 2005.


PageRank

Technology

Transcript of PageRank