Google: il problema del page ranking

• Vediamo il modello matematico.

• Supponiamo che siano n le pagine del web, e definiamo la matrice seguente:

h₁₁ h₁₂ h_1n h₂₁ h₂₂ h_2n H = . . . . . .

h_n1 h_n2 h_nn

1 se c’è un link dalla pagina i alla pagina j con hij =

0 altrimenti

numero di link che partono dalla pagina i: r_i

• Sommando i valori sulla colonna j si trova il numero di pagine che puntano alla pagina i: c_j.

Google: il problema del page ranking

• Indichiamo ora con x_jl’importanza della pagina j; risulta:

x_j= h_1jx₁/r₁ + h_2jx₂/r₂+ … + h_njx_n/r_n per j = 1, 2, 3, …, n

• Questo è un sistema lineare in n equazioni ed n incognite. Le soluzioni x₁, x₂, …, x_n forniscono il livello di importanza delle n pagine: page rank.

• L’equazione usata in Google è un po’ diversa, perché

“pesata” con un parametro e le soluzioni che derivano sono tutti valori compresi tra 0 e 1.

Google: il problema del page ranking

• Le pagine attive (odierne) sono oltre n= 8.5 ××××10⁹

• Un sistema lineare con la regola di Cramer si risolve con un numero di operazioni dell’ordine di n!.

• Il metodo di eliminazione di Gauss risolve il sistema con circa 2n³/3operazioni.

• Se usassimo quest’ultimo avremmo un numero di operazioni dell’ordine di:

2/3 ×××× (8.5 10⁹)³ ~4.1 ×××× 10²⁹

(miliardi di miliardi di miliardi) di operazioni aritmetiche.

Google: il problema del page ranking

• Uno dei calcolatori più veloci al mondo è attualmente il Blue Gene dell’IBM.

• Ha una velocità di circa 478 teraflops:

4.78××××10¹⁴operazioni al secondo (1 tera = 1000 giga)

• Per eseguire 4.1××××10²⁹ operazioni impiegherebbe più di 27 milioni di anni.

• Come può essere se Page e Brin calcolano il page rank ogni mese?

• Anche un calcolatore mille volte più veloce non risolverebbe il problema.

Google: il problema del page ranking

• Esistono metodi numerici (metodi che costruiscono soluzioni approssimate che possono essere implementate sul calcolatore) con i quali si riesce a risolvere il sistema lineare, in tempi più brevi.

• Si parte da una ipotetica soluzione, si stima un errore e in maniera iterativa la si migliora; si costruisce così una successione che converge indipendentemente dalla approssimazione iniziale:

x_j⁽¹⁾, x_j⁽²⁾, x_j⁽³⁾, …. x_j

con un errore di approssimazione che risulta essere:

e^(k)≤ λ^k dove λ (0 < λ < 1) è il modulo del secondo autovalore più grande di una certa matrice.

Google: il problema del page ranking

• L’algoritmo è molto più efficiente: il numero di prodotti e di somme dipende dal numero di 0 della matrice H, che solitamente sono molti (la matrice è sparsa); se ci fossero circa 50 elementi non nulli su una riga, l’algoritmo implementato sul calcolatore impiegherebbe pochi secondi per trovare la soluzione.

• Questo è il metodo adottato in Google.

HTML

• Un sito Web è costituito da più pagine (testo, immagini, video) collegate tra loro; volendo costruire un sito per prima cosa occorre pianificarne la struttura (Laganà, Righi, Romani Cap.11)

• Uno dei linguaggi per la costruzione di siti

Web è HTML (HyperText Markup

Language).

• Il file che contiene il testo scritto in questo linguaggio ha estensione .htm o .html

HTML

• Caratteristica del linguaggio è l’uso di tag, parole chiave che indicano l’operazione che deve essere eseguita sulla stringa che racchiudono.

• I tag sono racchiusi tra parentesi angolari;

ognuno ha il suo corrispondente di chiusura composto dal tag stesso preceduto dal simbolo /.

HTML

• Ogni documento HTML inizia e termina con la seguente coppia di tag:

<HTML>

…..

</HTML>

• Alcuni tag indicano l’inizio di una nuova riga

<BR>(andare a capo) o di un paragrafo <P>

(andare a capo e lasciare una riga bianca) e non hanno necessariamente il tag di chiusura.

HTML

• Solitamente un documento è suddiviso in una sezione di testa:

<HEAD> </HEAD>

e un corpo:

<BODY> </BODY>

• Nella sezione di testa si può inserire un titolo che il browser (Mozilla, Explorer, …) assegnerà al documento:

<TITLE> </TITLE>

HTML

• Alcuni tag di uso frequente:

<CENTER> testo </CENTER >

• scrive il testo nella zona centrale della finestra

<LI> … </LI>

• introduce un simbolo (un pallino o un numero) per rappresentare un elenco (non ordinato o ordinato); il tag per l’elenco ordinato è <OL>

per quello non ordinato <UL> con i rispettivi tagdi chiusura.

HTML

<B> … </B>

• grassetto

• Per introdurre caratteri speciali si deve scrivere una codifica preceduta dal simbolo &

&gt > (parentesi del tag)

&lt <

&egrave è

&Egrave È

&amp &

HTML

• Si possono costruire dei livelli di intestazione con dimensione di caratteri che diminuisce:

<H1> … </H1>

<H2> … </H2>

<H3> … </H3>

fino a 6 livelli.

• Si possono introdurre immagini

<IMG SRC="nomefile.jpeg">

HTML

• Collegamenti ad altre pagine. Il tag di riferimento è

<A HREF=" posizione pagina">

visualizzazione del link </A>

• Per una pagina esterna si deve fornire l’indirizzo completo, ad esempio http://www.nomedelsito

• Per una pagina locale, solo il nome del file.

• Vediamo un esempio.

HTML

<HTML>

<HEAD>

<TITLE>Pagina personale di Mario Rossi </TITLE>

</HEAD>

<BODY>

<H1>

<IMG SRC="bandiera.jpeg">

HTML

<B><CENTER><FONT COLOR = fuchsia> MARIO ROSSI

</FONT> </CENTER></B></H1>

<H2>

<B><CENTER><FONT

COLOR=green>futuro studente di ingegneria</FONT> </CENTER></B>

</h2>

<P><BR>

<HR><BR>

HTML

<B> Nome:</B> Mario Rossi (nato a ...., il 1 gennaio

2011)<BR>

<B>Indirizzo:</B> Via ...

<BR>

<B>Città :</B> da definire <BR>

HTML

<B>e-mail (per ora in

"prestito" ):</B>

<A HREF="mailto:

laurap@math.unipd.it">

laurap@math.unipd.it

</A>

<BR>

<HR>

<LI>

HTML

<B><A HREF=

"http://www.math.unipd.it/

~laurap/didattica/

Informatica-EN-0910/">

Corso di Informatica </A>

per Ingegneria dell'Energia

</B>

</LI>

<BR>

<HR>

<P>

HTML

<P>

<LI>

<A HREF="pagina2.html">

<B>IMMAGINE</B></A>

</LI>

</BODY>

</HTML>

Riepilogo TDA e strutture di

Nel documento Matlab Matlab Matlab Matlab (pagine 21-26)