Esercizio - PageRank di quattro pagine con teletrasporto e iterazione di potenza

Teoria: Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafiPasseggiata sulla retta con barriere (rovina del giocatore): da i con N come traguardo, P(vittoria)=i/N e durata attesa i(N-i) se il gioco è equo; con p diverso da 1/2, P=(1-r^i)/(1-r^N), r=q/p. Il 2-SAT si risolve con una passeggiata randomizzata (flip di una variabile di una clausola violata): E[T] ≤ n^2 passi, quindi 2n^2 passi bastano con errore ≤ 1/2 (3-SAT: deriva contraria, esponenziale). Sul grafo la passeggiata ha π_v=d(v)/2m, tempo di ritorno 2m/d(v), tempo di copertura < 4m(n-1), da cui la connettività s-t in spazio logaritmico; PageRank è la stazionaria di una passeggiata con teletrasporto.Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi →; catene di Markov: Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionariaUna catena di Markov a tempo discreto e stati finiti è descritta da una matrice stocastica P: P(X_{n+1}=j | X_n=i)=P_ij, la legge al tempo n è π_0 P^n. Gli stati si classificano in classi comunicanti (irriducibilità), periodo (aperiodicità) e ricorrenza/transitorietà. Una distribuzione stazionaria soddisfa πP=π; per catene finite irriducibili esiste ed è unica, vale π_i=1/h_ii (h_ii = tempo medio di primo ritorno), e se la catena è anche aperiodica P^n converge a una matrice con tutte le righe uguali a π. Le catene reversibili (π_i P_ij = π_j P_ji) hanno stazionaria immediata.Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionaria →.

Testo. Quattro pagine con i link $1\to2,3$; $2\to3$; $3\to1$; $4\to1,3$ (nessuno punta a $4$). Il navigatore casuale segue un link scelto a caso con probabilità $\alpha=0{,}85$, altrimenti salta a una pagina uniforme.

1. Scrivere la matrice di transizione $P$ senza salti e la matrice $G$ con i salti. Perché $G$ ha un'unica distribuzione stazionaria?
2. Calcolare il PageRank risolvendo il sistema lineare.
3. Perché la pagina $4$ ha il PageRank più basso e quanto vale?
4. Quanto converge l'iterazione di potenza da $x_0=(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$? Quante iterazioni per un errore $\le10^{-6}$?
5. Come cambia il risultato con $\alpha=0{,}5$ e $\alpha=0{,}99$?

Soluzione

1. Senza salti ($P_{ij}=1/d^+(i)$ se $i\to j$): $$P=\begin{pmatrix}0&\tfrac12&\tfrac12&0\\0&0&1&0\\1&0&0&0\\\tfrac12&0&\tfrac12&0\end{pmatrix},\qquad G=0{,}85\,P+\frac{0{,}15}4\,\mathbf 1\mathbf 1^T=0{,}85\,P+0{,}0375\,\mathbf 1\mathbf 1^T.$$ $P$ da sola non è irriducibile: la pagina $4$ è transitoria (nessuno la raggiunge) e $\{1,2,3\}$ è una classe chiusa, quindi darebbe $\text{PR}_4=0$ e dipenderebbe dalla struttura dei link. In $G$ ogni entrata è $\ge0{,}0375>0$, quindi da ogni pagina si va in un passo a ogni altra: la catena è irriducibile e aperiodica, ed esiste un'unica $\pi$ con $\pi G=\pi$ e $\pi^{(n)}\to\pi$.

2. Le equazioni sono $x_j=0{,}0375+0{,}85\sum_{i\to j}x_i/d^+(i)$: $$x_1=0{,}0375+0{,}85\,(x_3+\tfrac12x_4),\quad x_2=0{,}0375+0{,}85\cdot\tfrac12x_1,\quad x_3=0{,}0375+0{,}85\,(\tfrac12x_1+x_2+\tfrac12x_4),\quad x_4=0{,}0375.$$ Dalla quarta, $x_4=0{,}0375$ e $0{,}85\cdot\tfrac12x_4=0{,}0159375$. Allora:

• $x_1=0{,}0534375+0{,}85x_3$;
• $x_2=0{,}0375+0{,}425x_1$;
• $x_3=0{,}0534375+0{,}425x_1+0{,}85x_2=0{,}0534375+0{,}425x_1+0{,}031875+0{,}36125x_1=0{,}0853125+0{,}78625x_1$.

