Ranking di pagine Web

Debora Donato

Pagina 2

Ranking delle pagine

• Raccolta delle pagine html;

• Costruzione del webgraph;

• Transformazione dei dati in un formato adeguato;

• Ranking delle pagine del webgraph:– Con Pagerank;

– Con Hits.

Pagina 3

Libreria DIS

• Libreria software per l'analisi di grafi di grandi dimensioni.

• Tool sviluppato presso il Dipartimento di Informatica e Sistemistica dell' Universita’ La Sapienza.

• Disponibile gratuitamente in http://www.dis.uniroma1.it/~cosin/html_pages/COSIN-Tools.htm

• Documentazione in: http://www.dis.uniroma1.it/~cosin/publications/deliverableD13.pdf

Pagina 4

Libreria DIS

• Obiettivo: offre una serie di routines in grado di:– Generare grafi in base alla maggior parte dei

modelli presenti in letteratura

– Calcolare alcune delle misure statistiche proprie del grafo del Web • Distribuzione indegree outdegree

• Pagerank, hits

• SCCs, Clique

• Bowtie

Pagina 5

Installazione della Libreria

• Implementata in C++ versione 2.9;

• Raccomandata almeno 256 MB di RAM;

• Installazione:

– Scaricare e scompattare la libreria;

– Type “cd disRelease” (cambia directory)

– Type “make” (compila i sorgenti)

Pagina 6

Struttura della Libreria

• Per ogni programma viene creata una cartella. Ogni cartella contiene il codice (*.h, *.cpp, *.cc).

• Makefile: compila e crea gli eseguibili dei programma;• Common: contiene le routine comuni ai diversi

algoritmi (memoria secondaria, rappresentazione binaria, etc);

• bin: contiene gli eseguibili creati durante la esecuzione di Makefile;

Pagina 7

Struttura della Libreria

• Generators:

• Measures:

• Search algorithms:

• Bow-tie discovering:

• File converters:

• Miscellaneous:

Pagina 8

Programmi da usare nell'esercitazione

• Della categoria “file converters”:– text2ips.script: transforma un file testo nella rappresentazione

IPS;

• Della categoria “graph measurers”:– pagerank: esegue pagerank

– hits: esegue hits

Pagina 9

Grafo in formato testo

Grafo esempio

Grafo in formato testo

Pagina 10

Grafo in formato testo

– Per ogni grafo sono presenti 3 tipi di multifile:• .info: contiene l’indegree, l’outdegree il puntatore alla lista dei

successori (memorizzata in .succ), il puntatore alla lista dei predecessori (memorizzata in .pred)

• .succ: lista dei successori

• .pred: lista dei predecessori

Pagina 11

Grafo in formato IPS

Pagina 12

Multifile

– I file .ips devono essere in grado di contenere le informazioni relative a milioni di nodi e miliardi di archi.

– Limite: filesystem

– Soluzione: ogni file viene spezzato in piu’ file la cui gestione e’ completamente trasparente all’utente (multiFileWriter, multiFileReader)

Pagina 13

Implementazione di Page Rank

– Il calcolo di pagerank e’ fatto in blocchi:• I blocchi hanno misura fissa che dipende dal numero di

float allocabili in memoria principale;– numMB = memoria / (1024*1024);– numFloat = numMB/sizeof(float);– Nblocchi = numNodi/numFloat– NnodiPerBlocco = numNodi/Nblocchi

• Ogni blocco e’ caricato in memoria. Il page rank del blocco viene calcolato ed il risultato viene scritto su file;

Pagina 14

Inizializzazione

– Verifica la correttezza dei parametri

– Partiziona il file dei successori in blocchi.

– Inizializza tutti nodi a 1/N

– Esegue il ciclo principale

– Normalizza e calcola residual

– Stampa i file dei risultati

Pagina 15

Multifile utilizzati

