Argomenti – Lezione 8

•Modulo III --- Calcolo del PageRank

•Modulo IV --- Costruzione del Dizionario Globale delle Parole

PageRank -- Ripasso

Prima Approssimazione al Calcolo del PageRank

T1T1

T2T2

TkTk

AA

PR(A) = Pr(T1)/C(T1) + PR(T2)/C(T2) + ...... + Pr(Tk)/C(Tk)

PR(A) = Page Rank di APr(Ti) = Page Rank di TiC(Ti) = numero di link in uscita di Ti

Cosa Cattura il PageRank ?

PageRank fornisce un modello di comportamento di un utente che clicca in maniera aleatoria da un pagina all’altra.

L’idea è che un utente visita una certa pagina con una probabilità data dal valore di PageRank di quella pagina.

Quindi la probabilità che un utente clicchi su una pagina è data unicamente dal numero di pagine con un link a quella pagina. Ed è per questo che il pagerank viene diviso per il numero totale di pagine.

Una seconda approssimazione per Pagerank

Si vuole catturare l’idea che un utente non continua a cliccare aleatoriamente all’infinito, ma ad un certo punto salta in maniera aleatoria ad una pagina qualsiasi. Si introduce nella formula un fattore d, con 0<d<1 per implementare questa idea

PR(A) = (1-d)+d*(PR(t1)/C(T1) + PR(T2)/C(T2) + ...... + Pr(Tk)/C(Tk))

il termine (1-d) cattura la probabilità che un utente salti ad un pagina qualunque. Tanto più alto è d, tanto più alta è la probabilità che un utente continui a seguire aleatoriamente i link.Un valore consigliato per d è: d=0.85

Un esempio

AA

CCBB

d=0.5

PR(A)=0.5+0.5*PR(C)

PR(B)=0.5+0.5*(PR(A)/2)

PR(C)=0.5+0.5*(PR(A)/2+Pr(B))

PR(A) = 14/13 = 1.07692308

PR(B) = 10/13 = 0.76923077

PR(C) = 15/13 = 1.15384615

Risolviamo

Nota: la somma dei PageRank = numero totale di pagine

Cosa fare in generale ?

Due Problemi:

• Quando vi sono moltissime pagine non e’ possibile trovare una soluzione manualmente

•Casi ricorsivi

AA

CCBB

PR(A) = 0.5+0.5*(PR(A)/3+PR(C))

Calcolo del PageRankper approssimazioni successive

Idea:

Si suppongono dati dei valori iniziali per i pagerank di tutte le pagine

(1,1,......,1)

Partendo da questi valori si continua iterativamente a calcolare il PageRank di tutte le pagine fin quando la differenza tra il valore precedente e il successivo di tutti i PageRank è minore di una certa precisione che fissiamo a priori

Approssimazioni successive: Esempio

Iterazione PR(A) PR(B) PR(C)0 1 1 11 1 0.75 1.1252 1.0625 0.765625 1.14843753 1.07421875 0.76855469 1.152832034 1.07641602 0.76910400 1.153656015 1.07682800 0.76920700 1.153810506 1.07690525 0.76922631 1.153839477 1.07691973 0.76922993 1.153844908 1.07692245 0.76923061 1.153845929 1.07692296 0.76923074 1.1538461110 1.07692305 0.76923076 1.1538461511 1.07692307 0.76923077 1.1538461512 1.07692308 0.76923077 1.15384615

1.07692308 - 1.07692307 = 0.00000001 <

Calcolo del PageRank come un intero

Nel nostro caso, con poche pagine,scaleremo linearmente i valori del PageRank. Maggiori dettagli nelle specifiche.

Scaling: logaritmo in base 6

PageRank Intero PageRank Calcolato0/10 0.15-0.91/10 0.9-5.42/10 5.4-32.43/10 32.4-194.44/10 194.4-1,166.45/10 1,166.4-6,998.46/10 6,998.4-41,990.47/10 41,990.4-251,942.48/10 251,942.4-1,511,654.49/10 1,511,654.4-9,069,926.410/10 9,069,926.4-0.85 × N + 0.15

Cosa fare nel Modulo III

• Costruire un vettore di reali di dimensione pari al numero di pagine analizzate.

•Inizializzarlo tutto a 1

•Applicare l’algoritmo iterativo per approssimazioni successive per calcolare i PageRank di tutte la pagine usando le informazioni sul grafo dei link salvate per ogni pagina in lista_in e lista_out.

Quando fermare l’iterazione ?

#define EPSILON

double PR[NUMPAGE], aux[NUMPAGE];

double maxdiff(double PR[],double aux[]){

...../* calcola max(PR[i]-aux[i])*/

}

while maxdiff(PR,aux)< EPSILON{

..... /* Aggiorna PR */

}

Modulo IV – Dizionario Globale

Obbiettivo

Costruire un dizionario di tutte le (differenti) parole che compaiono in tutte gli ipertesti.

Per ognuna di tali parole avremo le seguenti informazioni:

• tutti gli ipertesti in cui compaiono

• per ognuno di tali ipertesti la hitlist corrispondente

alla parola

Aspetti implementativi

Per implementare il dizionario globale useremo un tabella hash.

Useremo quindi le dichiarazioni e i metodi di hashtab.h e hashtab.c. Le collisioni verranno gestite con il metodo delle liste di collisioni.

Ogni entry del dizionario globale

Il campo key prenderà il valore della parola

Il campo info conterrà le informazioni descritte prima. (dettagli più avanti)

Il campo info nel dizionario globale

Ad ogni parola nel dizionario globale dobbiamo associare una lista delle pagine in cui compare

PARk = parola k-esima

PAGi = puntatore all’elemento del dizionario delle pagine corrispondente lla pagina i-esima.

EDL(k,i) = puntatore all’elemento del dizionario locale della pagina i-esima corrispondente alla parola PARk. Nota che accediamo alla HitList di PARk nella pagina i-esima.

En

try D

izio

nari

o

Glo

bale PARk

PAGi EDL(k,j)

PAGjEDL(k,i)

PAGl

EDL(k,l)

Campo info

Cosa fare nel Modulo IV

Alto livello

• Scorrere il dizionario delle pagine.

•Per ogni pagina, esaminare il suo dizionario locale

•Data la parola PARk della pagina PARi, aggiornare il dizionario globale

Scorrere il Dizionario delle Pagine

Come per la creazione del grafo dei link possiamo usarela lista di tutti gli elementi del dizionario delle pagine contenuto nel campo ls della struct table

Esaminare il Dizionario Locale

Supponiamo di analizzare la pagina PAGi

Per analizzare il dizionario locale scorriamo la lista formata dalla struct elem_diz_loc

Aggiornare il Dizionario Globale (DG)

Supponiamo di analizzare la pagina PAGi e che la parola attuale nel dizionario locale di PAGi e PARk.

Per aggiornare il dizionario globale:• calcoliamo la posizione di PARk nel DG (usando la funzione hash).

• Aggiungiamo un nuovo elemento (puntatore a PAGi e puntatore a PARk) alla lista (al più vuota perché è la prima volta che vediamo PARk) nel DG che forma il campo info della parola PARk. Attenzione alla gestione delle collisioni