1 Lalgoritmo PageRank. 2 Il grafo del Web Si può pensare allinsieme dei documenti presenti sul Web...

11

L’algoritmo PageRankL’algoritmo PageRank

22

Il grafo del WebIl grafo del Web

Si può pensare all’insieme dei documenti presenti Si può pensare all’insieme dei documenti presenti

sul Web come a un grafo, in cui:sul Web come a un grafo, in cui:

• i i nodinodi sono gli URL; sono gli URL;

• c’è un c’è un arcoarco fra il nodo fra il nodo x x e il nodoe il nodo y y quando la pagina che quando la pagina che

corrisponde all’URL corrisponde all’URL xx contiene un link verso l’URL contiene un link verso l’URL yy..

Questo grafo è chiamato Questo grafo è chiamato grafo del Web. grafo del Web.

Ovviamente, si tratta di un grafo dinamico, che Ovviamente, si tratta di un grafo dinamico, che

cambia in continuazione.cambia in continuazione.

33

Dimensioni del WebDimensioni del Web

Difficili da valutare; comunque, il grafo è Difficili da valutare; comunque, il grafo è

enormeenorme..

• Numero di nodi(=documenti): 2/4 miliardi Numero di nodi(=documenti): 2/4 miliardi

(escludendo le pagine non accessibili).(escludendo le pagine non accessibili).

• Numero di archi: 60/100 miliardi.Numero di archi: 60/100 miliardi.

• Numero di host: 100/200 milioni.Numero di host: 100/200 milioni.

• Numero di utenti: 500/800 milioni.Numero di utenti: 500/800 milioni.

44

Richiami: componenti connesseRichiami: componenti connesse

Dato un grafo orientato Dato un grafo orientato G=(V,E)G=(V,E), definiamo una relazione , definiamo una relazione

fra i nodi, ponendo fra i nodi, ponendo x x y y quando esistono un cammino quando esistono un cammino

da da xx a a yy ee un cammino da un cammino da yy a a xx..

La relazione La relazione è una relazione di equivalenza, le cui classi è una relazione di equivalenza, le cui classi

sono dette sono dette componenti (fortemente) connessecomponenti (fortemente) connesse del grafo. del grafo.

È possibile costruire il È possibile costruire il grafo ridotto G*grafo ridotto G*, che ha come nodi le , che ha come nodi le

componenti connesse, e ha un arco fra la componente componenti connesse, e ha un arco fra la componente CC11 e e

la componente la componente CC22 quando esiste un arco che va da un nodo quando esiste un arco che va da un nodo

di di CC11 a un nodo di a un nodo di CC22..

55

Componenti connesse: un esempioComponenti connesse: un esempio

66


77


88

La struttura “a cravattino” del WebLa struttura “a cravattino” del Web

Componente gigante.Componente gigante.• Comprende circa il 30% delle pagine.Comprende circa il 30% delle pagine.• Stime del diametro: orientato=20/30; non Stime del diametro: orientato=20/30; non

orientato=10/17.orientato=10/17.• ““Com’è piccolo il mondo!” (small world theory).Com’è piccolo il mondo!” (small world theory).

99


Componenti “sorgente” (circa 24%).Componenti “sorgente” (circa 24%).• Puntano (direttamente o indirettamente) verso Puntano (direttamente o indirettamente) verso

la componente gigante, ma …la componente gigante, ma …• … … non sono raggiungibili dalla componente non sono raggiungibili dalla componente

gigante.gigante.• Sono le pagine “reiette”.Sono le pagine “reiette”.

1010


Componenti “pozzo” (circa 24%).Componenti “pozzo” (circa 24%).• Sono raggiungibili dalla componente gigante, Sono raggiungibili dalla componente gigante,

ma …ma …• … … da esse non si può tornare indietro.da esse non si può tornare indietro.• In questa categoria rientra la maggior parte dei In questa categoria rientra la maggior parte dei

documenti senza linkdocumenti senza link..

1111


Componenti “isolate” e tentacoli.Componenti “isolate” e tentacoli.• Non sono raggiungibili dalla componente gigante.Non sono raggiungibili dalla componente gigante.• Da esse non si raggiunge la componente gigante.Da esse non si raggiunge la componente gigante.• Ci sono collegamenti fra sorgenti e pozzi che non Ci sono collegamenti fra sorgenti e pozzi che non

passano per la componente gigante (passano per la componente gigante (tentacolitentacoli).).

1212

Come cercare informazioni?Come cercare informazioni?

La ricerca di informazioni è diventata sempre più La ricerca di informazioni è diventata sempre più

difficile, per vari motivi:difficile, per vari motivi:

