Metodi Computazionali

A.A. 2009/2010

Elisabetta Fersini fersini@disco.unimib.it

2

Catene di Markov  Applicazioni:

  Fisica – dinamica dei sistemi   Web – simulazione del comportamento utente   Biologia – evoluzione delle cellule   Musica – definizione di sw per la composizione

musicale   Finanza – credit risk

3

Web Mining   Il web è una collezione di documenti eterogenei

in continua evoluzione caratterizzato da:   Vastità dell’informazione disponibile

  Difficoltà di reperire facilmente conoscenza “interessante”

  Nasce così una fertile area di ricerca con lo scopo di applicare metodi in grado “organizzare”, per quanto possibile, il contenuto del web.

4

Web Structure Mining  Obiettivo:

  Analizzare la struttura topoligica di una rete di informazioni al fine di identificare comunità, relazioni nascoste, etc…

  Link Analysis   Area del Web Structure Mining orientata alla

Social Newtork Analysis

Markov Chains: la gallina dalle uova d’ora di Google!

5

Google…le assunzioni   Assunzioni:

1.  Un Hyperlink è un riferimento di una pagine web i contenuto in una pagina web j   un link da una pagina j verso una pagina i corrisponde ad

una “raccomandazione” della pagina i da parte dell’autore della pagina j .

  se le pagine j e i sono connesse tramite un link, allora la probabilità che esse trattino dello stesso argomento è più alta in confronto al caso in cui esse non siano connesse.

j i

6

Google…le assunzioni   Assunzioni:

2.  La visibilità di un sito si misura mediante il numero di siti che puntano ad esso

3.  La luminosità di un sito rappresenta il numero di siti che esso punta

4.  In generale la Link Analysis basa i suoi assunti sulla teoria dei grafi, in particolare:

  Un LINK GRAPH contiene un nodo per ogni pagina j ed assumono esista un arco diretto (j,i), se e solo se la pagina j contiene un hyperlink verso la pagina i.

7

PageRank - definizioni intuitive (1)   Introdotto da Page e Brin nel 1998   L’importanza di una pagina i è influenzata

dall’importanza delle pagine che puntano ad essa, in particolare:   un link dalla pagina j alla pagina i viene interpretato

come un voto di j per i e se a sua volta anche i ha un link verso j entrambe ricevono un voto ancora più alto (Feedback-Link).

  Se la pagina i ha un PageRank più alto, il valore di un suo link è ancora più elevato; se ha un valore più basso non esiste alcuna penalità.

8

PageRank - definizioni intuitive (2)   L'importanza di una pagina è data dal voto che

questa riceve "dalla Rete" nella sua globalità

  PageRank rappresenta l’intero web come un grafo diretto G = (V,E) contenente n pagine; il valore di PageRank associato ad una pagina i, denotato da P(i) è definito da:

Oj è il numero di out-link di j (1)

9

Notazione Matriciale   Sistema di n equazioni con n incognite   Sia P il vettore colonna dei PageRank score, cioè P = (P(1), P(2), …, P(n))T.

  Sia A la matrice di adiacenza del grafo del web, dove

  Possiamo scrivere le n equazioni come

(2)

(3)

10

Risolvere il sistema di equazioni   PageRank può essere calcolato da un semplice

algoritmo iterativo

  La soluzione al sistema corrisponderà agli autovettori della matrice normalizzata rappresentante i link del web

  Problema: per ottenere la convergenza devono essere soddisfatte due condizioni   1 è il più grande autovalore   P è il principale autovettore

11

…un passo indietro verso le Markov chain…

  Per introdurre le due condizioni la stessa equazione (3) dalla modellazione mediante catene di Markov:   Ogni pagina web rappresenta uno stato.   Ogni hyperlink è una transizione, che permette di

passare da una pagina all’altra con una determinata probabilità.

  Tale framework permette di simulare la navigazione di un utente web.

12

Random surfing  Oi denota il numero di out-links della

pagina i.

 Ogni probabilità di transizione è 1/Oi se assumiamo che l’utente sceglierà di passare da una pagina all’altra in maniera random.

13

Matrice delle probabilità di transizione   Sia A la matrice di probabilità di transizione

  Aij rappresenta la probabilità che un utente nello stato i (pagina i) passi allo stato j (pagina j). Aij è definita dall’equazione(2).

14

Let us start   Data la distribuzione di probabilità iniziale che

l’utente si trovi in un particolare stato o pagina   p0 = (p0(1), p0(2), …, p0(n))T (vettore colonna)   A : n×n matrice delle probabilità di transizione,

Avremo:

  Se la matrice A soddisfa l’equazione (5), allora diremo che A è la matrice stocastica della catena di Markov.

(4)

(5)

15

Distribuzione di probabilità stazionaria   Dal teorema delle Markov chain:

  Una catena di markov definita da una matrice stocastica A ha un’unica distribuzione di probabilità stazionaria se A è irriducible e aperiodica.

  Una distribuzione di probabilità stazionaria garantisce che dopo una serie di transizioni pk convergerà ad un vettore di probabilità π

16

…torniamo al grafo del web…   Per verificare la convergenza dell’algoritmo

verifichiamo le due condizioni   A è una matrice stocastica

  A è irriducibile e aperiodica

  Nessuna di queste condizioni è verificata!!!

17

A non è una matrice stocastica   A è la matrice di transizione del grafo del web

  Non soddisfa l’equazione (5)

  Perchè?

 Molte pagine web non hanno out-links, per cui in A potrebbero esserci delle righe uguali a 0.

18

Esempio

19

A non è una matrice stocastica: soluzione 1.  Rimuovere tutte le pagine che hanno non

hanno out-links 2.  Aggiungere un set di out-links dalle

pagine che non rispettano l’equazione (5) verso tutte le altre pagine del grafo.

20

A non è irriducibile   Irriducibile significa che il grafo del web è fortemente

connesso.

  Definizione: G = (V, E) è fortemente connesso se e solo se, per ogni coppia di nodi i,j ∈ V, esiste un percorso da i to j.

  Perchè il grafo del web rappresentato da A non è irriducibile?

  per alcune coppie di nodi i,j non è detto che esista un percorso

21

A non è aperiodica  Uno stato i in una catena di Markov è

periodico se esiste un ciclo che la catena deve attraversare.

 Se uno stato non è periodico si dice aperiodico.

 Una catena di Markov è definita aperiodica se tutti gli stati sono aperiodici.

22

Esempio di stato periodico

Esempio: Catena di Markov di periodo 3.

23

Irriducibilità e aperiodicità: soluzione  Aggiungere un link da ogni pagina verso

tutte le altre e dare ad ogni link una probabilità di transizione molto bassa, controllata da un parametro d.

24

PageRank   Il coefficiente di ranking della pagina pi si ottiene

risolvendo il seguente sistema di eq. lineari:

con il seguente vincolo:

Vettore delle probabilità stazionarie a cui la catena di markov converge!!!