Una breve storia di Google.

Probabilmente oggi su Google avrete notato un doodle per un’occasione speciale: oggi 27.09 (giorno di nascita di Luigi XIII e Francesco Totti) ricorre il 17-esimo compleanno di Google.

A pensarci bene la storia di Google è veramente breve (Google History): fondato nel vicinissimo 1998, in soli 17 anni di vita il suo contributo tecnologico e scientifico l’ha posizionato in fretta tra le prime aziende informatiche al mondo (basti pensare che Apple venne fondata nel 1976, mentre Microsoft nel 1975).

Android è uno dei sistemi operativi per mobile più utilizzati al mondo, Google Search è il motore di ricerca per antonomasia (a parte qualche realtà particolare come Russia e Cina), Gmail è il provider e-mail più utilizzato al mondo, mentre Google Maps e Google Translate sono due servizi Web ormai costantemente presenti nel quotidiano; tuttavia i progetti avviati da Google toccano anche degli ambiti ai limiti della fantascienza, come ad esempio lo studio delle leggi biologiche che regolano la durata della vita al fine di aumentare la longevità (Progetto Calico).

Larry Page e Sergey Brin

Larry Page e Sergey Brin

In questo post ci “limiteremo” ad analizzare l’aspetto distintivo, almeno nella fase iniziale, alla base di Google Search (il PageRank) e i suoi fondamenti matematici.

Il Web, il pagliaio dove andare a cercare il nostro ago.

Prima ancora di porsi il problema fondamentale di come fa il motore di ricerca a fornirci quello ci serve, è importante capire come il motore di ricerca considera il suo pane quotidiano, ossia il Web.

Il Web viene pensato come un enorme grafo, ossia una sorta di ragnatela i cui fili sono i collegamenti (link) tra le pagine e i nodi tra i vari fili sono le pagine.