• dimensioni (dimensioni (too much information…too much information…););

• mancanza di semantica (tentativi di realizzare il mancanza di semantica (tentativi di realizzare il Web Web

semanticosemantico) e struttura;) e struttura;

• qualità di informazione estremamente eterogenea;qualità di informazione estremamente eterogenea;

• i documenti sono soggetti a rapida modifica.i documenti sono soggetti a rapida modifica.

Per tali motivi, circa l’80% degli utenti utilizza Per tali motivi, circa l’80% degli utenti utilizza

abitualmente i motori di ricerca.abitualmente i motori di ricerca.

1313

Com’è fatto un motore di ricerca?Com’è fatto un motore di ricerca?

Tre attività logicamente distinte:Tre attività logicamente distinte:

• raccolta di dati;raccolta di dati;

• elaborazione dei dati raccolti;elaborazione dei dati raccolti;

• risposta alle query degli utenti;risposta alle query degli utenti;

1414

Raccolta datiRaccolta dati

Si tratta di recuperare il contenuto delle pagine Web (di Si tratta di recuperare il contenuto delle pagine Web (di

solito, limitandosi a quelle testuali).solito, limitandosi a quelle testuali).

Viene svolta da un’apposita componente, detta Viene svolta da un’apposita componente, detta spider.spider.

Problemi da affrontare (fra gli altri):Problemi da affrontare (fra gli altri):

• Quantità di dati; quantità di banda;Quantità di dati; quantità di banda;

• frequenza di aggiornamento;frequenza di aggiornamento;

• presenza di materiale nascosto (cfr. cravattino);presenza di materiale nascosto (cfr. cravattino);

• standard non rispettati;standard non rispettati;

• spider traps!spider traps!

1515

Elaborazione datiElaborazione dati

Obiettivi:Obiettivi:

• estrarre informazioni (parsing);estrarre informazioni (parsing);

• rilevare la presenza di duplicati (o quasi rilevare la presenza di duplicati (o quasi

duplicati) dovuti al mirroring;duplicati) dovuti al mirroring;

• rilevare la presenza di spamming;rilevare la presenza di spamming;

• indicizzare i dati;indicizzare i dati;

• eventualmente, calcolare informazioni eventualmente, calcolare informazioni

necessarie per il ranking.necessarie per il ranking.

1616

Risposta alle queryRisposta alle query

Diversi modi di rispondere alle query:Diversi modi di rispondere alle query:

• ricerche testuali sofisticate (ricerche testuali sofisticate (ricettaricetta AND AND (pasta(pasta

NEAR NEAR pesto)pesto)););

• uso di suggerimenti ontologici;uso di suggerimenti ontologici;

• riconoscimento linguistico;riconoscimento linguistico;

• analisi del profilo utente (logging di query, analisi del profilo utente (logging di query,

bookmarks, ecc.);bookmarks, ecc.);

• sistemi di categorizzazione automatica.sistemi di categorizzazione automatica.

1717

ElaborazioneElaborazione

1818

Il problemaIl problema

Nella fase di elaborazione occorre Nella fase di elaborazione occorre

indicizzare i documenti recuperati. indicizzare i documenti recuperati.

L’indicizzazione deve consentire in modo L’indicizzazione deve consentire in modo

efficiente di rispondere alle query.efficiente di rispondere alle query.

In particolare, l’indicizzazione deve In particolare, l’indicizzazione deve

permettere il ranking dei documenti!permettere il ranking dei documenti!

1919

Il rankingIl ranking

Dato un insieme Dato un insieme P P di pagine e una query di pagine e una query Q, Q,

definire una funzione definire una funzione rrQ Q :: P P R R che associ, ad che associ, ad

ogni pagina, un numero reale (rank), che indica il ogni pagina, un numero reale (rank), che indica il

grado di grado di rilevanza rilevanza di quella pagina a fronte di di quella pagina a fronte di

quella query.quella query.

Tecniche di ranking basate su:Tecniche di ranking basate su:

• analisi del contenuto testuale (Altavista);analisi del contenuto testuale (Altavista);

• analisi della struttura dei link (Google).analisi della struttura dei link (Google).

2020

Latent Semantic IndexingLatent Semantic Indexing

È una tecnica di ranking basata sul contenuto testuale. È È una tecnica di ranking basata sul contenuto testuale. È

adottata da Altavista.adottata da Altavista.

Sia Sia tt il numero di termini considerati (presi, per es., da un il numero di termini considerati (presi, per es., da un

dizionario, o tutte le parole incontrate nelle pagine raccolte).dizionario, o tutte le parole incontrate nelle pagine raccolte).

