From 79ce98e03daf15cb03fc0a940cec5d871412ef96 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Tue, 13 Oct 2009 18:50:50 +0200 Subject: [PATCH] Aggiunta l'appendice con il PageRank e trascritta la prima parte della lezione del 12 ottobre. --- AppPageRank.tex | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++ CalcoloScientifico.tex | 8 ++++++ 2 files changed, 81 insertions(+) create mode 100644 AppPageRank.tex diff --git a/AppPageRank.tex b/AppPageRank.tex new file mode 100644 index 0000000..1133e67 --- /dev/null +++ b/AppPageRank.tex @@ -0,0 +1,73 @@ +\chapter{Page Rank} +In questo capitolo ci porremo il problema di calcolare il \emph{page rank} di un determinato +insieme di pagine Web (o, analogamente, documenti \emph{ipertestuali}). \\ +Con Page Rank intendiamo un ``voto'' che viene dato ad una determinata pagina o documento +che stima la sua importanza. Un algoritmo derivato da quello che verrà in seguito +esposto è utilizzato attualmente da Google (\href{http://www.google.it}{http://www.google.it}) +per ordinare i risultati di una query nel suo motore di ricerca, così come da tutti i principali +\emph{search engine} presenti sul Web. + +\section{Presentazione del modello} +Prima di tutto dobbiamo occuparci di definire il modello matematico che vogliamo usare +per schematizzare la nostra valutazione di importanza. \\ +In generale l'idea che sta alla base del Page Rank è dare importanza ad una pagina +basandosi sui link\footnote{Un link in una pagina Web, ma anche in un documento PDF come questo +è un ``puntatore'' ad un altro documento. In genere l'utente può attivare il puntatore semplicemente +cliccandoci sopra con il mouse} che in essa sono presenti. + +Alcune idee che potrebbero sembrare valide potrebbero essere valutare l'importanza di una pagina +in base al numero di link presenti nella pagina, oppure al numero di link che puntano ad essa. + +Dopo una breve riflessione ci si rende conto che entrambi i metodi introducono svariate problematiche +di affidabilità. In generale, infatti, il creatore di una pagina ha il controllo di quanti link +sono presenti in una pagina, e non fatica molto a creare delle pagine fittizie che puntano a quella +appena creata. La valutazione sarebbe quindi falsata e molto vulnerabile a frode. + +Si può però cercare di affinare l'idea di base in modo da risolvere questi inconvenienti. +Per convenzione assumiamo di numerare tutte le pagine presenti nel Web con dei numeri naturali +$1 \ldots N$ (dove $N$ è un numero dell'ordine di $10^{10}$). +Fissata una certa pagina $j$ consideriamo i link che puntano a lei. Risulta chiaro che non solo +il \textbf{numero} dei link è importante per valutare la sua importanza, ma a sua volta anche l'\textbf{importanza} +di questi dovrebbe influire. Per esempio, se la homepage di Yahoo! punta +alla pagina di una persona, è naturale che questa pagina abbia una certa rilevanza. Viceversa, se sulla +mia pagina personale io metto un link al sito della stessa persona l'importanza di questo varia di poco\footnote{ +a meno che nel momento in cui voi leggiate queste pagine io non sia diventato una persona con una certa influenza, +ma questo è probabilmente un caso da scartare}. +Un'ultima e non meno importante considerazione è che se anche Yahoo! punta al mio sito ma lo fa in una pagina +con un altro centinaio di link è una faccenda molto diversa dall'essere puntati dall'unico link in homepage. + +Stiamo quindi arrivando ad un altro modello, in cui le pagine \emph{distribuiscono la loro importanza fra i link al +loro interno}. Questo modello è molto più ragionevole del precedente, ed è molto meno predisposto a dare +risultati falsati. Vorremo però avere una sua descrizione matematica precisa. + +\section{Un po' di matematica} +Consideriamo la matrice quadrata $H = (h_{ij})$, che chiameremo \emph{matrice delle connessioni}, definita +nel seguente modo +\[ + h_{ij} = \left\{ \begin{array}{ll} + 1 & \text{se esiste un link dalla pagina} \ i \ \text{alla pagina} \ j \\ + 0 & \text{altrimenti} + \end{array} \right. +\] +Questa matrice avrà dimensione $N \times N$ ma sarà sparsa, ovvero la maggior parte dei suoi valori saranno $0$. +Per fissare le idee consideriamo la Figura~\ref{fig:web}, un modello (molto) semplificato del Web, in cui esistono solamente +3 pagine. +\begin{figure}[hb] +\[ + \xymatrix{ +{\bullet{1}} \ar@/_/[dr] \ar@/^1pc/[drr] & \\ + & {\bullet{2}} \ar@/_/[ul]& {\bullet{3}} \ar@/^/[l]} +\] +\caption{Esempio di una rete composta da 3 pagine} +\label{fig:web} +\end{figure} + +La matrice di connessione $H$ associata a questo grafo è la seguente +\[ + H = \left[ \begin{array}{ccc} + 0 & 1 & 1 \\ + 1 & 0 & 0 \\ + 0 & 1 & 0 + \end{array} \right] +\] + diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index 665b5fe..d99a093 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -17,6 +17,7 @@ \usepackage{subfigure} \usepackage{multirow} \usepackage{enumerate} +\usepackage[all]{xy} %% %% Ci piace, a causa del carattere usato (pxfonts) @@ -207,4 +208,11 @@ %% tridiagonali \include{capitolo2} +%% Comincia l'appendice, ovvero dove +%% esponiamo gli algoritmi visti con Bini +\appendix + +%% Page rank +\include{AppPageRank} + \end{document} -- 2.1.4