– fileSorgente: contiene i valori di PR calcolati alla fine del passo precedente. Viene inizializzato all’inizio di ogni ciclo con i valori di fileDestinatario– fileTemporaneo: contiene i valori di PR alla fine

del ciclo principale, prima del passo di normalizzazione.– fileDestinatario: contiene i valori di PR dopo il

passo di normalizzazione.

Pagina 16

Partizionamento del grafo

– I file Grafo.succ e’ partizionato in Nblocchi file di misura prefissata;

– Funzione partizionaFileSuccessori()

• Calcola: numSucc, numInfo, numNodi e numNodiPerOgniBlocco;

• esegue partizione (pseudocode nella prossima slide);

Pagina 17

Partizionamento del grafo

For each structInfoi = readInfo() /* fInfo.read() */

For each successor node of is = readSuccess() /* fSucc.read() */insert(s,buffer) /* buffer = fTempo*/

if block_is_full writeToDisk();}

writeToDisk()}– writeToDisk(): scrive sul file relativo al blocco corrente l’ ID

del nodo, il numero totale di successori del nodo e la lista dei successori.

Pagina 18

Inizializzazione di Page Rank

– Inizializza il file destinatario con il valore di pagerank; 1/N

• bufferFloatPR [numNodiperOgniBlocco]

• For i from 1 to numNodiPerOgniBlocco

• bufferFloatPR[i] = 1 / N

• scrive bufferFloatPR nel destFile numOfBlocchi volte;

Pagina 19

Ciclo principale

while (stop==false){

for each blocco b from 1 to Nblocchi{

pr = 0; //azzera il buffer

for each node i del blocco b

prende pr(i);

identifica tutti i successori di I;

for each succ j from 1 to numsucc pr(j) += pr(i)/numsucc;

for each succ j from 1 to numsucc

pr(j)= c*pr(j)+ (1-c)*(1/N);

}

scrive su fileDestPR;}

}

M '* Rank=cM∗Rank+ 1−c ∗[ 1N ]N∗1

M '* Rank=cM∗Rank+ 1−c ∗[ 1N ]N∗1

Pagina 20

Terminazione

stop: l’algoritmo si ferma quando il numero di iterazioni e’ > che maxIter o il residuo e’ < residual

Pagina 21

Passo di normalizzazione

– Si prende la somma di tutti i valori di PR alla fine del ciclo principale: sommaPR

– Si dividono tutti I valori di PR memorizzati all’interno del fileTemporaneo per sommaPR.

– Il risultato viene memorizzato in fileDestinatario

Pagina 22

Calcolo del residuo

– Il residuo e’ la radice quadrata della sommatoria dei quadrati delle differenze dei valori di PR calcolati in due iterazioni successive.

• residual = 0;• residual += (fileSorgente-fileDestinatario)2

• residual= sqrt(residual)

Pagina 23

Text2IPSscript

– INPUT: il nome del file contenente il grafo (ASCII)

– OUTPUT: i file testo in multifile format

• NameMultifile.%d.info

• NameMultifile.%d.pred

• NameMultifile.%d.succ

Pagina 24

Text2IPSscript

– Uso: text2ips.script <ram> –savesource <InputFile> <NameMultifile.%d>

• ram: memoria disponibile in MB

• -savesource: non cancella il file originale

• %d: DA SPECIFICARE ogni volta che vogliamo un multifile.

Pagina 25

Text2IPSscript

– Creare una directory graphs/ nella directory che contiene dis_library;

– Mettere al’interno della cartella appena creata l’archivio graph-testo-name (es. edgeit)

– Posizionarsi in dis_library

– Creare il grafo IPS:

– bin/text2ips.script 300 -savesource graphs/edgeit edgeit.%d

Pagina 26

Calcolo di PageRank

– INPUT: il grafo in formato IPS

– OUTPUT: ranking delle pagine secondo l’algoritmo pagerank

– Uso: pagerank <ram> <InputFile.%d> <prob> <residual> <maxIter> <outputFile.%d> columns > printFile