Ad ogni pagina Ad ogni pagina PP è associato un vettore di è associato un vettore di tt elementi elementi

dovedove

(d(dPP))j j == # occorrenze del termine # occorrenze del termine jj in in PP..

2121


Ad ogni query Ad ogni query QQ si associa un analogo si associa un analogo

vettore , che ha un 1 in corrispondenza vettore , che ha un 1 in corrispondenza

dei termini che compaiono nella query, e dei termini che compaiono nella query, e

uno 0 altrimenti.uno 0 altrimenti.

Si tratta di determinare l’affinità tra Si tratta di determinare l’affinità tra QQ e e DD::

2222


Assunzione ingenua del LSI:Assunzione ingenua del LSI:

una pagina è autorevole su un argomento se iuna pagina è autorevole su un argomento se i

termini relativi a quell’argomento vi compaionotermini relativi a quell’argomento vi compaiono

spesso.spesso.

Non è vera (per es. FIAT) ed è suscettibile allo spamming. Si Non è vera (per es. FIAT) ed è suscettibile allo spamming. Si

possono migliorare le prestazioni estendendo il testo della pagina possono migliorare le prestazioni estendendo il testo della pagina

con i testi delle ancore che puntano alla pagina (ed, eventualmente, con i testi delle ancore che puntano alla pagina (ed, eventualmente,

il loro contesto).il loro contesto).

Inoltre, il LSI funziona bene solo su query multiple, ma la maggior Inoltre, il LSI funziona bene solo su query multiple, ma la maggior

parte delle query sono semplici (una, due, al massimo tre parole).parte delle query sono semplici (una, due, al massimo tre parole).

2323

PageRank: caratteristichePageRank: caratteristiche

PageRank è un algoritmo di ranking con le seguenti PageRank è un algoritmo di ranking con le seguenti

caratteristiche:caratteristiche:

• assegna a ciascuna pagina assegna a ciascuna pagina ii un rank un rank RRii in modo in modo staticostatico, cioè , cioè

indipendente dalla query: data una query indipendente dalla query: data una query QQ, si determineranno , si determineranno

le pagine che soddisfano la query, e queste pagine verranno le pagine che soddisfano la query, e queste pagine verranno

ordinate in base al loro rank;ordinate in base al loro rank;

• determina l’importanza di una pagina determina l’importanza di una pagina esclusivamenteesclusivamente sulla sulla

base dei link, e non del contenuto testuale: si basa sull’idea che base dei link, e non del contenuto testuale: si basa sull’idea che

il contenuto il contenuto non è autodescrittivonon è autodescrittivo, e che il conferimento di , e che il conferimento di

importanza di una pagina è un processo importanza di una pagina è un processo esogenoesogeno..

È alla base dell’algoritmo di ranking usato da Google.È alla base dell’algoritmo di ranking usato da Google.

2424

PageRank: l’ideaPageRank: l’idea

Una pagina è tanto più importante quanto più numerose sono le Una pagina è tanto più importante quanto più numerose sono le

pagine che la puntano.pagine che la puntano.

Se Se RRii indica l’importanza (rango) di una pagina indica l’importanza (rango) di una pagina ii, essa distribuisce la , essa distribuisce la

propria importanza in modo uniforme alle pagine che punta:propria importanza in modo uniforme alle pagine che punta:

dove dove jj i i indica la presenza di un link da indica la presenza di un link da jj a a ii, e , e NNjj è il numero di link è il numero di link

contenuti nella pagina contenuti nella pagina j.j.

Esiste una (unica) soluzione all’equazione di ricorrenza?Esiste una (unica) soluzione all’equazione di ricorrenza?

Solo se il grafo è fortemente connesso!Solo se il grafo è fortemente connesso!

2525

PageRank: la formulaPageRank: la formula

Per garantire che il grafo sia fortemente connesso, si introduce un Per garantire che il grafo sia fortemente connesso, si introduce un

fattore che corrisponde a introdurre dei “link random” al grafo:fattore che corrisponde a introdurre dei “link random” al grafo:

dove dove NN è il numero di pagine. è il numero di pagine.

Il rango della pagina Il rango della pagina ii è determinato in parte (cioè, per una frazione è determinato in parte (cioè, per una frazione

11--) dalle pagine che puntano ) dalle pagine che puntano ii, e in parte (frazione , e in parte (frazione ) è acquisito ) è acquisito

“gratuitamente” (come per effetto della presenza di archi da tutte le “gratuitamente” (come per effetto della presenza di archi da tutte le

pagine alla pagina pagine alla pagina ii).).