Sostituendo $x_3$ in $x_1$: $x_1=0{,}0534375+0{,}072515625+0{,}6683125\,x_1=0{,}125953125+0{,}6683125\,x_1$, da cui $x_1=\dfrac{0{,}125953125}{0{,}3316875}=0{,}3797$. Poi $x_2=0{,}0375+0{,}425\cdot0{,}3797=0{,}1989$ e $x_3=0{,}0853125+0{,}78625\cdot0{,}3797=0{,}3839$. Controllo: $0{,}3797+0{,}1989+0{,}3839+0{,}0375=1{,}0000$ ✓. $$\boxed{\text{PR}=(0{,}3797;\ 0{,}1989;\ 0{,}3839;\ 0{,}0375).}$$ (Valori esatti: $x_1=\tfrac{2687}{7076}$, $x_2=\tfrac{56293}{283040}$, $x_3=\tfrac{108653}{283040}$, $x_4=\tfrac3{80}$.)

3. La pagina $4$ non riceve link: l'unico modo di arrivarci è un salto casuale, che ha probabilità $\tfrac{1-\alpha}n=\tfrac{0{,}15}4=0{,}0375$ a ogni passo, quindi $\text{PR}_4=0{,}0375$ esattamente. Le pagine $3$ e $1$ si scambiano quasi tutto il peso ($3\to1$ con probabilità $1$, e $1$ manda metà del suo peso a $3$ più tutto il contributo di $2$): per questo sono prime e seconde. Nonostante $4$ punti a $1$ e $3$, il suo contributo vale solo $0{,}85\cdot0{,}0375/2=0{,}0159$ a ciascuna.

4. L'iterazione $x^{(k+1)}=x^{(k)}G$ converge con rapidità $|\lambda_2(G)|^k$. Gli autovalori di $P$ sono $1$, $-\tfrac12\pm\tfrac12i$ (modulo $\tfrac1{\sqrt2}=0{,}7071$) e $0$, e quelli di $G$ diversi da $1$ sono $0{,}85$ volte quelli di $P$: $|\lambda_2|=0{,}85\cdot0{,}7071=0{,}601$. L'errore in norma $L^1$ vale (calcolato)

Per un errore $\le10^{-6}$ servono $\boxed{25}$ iterazioni ($1{,}55\cdot10^{-6}$ a $k=24$, $7{,}8\cdot10^{-7}$ a $k=25$). In pratica PR non è noto e ci si ferma quando la differenza fra due iterate consecutive è $<10^{-6}$: qui succede a $k=28$, perché il passo $\lVert x^{(k+1)}-x^{(k)}\rVert_1$ è più grande dell'errore residuo (con autovalori complessi l'errore oscilla), quindi il criterio pratico è più prudente di qualche iterazione.

5. Il numero di iterazioni cresce con $\alpha$ (autovalore $\alpha\cdot0{,}7071$), mentre i pesi diventano più "puri" (vicini alla stazionaria di $P$ nella classe $\{1,2,3\}$):

Con $\alpha=0{,}99$ la pagina $4$ scende a $0{,}0025$ (si tende alla stazionaria di $P$, dove $4$ ha peso $0$) ma la convergenza è più lenta. È il compromesso scelto in pratica: $\alpha=0{,}85$.

Codice di verifica

import numpy as np

L = {0: [1, 2], 1: [2], 2: [0], 3: [0, 2]}                 # pagine 1..4 come indici 0..3
P = np.zeros((4, 4))
for i, out in L.items():
    P[i, out] = 1 / len(out)

def pagerank(alpha, tol=1e-6):
    G = alpha * P + (1 - alpha) / 4 * np.ones((4, 4))
    w, v = np.linalg.eig(G.T)
    pr = np.real(v[:, np.argmax(np.real(w))]); pr /= pr.sum()          # stazionaria esatta
    x, k = np.ones(4) / 4, 0
    while np.abs(x - pr).sum() > tol:
        x, k = x @ G, k + 1                                          # iterazione di potenza
    return pr, k, np.sort(np.abs(w))[-2]

for a in (0.5, 0.85, 0.99):
    pr, k, l2 = pagerank(a)
    print(a, np.round(pr, 4), "iterazioni:", k, " |lambda2| =", round(l2, 3))

Output:

0.5 [0.3269 0.2067 0.3413 0.125 ] iterazioni: 12  |lambda2| = 0.354
0.85 [0.3797 0.1989 0.3839 0.0375] iterazioni: 25  |lambda2| = 0.601
0.99 [0.3987 0.1999 0.3989 0.0025] iterazioni: 36  |lambda2| = 0.7