PageRank (Italiano)

L’algoritmo PageRank emette una distribuzione di probabilità utilizzata per rappresentare la probabilità che una persona che fa clic casualmente sui link arrivi a una particolare pagina. PageRank può essere calcolato per raccolte di documenti di qualsiasi dimensione. Si presume in diversi documenti di ricerca 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 per riflettere più da vicino il valore reale 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%” di qualcosa che accade. Quindi, un documento con un PageRank di 0,5 significa che c’è una probabilità del 50% che una persona che fa clic su un link casuale venga diretta a tale documento.

Algoritmo semplificatomodifica

Assume un piccolo universo di quattro pagine web: A, B, C e D., I collegamenti da una pagina a se stessa vengono ignorati. Più collegamenti in uscita da una pagina a un’altra pagina vengono trattati come un singolo collegamento. PageRank viene inizializzato allo 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, assumono una distribuzione di probabilità compresa tra 0 e 1. Quindi il valore iniziale per ogni pagina in questo esempio è 0.25.,

Il PageRank trasferito da una data pagina alle destinazioni dei suoi collegamenti in uscita alla successiva iterazione viene diviso equamente tra tutti i collegamenti in uscita.

Se gli unici collegamenti nel sistema erano dalle pagine B, C e D ad A, ogni collegamento trasferirebbe 0,25 PageRank ad A alla successiva iterazione, per un totale di 0,75.

P R (A ) = P R (B ) + P R (C ) + P R (D). {\displaystyle PR (A)=PR (B) + PR (C) + PR (D).\ ,}

Supponiamo invece che la pagina B avesse un collegamento alle pagine C e A, la pagina C avesse un collegamento alla pagina A e la pagina D avesse collegamenti a tutte e tre le pagine., Quindi, alla prima iterazione, la pagina B trasferirebbe metà del suo valore esistente, o 0.125, alla pagina A e l’altra metà, o 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, trasferirebbe 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.

P R (A ) = P R (B ) 2 + P R ( C ) 1 + P R (D ) 3 . Per ulteriori informazioni, consultare il sito:.,\ ,}

In altre parole, il PageRank conferito da un collegamento in uscita è uguale al punteggio del PageRank del documento diviso per il numero di collegamenti in uscita L( ).

P R (A ) = P R ( B ) L (B ) + P R (C) L ( C) + P R (D) L ( D). Il nostro sito utilizza cookie tecnici e di terze parti per migliorare la tua esperienza di navigazione.Nel caso generale, il valore PageRank per qualsiasi pagina u può essere espresso come: P R (u) = v v in B u P R ( v ) L ( v ) {\displaystyle PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}} ,

cioè, il valore del PageRank per una pagina u dipende dai valori del PageRank per ogni pagina v contenuta nel set Bu (il set contenente tutte le pagine che si collegano alla pagina u), diviso per il numero L(v) di link dalla pagina v.

Fattore di smorzamento

La teoria del PageRank sostiene che un surfista immaginario che sta facendo clic casualmente sui link finirà per smettere di fare clic. La probabilità, in qualsiasi fase, che la persona continuerà è un fattore di smorzamento d. Vari studi hanno testato diversi fattori di smorzamento, ma si presume generalmente che il fattore di smorzamento sarà impostato intorno a 0,85.,

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è,

P R (A ) = 1-d N + d ( P R (B ) L (B) + P R ( C ) L ( C ) + P R ( D ) L (D ) + ⋯ ) . Il nostro sito utilizza cookie tecnici e di terze parti per migliorare la tua esperienza di navigazione.}

Quindi il PageRank di qualsiasi pagina è derivato in gran parte dai PageRanks di altre pagine., Il fattore di smorzamento regola il valore derivato verso il basso. Il documento originale, tuttavia, ha dato la seguente formula, che ha portato a una certa confusione:

P R ( A ) = 1 − d + d ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + ⋯ ) . Il nostro sito utilizza cookie tecnici e di terze parti per migliorare la tua esperienza di navigazione.}

