L’algoritmo del TrustRank

Il TrustRank riesce a identificare nel web le pagine che non effettuano spam partendo da un piccolo insieme di pagine identificate come buone da un essere umano. Vediamo come è stato sviluppato l’algoritmo che svolge questo compito.

Iniziamo l’analisi dell’algoritmo supponendo per semplicità che le pagine seme vengano scelte in maniera casuale, in realtà non è così, ma torneremo su questo argomento in seguito. Una volta selezionate le pagine seme esse devono essere esaminate da un esperto umano per stabilire quali sono “buone” e quali “cattive”.

Per convenienza, nello studio che stiamo analizzando, questa fase viene equiparata ad una funzione “booleana” che restituisce un valore “0” se la pagina effettua spam ed un valore “1” se invece la pagina è buona. Questa funzione viene chiamata “Oracolo”. Usare la funzione Oracolo è costoso in termini di tempo e di risorse umane, perciò le chiamate alla funzione oracolo devono venire ridotte il più possibile.

Per poter identificare le pagine buone nel web senza dover invocare ogni volta l’oracolo gli ideatori del trutRank fanno affidamento su una osservazione empirica che sta alla base di tutto l’algoritmo: le pagine “buone” tendenzialmente non contengono link che puntano alle pagine “cattive”.

Le pagine cattive sono costruite per ingannare i motori di ricerca e non contengono informazioni utili agli esseri umani, per questo nessun webmaster che crea siti “buoni” ha una ragione per inserirvi dei link che vi puntano. In realtà nel web esistono alcuni link da pagine buone a pagine cattive perchè la quasi totalità di essi è ottenuta con l’inganno. Pensate ad esempio a dei siti di qualità che abbiano però delle chat non moderate o dei guestbook non controllati: queste aree potrebbero essere usate per effettuare spam inserendovi commenti contenenti dei link verso le pagine che si vogliono spingere. Oppure dei webmaster malintenzionati possono creare siti con contenuto valido, inserendovi dei link nascosti a pagine che effettuano spam, al solo scopo di ottenere backlink spontanei, per spingere queste ultime attraverso i siti “buoni” che sono serviti da esca (in queso caso i siti buoni sono chiamati “honey pots”, vasi di miele).

E’ importante capire che,a differenza dei siti buoni, quelli che effettuano spam non si linkano soltanto fra loro, anzi, molto spesso contengono numerosi link a siti di alta qualità che servono a valorizzare i contenuti dei “vasi di miele” e ad aumentare il punteggio hub nei vari motori di ricerca. Quindi per poter esprimere un giudizio su una pagina senza dover usare la funzione Oracolo si cerca di determinare la probabilità che una pagina sia buona basandosi sul grado di vicinanza, in termini di link, all’insieme “relativamente isolato” di pagine buone.

Una funzione “Trust” ideale dovrebbe fornire per ogni pagina del web la probabilità assoluta che essa sia buona, nella realtà questo è molto difficile da ottenere, ma per gli scopi che l’algoritmo si prefigge è sufficiente che svolga due compiti più semplici:

1) Ordinare le pagine contenute nell’indice del motore secondo la probabilità che queste siano buone. Per questo è sufficiente che i rapporti fra i valori di probabilità assegnati alle varie pagine siano corretti, anche se non sono calcolati in modo assoluto.

2) Introdurre un valore di soglia per il quale tutte le pagine che superano un certo valore di probabilità di essere buone vengono considerate buone. Questo serve ad individuare un sottoinsieme di pagine quasi sicuramente esenti da spam.

Per capire meglio l’algoritmo finale del TrustRank iniziamo ad esaminare alcuni approcci di base e, analizzandone i difetti arriviamo per gradi alla struttura finale della funzione che assegna il valore di “Trust” alle pagine.

Se all’inizio viene stabilito di voler usare la funzione oracolo un numero massimo “L” di volte, deve essere per prima cosa selezionato un insieme “S” composto da un numero “L” di pagine seme e poi usato l’oracolo su ciascuna di queste. Al termine l’Oracolo avrà identificato un sottoinsieme di pagine buone S+ ed uno di pagine cattive S-.

A questo punto la funzione “Trust” processa l’indice del motore di ricerca assegnando un valore 1 alle pagine appartenenti a S+, un valore 0 a tutte le pagine appartenenti ad S- e un valore 0,5 a tutte le pagine di cui non si sa ancora niente perché non appartengono all’insieme S esaminato dall’oracolo. Questa parte della funzione viene definita “Ignorant Trust” perché il valore di fiducia ottenuto per le pagine dell’indice non tiene ancora conto delle relazioni fra di esse.

Basandosi sull’osservazione fatta precedentemente, sul relativo “isolamento” delle pagine buone rispetto a quelle cattive, il sistema più semplice per propagare la fiducia dalle pagine seme alle altre è quello di assegnare un valore di 1 a tutte le pagine raggiungibili entro un numero M di passi (link) da una delle pagine seme.