Pagina 27

Calcolo di PageRank

• inputFile: base-name del file in formato IPS

• prob: probabilita’ di scegliere una pagina vicina (e non saltare a un' altra pagina)

• residual: pagerank si ferma se il residuo e’ piu piccolo di residual

• maxIter: numero massimo di iterazioni eseguite per pagerank;

Pagina 28

Calcolo di PageRank

• outputFile%d: nome del multifile di output in cui vengono memorizzati i risultati del calcolo di PageRank

• columns: stampa vari tipi di informazione:

– N: colonna con l’id del nodo;

– I: colonna con l’indegree del nodo;

– O: colonna con l’outdegree del nodo;

– P: colonna con il rank del nodo;

• printFile: contiene l'output generato durante l'esecuzione della routine, ad es. Risultati parziali delle singole iterazioni

Pagina 29

Esecuzione calcolo di PageRank

– bin/pagerank 300 graphs/graph-ips-name.%d 0.85 0.001 50 outputFile.%d NIOP > print-file.txt

– File generati:

• outputFile.pr_distrib.txt: distribuizione dei risultati di pagerank

• outputFile.report.txt: risultati di pagerank

Pagina 30

Visualizzazione dei risultati con Gnuplot

– Per entrare nell' ambiente: gnuplot

– gnuplot> set logscale

– gnuplot> plot “outputFile.pr_distrib.txt” using 1:2 w p

Pagina 31

HITS

– INPUT: grafo in formato IPS

– OUTPUT: ranking delle pagine secondo l’algorithmo hits

– Uso: bin/hits

– Nota: questa routine e` fornita solo in versione interattiva. I parametri devono essere forniti da std input.

• InputFile: GraphName.%d

• maxResidual: hits si ferma se il residuo e’ piu piccolo di maxResidual

• maxIter: numero massimo di iterazioni

Pagina 32

Esecuzione di HITS

– bin/hits

– Insert graph name : graphs/graphIPSName.%d

– Insert maxResidual : 0.001

– Insert maxIteration: 50

Pagina 33

Utilizzo delle librerie Webgraph e LAW per il calcolo di PageRank

– Webgraph: framework per lo studio del grafo del Web. Supporta la gestione di grafi di grandi dimensioni attraverso l'utilizzo di moderne tecniche di compressione.

– Tool sviluppato presso il Laboratory of Web Algorithmics dell'Universita' di Milano

– Disponibile gratuitamente:

– http://webgraph.dsi.unimi.it/

Pagina 34

Utilizzo delle librerie Webgraph e LAW per il calcolo di PageRank

– LAW: collezione software distribuita dal laboratory of Web Algorithmics.

– Contiene il piu' grande insieme di classi e documentazione relativi a PageRank reso disponibile pubblicamente.

– http://law.dsi.unimi.it/software/

Pagina 35

Impostazione del classpath

– Scaricare e scompattare gli archivi seguenti:

– http://law.dsi.unimi.it/software/law-1.3.1-bin.tar.gz

– http://law.dsi.unimi.it/software/law-deps.tar.gz

– Aggiungere al classpath tutti i file jar contenuti negli archivi suddetti.

Pagina 36

Impostazione del classpath

– export DIR=(directory in cui sono stati scaricati gli archivi)

– export CLASSPATH=$CLASSPATH:.:$DIR/colt-hep-1.2.0.jar:$DIR/colt-1.2.0.jar:$DIR/dsiutils-1.0.jar:$DIR/fastutil5-5.1.2.jar:$DIR/gnu.getopt-1.0.12.jar:$DIR/jakarta-commons-codec-1.3.jar:$DIR/jakarta-commons-httpclient-3.0.1.jar:$DIR/jakarta-commons-io-1.3.2.jar:$DIR/jakarta-commons-lang-2.3.jar:$DIR/jakarta-commons-logging-1.1.jar:$DIR/jakarta-commons-collections-3.2.jar:$DIR/jakarta-commons-configuration-1.2.jar:$DIR/classpathx-jaf-1.0.jar:$DIR/jal-20031117.jar:$DIR/jetty5/jetty5-5.1.12.jar:$DIR/jetty5/jetty5-jmx-5.1.12.jar:$DIR/jetty5/jetty5-servlet-5.1.12.jar:$DIR/jsap-2.0.jar:$DIR/log4j-1.2.14.jar:$DIR/mg4j-2.1.jar:$DIR/sux4j-0.2.jar:$DIR/velocity-1.4.jar:$DIR/webgraph-2.1.jar:$DIR/law-1.3.1/law-1.3.1.jar

Pagina 37

Conversione del grafo in formato Webgraph

– Passo 1: conversione nel formato testuale supportato dal framework.

– Il grafo e' memorizzato in un file chiamato basename.graph-txt. La prima linea contiene il numero di nodi, n. Quindi, il file contiene n linee: la linea i-esima contiene i successori del nodo i in ordine crescente (la numerazione dei nodi va da 0 a n−1). I successori sono separati tra di loro da uno spazio.

– java Text2ASCII graph-name crea un file graph-name.graph-txt contenente il grafo in formato ASCIIGraph

– more graph-name.graph-txt

Pagina 38

Conversione del grafo in formato Webgraph

– Passo 2: conversione dal formato testuale al formato BV.

– java it.unimi.dsi.webgraph.BVGraph -g ASCIIGraph graph-name graph-name

– Produce un grafo compresso in formato BVGraph, con basename graph-name.

– Il grafo risultante viene memorizzato in tre file:

– graph-name.graph

– graph-name.offsets

– graph-name.properties

Pagina 39

Utilizzo della libreria LAW per il calcolo di PageRank

– Il package it.unimi.dsi.law.rank contiene una vasta collezione di classi dedicate al calcolo di PageRank.

– PageRank: classe astratta base. Definisce metodi e attributi per il supporto delle computazioni di PageRank o simili.

– PageRank.IterationNumberStoppingCriterion: criterio di terminazione: si ferma quando il numero di iterazioni raggiunge un dato limite.

– PageRankJacobi: calcola PageRank usando il metodo di Jacobi.

– PageRankPowerMethod: calcola PageRank usando il metodo delle potenze.

– ....

Pagina 40

Utilizzo della libreria LAW per il calcolo di PageRank

– Il package it.unimi.dsi.law.rank contiene una vasta collezione di classi dedicate al calcolo di PageRank.

– PageRank: classe astratta base. Definisce metodi e attributi per il supporto delle computazioni di PageRank o simili.

– PageRank.IterationNumberStoppingCriterion: criterio di terminazione: si ferma quando il numero di iterazioni raggiunge un dato limite.

– PageRankJacobi: calcola PageRank usando il metodo di Jacobi.

– PageRankPowerMethod: calcola PageRank usando il metodo delle potenze.

– Input: grafo in formato BVGraph

Pagina 41

Calcolo di PageRank: esempio

– java it.unimi.dsi.law.rank.PageRankPowerMethod graph-name graph-name

– Calcola sul grafo di nome graph-name il PageRank score di tutti i nodi.

– Output: graph-name.properties, graph-name.ranks (file binario contenente i punteggi calcolati per ogni nodo)

– Lettura degli score calcolati per i nodi del grafo:

– java PrintRanks graph-name.ranks

– Stampa lo score calcolato per tutti i nodi. La riga i-esima contiene lo score del nodo i-esimo.

Pagina 42

Calcolo di PageRank: esercizio

– Applicare gli altri metodi supportati per il calcolo di PageRank.

– java it.unimi.dsi.law.rank.PageRankGaussSeidel graph-name graph-name

– java PrintRanks graph-name

– java it.unimi.dsi.law.rank.PageRankJacobi graph-name graph-name

– java PrintRanks graph-name