Big Data Analysis

M

otteniamo un vettore che definisce la distribuzione dopo uno step. Prendendo

v

questo vettore e moltiplicandolo di nuovo per M, otteniamo ancora un

1

v

vettore che indica la distribuzione dopo 2 step, e così via, fino ad ottenere

2 v v

una distribuzione che risulta essere uguale alla precedente , dopo i+1

+1

i i

step (si arriva a convergenza).

Questo procedimento così descritto è un esempio di Processo Markoviano,

ossia un processo tale per cui il passo successivo dipende esclusivamente dal

precedente. In particolare:

Definizione (Markov Chains). v

Per una qualsiasi vettore di partenza , il power method applicato alla

0

matrice di transizione M, converge ad un unico vettore stazionario positivo,

ammesso che M sia Stocastica (le colonne sommano ad 1), Irriducibile (la

rete non deve avere vicoli ciechi) e Aperiodica (il grafo non deve presentare

cicli).

Tutto ciò si traduce nell’avere un grafo Fortemente Connesso, privo di Vicoli

Ciechi.

Nell’esempio sottostante vediamo come dopo molte iterazioni abbiamo

convergenza: C’è una connessione

geometrica di questo

processo con autovalori ed

autovettori, basti saperlo,

non bisogna sapere qual è.

Parte IV- Page Rank e Web

Ma il web rispetta le condizioni sopra imposte? Il web ha un nucleo di pagine

fortemente connesse ed altre parti poco connesse. Pertanto, in generale non è

fortemente connesso, in quanto non è esclusa la presenza di vicoli ciechi o cicli

interni nella struttura. Alias, la sua struttura viola le condizioni necessarie per il

processo markoviano. Il Page Rank va perciò modificato per prevenire le

anomalie dovute ad una struttura non propriamente idonea. In particolare,

dobbiamo evitare due situazioni:

- vicoli ciechi (dead ends), cioè percorsi senza uscita, dovuti da una o

più pagine che non hanno link in uscita verso nessun'altra pagina.

Quando abbiamo dei vicoli ciechi, la matrice di transizione non è più

stocastica, in quanto ci sarà almeno una colonna che somma a 0 e non

ad 1 (tutti zeri). Questo perché le informazioni "muoiono" in un nodo, cioè

dopo averlo raggiunto non vanno più da nessuna parte;

- spider traps, cioè quando ci imbattiamo in percorsi ciclici, dovuti a

riferimenti in un gruppo di pagine (appunto delle trappole). La trappola

ciclica più semplice è un riferimento di una pagina a sé stessa (auto-link).

In questo caso, utilizzando il ragionamento precedente ci imbattiamo in

una rete che collassa sul nodo stesso.

Ma come evitiamo questi problemi? Per evitare i vicoli ciechi possiamo

banalmente eliminare i nodi che ne sono la causa, quindi gli archi che giungono

ad essi. Per assegnare poi i valori ai nodi eliminati possiamo ricostruire il

grafico ed approssimare il page rank. Non è un metodo molto ottimizzato,

considerando la grandezza del web, anche perché, tipicamente, eliminando

quei nodi, si creano altri vicoli ciechi. In ogni caso è un metodo esatto, che crea

una struttura fortemente connessa. Un altro metodo per eliminare i vicoli ciechi

risolve anche il problema delle spider traps. Esso è detto “Taxation” e si basa

sul modificare il processo con il quale il navigatore casuale si muove nel web.

Fondamentalmente, modifica la formula di partenza aggiungendo un parametro

, compreso tra 0,8 e 0,9. Il parametro è un indicatore casuale che può

β

avere due opzioni, che è quello di seguire la rete (cioè seguire il link) all'80% o

90%, oppure al 20% o 10% (1 - ) salta in un altro nodo casuale della rete,

β

anche non collegato direttamente a quel nodo dove ci troviamo (tutti i nodi

sono equiprobabili). Così facendo, evitiamo sicuramente i vicoli ciechi ed i cicli,

perché ogni nodo è collegato in teoria a tutti gli elementi della rete e dopo un

tot di passaggi, abbiamo un salto casuale.

Ove, e è un vettore di uni ed n il numero di pagine web.

Avere ipoteticamente tutti i nodi collegati tra loro, rende vere le condizioni del

processo Markoviano, cioè otteniamo una struttura Aperiodica, Stocastica ed

Irriducibile.

Parte V- Page Rank e Map-Reduce

Come ampiamente discusso, il calcolo del PageRank, coincide con il calcolo di

un prodotto di una matrice per un vettore, ripetuto fino a convergenza. Come

già visto in una sezione precedente, è questa un’operazione implementabile

con il paradigma Map-Reduce. In particolare, occorre distinguere due possibili

implementazioni, una per vettori tali da poter risiedere in memoria centrale,

l’altra per vettori che non riescono a risiedere in memoria centrale. Nel primo

caso non abbiamo problemi particolari e il paradigma map-reduce sarà identico

a quello osservato nella sezione precedente (matrice x vettore). Nel secondo

caso la situazione cambia e bisogna trovare soluzioni a riguardo.

N.B.: c’è qualcosa di più di un calcolo di una matrice per un vettore dopo

l’aggiunta di beta, ma il concetto è lo stesso.

1. Soluzione Naive: Quando non può essere contenuto in memoria,

v

sicuramente una o qualcuna delle sue componenti può. Pertanto,