Esaminando gli effetti causati da queso tipo di propagazione, però, si evidenzia subito un grosso problema: anche se non è certo che le pagine a cui viene assegnata la fiducia siano effettivamente buone questa viene comunque trasmessa interamente. Ciò comporta che, nel momento in cui l’algoritmo incontra uno dei rari link che puntano da una pagina buona ad una cattiva, la pagina cattiva acquista lo status di “buona” e può a sua volta propagare interamente la fiducia ad altre pagine che effettuano SPAM.

Gli autori dello studio hanno così ritenuto ragionevole assumere che più ci si allontana dall’insieme di pagine seme buone e più aumenta la probabilità di trovare un link ad una pagina cattiva; quindi hanno inserito nell’algoritmo un sistema cosiddetto di “trust attenuation”, per diminuire la quantità di fiducia che una pagina passa alle altre pagine, via via che ci si allontana dall’insieme originale delle pagine seme buone (S+). Questo tipo di meccanismo può essere realizzato in modi diversi.

Nella figura A vediamo uno schema chiamato “Trust dampening”. La pagina 1 appartiene all’insieme S+ di pagine insieme buone e contiene un link che punta alla pagina 2 alla quale passa un valore di fiducia β minore di 1. Alla pagina 3 che invece è raggiungibile direttamente dalla pagina 2 viene trasmesso un valore di fiducia uguale a β*β e così via. Nel caso in cui le pagine ricevano fiducia da link multipli, può essere assegnato ad esse il valore maggiore trasmesso da una singola pagina oppure una media di tutti i valori.

Il secondo schema, illustrato in figura B viene chiamato invece “Trust splitting” e si basa sul fatto che la cura con cui vengono aggiunti dei link nelle pagine web è spesso inversamente proporzionale al loro numero. Se una pagina buona contiene pochi link questi molto probabilmente punteranno a pagine a loro volta buone, mentre se la stessa pagina contiene centinaia di link è più probabile che alcuni di essi puntino a pagine cattive.

Quindi se una pagina buona ha un valore di fiducia T e contiene ω link ad altre pagine, ad ognuna di queste sarà trasmesso un valore di fiducia uguale a T/ω. In questo caso i punteggi che una pagina riceve da link multipli provenienti da pagina buone vengono sommati. In figura B la pagina 1, appartenente all’insieme di pagine seme buone S+, contiene due link in uscita, così assegna a ciascuna delle pagine a cui punta un valore pari a 0,5 (la metà della sua fiducia). Anche la pagina 2 appartiene all’insieme di pagine seme buone S+, ma contiene tre link in uscita, quindi trasmette a ciascuna delle pagine a cui punta un valore pari a 0,333 (un terzo della sua fiducia). La pagina 3 riceverà quindi una fiducia totale pari a 0,5+0,333=0,833.

Questi due approcci possono anche essere combinati. In questo caso, sempre riferendosi alla fig.B la pagina 3 riceve un punteggio di β*(0,5+0,333).

Per la formulazione finale dell’algoritmo di TrustRank gli autori hanno deciso di propagare la fiducia usando una versione “personalizzata” dell’algoritmo di PageRank dove, ovviamente, il valore calcolato per ogni pagina, ad ogni iterazione dell’algoritmo, non è il PR ma la fiducia. Il passaggio della fiducia dalle pagine seme buone avviene sostituendo il vettore risultante dal calcolo della funzione di “Ignorant Trust” (vedi sopra) al fattore di dispersione uniforme usato nel calcolo del PageRank. Questa soluzione è stata scelta perché, oltre ad essere funzionale, permette agli autori di sfruttare i risultati dei molteplici studi effettuati negli anni per ottimizzare il calcolo del PageRank, inoltre utilizzi personalizzati dell’algoritmo del PageRank che sfruttassero fattori di distribuzione non uniformi erano stati ipotizzati già anni fa da Page e Brin, vedi per esempio “The PageRank Citation Ranking Bringing Order to the Web” al capitolo 6.

Gli ideatori dell’algoritmo hanno effettuato degli esperimenti pratici utilizzando l’indice dei documenti indicizzati da Altavista nell’Agosto 2003. Allo scopo di ridurre i tempi e le risorse necessarie per effettuare i calcoli gli esperimenti sono stati fatti lavorando al livello dei siti e non dei singoli documenti. Utilizzando algoritmi già sviluppati da Altavista i miliardi di documenti appartenenti all’indice sono stati raggruppati in 31.003.946 siti web. Dopo il raggruppamento quando nei documenti che formano sito A vengono rilevati uno o più link che puntano verso documenti del sito B viene conteggiato un solo link fra i due siti.

Prima di poter procedere all’applicazione dell’algoritmo ed alla valutazione dei risultati ottenuti restava da sciogliere un nodo molto delicato: identificare il criterio migliore per la selezione delle pagine seme. L’insieme di pagine seme deve essere tale da permettere all’algoritmo di TrustRank di identificare altre pagine buone in modo efficace, inoltre deve rimanere relativamente piccolo per limitare le chiamate dell’oracolo. Vedremo nel prossimo articolo come gli autori dello studio hanno affrontato questo problema.

Ultima modifica: 30/11/2005 - 10:17