In particolare, dato un insieme di pagine Web $$\left\{ P_i \right\}_{i = 1\dots{} n}$$ si definiscono:

  • la matrice di adiacenza $$M_{adj} = (m_{adj})_{i,j}$$
    $$(m_{adj})_{i,j} := \left\{\begin{array}{ll}1 \ & \exists \text{ collegamento tra } P_i \text{ e } P_j\\{0} \ & altrimenti\end{array}\right.$$
  • la matrice di transizione $$M_{trans} = (m_{trans})_{i,j}$$
    $$(m_{trans})_{i,j} := \left\{\begin{array}{ll}\frac{1}{|P_i|} \ & \exists \text{ collegamento tra } P_i \text{ e } P_j\\{0} \ & altrimenti\end{array}\right.$$
    dove $$|P_i|$$ rappresenta il numero totale delle pagine a cui punta la pagina $$P_i$$.

Esempio (parte 1)
Consideriamo ad esempio la seguente piccola porzione di rete (ottenuta tramite MatLab, modulo surfer.m) a partire dalla pagina Web http://www.guerrestellari.net ridotta ad hoc a 5 nodi (anche se rispecchia poco la realtà del sito, va benissimo a titolo esplicativo). In particolare si hanno le seguenti URL:

  • $$P_1$$ https://www.facebook.com/GuerreStellari.Net?_rdr=p
  • $$P_2$$ http://www.guerrestellari.net/2015/06/19/secondo-teaser-trailer-star-wars-risveglio-della-forza-guinness-world-records/
  • $$P_3$$ http://www.guerrestellari.net
  • $$P_4$$ http://www.guerrestellari.net/gs-net/redazione/
  • $$P_5$$ http://www.guerrestellari.net/2015/04/21/il-risveglio-della-forza-incassera-oltre-540-milioni-di-dollari-allesordio/

Costruiamo dapprima la matrice di adiacenza del nostro Web (ossia $$1$$ se il nodo $$i$$ punta al nodo $$j$$ e $$0$$ altrimenti)

$$M_{adj} = \begin{pmatrix}1 & 0 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 1 \\1 & 0 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 0 \\ 0& 0 & 1 & 0 & 1\end{pmatrix}$$

la cui rappresentazione grafica è la seguente (realizzata in R)

esempio_grafo

Grafo associato alla porzione di rete dell’Esempio

 

mentre la matrice di transizione (che tiene conto dei collegamenti in uscita di ciascuna pagina) è

$$M_{trans} = \begin{pmatrix}\frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\\frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} \\\frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 \\{0} & 0 & \frac{1}{2} & 0 & \frac{1}{2}\end{pmatrix}$$

Il Web ha dimensioni enormi ma non infinite ed è in continua espansione (anche mentre state leggendo questo articolo): infatti basti pensare che, se nel 2011 si contavano 300 milioni circa di pagine Web, nel 2014 si è arrivati a poco più di un miliardo.
E allora come muoversi in questo sconfinato grafo del Web per ottenere quello che si sta cercando?

I parametri alla base della ricerca in Google.

La prassi moderna di ricerca è la seguente: si apre un browser, si va su un motore di ricerca, si digita qui l’oggetto d’interesse e poi si sceglie nella lista dei risultati fornita (di solito la prima pagina fornisce già la risposta che si cercava). Ovviamente i motori di ricerca hanno performance diverse, noi ci concentriamo sul motore di ricerca che è il più utilizzato, se non addirittura il migliore.

Ma cosa c’è dietro questo “bibliotecario virtuale” fenomenale?

Cito testuale lo stesso Google:

Attualmente gli algoritmi di Google si basano su oltre 200 segnali univoci o “indizi” che consentono di intuire che cosa stai realmlente cercando. Questi segnali includono elementi quali i termini presenti nei siti web, l’attualità dei contenuti, l’area geografica e il PageRank.

Tralasciando l’area geografica e l’attualità dei contenuti, la principale novità introdotta dai due fondatori di Google, Larry Page e Sergey Brin, sta proprio nel superamento della semplice analisi testuale di una pagina in relazione ad una query; infatti due pagine potrebbero parlare dello stesso argomento, ma come fare per scegliere tra le due? La filosofia adottata è la seguente:

  • una pagina è considerata importante se è collegata a pagine importanti;
  • una pagina importante dà molta importanza alle pagine a cui è collegata, mentre una pagina non importante dà poca importanza alle pagine a cui è collegata.

Per definire il concetto di importanza di una pagina interviene il PageRank.

Il PageRank è un valore che Google assegna a ogni sito presente nel suo database. Google usa una formula matematica chiamata appunto PageRank per giudicare l’importanza delle pagine che corrispondono ad una ricerca. Brin teorizzò un ordinamento dell’informazione sul Web secondo la popolarità dei link: una pagina è considerata di migliore qualità rispetto a un’altra se possiede un numero maggiore di inlinks (ossia link esterni che puntano ad essa) di alta qualità.

Una formulazione semplificata del PageRank è rappresentata dalla seguente Formula:

$$\begin{equation}\rho(X) = \frac{1-\alpha}{N} + \alpha \sum\limits_{i=1}^n \frac{\rho(P_i)}{|P_i|}\end{equation}$$     (1)

 dove

  1. $$\rho(X)$$ è il valore di PageRank della pagina $$X$$ che vogliamo calcolare.
  2. $$N$$ è il numero totale di pagine note.
  3. $$n$$ è il numero di pagine che contengono almeno un link verso $$X$$.
  4. $$\rho(P_i)$$ sono i valori di PageRank di ogni pagina $$P_i$$.
  5. $$|P_i|$$ è il numero complessivo di link contenuti nella pagina $$P_i$$.
  6. $$\alpha$$ (damping factor) è una costante stabilita da Google che nella documentazione originale assume valore $$0,85$$.

Il fattore $$\alpha$$ può essere visto come la percentuale di tempo che l’utente sta nel Web seguendo i link tra le varie pagine.

Osservazione 1
Considerando la formulazione semplificata, si osserva come i valori di Page Rank siano definiti ricorsivamente; tornando all’Esempio si vede come la pagina $$P_1$$ comunichi con se stessa, pertanto per il calcolo del suo valore di PageRank (ma vale anche per le altre 4) occorre partire da un valore iniziale.

Scegliendo come vettore iniziale $$\rho(P_1, P_2, P_3, P_4, P_5) = \frac{1}{5} (1, 1, 1, 1, 1)$$, per le pagine dell’Esempio si ottiene come prima approssimazione

$$\rho(P_1, P_2, P_3, P_4, P_5) = (0.2765, 0.1065, 0.3615, 0.1065, 0.1490)$$

 

star_wars_google

Risultati restituiti da Google per la query “star wars italia”

Diamo una spiegazione del risultato ottenuto.
Notiamo che le componenti 1 e 3 del vettore PageRank hanno valori superiori alle tre rimanenti. La pagina $$P_5$$ ha ad esempio lo stesso numero di link delle pagine $$P_1$$ e $$P_3$$ ma queste sono puntate da pagine con un numero maggiore di collegamenti in entrata (la $$P_2$$ e la $$P_4$$).
Il vettore (approssimato alla prima iterazione) di PageRank ci dice in sostanza che un random surfer (navigatore Web che si muove a caso tra i vari link) visiterà la pagina $$P_3$$ per il $$36\%$$ del tempo, la pagina $$P_1$$ per il $$27\%$$ mentre la pagina $$P_5$$ per il $$14\%$$.
Ora supponiamo di andare su Google e di ricercare “Star Wars Italia“. Questo parametro, congiuntamente ad altri, definisce l’ordine dei risultati ed esaminando i risultati in Figura si osserva come le pagine $$P_1$$ e $$P_3$$ compaiano tra i primi $$3$$ risultati della ricerca.
Per concludere spieghiamo i motivi per cui il risultato, seppur attendibile, non è del tutto coincidente con quanto restituito nella realtà da Google:

  1. oltre al PageRank intervengono altri fattori nella classificazione del risultato (area geografica, attualità contenuti);
  2. la porzione di rete considerata (a 5 nodi) è infinitamente piccola rispetto a tutte le pagine realmente presenti nel Web (circa 3.130.000 risultati).

La trattazione generale del PageRank finisce qui ed inizia ora la spiegazione dettagliata dell’algoritmo, che abbraccia parecchi aspetti della matematica, quali teoria dei grafi, catene di Markov e algebra lineare (ci concentreremo soprattutto sugli ultimi due).

Il Metodo delle Potenze

Introduciamo dapprima alcune nozioni relative al metodo iterativo utilizzato per determinare il vettore di PageRank.

Definizione 1
Una matrice A non negativa si dice riducibile se esiste una matrice di permutazione P tale che

$$PAP^T=\left(\begin{matrix}B & 0 \\ 0 & D \end{matrix}\right)$$

Altrimenti si dice irriducibile.

Definizione 2
Una matrice non negativa $$A$$ si dice primitiva se è irriducibile e il suo raggio spettrale $$\rho(A)$$ è strettamente dominante (ossia l’autovalore di modulo massimo ha molteplicità algebrica pari ad 1 e non esistono altri autovalori con lo stesso modulo).

Proposizione 1
Sia $$A$$ una matrice non negativa. A è primitiva se e solo se $$\exists \ m \in \mathbb{N}$$ t.c. $$A^m>0$$.

Teorema 1
Una matrice $$A$$ non negativa e irriducibile, è primitiva se e solo se esiste $$\lim_{k \to \infty}{(\frac{A}{\rho(A)})}^k $$.

In tal caso

$$\lim_{k \to \infty}(\frac{A}{\rho(A)})^k = \frac{pq^T}{q^Tp}>0$$

dove $$p$$ e $$q^T$$ sono rispettivamente i vettori di Perron destro e sinistro di $$A$$.

Osservazione 2
Una matrice primitiva è sempre irriducibile; il viceversa non è vero in generale, si consideri ad esempio la matrice

$$\left(\begin{matrix}0 & 1 \\ 1 & 0\end{matrix}\right)$$

 

Introduciamo ora il metodo delle potenze che permette di ottenere una stima dell’autovalore dominante di una matrice e dell’autovettore ad esso associato.

Sia $$A$$ una matrice che ammetta $$n$$ autovettori indipendenti $$x_1, \dots{}, x_n$$ in $$\mathbb{R}^n$$ o $$\mathbb{C}^n$$ e sia $$\lambda_1$$ l’autovalore di modulo massimo (ossia il raggio spettrale di $$A$$), ossia tale che

$$|\lambda_1| > |\lambda_2| \geq \dots{} \geq |\lambda_n|$$

Sia $$y_0$$ un generico vettore di $$\mathbb{R}^n$$ o $$\mathbb{C}^n$$, allora

$$y_0 = \alpha_1x_1 + \alpha_2x_2 + \dots{} + \alpha_nx_n$$

ed imponiamo che $$<y_0, x1> \neq 0$$.

Consideriamo ora la successione $$y_{k+1} = Ay_k$$, si ottiene

$$y_k = Ay_{k-1} = \dots{} = A^ky_0 = A^k \sum\limits_{i=1}^n \alpha_ix_i = \sum\limits_{i=1}^n \alpha_i \lambda_i^k x_i = $$

$$\alpha_1 \lambda_1^k x_1 + \sum\limits_{i=2}^n \alpha_i \lambda_i^k x_i = \lambda_1 (\alpha_1 x_1 + \sum\limits_{i=2}^n \alpha_i \frac{\lambda_i^k}{\lambda_1^k} x_i)$$

ed essendo $$\left(\frac{\lambda_i}{\lambda_1} \right)^k \rightarrow 0 $$ per $$k \rightarrow \infty$$ si ottiene

$$y_k = \lambda_1^k \alpha_1 x_1$$

Allora si ha che:

  • la successione $$\theta_k = \frac{y_k^H y_{k+1}}{y_k^H y_k}$$ converge all’autovalore dominante di $$A$$ per $$k \rightarrow \infty$$;
  • la successione $$y_k$$ converge all’autovettore dominante di $$A$$ per $$k \rightarrow \infty$$.

Per evitare che i vettori $$y_k$$ tendano ad assumere valori troppo grandi (overflow) o troppo piccoli (underflow), ad ogni iterazione del metodo si aggiunge la condizione di normalizzazione, ossia posto $$z_0=y_0$$ e $$||w_0||=\frac{z_0}{||z_0||_2}$$ si ha

$$\left\{\begin{array}{ll}z_k =Aw_{k-1}\\w_k=\frac{z_k}{||z_k||_2}\end{array}\right.$$

Abbiamo appena dimostrato che il metodo delle potenze converge in caso di matrice diagonalizzabile con raggio spettrale strettamente dominante.

Osservazione 3
Se l’autovalore di modulo massimo non è unico, si dimostra che il metodo delle potenze non converge.

Determinazione del PageRank

Partendo dalle considerazioni iniziali sull’importanza attribuita ad una pagina Web, la definizione base di PageRank di una pagina Web $$P_j$$ è

$$\rho(P_j) = \sum\limits_{P_i \in L_{P_j}} \frac{\rho(P_i)}{|P_i|}$$

dove

  • $$L_{P_j}$$ è l’insieme delle pagine che puntano alla pagina $$P_j$$.
  • $$|P_i|$$ è il numero complessivo di link contenuti nella pagina $$P_i$$.

I valori $$\rho(P_j)$$ sono sconosciuti e per superare questo limite Brin e Page seguirono un approccio iterativo: si considera inizialmente lo stesso valore di PageRank per tutte le pagine del Web per poi procedere ricorsivamente, ossia

$$\rho_0(P_j) = \frac{1}{n} \ \ \ \ \ \ \ \ \ \ \ \ \ \forall j = 1, \dots{}, n$$
$$\rho_{k+1}(P_j) = \sum\limits_{P_i \in L_{P_j}} \frac{\rho_k(P_i)}{|P_i|}$$

o, in termini matriciali,

$$\pi_{k+1}^T = \pi_{k}^T M$$

dove

  • $$m_{i,j} := \left\{\begin{array}{ll}\frac{1}{|P_i|} \ & \exists \text{ collegamento tra }P_i \text{ e } P_j\\ {0} \ & altrimenti\end{array}\right.$$
    M è la matrice del grafo del Web e i suoi elementi sono probabilità, infatti $m_{i, j}$ rappresenta la probabilità che la pagina $P_i$ sia connessa alla pagina $P_j$.
  • $$\pi_{k}^{T} := (\rho_k(P_1), \dots{}, \rho_k(P_n))$$
    $$\pi_{k}^{T}$$ rappresenta il vettore di PageRank all’iterazione $$k$$ per le $$n$$ pagine che costituiscono il Web, con valore iniziale vettore $$\pi_0^T := \frac{1}{n}e^T = \frac{1}{n}(1, \dots{}, 1)$$.

Osservazione 4
A questo punto le considerazioni da fare sono le seguenti:

  1. Quali proprietà deve avere la matrice $$M$$ perché si possa arrivare alla convergenza?
  2. La scelta iniziale di $$\pi_0^T$$ influisce sulla convergenza?

Per rispondere alla prima domanda abbiamo bisogno prima del seguente risultato.

Teorema di Perron-Frobenius
Sia $$A \in \mathbb{R}^{n \times n}$$ una matrice non negativa e irriducibile, allora vale che:

  • il raggio spettrale $$\rho(A) \ > \ 0$$ e ha molteplicità algebrica pari a $$1$$;
  • $$\exists \ x \in \mathbb{R}^{n}$$, $$x>0$$ autovettore per $$\rho(A)$$;
  • Il vettore di Perron $$p$$ è l’unico tale che:
    1. $$p>0$$
    2. $$A p = \rho(A) p$$
    3. $$\sum\limits_{i=1}^n |p|_i = 1$$
  • $$A > 0$$, $$\rho(A)$$ è l’unico autovalore dominante.

Data la matrice $$M$$ del Web come sopra non si hanno le condizioni di convergenza, infatti si osserva il seguente problema: in caso di pagine senza link (dette anche pozzi), dopo alcune iterazioni si avranno valori alti di PageRank per questo tipo di pagine e valori nulli per le pagine che puntano a queste.

Per ovviare a questo problema viene apportata una prima modifica alla matrice $$M$$.
Le righe nulle di $$M$$ vengono sostituite con il vettore $$\frac{1}{n}e^T$$ e si ottiene

$$\hat{M} = M + \beta \frac{1}{n}e^T$$

dove le componenti $$\beta_i$$ del vettore $$\beta$$ assumono valore $$1$$ se la pagina $$P_i$$ è un pozzo e $$0$$ altrimenti.

La nuova matrice $$\hat{M}$$ ha il vantaggio di essere una matrice stocastica (ossia tale che tutti i suoi elementi siano $$\geq 0$$ e per ciascuna riga la somma delle componenti sia pari ad $$1$$).
Non siamo ancora in grado di provare la convergenza del metodo ed è necessaria un’ulteriore modifica alla matrice $$\hat{M}$$, che risulta riducibile e non possiede raggio spettrale strettamente dominante (si veda l’Osservazione 3).
Si definisce pertanto una nuova matrice $$G$$

$$G = \alpha \hat{M} + (1-\alpha) \frac{1}{n}ee^T \quad \alpha \in (0,1)$$     (2)

Il fattore $$\alpha$$ può essere spiegato in questo modo: immaginiamo di navigare sul Web seguendo la fitta rete di collegamenti link da una pagina all’altra e, ad un certo punto, di non avere più interesse nel seguire questo percorso (ad esempio vogliamo iniziare una nuova ricerca); la costante $$\alpha$$ descrive questo comportamento, ossia per il $$\alpha\%$$ del tempo si segue il percorso dei link ($$\hat{M}$$), mentre per il restante $$(1-\alpha)\%$$ del tempo sul Web si eseguono nuove ricerche.

La nuova matrice $$G$$ gode delle seguenti proprietà:

  • è stocastica (è somma di due matrici stocastiche $$\hat{M}$$ e $$\frac{1}{n}ee^T$$);
  • è primitiva (infatti $$G>0$$);
  • è irriducibile (avendo inserito link in tutte le pagine, il grafo associato è fortemente connesso, ossia è possibile andare da un qualsiasi nodo ad un altro nodo del grafo).

Applicando infine il metodo delle potenze finite alla matrice $$G$$

$$\pi_{k+1}^T = \pi_{k}^T G$$     (3)

possiamo concludere che si ha la convergenza al vettore di PageRank (che esiste ed è unico per il Teorema di Perron-Frobenius) per la matrice modificata G che descrive il nostro Web.

Esempio (Parte 2)
Riprendiamo l’esempio iniziale e osserviamo che la matrice di transizione risulta stocastica ma riducibile (e pertanto non primitiva). Procediamo ad effettuare la trasformazione (2) (con $$\alpha = 0.85$$) per poter applicare il metodo delle potenze

$$G = \alpha M_{trans} + (1 – \alpha)\frac{1}{n}ee^{T} = \begin{pmatrix}0.4550 & 0.0300 & 0.4550 & 0.0300 & 0.0300 \\ {0.2000} & 0.2000 & 0.2000 & 0.2000 & 0.2000 \\ {0.4550} & 0.0300 & 0.4550 & 0.0300 & 0.0300 \\ 0.2425 & 0.2425 & 0.2425 & 0.2425 & 0.0300 \\ 0.0300 & 0.0300 & 0.4550 & 0.0300 & 0.4550\\\end{pmatrix}$$

ed otteniamo una matrice stocastica per righe (somma delle componenti di ciascuna riga pari ad $$1$$), irriducibile (tutti i nodi comunicano tra di loro) e primitiva (ogni elemento è $$> 0$$).

A questo punto utilizziamo l’iterazione (3) ed otteniamo (si riportano per comodità le prime 7 iterazioni)

Risultati Iterazioni Metodo delle Potenze per l'Esempio 1

Risultati Iterazioni Metodo delle Potenze per l’Esempio 1

e si converge al vettore di PageRank di $$G$$ (calcolato in MatLab)

$$\rho = (0.4288684, 0.03865168, 0.4444257, 0.03865168, 0.0494025)$$

 

Per concludere rispondiamo alla seconda domanda dell’Osservazione 4.

Catene di Markov

La convergenza al vettore di PageRank non dipende dal vettore di partenza $$\pi_0^T$$. Questo segue dalle proprietà delle matrici stocastiche.

Riportiamo alcune definizioni utili per arrivare alla risposta del quesito.

Definizione 3 [Processo Stocastico]
Sia $$\left\{\Omega, A, P\right\}$$ uno spazio di probabilità, $$T$$ l’insieme dei possibili valori del parametro $$t$$, $$\xi$$ una $$\sigma – algebra$$ e $$\left\{E, \xi \right\}$$ uno spazio misurabile. Si definisce processo aleatorio di parametro $$t$$ una famiglia di variabili $$\left\{X_t\right\}_{t \in T}$$ definite in $$\Omega$$ e a valori in $$E$$.\newline
I valori assunte dalle variabili $$X_t$$ sono detti stati ed $$E$$ rappresenta il loro insieme.

Definizione 4 [Proprietà di Markov]
Un processo stocastico verifica la proprietà di Markov se per ogni istante di tempo $$t \in T$$, per ogni coppia di stati $$i, j \in E$$ e per ogni sequenza di stati $$k_0, \dots{}, k_{t-1}$$ si ha

$$P(X_{t+1} = j | X_0 = k_0, \dots{}, X_{t-1} = k_{t-1}, X_t = i) = P(X_{t+1} = j | X_t = i)$$

dove $$P(X_{t+1} = j | X_t = i) = p_{i, j}(t)$$ è detta probabilità di transizione al tempo $$t$$ dallo stato $$i$$ allo stato $$j$$.

Definizione 5
Un processo stocastico $$\left\{X_t\right\}$$ con $$t \in T$$, $$T \subseteq \mathbb{N}$$ ed $$E$$ numerabile si dice catena di Markov se rispetta la proprietà di Markov.
Una catena di Markov si dice omogenea se per ogni coppia di stati $$i, j$$ si ha che $$P(X_{t+1} = j | X_t = i)$$ è indipendente dal tempo $$t$$.

Ora per studiare le catene di Markov a stati finiti è fondamentale la seguente Definizione.

Definizione 6
La matrice $$P = (p_{i,j})$$ è detta matrice di transizione della catena di Markov se i suoi elementi rispettano le seguenti proprietà:

  • $$p_{i, j} \geq 0$$ per ogni $$i, j \in E$$
  • $$\sum\limits_{i=1}^n |p|_i = 1$$

ossia $$P$$ è una matrice stocastica.
Una catena di Markov si dice irriducibile se la matrice di transizione associata è irriducibile, mentre si definisce aperiodica se è irriducibile e la sua matrice di transizione è primitiva.

Osservazione 5
In sostanza studiare una catena di Markov a stati finiti è equivalente a studiare la matrice stocastica associata.

Abbiamo ora tutti gli elementi per stabilire la convergenza dell’algoritmo di PageRank indipendentemente dal vettore di PageRank iniziale.

Ricordiamo che la nostra matrice G è stocastica, irriducibile e primitiva.

Sia $$p^T(0)=(p_1(0), \dots{}, p_n(0))^T$$ il vettore di probabilità iniziale, allora per la proprietà di Markov si ha

$$p^T(k) = p^T(0)G^k$$

poiché $$G$$ è primitiva, per il Teorema 1 esiste il limite di $$G^k$$ ed è pari a $$e\pi^T$$, essendo $$\frac{e}{n}$$ e $$\pi^T$$ rispettivamente vettore di Perron destro e sinistro di $$G$$.

Allora si ha

$$\lim_{k\to \infty}{p^T(k)} = \lim_{k\to \infty}{p^T(0)G^k} = p^T(0)e\pi^T = \pi^T$$

poiché $$p^T(0)e = 1$$ e si ha quindi che il limite è indipendente dal vettore di probabilità iniziale $$p^T(0)$$.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.