Centralità PageRank
- Introdotto da
- Page, Brin, Motwani & Winograd
- Anno
- 1999
- Tipo
- Iterative link-based centrality algorithm
- Famiglia
- Centrality
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
PageRank è un algoritmo di centralità basato sui collegamenti che assegna un punteggio di importanza a ciascun nodo in un grafo orientato misurando quanti nodi di alta qualità puntano ad esso.
Introdotto da Larry Page, Sergey Brin, Rajeev Motwani e Terry Winograd alla Stanford University nel 1999, divenne il fondamento matematico del motore di ricerca Google e rimane uno degli algoritmi più influenti nella scienza delle reti e nel recupero dell'informazione.
L’intuizione alla base del metodo
Immagina un navigatore web casuale che clicca sui link in modo casuale, saltando occasionalmente a una pagina completamente casuale anziché seguire un link. La frazione di tempo che questo navigatore trascorre su ciascuna pagina, dopo infiniti clic, è il PageRank di quella pagina. Una pagina visitata spesso — perché molte pagine popolari vi puntano — riceve un punteggio elevato. Il fattore di smorzamento (tipicamente 0,85) modella la probabilità di continuare a cliccare anziché saltare.
Storia
PageRank è stato sviluppato alla Stanford University da Larry Page e Sergey Brin come meccanismo di ranking principale del loro progetto di ricerca BackRub, che divenne Google nel 1998. Il rapporto tecnico fondamentale, co-redatto con Rajeev Motwani e Terry Winograd, fu pubblicato nel 1999. L'algoritmo ha reso popolare l'uso della centralità basata sugli autovettori nelle reti orientate su larga scala e ha ispirato direttamente algoritmi successivi di analisi dei link, tra cui HITS e TrustRank.
Quando usarlo
PageRank è appropriato quando è necessario classificare i nodi in un grafo orientato in base all'importanza strutturale globale, specialmente quando la direzione dell'arco codifica l'approvazione o l'influenza (iperlink, citazioni, follow sui social). Presuppone che il grafo possa essere modellato come una catena di Markov e richiede una componente connessa o fortemente connessa per una convergenza pulita. È meno adatto per reti non orientate dove la centralità HITS o di intermediazione potrebbero essere preferite, ed è sensibile allo spam di link o a un grado entrante artificialmente gonfiato.
Limiti e considerazioni
- Richiede un grafo orientato; l'applicazione a reti non orientate richiede scelte convenzionali
- La velocità di convergenza dipende dal gap spettrale della matrice di transizione e può essere lenta per grafi scarsamente connessi
- Sensibile alla scelta del fattore di smorzamento d; valori diversi possono alterare sostanzialmente le classifiche
- Vulnerabile alla manipolazione delle fattorie di link e ai collegamenti entranti costruiti artificialmente
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Fondamento probabilistico rigoroso tramite il modello di catena di Markov del navigatore casuale
- Scalabile a grafi molto grandi tramite prodotti matrice-vettore sparsi e iterazione di potenza
- Cattura la topologia globale del grafo, premiando i nodi approvati da altri nodi ad alto punteggio
- Ampiamente validato nei domini del web, delle citazioni, della biologia e delle reti sociali
Applicazioni
- Classificazione dei motori di ricerca web: ordinamento dei risultati di ricerca in base all'autorità globale delle pagine web
- Analisi delle citazioni accademiche: identificazione di articoli o riviste influenti nelle reti di letteratura scientifica
- Misurazione dell'influenza nelle reti sociali: classificazione degli utenti in base al prestigio dei loro follower
- Analisi delle reti biologiche: individuazione di proteine o geni hub nelle reti di interazione proteica e regolazione genica
- Sistemi di raccomandazione: propagazione di segnali di preferenza attraverso grafi bipartiti utente-elemento
Come funziona
Come funziona
Ogni nodo nel grafo inizia con un punteggio PageRank uguale di 1/N, dove N è il numero totale di nodi. Questa inizializzazione uniforme assicura che nessun nodo abbia un vantaggio artificiale e fornisce una distribuzione di probabilità valida sulla rete prima della prima iterazione.
Formula
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}Una matrice di transizione stocastica per colonne M viene costruita dalla struttura di adiacenza del grafo. Ogni elemento M_ij è uguale a 1 diviso per il grado uscente del nodo j se esiste un arco da j a i, e zero altrimenti. I nodi pendenti (senza archi uscenti) vengono tipicamente gestiti ridistribuendo il loro punteggio uniformemente su tutti i nodi.
Formula
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}Il vettore PageRank viene aggiornato iterativamente utilizzando la formula del navigatore casuale. Con il fattore di smorzamento d (predefinito 0,85), ogni nodo riceve una probabilità di base di teletrasporto (1-d)/N più d volte la somma pesata dei punteggi contribuiti da tutti i nodi che puntano ad esso. Questo passaggio viene ripetuto finché i punteggi non si stabilizzano.
Formula
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}Dopo ogni iterazione, la norma L1 della variazione nel vettore dei punteggi viene confrontata con una piccola tolleranza epsilon (ad esempio, 1e-6). Quando la variazione scende al di sotto di questa soglia, l'algoritmo è convergito e il vettore dei punteggi corrente viene restituito come distribuzione PageRank finale.
Formula
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilonErrori comuni
- Ignorare i nodi pendenti (nodi senza archi uscenti) può rompere la proprietà stocastica della matrice di transizione e causare punteggi errati
- L'uso di PageRank su grafi non orientati senza convertirli in un modello di transizione simmetrico può produrre stime di centralità fuorvianti
- Impostare la tolleranza troppo lassamente porta a una convergenza prematura; troppo strettamente aumenta il calcolo senza cambiamenti significativi nei punteggi
- Interpretare PageRank come una metrica di importanza assoluta piuttosto che una classifica relativa all'interno di un contesto di grafo specifico
Domande frequenti
Cosa rappresenta il fattore di smorzamento d e come dovrebbe essere scelto?
Il fattore di smorzamento d (tipicamente 0,85) è la probabilità che il navigatore casuale segua un link anziché teletrasportarsi su un nodo casuale. Valori vicini a 1 rendono l'algoritmo più sensibile alla struttura del grafo ma più lento a convergere e più incline ai 'rank sink' (nodi che accumulano punteggio); valori vicini a 0 si avvicinano a una classificazione uniforme. Il valore 0,85 è stato validato empiricamente da Page e Brin per il grafo del web ed è il valore predefinito standard.
In che modo PageRank differisce dalla centralità di grado?
La centralità di grado conta solo il numero diretto di link entranti a un nodo, trattando tutte le fonti allo stesso modo. PageRank pondera ciascun link entrante per il punteggio del nodo che lo collega, quindi un'approvazione da un nodo ad alto punteggio contribuisce più di quella di un nodo a basso punteggio. Questa definizione ricorsiva cattura la struttura globale del grafo piuttosto che la sola connettività locale.
PageRank può essere applicato a grafi non orientati?
Sì, ma con delle avvertenze. Un grafo non orientato deve essere convertito in una rappresentazione orientata sostituendo ogni arco non orientato con due archi orientati. I punteggi PageRank risultanti diventano quindi una funzione del grado del nodo, riducendo l'algoritmo a una centralità di grado ponderata. Per le reti non orientate, misure di centralità alternative come la centralità degli autovettori o la centralità di intermediazione sono spesso più informative.
Metodi correlati
Fonti
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.
Apri il riferimento della pubblicazioneCopiato.