L’algoritmo di page rank di Google è basato su una particolare ricerca dell’autovalore, che nel caso più semplice è basata sull’uso del metodo delle potenze.

Domanda: Quando cerco una stringa alfanumerica su un motore di ricerca, come posso classificare le “pagine correlate”, i.e., le pagine che contengono quella stringa?

• Risposta 1: Controllo quante volte la stringa compare. Questo mi da qualche problema perchè i siti potrebbero contenere determinate stringhe “studiate” inserite in modo ripetuto o addirittura nascoste;
• Risposta 2: Basandoci su quante pagine una data pagina “punta”. Però questo non è molto ragionevole dato che potrei forzare la mia pagina a puntare a $10^{10}$ altre pagine;
• Risposta 3: Basandoci su quante pagine “puntano” a una data pagina. Però anche questo non ha senso perchè potrei pagare per avere $10^{10}$ pagine che “puntano” alla mia pagina;
• Risposta 4 (versione base del page rank): Essenzialmente la risposta 3, ma quando una pagina punta alla mia pagina, questo collegamento deve essere pesato basandosi sull’importanza di quella pagina.

Facciamo un esempio con 3 pagine:

Una freccia $A\to B$ significa che la pagina $A$ punta (e quindi è collegata) alla pagina $B$.

Introduciamo ora la matrice di vicinanza $H \in \R^{n\times n}$ , data $n$ dimensione della rete, costruita in questo modo

$$ H_{i,j}=\begin{cases} 0 &\text{ se l'i-esimo nodo non è collegato con il j-esimo nodo}\\ 1 &\text{ altrimenti} \end{cases} $$

Con la rete sopra avremmo

$$ H=\begin{bmatrix} 0 &1 &1\\ 1 &0 &0\\ 0 &1 &0 \end{bmatrix} $$

Poi, introduciamo una norma di collegamento, i.e., $w^\rarr \in \R^n$ che contiene il valore dell’i-esimo nodo nella i-esima entry.

Introduciamo anche $d^\rarr \in \R^n$ dato da

$$ d^\rarr_i = \sum_{l=1}^N H_{i,l} \ \ \ \ \forall i=1,..., N, $$

i.e., $d_i^\rarr$ contiene il numero di nodi collegati dall’i-esimo nodo.