PageRank Pesato
- Introdotto da
- Xing, W. & Ghorbani, A.
- Anno
- 2004
- Tipo
- Centrality measure / ranking algorithm
- Famiglia
- Network science
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il PageRank Pesato estende l'algoritmo PageRank classico alle reti in cui gli archi hanno diverse forze o frequenze, distribuendo l'importanza proporzionalmente ai pesi degli archi entranti e uscenti piuttosto che trattare tutti i collegamenti allo stesso modo.
Ciò lo rende sostanzialmente più informativo del PageRank binario in qualsiasi rete in cui la forza della connessione è rilevante.
L’intuizione alla base del metodo
Il PageRank classico tratta ogni hyperlink o legame in modo identico: un nodo acquisisce lo stesso prestigio da una connessione debole come da una forte. Il PageRank Pesato corregge ciò scalando ogni voto in base al peso relativo dell'arco. Un nodo che riceve numerosi archi entranti di peso elevato da nodi già importanti sale più in alto nella classifica, mentre un nodo con numerose ma deboli connessioni rimane modesto. Ciò rispecchia come l'influenza si accumula effettivamente nella maggior parte delle reti del mondo reale, dove la frequenza di interazione o il volume delle transazioni segnalano l'importanza reale.
Storia
Il PageRank è stato introdotto da Brin e Page nel 1998 come fondamento di Google Search, trattando tutti gli hyperlink come voti uguali. Il PageRank Pesato è stato formalizzato da Xing e Ghorbani nel 2004, estendendo l'algoritmo per assegnare la distribuzione del rango proporzionale ai pesi degli archi, basandosi su frazioni di peso entrante e uscente. Da allora è stato applicato nell'analisi delle citazioni, nella bioinformatica, nell'analisi delle reti sociali e nei sistemi di raccomandazione ovunque la forza del collegamento sia un proxy significativo per l'influenza.
Quando usarlo
Utilizzare il PageRank Pesato quando la rete presenta pesi degli archi significativi e si necessita di una classifica globale e consapevole del flusso dell'importanza dei nodi. È ideale per reti di citazioni con conteggi di co-citazioni, grafi web con volumi di traffico, reti di interazione biologica con livelli di espressione, reti sociali con frequenze di interazione e reti di transazioni finanziarie. Preferire il PageRank Pesato al PageRank binario ogni volta che ignorare la forza dell'arco potrebbe travisare il flusso di influenza. Evitarlo quando i pesi degli archi non sono affidabili o sono assegnati arbitrariamente, quando la rete è molto sparsa e i pesi sono per lo più binari (il PageRank semplice è sufficiente), o quando si necessita di una misura di centralità puramente locale come il grado pesato. Non è appropriato per reti non dirette in cui la direzione del flusso è concettualmente priva di significato.
Limiti e considerazioni
- Richiede che i pesi degli archi siano significativi e misurati in modo affidabile; pesi rumorosi o arbitrari degradano la qualità della classifica.
- Il fattore di smorzamento (d) è un parametro libero; il convenzionale 0,85 potrebbe non essere ottimale per reti non web.
- Sensibile allo schema di normalizzazione dei pesi scelto; i risultati possono differire se i pesi entranti e uscenti vengono combinati diversamente.
- Non distingue tra diversi tipi di archi; un modello a peso singolo potrebbe collassare distinzioni strutturali importanti.
- La convergenza può essere lenta su reti molto grandi e dense senza efficienti implementazioni di matrici sparse.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Incorpora la forza dell'arco direttamente nella propagazione dell'importanza, fornendo classifiche più realistiche del PageRank binario nelle reti pesate.
- Cattura il prestigio globale, a livello di rete, piuttosto che solo la connettività locale.
- Preserva il meccanismo di teletrasporto del PageRank, rendendolo robusto contro nodi pendenti e componenti disconnesse quando corretto.
- Scala a reti di grandi dimensioni tramite un calcolo iterativo efficiente; le operazioni su matrici sparse mantengono la memoria gestibile.
- Facilmente interpretabile: un punteggio elevato significa che un nodo riceve un'adesione ponderata e significativa da altri nodi ad alto punteggio.
Applicazioni
- Identificare articoli o autori influenti in reti di citazioni e co-pubblicazioni pesate.
- Classificare pagine web o documenti quando sono disponibili volumi di traffico di hyperlink o tassi di click-through.
- Rilevare proteine o geni chiave in reti di interazione biologica pesate.
- Prioritizzare nodi in reti di transazioni finanziarie in base al flusso del volume delle transazioni.
- Classificare utenti o contenuti in grafi di interazione di social media pesati.
- Costruire sistemi di raccomandazione in cui le frequenze di co-occorrenza degli elementi fungono da pesi degli archi.
Come funziona
Come funziona
Rappresentare la rete come un grafo in cui ogni arco porta un peso numerico che riflette la forza del legame — come la frequenza di interazione, il volume delle transazioni, il conteggio delle co-pubblicazioni o il punteggio di similarità. L'algoritmo richiede che questi pesi siano non negativi; i pesi negativi devono essere trasformati prima dell'analisi.
Per ogni arco diretto da v a u, calcolare due fattori di peso: un fattore di peso entrante che normalizza il peso dell'arco per il peso entrante totale di u, e un fattore di peso uscente che lo normalizza per il peso uscente totale di v. Queste frazioni determinano quanta parte del rango di v viene distribuita a u tramite questo specifico arco.
Formula
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}Applicare la formula del PageRank Pesato iterativamente: il rango di ciascun nodo è uguale a un termine di base di teletrasporto (1 meno il fattore di smorzamento d, tipicamente 0,85) più d volte la somma su tutti i vicini entranti del loro rango scalato dai due fattori di peso. Ciò distribuisce il rango proporzionalmente alla forza dell'arco piuttosto che uniformemente.
Formula
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)Ripetere l'aggiornamento del rango finché la variazione del punteggio di ogni nodo scende al di sotto di una piccola tolleranza (comunemente 1e-6). La convergenza è garantita per grafi fortemente connessi; per grafi con nodi pendenti o componenti isolate, applicare la correzione standard per i nodi pendenti prima di iterare.
Una volta che i punteggi sono convergenti, ordinare tutti i nodi in base al loro punteggio di PageRank Pesato in ordine decrescente. Questi ranghi riflettono l'importanza strutturale globale di ciascun nodo, tenendo conto sia della topologia della rete che della forza dell'arco.
Errori comuni
- Utilizzare pesi degli archi grezzi, non normalizzati, senza verificarne la scala — mescolare conteggi nell'ordine delle decine con valori nell'ordine dei milioni distorce la propagazione del rango.
- Dimenticare di gestire i nodi pendenti (nodi senza archi uscenti), che possono drenare rango dall'intera rete se non corretti.
- Presumere che il fattore di smorzamento predefinito di 0,85 sia universalmente appropriato; nelle reti di citazioni o biologiche un valore diverso potrebbe riflettere meglio il dominio.
- Interpretare i punteggi di PageRank Pesato come probabilità assolute piuttosto che classifiche relative — solo il loro ordine è stabile tra diverse esecuzioni.
- Confrontare i punteggi di PageRank Pesato tra reti di dimensioni diverse senza normalizzazione.
Domande frequenti
In che modo il PageRank Pesato differisce dal PageRank standard?
Il PageRank standard distribuisce il rango di un nodo equamente a tutti i suoi vicini uscenti indipendentemente dalla forza dell'arco. Il PageRank Pesato scala questa distribuzione in base al peso entrante e uscente relativo di ciascun arco, quindi le connessioni più forti trasportano proporzionalmente più rango.
Quale fattore di smorzamento dovrei usare?
Il valore convenzionale è 0,85, derivato da ipotesi sui grafi web riguardo al surf casuale. Per reti sociali, biologiche o di citazioni, valori tra 0,5 e 0,9 sono esplorati nella letteratura. Si raccomanda un'analisi di sensibilità su una gamma di valori di smorzamento.
Il PageRank Pesato può essere applicato a reti non dirette?
Sì, rappresentando ogni arco non diretto come una coppia di archi diretti con lo stesso peso. L'algoritmo produce quindi fattori di peso entrante e uscente simmetrici, che si semplificano in una formula che rispetta ancora la forza dell'arco.
Come gestisco gli archi con peso zero?
Gli archi con peso zero non contribuiscono alla propagazione del rango, quindi possono essere rimossi prima dell'analisi. Se i pesi zero sono strutturalmente significativi (assenza vs dati mancanti), documentare chiaramente la distinzione prima di rimuoverli.
Il PageRank Pesato è migliore della centralità del grado pesato?
Dipende dalla domanda di ricerca. La centralità del grado pesato cattura solo le connessioni dirette, mentre il PageRank Pesato cattura il prestigio globale propagato attraverso l'intera rete. Utilizzare il grado pesato per l'influenza locale e il PageRank Pesato per l'importanza a livello di rete.
Metodi correlati
Fonti
Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.
Apri il riferimento DOICopiato.PageRank. Wikipedia.
Apri il riferimento della pubblicazioneCopiato.