La definizione formale di PageRank, come definito a pagina 4 del documento citato, è espressa nell'equazione matematica con il buffo simbolo "E" (è infatti la lettera greca capitale Sigma. Sigma è la lettera "S" "che sta per Summation).
In poche parole questa formula dice che per calcolare il PageRank di pagina X ...
For all the backlinks to this page (=all the pages that link to X)
you need to calculate a value that is
The PageRank of the page that links to X [R'(v)]
divided by
the number of links found on this page. [Nv]
to which you add
some "source of rank", [E(u)] normalized by c
(we'll get to the purpose of that later.)
And you need to make the sum of all these values [The Sigma thing]
and finally, multiply it by a constant [c]
(this constant is just to keep the range of PageRank manageable)
L'idea chiave è questa formula è che tutte le pagine web che puntano a una determinata pagina X stanno aggiungendo valore al suo "valore". Collegando ad alcune pagine stanno "votando" a favore di questa pagina. Tuttavia, questo "voto" ha più o meno peso, a seconda di due fattori:
- La popolarità della pagina che si collega a X [R '(v)]
- Il fatto che la pagina che si collega a X collega anche a molte altre pagine o no. [Nv]
Questi due fattori riflettono idee molto intuitive:
- E 'generalmente meglio per ottenere una lettera di raccomandazione da un esperto riconosciuto nel campo che da una persona sconosciuta.
- Indipendentemente da chi dà la raccomandazione, dando anche consigli ad altre persone, stanno diminuendo il valore della loro raccomandazione a voi.
Come si nota, questa formula si avvale di un po 'di un riferimento circolare, perché per conoscere l'intervallo di pagine di X, è necessario conoscere il PageRank di tutte le pagine che si collegano a X. E allora come si fa a capire questi valori PageRank? ... Ecco dove il prossimo numero di convergenza spiegato nella sezione del documento kick in.
In sostanza, iniziando con alcuni valori "casuali" (o preferibilmente "discreti" di PageRank, per tutti pagine, e calcolando il PageRank con la formula di cui sopra, i nuovi valori calcolati ottenere "migliore", come eseguire iterazioni questo processo un paio di volte. i valori convergono, vale a dire si avvicinano sempre di più a quello che è il valore effettivo/teorico. Quindi, ripetendo una quantità sufficiente di volte, raggiungiamo un momento in cui le iterazioni aggiuntive non aggiungerebbero alcuna precisione pratica ai valori forniti dall'ultima iterazione.
Ora ... Che è bello e dandy, in teoria. Il trucco è convertire questo algoritmo in qualcosa di equivalente ma che può essere fatto più rapidamente. Ci sono diversi documenti che descrivono come questo, e attività simili, possono essere fatte. Non ho riferimenti di questo tipo, ma li aggiungerò più tardi. Attenti che comporteranno una buona dose di algebra lineare.
MODIFICA: come promesso, qui ci sono alcuni link relativi agli algoritmi per calcolare il grado di pagina. Efficient Computation of PageRank Haveliwala 1999 /// Exploiting the Block Structure of the Web for Computing PR Kamvar etal 2003 /// A fast two-stage algorithm for computing PageRank Lee et al. 2002
Anche se molti dei dei link forniti in precedenza gli autori sono a Stanford, non ci vuole molto a capire che la ricerca di efficienza di calcolo del PageRank come una vasca campo di ricerca. Mi rendo conto che questo materiale va oltre lo scopo dell'OP, ma è importante accennare al fatto che l'algoritmo di base non è pratico per le grandi reti.
Per terminare con un testo molto accessibile (ma con molti collegamenti ad approfondite informazioni), mi piacerebbe parlare Wikipedia's excellent article
Se siete seriamente di questo genere di cose, si può considerare un introduttivo/classe di aggiornamento in matematica, in particolare algebra lineare, nonché una classe di informatica che si occupa di grafici in generale. A proposito, grande suggerimento da parte di Michael Dorfman, in questo post, per il video di OCW delle lezioni del 1806.
Spero che questo aiuta un po '...
Perché i voti ravvicinati, questa è una domanda perfettamente valida sugli algoritmi? – johnc
Infatti. Vorrei poter votare per "non chiudere". –
Se si sta sviluppando un motore di ricerca e si desidera utilizzare PageRank, è consigliabile verificare con un avvocato. PageRank è coperto da brevetti, almeno negli Stati Uniti. Non sono sicuro di come funzionerebbe legalmente nel tuo paese, ma probabilmente dovresti consultare qualcuno che lo saprebbe per certo (cioè il tuo avvocato locale). –