Il TrustRank è un algoritmo brevettato da Google, in parte basato sulla valutazione dei siti effettuata da esseri umani, progettato per risolvere il grosso problema dello spam presente negli indici dei motori di ricerca.
Uno dei problemi più grandi che i motori di ricerca si sono trovati a combattere negli ultimi anni è la crescita del fenomeno denominato spam. Lo spam, in questo contesto può essere a grandi linee definito come la pubblicazione di pagine web create con il solo scopo di ingannare gli algoritmi dei motori di ricerca.
Uno dei primi metodi utilizzati per fare spam è stato quello di inserire nelle pagine web del testo nascosto agli esseri umani ma visibile ai motori di ricerca (per esempio impostando il testo con lo stesso colore dello sfondo della pagina oppure usando alcune proprietà dei fogli di stile), così da ottenere buoni posizionamenti relativamente ad argomenti che effettivamente non avevano niente a che fare con il contenuto visibile delle pagine.
Un altro metodo molto popolare per fare spam è quello di creare decine, o anche centinaia, di pagine sostanzialmente inutili per gli utenti, ma tutte contenenti uno o più link verso una specifica pagina, la quale la quale vedrà migliorato il suo posizionamento nei motori di ricerca a causa dell’aumento di fattori come la link-popularity o il PageRank.
In effetti, quando un motore di ricerca si trova davanti ad un circuito di siti web fortemente linkati fra loro, deve effettuare la difficile scelta di stabilire se essi siano davvero siti che si citano per approfondimenti reciproci dell’argomento trattato oppure semplicemente un circuito di spam. Per un essere umano che “conosca il mestiere” è relativamente semplice capire se un sito effettua spam, osservando per esempio in che percentuale esista nelle pagine contenuto utile e testo invisibile, controllando la visibilità e l’effettiva natura dei link, i nomi assegnati a domini, file e cartelle, confrontando gli indirizzi IP dei documenti a cui i collegamenti puntano ed altri fattori ancora. Per un computer, al contrario, riconoscere lo spam è un compito decisamente difficile, tanto è vero che l’approccio finora utilizzato da parte dei motori di ricerca è quello di far eseguire ad un apposito staff di persone il monitoraggio dei risultati per individuare pagine che effettuano spam ed eliminarle dall’indice del motore. Molti motori di ricerca possiedono apposite interfacce pubbliche che permettono la segnalazione di spam direttamente allo staff del motore che, appena possibile, verifica la correttezza della segnalazione ed eventualmente prende i provvedimenti del caso. Il problema dell’eliminazione dello spam dai propri indici è così importante per i motori di ricerca che, in mancanza di meglio sono disposti ad utilizzare questo tipo di approccio, assai lento, costoso, e in definitiva molto poco efficiente.
Nel 2004 alcuni ricercatori del dipartimento di Computer Science della Stanford University hanno pubblicato uno studio dal titolo “Combating web spam with TrustRank” (Combattere lo spam con il TrustRank) ed il 16 marzo 2005 la tecnologia TrustRank è stata ufficialmente brevettata da Google.
L’algoritmo di TrustRank può essere utilizzato sia per suggerire automaticamente allo staff di esseri umani quali sono le pagine del web da controllare più attentamente perché “a rischio spam,” sia per generare un punteggio da usare in fase di ordinamento delle pagine allo scopo di compensare gli effetti negativi che lo spam ha avuto sull’efficacia di altri algoritmi, come quelli per l’analisi del contenuto o quello del PageRank.
Dal momento che identificare lo spam è molto difficile per un computer il TrustRank utilizza in parte l’intervento umano per addestrare l’algoritmo a riconoscerlo.
Indice contenuto
Come funziona il TrustRank
A grandi linee il funzionamento de TrustRank è questo.
1)L’algoritmo seleziona un insieme di pagine relativamente piccolo (“seed pages”, pagine seme) secondo criteri che spiegheremo in seguito, delle quali non si sa ancora se effettuino spam o meno.
2)Un essere umano esamina ad una ad una tutte le pagine dell’insieme e le divide in “buone” (pagine che non effettuano spam) e “cattive” (pagine che effettuano spam).
3)L’algoritmo processa l’intero indice del motore di ricerca ed assegna a ciascuna pagina che vi è contenuta un punteggio di “trust” (fiducia) basato sul grado di vicinanza alle pagine seme “buone” nel grafo del web.
Ora vedremo in dettaglio come vengono scelte le “pagine seme”, come viene effettuata effettua la loro valutazione ed ovviamente come viene propagata la “fiducia” (trust) dalle pagine buone a tutte quelle che a loro collegate, più o meno direttamente.
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.
Le pagine seme del TrustRank
La composizione dell’insieme di pagine seme influisce in modo determinante sui risultati restituiti dall’algoritmo TrustRank, inoltre conoscere i criteri di selezione delle pagine seme considerate buone può essere molto utile.
Finora parlando dell’algoritmo del TrustRank abbiamo dato per scontato che le pagine seme, quelle cioè che devono essere valutate manualmente dall’oracolo, fossero scelte casualmente. In realtà la scelta di un insieme di pagine seme piccolo ed efficiente è fondamentale per un buon funzionamento di TrustRank
L’insieme delle pagine seme deve rimanere piccolo per limitare le invocazioni dell’oracolo che, come visto sopra, sono dispendiose sia dal punto di vista del tempo che da quello delle risorse economiche. L’efficienza dell’insieme invece si identifica nella capacità delle pagine selezionate di consentire una buona propagazione della fiducia, attraverso i loro link in uscita, verso il maggior numero possibile di pagine buone e rilevanti.
Come abbiamo la fiducia viene propagata dalle pagine seme buone ad altre pagine, per cui un buon criterio iniziale per la scelta delle prime è che abbiano un alto numero di link in uscita. Implementando questo tipo di ragionamento possono essere selezionate pagine che contengono molti link uscenti che puntano verso pagine che a loro volta contengano molti link uscenti e così via.
La formula che viene fuori è quasi identica a quella del PageRank con l’unica differenza che in questo caso il punteggio non dipende dal numero di link in ingresso, bensì da quello dei link in uscita. Per questo viene definita “Page Rank inverso”. La formula del PageRank inverso, in effetti, non garantisce la massima copertura di pagine dell’indice, ma questa sarebbe matematicamente molto più complessa da calcolare mentre l’applicazione dell’algoritmo del PageRank è stata ottimizzata e perfezionata nel corso degli anni diventando estremamente efficiente.
Il PageRank inverso non è comunque l’unico sistema possibile per la scelta delle pagine seme. Un diverso tipo di approccio potrebbe per esempio mettere già in discussione che ogni pagina contenuta nell’indice del motore sia egualmente importante e che sia indifferente attribuire il punteggio di fiducia ad una piuttosto che ad un’altra. Al contrario può essere considerato preferibile assegnare il punteggio di fiducia alle pagine che hanno maggiore probabilità di apparire in buona posizione rispetto alle ricerche, perché sono quelle che verranno selezionate più spesso dagli utenti.
Google ordina le pagine basandosi sia sul loro contenuto che sul valore di PageRank, potrebbe quindi essere una buona strategia assegnare i punteggi di fiducia alle pagine con più alto PageRank. Inoltre, visto che sperimentalmente si può affermare che spesso le pagine con alto PageRank sono fortemente collegate fra loro la fiducia verrebbe propagata a pagine che a loro volta hanno buone probabilità di essere visualizzate dagli utenti del motore di ricerca e così via.
Nell’esperimento condotto dagli autori dello studio questi due metodi di selezione sono stati comparati utilizzando un grafo “ridotto” del web dove erano comunque presenti degli esempi dei principali tipi di spam. Il sistema che ha permesso di selezionare il miglior insieme di pagine seme è risultato essere il PageRank inverso (anche se la differenza nella qualità dei due insiemi non era enorme) che è quindi stato usato per il resto dell’esperimento.
La prima fase per la selezione delle pagine seme da sottoporre alla valutazione dell’oracolo è quindi consistita nel calcolo del PageRank inverso di tutte le pagine dell’indice del motore utilizzando un fattore di attenuazione di 0,85 (un classico nella letteratura relativa al PageRank ) ed effettuando 20 iterazioni che hanno permesso di ottenere un risultato sufficientemente stabile (vedi la formula originale del PageRank).
Dopo aver ordinato i siti in ordine di Pagerank inverso sono state scelti i primi 25.000 e su questi sono state applicate ulteriori operazioni automatiche di filtraggio allo scopo di ottenere un insieme più ridotto.
Nei 25.000 siti selezionati è stata infatti immediatamente rilevata una massiccia presenza di cloni della intera directory DMOZ realizzati al solo scopo di simulare dei contenuti di qualità o di ottenere un elevato punteggio HUB.
La tattica seguita per eliminare questo tipo di siti è stata quella di rimuovere dall’insieme tutti i siti che non fossero presenti in nessuna delle maggiori web directory. Questo tipo di filtro ha ridotto l’insieme a circa 7900 siti e facendo dei controlli a campione su quelli eliminati è stato accertato che pochissimi siti di qualità erano stati scartati.
Dei 7900 siti rimanenti sono stati esaminati manualmente i primi 1250 in ordine di PageRank inverso (questi rappresentano l’insieme “S”, vedi “L’algoritmo del Trustrank”), il che equivale a dire che la funzione “oracolo” è stata chiamata 1250 volte.
La funzione oracolo ha stabilito che 178 siti fra quelli esaminati erano esenti da spam e quindi sono andati a formare l’insieme delle pagine seme buone (S+).
Un “particolare” molto Interessante da notare è che i criteri con cui l’oracolo ha giudicato i siti sono stati estremamente rigorosi, infatti i siti scelti non risultavano soltanto esenti da spam, ma erano anche siti la cui gestione poteva essee ricondotta in maniera chiara ed univoca ad una istituzione di qualche tipo (es. governativa, mlitare, universitaria).Questo ultimo accorgimento è stato preso per garantire longevità all’insieme delle pagine seme, ipotizzando che i siti gestiti da una qualche organizzazione (ed i loro contenuti) siano più “stabili” e coerenti a medio-lungo termine.
Articolo originale di Stefano Becheroni