La differenza tra loro è che i valori PageRank nella prima formula somma a uno, mentre nella seconda formula ogni PageRank viene moltiplicato per N e la somma diventa N., Una dichiarazione in Page and Brin’s paper che “la somma di tutti i PageRanks è una” e le affermazioni di altri dipendenti di Google supportano la prima variante della formula 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.

Google ricalcola i punteggi PageRank ogni volta che esegue la scansione del Web e ricostruisce il suo indice., Come Google aumenta il numero di documenti nella sua collezione, l’approssimazione iniziale di PageRank diminuisce per tutti i documenti.

La formula utilizza un modello di un surfista casuale che raggiunge il loro sito di destinazione dopo diversi clic, quindi passa a una pagina casuale. Il valore PageRank di una pagina riflette la possibilità che il surfista casuale atterrerà su quella pagina facendo clic su un link. Può essere inteso come una catena di Markov in cui gli stati sono pagine e le transizioni sono i collegamenti tra le pagine – tutti ugualmente probabili.,

Se una pagina non ha collegamenti ad altre pagine, diventa un sink e quindi termina il processo di navigazione casuale. Se il surfista 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 collegamenti in uscita si colleghino a tutte le altre pagine della raccolta. I loro punteggi 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 nel Web. Questa probabilità residua, d, è solitamente impostata su 0.,85, stimato dalla frequenza che un surfista medio utilizza la funzione segnalibro del suo browser. Così, l’equazione è la seguente:

P R ( p i ) = 1 − d N + d ∑ p j ∈ M ( p, i ) P R ( p j ) L ( p j ) {\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}

I valori di PageRank sono le voci di dominante diritto autovettore modificati matrice di adiacenza riproporzionato in modo che ogni colonna aggiunge ad uno.,_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\vdots \\\vdots &&\ell (p_{i},p_{j})&\\\ell (p_{N},p_{1})&\cdots &&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R} } ∑ i = 1 N ℓ ( p i , p j ) = 1 {\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1} ,

i.,e. gli elementi di ogni colonna sommano fino a 1, quindi la matrice è una matrice stocastica(per maggiori dettagli vedere la sezione di calcolo sotto). Quindi questa è una variante della misura di centralità dell’autovettore usata comunemente nell’analisi di rete.

A causa del grande eigengap della matrice di adiacenza modificata sopra, i valori dell’autovettore PageRank possono essere approssimati a un alto grado di precisione in poche iterazioni.,

I fondatori di Google, nel loro documento originale, hanno riferito che l’algoritmo PageRank per una rete composta da 322 milioni di collegamenti (in-edges e out-edges) converge entro un limite tollerabile in 52 iterazioni. La convergenza in una rete di metà delle dimensioni di cui sopra ha richiesto circa 45 iterazioni. Attraverso questi dati, hanno concluso che l’algoritmo può essere scalato molto bene e che il fattore di ridimensionamento per reti estremamente grandi sarebbe approssimativamente lineare in log n n {\displaystyle \log n} , 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 a uguale t-1 {\displaystyle t^{-1}} dove t {\displaystyle t} è l’aspettativa del numero di clic (o salti casuali) necessari per tornare dalla pagina a se stessa.

Uno svantaggio principale di PageRank è che favorisce le pagine più vecchie. Una nuova pagina, anche molto buona, non avrà molti collegamenti a meno che non faccia parte di un sito esistente (un sito che è un insieme di pagine densamente connesse, come Wikipedia).,

Sono state proposte diverse strategie per accelerare il calcolo del PageRank.

Varie strategie per manipolare PageRank sono stati impiegati in sforzi concertati per migliorare le classifiche dei risultati di ricerca e monetizzare i link pubblicitari. Queste strategie hanno gravemente influenzato l’affidabilità del concetto di PageRank, che pretende di determinare quali documenti sono in realtà molto apprezzati dalla comunità Web.,

Dal dicembre 2007, quando ha iniziato a penalizzare attivamente i siti che vendono link di testo a pagamento, Google ha combattuto link farm e altri schemi progettati per gonfiare artificialmente PageRank. Come Google identifica link farm e altri strumenti di manipolazione PageRank è tra i segreti commerciali di Google.

ComputationEdit

