Link Analysis

Appunti presi dalle lezioni dell'anno 2021.

Non è facile formalizzare il concetto di importanza di una pagina web, non ci si può basare semplicemente (ad esempio) sul numero di keywords di una pagina (problema dello spamming). \(\rightarrow\) Si può pensare di misurare il numero di link entranti della pagina! Viene quindi analizzato il grafo dei collegamenti ipertestuali delle pagine \(\rightarrow\) tecnica della link analysis.

Nascono quindi degli algoritmi di page rank, che si basano totalmente sul grafo delle dipendenze, dando in output un livello di "autorevolezza" della pagina, ignorando il contenuto.

Algoritmo che stila il ranking del web (a priori). Esistono anche algoritmi come HITS che effettuano il ranking di un piccolo subset di pagine in base alla query dell'utente. Queste tecniche si basano sulla natura anarchica del web.

Page rank considera anche l'autorità della sorgente del link!

\begin{equation} R(P) = \overbrace{(1-\alpha) \sum_{q:q \rightarrow p}\frac{R(q)}{N_{q}}}^\text{p. di essere arrivato sulla pagina da un predecessore} + \overbrace{\alpha E(p)}^\text{p. di essere arrivato sulla pagina a caso} \end{equation}

Essenzialmente ogni documento sorgente \(q\) distribuisce equamente la sua autorevolezza a tutte le pagine a cui punta.

  • \(\alpha\) serve per "tunare" la formula per dare più o meno peso al fattore random.

  • l'aggiunta di \(E(p)\) serve anche per prevenire il fenomeno del rank sink, che assorbe tutto il rank del sistema.

  • \(E(p)\) può essere tunato in base all'utente, ad esempio in base alle sue ricerche passate. In questo modo viene data un'autorevolezza più alta in modo personalizzabile.

  • \(O(\log(n))\) dove n è il numero di links. Recentemente la Distributed Page Rank Computation ha ridotto i tempi di convergenza di circa 5 volte.

  • E' importante avere un algoritmo efficiente perchè il page rank viene lanciato spesso, dato che la struttura del web cambia continuamente.

  • Ultimamente sono stati sviluppati metodi che riducono la grandezza del grafo per farlo stare in memoria principale.

  • Ogni volta che viene lanciato Page Rank non si ricreano i valori da 0, ma esistono metodi per "aggiornare" i valori già esistenti all'interno del DB.