2 preliminare
2.1 web model
(quà ci sono un po' di cose matematiche, quindi provo a sintetizzare quello che ho capito io, Non necessariamente sarà corretto quello che dico)
Noi modelleremo il web come un grafo G=(V, E) che consiste in un set V di N pagine (vertici) ed un set E di
link diretti (edges) che connettono le pagine. Praticamente una pagina web p può avere multipli hyperlink
HTML ad un'altra pagina q. in questo caso noi compattiamo questi hyperlink multipli in un singolo link (formula matematica vedi documento originale). Rimuoveremo inoltre i link verso il sito stesso(self hyperlinks). La figura 1 rappresenta un grafo web molto semplice di quattro pagine e quattro links. (per il nostro esperimento nella sezione 6, distribuiremo i siti web come contrapposizione alle pagine web individuali. Comunque il nostro
algoritmo puòessere trasferito anche al caso in cui i vertici del grafo siano interi siti.
Ogni pagina ha alcuni links in ingresso o inlinks, ed alcuni link in uscita o outlinks.
(adesso spiega la lunga formula matematica che segue nel documento originale, lascio agli esperti la spiegazione di queste formule io mi limito a tradurre il testo dove si parla in "Chiaro" ).
----snip--------
Le pagine che non hanno inlinks sono chiamate unreferenced pages. Le pagine senza outlinks sono chiamate non-referencing pages. Le pagine che allo stesso tempo sono ureferenced e non-referencing sono chiamate isolated (isolate).
La pagina 1 nella figura 1 è una unreferencing mentre la 4 è non-referencing.
(NDT: Adesso ci sono frmule matematiche e taglio)
-------snip--------
2.2
Page Rank
il page rank è il noto algoritmo che usa le informazioni dei link per assegnare un punteggio globale di importanza a tutte le pagine del web.
siccome il nostro algoritmo ha una relazione con il page rank questa sezione offre una breve descrizione di esso.
L'intuizione alla base del Page Rank è che una pagina è importante se altre diverse pagine importanti puntano verso di essa.
Corrispondentemente, il Page Rank è basato su un mutuo rafforzamento tra le pagine: l'importanza di certe pagine influenza ed è influenzata dall'importanza di altre pagine.
(NDT: Adesso c'e la formula del page rank e la sua spiegazione matematica)
----snip-----
Da questo momento il punteggio di alcune pagine p è la somma di due componenti, una parte del punteggioo viene dalle pagine che puntano verso p, ed un'altra parte (statica) del punteggio è uguale per tutte le pagine web.
Il punteggio di page rank può essere stimato iterativamente, per esempio con il metodo jacobi. Allo stesso tempo, in senso strettamente matematico,
l'iterazione può andare verso la convergenza, ma in pratica è molto comunemente usato un numero fisso di M iterazioni.
E' importante notare che mentre il normale algoritmo di Page Rank assegna lo stesso valore statico ad ogni pagina, la versione Bisead (non so come tradurlo suppongo una cosa del tipo "a due valori") del page Rank può sottrarsi a questa regola.
(NDT: adesso c'una equazione e la spiega così)
Il vettore d è un vettore di distribuzione statica arbitrario, non negativo che si somma ad uno. il vettore d può essere usato per assegnare un valore statico Non-zero solamente ad un set di pagine "speciali".
Il punteggio di tali pagine speciali viene esteso durante l'iterazione con le pagine alle quali puntano.
---------------------------------------------------------------------------------
3 assegnazione del
TRUST (fiducia, credito)
3.1 Oracle (oracolo,previsione) e funzioni di
Trust
Come detto nella sezione 1 stabilire se una pagina è
spam è una cosa soggettiva e richiede la valutazione umana. Noi formalizziamo la nozione di controllo umano con una oracle function O sopra tutte le pagine (formula matematica)
---snip-----
La figura 2 rappresenta un piccolo web di sette pagine dove le pagine buone sono rappresentate in bianco e le pagine cattive sono nere. Per questo esempio chiamando l'oracle nella pagina 1 alla 4 produrrà un valore di 1.
La chiamata all'oracle è dispendiosa e impiega tempo, così noi ovviamente non vogliamo usare l'oracle function in tutte le pagine allora il nostro obbiettivo è di selezionare, ad esempio, chiedendo l'intervento umano di un esperto che valute solo alcune delle pagine web.
Per scoprire le pagine buone senza invocare l'oracle function, ci dovremo fidare di una importante osservazione empirica che chiamiamo "approximate isolation" di un buon set: Le pagine buone raramente puntano a pagine cattive, questa nozione è onestamente intuitiva -le pagine cattive sono costruite per imbrogliare i
motori di ricerca non per fornire informazioni utili. D'altro canto le persone che creano pagine buone hanno poche ragioni per puntare alle pagine cattive.
Per quanto i creatori di buone pagine web possono a volte essere ingannati, così noi potremo trovare alcune pagine buone che puntano a pagine cattive nel web. (nella figura 2 mostriamo uno di questi link dalla pagina 4 alla pagina 5 segnato con un asterisco).
Consideriamo il seguente esempio:
Prendiamo un buon, ma non moderato, message board, lo spammer può includere il l'URL dellla sua pagina spam come parte di un messaggio che sembra innocente.
Di conseguenza la pagina buona della message board avrà un link ad una pagina cattiva.
A volte anche alcuni siti di spam offrono cò che viene chiamato vaso di miele, cioè un insieme di pagine che forniscono utili informazioni ma che hanno anche dei link verso le loro pagine di spam, il vaso di miele attrae le persone a puntare verso di esso aumentando il rank della pagina spam.
Da notare che la relazione inversa (NDT:non sono sicuro di avere tradotto bene)all'isolamento approssimato no è necessariamente influente: le pagine spam possono infatti fare spesso un link alle pagine buone. Per esempio i creatori di pagine spam puntano ad importanti pagine buone al fine di creare un "vaso di miele" oppure sperando che molti outlinks potranno aumentare lo score della loro pagina.
Per valutare le pagine senza fare assegnamento su O, noi stimeremo che con tutta probabilità quello che dà la pagina p sia buono.
Più formalmente definiremo la Trust function T che produrrà un range di valori compreso tra 0 (cattivo) e 100 (buono). Idealmente , per ogni pagina p, T(p) ci darà la probabilità che p sia buona
Ideal Trust Property
(c'è una formula e poi la spiega)
Per illustrare ciò, consideriamo di avere un set di 100 pagine e diciamo che il trust score di ognuna di queste pagine possa essere 0.7.
Adesso supponiamo di valutare tutte le 100 pagine con la oracle function.
Allora se T lavora correttamente, per 70 delle pagine in esame l'oracle score potrà essere 1 e per le rimanenti 30 sarà 0.
In pratica è molto difficile arrivare ad una funzione T con le proprietà dette prima.
Per quanto, anche se T non misura accuratamente la probabilità che una pagina sia buona ci può essere utile in una funzione che possa ordinare le pagine secondo la loro probabilità di essere buone.
Questo è, se noi diamo una coppia di pagine p e q, e p ha un trust score basso quanto q , questo indicherà che p è probabilmente meno buona di q.
Similmente una funzione sarà utile per l'ordinamento dei risultati di una ricerca dando la preferenza alle pagine che sono più probabilmente buone.
(adesso definiscono la Trust Function e mettono un po' di formule)
------snip------