PageRank può essere calcolato iterativamente o algebricamente. Il metodo iterativo può essere visto come il metodo di iterazione di potenza o il metodo di potenza. Le operazioni matematiche di base eseguite sono identiche.,

IterativeEdit

At t = 0 {\displaystyle t=0} , si assume una distribuzione di probabilità iniziale, di solito

P R ( p i ; 0 ) = 1 N {\displaystyle PR(p_{i};0)={\frac {1}{N}}} .

dove N è il numero totale di pagine e p i ; 0 {\displaystyle p_{i};0} è la pagina i al tempo 0.,

(1)

The matrix M {\displaystyle {\mathcal {M}}} is defined as

M i j = { 1 / L ( p j ) , if j links to i 0 , otherwise {\displaystyle {\mathcal {M}}_{ij}={\begin{cases}1/L(p_{j}),&{\mbox{if }}j{\mbox{ links to }}i\ \\0,&{\mbox{otherwise}}\end{cases}}}

i.,e.,

M := ( K − 1 A ) T {\displaystyle {\mathcal {M}}:=(K^{-1}A)^{T}},

dove A {\displaystyle A} indica la matrice di adiacenza del grafico e K {\displaystyle K} è 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 ϵ {\displaystyle \epsilon }

| R ( t + 1 ) − R ( t ) | < ϵ {\displaystyle |\mathbf {R} (t+1)-\mathbf {R} (t)|<\epsilon } ,

cioè, quando la convergenza è assunto.,

AlgebraicEdit

—For t → ∞ {\displaystyle t\to \infty } (i.e., in the steady state), the equation (1) reads

(2)

The solution is given by

R = ( I − d M ) − 1 1 − d N 1 {\displaystyle \mathbf {R} =(\mathbf {I} -d{\mathcal {M}})^{-1}{\frac {1-d}{N}}\mathbf {1} } ,

with the identity matrix I {\displaystyle \mathbf {I} } .,

La soluzione esiste ed è unica per 0 < d < 1 {\displaystyle 0<d<1} . Questo può essere visto notando che M {\displaystyle {\mathcal {M}}} è per costruzione una matrice stocastica e quindi ha un autovalore uguale a uno come conseguenza del teorema di Perron–Frobenius.,

Power methodEdit

(3)

x ( t + 1 ) = M ^ x ( t ) {\displaystyle x(t+1)={\widehat {\mathcal {M}}}x(t)} ,

until

| x ( t + 1 ) − x ( t ) | < ϵ {\displaystyle |x(t+1)-x(t)|<\epsilon } .,

si noti che nell’equazione (3) la matrice sulla destra, nella parentesi può essere interpretato come

1 − d N E = ( 1 − d ) P 1 t {\displaystyle {\frac {1-d}{N}}\mathbf {E} =(1-d)\mathbf {P} \mathbf {1} ^{t}}

dove P {\displaystyle \mathbf {P} } è una prima distribuzione di probabilità. Nel caso attuale

P: = 1 N 1 {\displaystyle \ mathbf {P}: = {\frac {1}{N}}\mathbf {1} } .,therwise {\displaystyle \mathbf {D} _{i}={\begin{cases}1,&{\mbox{if }}L(p_{i})=0\ \\0,&{\mbox{otherwise}}\end{cases}}}

In this case, the above two computations using M {\displaystyle {\mathcal {M}}} only give the same PageRank if their results are normalized:

R power = R iterative | R iterative | = R algebraic | R algebraic | {\displaystyle \mathbf {R} _{\textrm {power}}={\frac {\mathbf {R} _{\textrm {iterative}}}{|\mathbf {R} _{\textrm {iterative}}|}}={\frac {\mathbf {R} _{\textrm {algebraic}}}{|\mathbf {R} _{\textrm {algebraic}}|}}} .,

ImplementationEdit

Scala/Apache SparkEdit

Un esempio tipico è l’utilizzo della programmazione funzionale di Scala con gli RDD Apache Spark per calcolare iterativamente i ranghi delle pagine.

MATLAB/OctaveEdit

Esempio di codice che chiama la funzione di rango definita sopra:

M = ;rank2(M, 0.80, 0.001)

PythonEdit

Questo esempio richiede ≈13 iterazioni per convergere.