Come vengono classificate le pagine web
Algoritmo PageRank
utilizzato da Google Search per classificare le pagine
PageRank ( PR ) è un algoritmo utilizzato da Google Search per classificare le pagine web nei risultati dei motori di ricerca. Prende il nome sia dal termine "pagina web" che dal co-fondatore Larry Page. Il PageRank è un modo per misurare l'importanza delle pagine del sito web. Secondo Google:
il PageRank funziona contando il numero e la qualità dei link a una pagina per determinare una stima approssimativa dell'importanza del sito web. L'assunto di base è che è probabile che i siti web più importanti ricevano più link da altri siti web. [1]
Attualmente, il PageRank non è l'unico algoritmo utilizzato da Google per ordinare i risultati di ricerca, ma è il primo algoritmo utilizzato dall'azienda, ed è il più conosciuto. [2] [3] A partire dal 24 settembre 2019, tutti i brevetti associati al PageRank sono scaduti. [4]
Descrizione
PageRank è un algoritmo di analisi dei link e assegna un peso numerico a ciascun elemento di un insieme ipercollegato di documenti, come il World Wide Web, con lo scopo di "misurare" la sua importanza relativa all'interno dell'insieme. L'algoritmo può essere applicato a qualsiasi insieme di entità con quotazioni e riferimenti reciproci. Il peso numerico che assegna a un dato elemento E è indicato come PageRank di E e indicato da
A Il PageRank risulta da un algoritmo matematico basato sul webgraph, creato da tutte le pagine del World Wide Web come nodi e dai collegamenti ipertestuali come bordi, prendendo in considerazione hub di autorità come cnn.com o mayoclinic.org. Il valore di ranking indica l'importanza di una determinata pagina. Un collegamento ipertestuale a una pagina conta come un voto di sostegno. Le Il PageRank di una pagina è definito in modo ricorsivo e dipende dal numero e dalla metrica PageRank di tutte le pagine che vi si collegano ("link in entrata"). Una pagina a cui sono collegate molte pagine con un PageRank elevato riceve un ranking elevato.
Numerosi articoli accademici riguardanti il PageRank sono stati pubblicati dopo l'articolo originale di Page e Brin. [5] In pratica, il concetto di PageRank può essere vulnerabile alla manipolazione. Sono state condotte ricerche per identificare le classifiche del PageRank falsamente influenzate. L'obiettivo è quello di trovare un mezzo efficace per ignorare i link provenienti da documenti con PageRank falsamente influenzato. [6]
Altri algoritmi di ranking basati su link per le pagine Web includono l'algoritmo HITS inventato da Jon Kleinberg (utilizzato da Teoma e ora Ask.com), il progetto IBM CLEVER, l'algoritmo TrustRank, l'algoritmo Hummingbird, [7] e l'algoritmo SALSA. [8]
Il
problema degli autovalori alla base dell'algoritmo di PageRank è stato riscoperto in modo indipendente e riutilizzato in molti problemi di punteggio. Nel 1895, Edmund Landau suggerì di usarlo per determinare il vincitore di un torneo di scacchi. [9] [10] Il problema degli autovalori è stato suggerito anche nel 1976 da Gabriel Pinski e Francis Narin, che hanno lavorato su riviste scientifiche di classificazione scientometrica, [11] nel 1977 da Thomas Saaty nel suo concetto di Processo di Gerarchia Analitica che ponderava le scelte alternative, [12] e nel 1995 da Bradley Love e Steven Sloman come modello cognitivo per i concetti, l'algoritmo di centralità. [13] [14]
Un motore di ricerca chiamato "RankDex" di IDD Information Services, progettato da Robin Li nel 1996, ha sviluppato una strategia per il punteggio del sito e il page-ranking. [15] Li ha fatto riferimento al suo meccanismo di ricerca come "analisi dei link", che consisteva nel classificare la popolarità di un sito web in base a quanti altri siti si erano collegati ad esso. [16] RankDex, il primo motore di ricerca con algoritmi di page-ranking e site-score, è stato lanciato nel 1996. [17] Li ha depositato un brevetto per la tecnologia in RankDex nel 1997; È stato concesso nel 1999. [18] In seguito lo ha usato quando ha fondato Baidu in Cina nel 2000. [19] [20] Il fondatore di Google, Larry Page, ha fatto riferimento al lavoro di Li come citazione in alcuni dei suoi brevetti statunitensi per PageRank. [21] [17] [22]
Larry Page e Sergey Brin hanno sviluppato PageRank presso la Stanford University nel 1996 come parte di un progetto di ricerca su un nuovo tipo di motore di ricerca. Un'intervista con Héctor García-Molina, professore di informatica a Stanford e consulente di Sergey, [23] fornisce informazioni di base sullo sviluppo dell'algoritmo di page-rank. [24] Sergey Brin ha avuto l'idea che le informazioni sul web potessero essere ordinate in una gerarchia per "link popularity": una pagina si posiziona più in alto quanto più ci sono link ad essa. [25] Il sistema è stato sviluppato con l'aiuto di Scott Hassan e Alan Steremberg, entrambi citati da Page e Brin come fondamentali per lo sviluppo di Google. [5] Rajeev Motwani e Terry Winograd sono co-autori con Page e Brin del primo articolo sul progetto, che descrive il PageRank e il prototipo iniziale del motore di ricerca Google, pubblicato nel 1998. [5] Poco dopo, Page e Brin fondarono Google Inc., la società dietro il motore di ricerca Google. Sebbene sia solo uno dei tanti fattori che determinano il posizionamento dei risultati di ricerca di Google, il PageRank continua a fornire la base per tutte le ricerche web di Google utensileria. [26]
Il nome "PageRank" gioca sul nome dello sviluppatore Larry Page, così come sul concetto di pagina web. [27] [28] La parola è un marchio di Google e il processo PageRank è stato brevettato (brevetto USA 6.285.999). Tuttavia, il brevetto è assegnato alla Stanford University e non a Google. Google ha i diritti di licenza esclusivi sul brevetto della Stanford University. L'università ha ricevuto 1,8 milioni di azioni di Google in cambio dell'uso del brevetto; ha venduto le azioni nel 2005 per 336 milioni di dollari. [29] [30]
Il PageRank è stato influenzato dall'analisi delle citazioni, sviluppata da Eugene Garfield negli anni '50 presso l'Università della Pennsylvania, e dall'Hyper Search, sviluppata da Massimo Marchiori presso l'Università di Padova. Nello stesso anno in cui è stato introdotto il PageRank (1998), Jon Kleinberg ha pubblicato il suo lavoro su HITS. I fondatori di Google citano Garfield, Marchiori e Kleinberg nei loro documenti originali. [5] [31]
Algoritmo: l'algoritmo
PageRank produce una distribuzione di probabilità utilizzata per rappresentare la probabilità che una persona che clicca casualmente sui link arrivi a una determinata pagina. Il PageRank può essere calcolato per raccolte di documenti di qualsiasi dimensione. In diversi articoli di ricerca si presume che la distribuzione sia equamente divisa tra tutti i documenti della collezione all'inizio del processo computazionale. I calcoli del PageRank richiedono diversi passaggi, chiamati "iterazioni", attraverso la raccolta per regolare i valori approssimativi del PageRank in modo che riflettano più da vicino il vero valore teorico.
Una probabilità è espressa come un valore numerico compreso tra 0 e 1. Una probabilità di 0,5 è comunemente espressa come una "probabilità del 50%" che accada qualcosa. Quindi, un documento con un PageRank di 0,5 significa che c'è una probabilità del 50% che una persona che clicca su un link casuale venga indirizzata a detto documento.
Algoritmo semplificato
Supponiamo un piccolo universo di quattro pagine web: A , B , C e D . I collegamenti da una pagina a se stessa vengono ignorati. Più link in uscita da una pagina all'altra vengono trattati come un singolo link. Il PageRank viene inizializzato sullo stesso valore per tutte le pagine. Nella forma originale di PageRank, la somma di PageRank su tutte le pagine era il numero totale di pagine sul Web in quel momento, quindi ogni pagina in questo esempio avrebbe un valore iniziale di 1. Tuttavia, le versioni successive di PageRank e il resto di questa sezione presuppongono una distribuzione di probabilità compresa tra 0 e 1. Pertanto, il valore iniziale per ogni pagina in questo esempio è 0,25.
Il PageRank trasferito da una determinata pagina agli obiettivi dei suoi link in uscita alla successiva iterazione viene diviso equamente tra Tutti i link in uscita.
Se gli unici collegamenti nel sistema fossero dalle pagine B , C e D ad A , ogni collegamento trasferirebbe 0,25 PageRank ad A all'iterazione successiva, per un totale di 0,75.
Supponiamo invece che la pagina B abbia un collegamento alle pagine C e A , la pagina C abbia un collegamento alla pagina A e la pagina D abbia collegamenti a tutte e tre le pagine. Pertanto, alla prima iterazione, la pagina B trasferirebbe metà del suo valore esistente (0,125) alla pagina A e l'altra metà (0,125) alla pagina C . La pagina C trasferirebbe tutto il suo valore esistente (0,25) all'unica pagina a cui si collega, A . Poiché D aveva tre collegamenti in uscita, trasferiva un terzo del suo valore esistente, o circa 0,083, ad A . Al termine di questa iterazione, la pagina A avrà un PageRank di circa 0,458.
In altre parole, il PageRank conferito da un link in uscita è uguale al punteggio PageRank del documento diviso per il numero di link in uscita L( ) .
Nel caso generale, il valore PageRank per qualsiasi pagina u può essere espresso come:
- ,
cioè il valore PageRank per una pagina u dipende dai valori PageRank per ogni pagina v contenuti nell'insieme B u (l'insieme contenente tutte le pagine che collegano alla pagina u ), diviso per il numero L ( v ) di collegamenti dalla pagina v .
Fattore di smorzamento
La teoria del PageRank sostiene che un navigatore immaginario che sta cliccando casualmente sui link alla fine smetterà di cliccare. La probabilità, in qualsiasi fase, che la persona continui a seguire i link è un fattore di smorzamento d . La probabilità che invece saltino a qualsiasi La pagina casuale è 1 - d . Vari studi hanno testato diversi fattori di smorzamento, ma generalmente si presume che il fattore di smorzamento sarà impostato intorno a 0,85. [5]
Il fattore di smorzamento viene sottratto da 1 (e in alcune varianti dell'algoritmo, il risultato viene diviso per il numero di documenti ( N ) nella raccolta) e questo termine viene quindi aggiunto al prodotto del fattore di smorzamento e alla somma dei punteggi PageRank in entrata. Cioè,
quindi il PageRank di qualsiasi pagina deriva in gran parte dai PageRank di altre pagine. Il fattore di smorzamento regola il valore derivato verso il basso. L'articolo originale, tuttavia, dava la seguente formula, che ha portato a una certa confusione:
la differenza tra loro è che i valori di PageRank nella prima formula sommano a uno, mentre nella seconda formula ogni PageRank viene moltiplicato per N e la somma diventa N . Un'affermazione nell'articolo di Page e Brin che "la somma di tutti i PageRank è uno" [5] e le affermazioni di altri dipendenti di Google [32] supportano la prima variante della formula di cui sopra.
Page e Brin hanno confuso le due formule nel loro articolo più popolare "The Anatomy of a Large-Scale Hypertextual Web Search Engine", dove hanno erroneamente affermato che quest'ultima formula formava una distribuzione di probabilità sulle pagine web. [5]
Google ricalcola i punteggi del PageRank ogni volta che esegue la scansione del Web e ricostruisce il suo indice. Man mano che Google aumenta il numero di documenti nella sua raccolta, l'approssimazione iniziale del PageRank diminuisce per tutti i documenti.
La formula utilizza un modello di un navigatore casuale che raggiunge il sito di destinazione dopo diversi clic, quindi passa a una pagina casuale. Il valore di PageRank di una pagina riflette la probabilità che il navigatore casuale atterri su quella pagina cliccando su un link. Può essere intesa come una catena di Markov in cui gli stati sono pagine e le transizioni sono i collegamenti tra le pagine - tutte ugualmente probabili.
Se una pagina non ha collegamenti ad altre pagine, diventa un sink e quindi termina il processo di navigazione casuale. Se l'utente casuale arriva a una pagina sink, sceglie un altro URL a caso e continua a navigare di nuovo.
Quando si calcola il PageRank, si presume che le pagine senza link in uscita si colleghino a tutte le altre pagine della raccolta. I loro punteggi di PageRank sono quindi divisi equamente tra tutte le altre pagine. In altre parole, per essere onesti con le pagine che non sono sink, queste transizioni casuali vengono aggiunte a tutti i nodi del Web. Questa probabilità residua, d , è solitamente impostata a 0,85, stimata dalla frequenza con cui un navigatore medio utilizza la funzione di segnalibro del proprio browser. Quindi, l'equazione è la seguente:
dove sono le pagine in esame, è l'insieme di pagine che si collegano a , è il numero di collegamenti in uscita sulla pagina e è il numero totale di pagine.
I valori di PageRank sono le voci dell'autovettore destro dominante della matrice adiacente modificata ridimensionata in modo che ogni colonna si aggiunga a una. Questo rende il PageRank una metrica particolarmente elegante: l'autovettore è
dove R è la soluzione dell'equazione
dove la funzione di adiacenza è il rapporto tra il numero di link in uscita dalla pagina j alla pagina i e il numero totale di link in uscita della pagina j. La funzione di adiacenza è 0 se la pagina non si collega a , e normalizzata in modo tale che, per ogni j
- ,
cioè la somma degli elementi di ogni colonna sia 1, quindi la matrice è una matrice stocastica (per maggiori dettagli vedere la sezione di calcolo di seguito). Quindi questa è una variante del Misura di centralità autovettoriale utilizzata comunemente nell'analisi delle reti.
A causa dell'ampio autogap della matrice di adiacenza modificata di cui sopra, [33] i valori dell'autovettore PageRank possono essere approssimati entro un alto grado di precisione in poche iterazioni.
I fondatori di Google, nel loro articolo originale, [31] hanno riferito che l'algoritmo PageRank per una rete composta da 322 milioni di collegamenti (in-edge e out-edges) converge entro un limite tollerabile in 52 iterazioni. La convergenza in una rete di dimensioni dimezzate ha richiesto circa 45 iterazioni. Attraverso questi dati, hanno concluso che l'algoritmo può essere scalato molto bene e che il fattore di scala per reti estremamente grandi sarebbe approssimativamente lineare in , dove n è la dimensione della rete.
Come risultato della teoria di Markov, si può dimostrare che il PageRank di una pagina è la probabilità di arrivare a quella pagina dopo un gran numero di clic. Questo accade per essere uguale a dove è l'aspettativa del numero di clic (o salti casuali) necessari per tornare dalla pagina a se stessa.
Uno dei principali svantaggi del PageRank è che favorisce le pagine più vecchie. Una nuova pagina, anche molto buona, non avrà molti link a meno che non faccia parte di un sito esistente (un sito è un insieme di pagine densamente collegate, come Wikipedia).
Diverse strategie sono state proposte per accelerare il calcolo del PageRank. [34]
Varie strategie per manipolare il PageRank sono state impiegate in sforzi concertati per migliorare il posizionamento nei risultati di ricerca e monetizzare i link pubblicitari. Queste strategie hanno fortemente influenzato l'affidabilità del concetto di PageRank, che pretende di determinare quali documenti sono effettivamente molto apprezzati dalla comunità Web.
Dal dicembre 2007, anno in cui è iniziato penalizzando attivamente i siti che vendono link di testo a pagamento, Google ha combattuto le link farm e altri schemi progettati per gonfiare artificialmente il PageRank. Il modo in cui Google identifica le link farm e altri strumenti di manipolazione del PageRank è tra i segreti commerciali di Google.
Il PageRank
può essere calcolato in modo iterativo o algebrico. Il metodo iterativo può essere visto come il metodo di iterazione della potenza [35] [36] o il metodo della potenza. Le operazioni matematiche di base eseguite sono identiche.
Iterativa
A , si assume una distribuzione di probabilità iniziale, di solito
- .
dove N è il numero totale di pagine, e è la pagina i al tempo 0.
Ad ogni passo temporale, il calcolo, come descritto sopra, produce
dove d è il fattore di smorzamento,
o nella notazione matriciale
| , | 1 |
dove e è la colonna vettore di lunghezza contenente solo uno.
La matrice è definita come
cioè
- ,
dove denota la matrice di adiacenza del grafo ed è la matrice diagonale con gli outdegrees nella diagonale.
Il calcolo della probabilità viene effettuato per ogni pagina in un punto temporale, quindi ripetuto per il punto temporale successivo. Il calcolo termina quando per qualche piccolo
- ,
cioè quando si assume la convergenza.
Metodo di potenza
Se la matrice è una probabilità di transizione, cioè colonna-stocastica ed è una distribuzione di probabilità (cioè, , dove è la matrice di tutti gli uno), allora l'equazione ( 2 ) è equivalente a
| . | 3 |
Quindi il PageRank è l'autovettore principale di . Un modo semplice e veloce per calcolare questo è utilizzare Il metodo della potenza: partendo da un vettore arbitrario , l'operatore viene applicato in successione, cioè
- fino
a
- .
Si noti che nell'equazione ( 3 ) la matrice sul lato destro della parentesi può essere interpretata come
- ,
dove è una distribuzione di probabilità iniziale. n il caso corrente
- .
Infine, se ha colonne con solo valori zero, dovrebbero essere sostituite con il vettore di probabilità iniziale . In altre parole,
- ,
dove la matrice è definita come
- ,
con
In questo caso, i due calcoli precedenti che utilizzano danno lo stesso PageRank solo se i loro risultati sono normalizzati:
- .
Implementazione
Python
Variazioni
Il PageRank di un grafo non orientato è statisticamente vicino alla distribuzione dei gradi del grafo, [37] ma generalmente non sono identici: If è il vettore PageRank definito sopra, e è il vettore
dove denota il grado di vertice , e è l'insieme di spigoli del grafo, allora, con , [38] mostra che:
cioè, il PageRank di un grafo non orientato è uguale al vettore di distribuzione dei gradi se e solo se il grafo è regolare, cioè ogni vertice ha lo stesso grado.
Classificazione di oggetti di due tipi
Una generalizzazione del PageRank per il caso di classificazione di due gruppi di oggetti interagenti è stata descritta da Daugulis. [39] Nelle applicazioni può essere necessario modellare sistemi con oggetti di due tipi in cui una relazione ponderata è definita su coppie di oggetti. Questo porta a considerare i grafi bipartiti. Per tali grafi possono essere definite due matrici irriducibili positive o non negative correlate corrispondenti a insiemi di partizioni di vertici. Si possono calcolare le classifiche degli oggetti in entrambi i gruppi come autovettori corrispondenti agli autovalori positivi massimi di queste matrici. Gli autovettori normati esistono e sono unici per il teorema di Perron o Perron-Frobenius. Esempio: consumatori e prodotti. La relazione peso è il tasso di consumo del prodotto.
Sarma et al. descrivono due algoritmi distribuiti basati su walk casuali per il calcolo del PageRank dei nodi in una rete. [40] Un algoritmo esegue round con alta probabilità su qualsiasi grafo (diretto o non diretto), dove n è la dimensione della rete ed è la probabilità di reset ( , che è chiamata fattore di smorzamento) utilizzata nel calcolo del PageRank. Presentano anche un algoritmo più veloce che esegue i round in grafi non orientati. In entrambi gli algoritmi, ogni nodo elabora e invia un numero di bit per round che sono polilogaritmici in n, la dimensione della rete.
Google Toolbar
La Google Toolbar