Web Search - Page Rank
Traduzione e Integrazione
delle Lezioni a cura di Sandro Gallo
Home Locality
Sensitive Hashing(LSH) e Hamming-LSH Web Search - Hub and Authority
Il page rank è una tecnica per scoprire le
pagine più importanti del Web.
Il concetto di importanza è espresso in termini ricorsivi,
cioè una pagina è importante se pagine importanti
puntano ad essa.
Per trovare queste pagine iniziamo costruendo una matrice
stocastica del web tale che:
- la pagina i corrisponde alla riga i e alla colonna i
- se j ha n successori (links), allora l'elemento (i,j) vale
1/n se la pagina i è una degli n successori, vale zero
altrimenti.
Dovremo risolvere un sistema del tipo p=Ap, in cui se all'inizio
ogni pagina ha importanza 1, questa viene divisa tra i suoi
successori e ogni pagina prende importanza dai suoi
predecessori.
L'importanza tende ad un limite, che è l'autovettore
principale della matrice A. L'importanza è anche la
probabilità che un navigatore ha di arrivare a una data
pagina dopo un numero sufficientemente grande di links
seguiti.
Alcuni problemi che sorgono con il page rank sono:
- Dead end, cioè se una pagina non ha successori non
potrà trasmettere importanza per cui alla lunga anche lei
la perderà.
- Spider trap, cioè quando un gruppo di pagine che non
hanno link esterni accumulano tutta l'importanza.
Home Locality
Sensitive Hashing(LSH) e Hamming-LSH Web Search - Hub and Authority