[[00,,11]]: di solito : di solito 00,,15 (fattore di spargimento).15 (fattore di spargimento).

2626

PageRank: il problema dei pozziPageRank: il problema dei pozzi

La formula di PageRank si può calcolare La formula di PageRank si può calcolare

iterativamente, a partire daiterativamente, a partire da

(tutte le pagine hanno la stessa importanza) e (tutte le pagine hanno la stessa importanza) e

applicando la formula, che “redistribuisce” applicando la formula, che “redistribuisce”

l’importanza delle pagine.l’importanza delle pagine.

Ad ogni passo, viene mantenuta somma 1?Ad ogni passo, viene mantenuta somma 1?

2727

PageRank: il problema dei pozziPageRank: il problema dei pozzi

Per ogni nodo Per ogni nodo jj con con almeno un arco uscentealmeno un arco uscente, il fattore , il fattore RRjjtt/N/Nj j viene viene

sommato per ciascun arco uscente (ce ne sono sommato per ciascun arco uscente (ce ne sono NNjj in tutto):in tutto):

La somma è 1 solo se La somma è 1 solo se non ci sono pozzi non ci sono pozzi (cioè, nodi senza archi (cioè, nodi senza archi

uscenti). Altrimenti, la somma sarà < 1: i pozzi assorbono uscenti). Altrimenti, la somma sarà < 1: i pozzi assorbono

importanza dalle pagine senza restituirla al sistema!importanza dalle pagine senza restituirla al sistema!

2828

PageRank: eliminazione dei pozziPageRank: eliminazione dei pozzi

Per risolvere il problema, si può operare in molti Per risolvere il problema, si può operare in molti

modi diversi:modi diversi:

• per ogni pozzo per ogni pozzo ii, si aggiungono archi fittizi da , si aggiungono archi fittizi da ii ad ogni ad ogni

altra pagina (cosicchè i pozzi “cedano” uniformemente la altra pagina (cosicchè i pozzi “cedano” uniformemente la

loro importanza a tutte le pagine);loro importanza a tutte le pagine);

• equivalentemente, ad ogni passo di PageRank, si equivalentemente, ad ogni passo di PageRank, si

aggiunge a tutti gli aggiunge a tutti gli RRii una stessa quantità in modo che la una stessa quantità in modo che la

somma rimanga 1;somma rimanga 1;

• si eliminano iterativamente i pozzi e si applica PageRank si eliminano iterativamente i pozzi e si applica PageRank

al resto del grafo; i pozzi vanno poi reintegrati alla fine.al resto del grafo; i pozzi vanno poi reintegrati alla fine.

2929

PageRank: interpretazione PageRank: interpretazione stocasticastocastica

L’algoritmo di PageRank può essere interpretato come un L’algoritmo di PageRank può essere interpretato come un

processo stocastico. Assumiamo un processo stocastico. Assumiamo un navigatore probabilisticonavigatore probabilistico

che naviga sul grafo del Web (senza pozzi) nel seguente che naviga sul grafo del Web (senza pozzi) nel seguente

modo:modo:

• parte da una pagina parte da una pagina ii a caso; a caso;

• con probabilità con probabilità ((11--) ) segue uno dei link della pagina corrente;segue uno dei link della pagina corrente;

• con probabilità con probabilità si muove verso una pagina a caso. si muove verso una pagina a caso.

Il rank Il rank RRii è la frazione di tempo trascorsa dal navigatore è la frazione di tempo trascorsa dal navigatore

probabilistico nella pagina probabilistico nella pagina ii..

3030

PageRank: vantaggi/svantaggiPageRank: vantaggi/svantaggi

Viene calcolato con grande efficienza; il processo iterativo Viene calcolato con grande efficienza; il processo iterativo

converge entro pochi passi.converge entro pochi passi.

Va calcolato una volta sola, in modo indipendente dalla Va calcolato una volta sola, in modo indipendente dalla

query.query.

È possibile costruire insiemi di pagine “artefatte” che È possibile costruire insiemi di pagine “artefatte” che

infuiscono sul ranking.infuiscono sul ranking.

L’indipendenza dalla query è un limite!L’indipendenza dalla query è un limite!

Di solito va aggiustato usando un secondo ranking, basato Di solito va aggiustato usando un secondo ranking, basato

sul contenuto (per.es., LSI).sul contenuto (per.es., LSI).

1 Lalgoritmo PageRank. 2 Il grafo del Web Si può pensare allinsieme dei documenti presenti sul Web...

Documents

Transcript of 1 Lalgoritmo PageRank. 2 Il grafo del Web Si può pensare allinsieme dei documenti presenti sul Web...