assumiamo che solo una parte di quel vettore può essere contenuta in

memoria, dividendo la matrice in bande verticali ed il vettore in bande

v

orizzontali. Non a caso, (nella banda orizzontale), per il calcolo della

1 m m

moltiplicazione, interesserà solo ed (nella banda verticale), in

11 21

questo modo:

Questo però non risolve il problema, in quanto, in fase di ricostruzione del

risultato, questo non riesce a stare in memoria, essendo anch’esso lungo

tanto quanto per definizione. Ricordiamo che un risultato di una

v

moltiplicazione diventa il vettore per la successiva moltiplicazione,

quindi, vogliamo che anche quello sia in grado di essere memorizzato in

memoria.

2. Soluzione a cubetti: In questo caso, dividiamo il vettore in bande

orizzontali e la matrice sia in bande verticali che orizzontali (a cubetti).

M

Fatto ciò, assegniamo ad ogni task un blocco della matrice ed ogni

ij

v v

banda del vettore viene spedita in k diversi task di map; cioè

j j

M

viene spedita al task di per ogni possibile k valore di i. In questo

ij

modo, ogni operazione incide su un singolo blocco nel risultato. Così

facendo abbiamo un risultato spezzato in blocchi, in modo tale che ogni

blocco sia in grado di poter essere inserito in memoria.

Di base è questo un metodo inefficiente, in quanto la matrice M è sparsa,

ha tantissime righe e tantissime colonne, quindi, la sua memorizzazione

è troppo onerosa. Per questo motivo, la matrice viene memorizzata in

modo efficiente con un’altra rappresentazione: in una colonna il nodo di

partenza, poi quelli di uscita ed il grado (quanti nodi di uscita ci sono),

vediamo sotto:

Parte VII- Topic Sensitive Page Rank

Si tenga conto che fin ora abbiamo parlato del calcolo del Page Rank in modo

generico all’interno del web. È però molto utile misurare il rank all'interno di

singoli topics, ottenendo un Topic-Sensitive PageRank. In questo senso

l'obiettivo è valutare una pagina non in base alla sua popolarità in generale, ma

in base alla sua popolarità su un certo argomento (Es. sport, storia). Le

modifiche al PageRank tipico sono quelle ovvie, il tutto non avviene più sulla

totalità della rete, ma su un suo sottoinsieme. Per esempio, il teleport non va

su tutta la rete, ma solamente su un suo sottoinsieme di pagine individuate per

quel topic. Ciò ovviamente prevede una parte iniziale di individuazione del

sottoinsieme in questione, in base tipicamente a richieste dell’utente (query).

Parte VII- Link Spam

Il Link Spam è un modo artificiale per imbrogliare il Page Rank, aumentando la

popolarità di una pagina a dismisura rispetto al valore atteso. Infatti,

utilizzando un'architettura specifica, creiamo una o più pagine (tipicamente

una, detta pagina target) con altissimo Page Rank, tramite l'utilizzo di link

verso m pagine fantasma (pagine di supporto o link spam farm), che linkano

esclusivamente la pagina target. Forme di Link Spam possono essere anche

semplici commenti all’interno di blog con un link alla propria pagina. Sotto è

mostrato un esempio di struttura tipica.

I modi per ottenere Link Spam sono tantissimi e sono tantissime le possibili

infrastrutture realizzabili allo scopo di aumentare il Page Rank. Noi qui

osserveremo come aumenta il page rank osservando una struttura classica.

Considerando la formula della Taxation, definiamo:

- n, numero pagine nel web;

- m, numero pagine di supporto o link spam farm;

- �, page rank complessivo del nodo target (quello che voglio aumentare).

Il Page Rank �, è dato da due contributi, il contributo delle pagine esterne � e

quello delle m pagine di supporto. Ognuna delle m pagine di supporto, ha page

rank come in sotto, tramite taxation:

βy 1−β

+

m n

Considerando il contributo fornito da tutte le pagine di supporto, questo sarà

dato da β per m volte l’espressione precedente:

( )

βym 1−β 1−β

+

βm +

n n

Di cui l’ultimo contributo è trascurabile. Svolgiamo i calcoli:

( ) ( ) (1−β)

β 1− β m β 1−β m β m

x x βm

( )

2 2

+ + =x+ + = +

y=x β y → y 1−β → y=

n n ( ) ( ) ( )

)(1+

n(1−β β) 1+ β n

2 2

1− β 1−β

β

c=

Imponendo , otteniamo:

1+ β

x m

+c

y= n

( )

2

1−β

Da questo risultato possiamo immediatamente notare come il secondo

contributo aumenta all’aumentare di m (pagine di supporto) in modo lineare.

Inoltre, anche il valore del page rank iniziale viene amplificato (x), essendo la

( )

2

quantità .

<1

1−β

Il Link Spam è un qualcosa che un buon motore di ricerca deve ovviamente

evitare, riducendo la popolarità di quelle pagine ove individua uno spam.

Tipicamente risulta difficile andare ad intercettare strutture di questa tipologia

ed identificarle come Spammer, in quanto c’è la possibilità che non siano

effettivamente spam, ma comunque possono rappresentare dei potenziali

candidati. La contromossa più utilizzata è il TrustRank, insieme con lo Spam

Mass. Il primo è una variazione del Topic-Sensitive PageRank, dove il “topic” è

un insieme di pagine considerate affidabili (cioè prive di spam). Nello specifico,

il trust