IR - 15 - Link Analysis

• Data: [2020-01-10 ven]

• Sito corso: link

• Slides:

• Introduzione: In questa lezione abbiamo analizzato delle tecniche di link analysis che ci permettono di calcolare la rilevanza di un documento rispetto a come è relazionato agli altri documenti. Per tutta la lezione si suppone quindi di lavorare con collezioni di documenti che presentano degli hyperlinks, ovvero dei collegamenti tra i vari documenti, in modo tale che la rilevanza di un documento \(d\) dipende anche dal numero e dalla rilevanza dei documenti che fanno riferimento a \(d\).

Supponiamo di avere un documento \(d_1\) che punta ad un altro documento \(d_2\) (\(d_1 \Rightarrow d_2\)). Per anchor text intendiamo il testo presente nel documento \(d_1\) che descrive il contenuto del documento \(d_2\).

Molto spesso risulta essere utile andare ad incizzare non solo il testo del documento \(d_2\), ma anche l'anchor text che punta al documento \(d_2\).

Un tipico esempio in cui la link analysis risulta essere utile è il caso della rilevanza nel contesto degli articoli scientifici. La rilevanza di un articolo scientifico infatti dipende dalla rilevanza e dal numero di articoli che lo citano.

Volendo formalizzare il tutto, supponiamo di lavorare in un grafo \(G=(V,E)\) in cui i nodi \(V = \{1, 2, ..., N\}\) sono gli articoli scientifici e abbiamo un arco \((i, j) \in E\) quando l'articolo \(i\) cita l'articolo \(j\). Definiamo quindi la citation matrix \(H = (h_{i, j})_{i, j}\) nel seguente modo

\[h_{i, j} := \frac{C_{i, j}}{C_i}\]

dove \(C_{i}\) è il numero di archi uscenti dall'articolo \(i\), e \(C_{i, j}\) è il numero di archi uscenti da \(i\) che puntano a \(j\). In altre parole \(h_{i, j}\) è la frazione di citazioni all'articolo \(j\) contenute nell'articolo \(i\). Nel contesto degli articoli scientifici poi, dato che ci può essere al massimo una sola citazione, troviamo che

\[h_{i, j} = \begin{cases} \frac{1}{C_i} \,\,\,&,\,\,\, i \text{ cita } j \\ 0 \,\,\,&,\,\,\, \text{ altrimenti } \\ \end{cases}\]

L'influence score dell'articolo \(j\) è denotato con \(\pi_j\) e può essere calcolato nel seguente modo

\[\pi_j = \sum\limits_{i} \pi_i \cdot h_{i, j}\]

che utilizzando una notazione matriciale equivale a dire che

\[\pi = \pi \cdot H\]

Per ottenere il vettore \(\pi\) con l'influenza di tutti gli articoli dobbiamo quindi trovare l'autovettore della matrice \(H\) associato all'autovalore \(\lambda = 1\). Lo scopo della link analysis è proprio quello di capire le condizioni di esistenza di questo autovettore rispetto alla struttura della matrice \(H\).

Il page rank è basato sulla citation analysis, con però alcune modifiche derivanti dal contesto di utilizzo, ovvero il web. La formula per calcolare l'influenza del documento \(v\), che in questo caso è una pagina web, è la seguente

\[\pi(v) := \frac{(1 - \delta)}{n} + \delta \cdot \sum\limits_{i = 1}^n \frac{\pi(v_i)}{O(v_i)}\]

dove,

• \(v :=\) pagina di interesse.

• \(\delta :=\) dumping factor.

• \(v_1, ..., v_n :=\) pagine che puntano a \(v\)

• \(O(v_i) :=\) numero di hyperlinks uscenti da \(v_i\).

Il dumping factor viene introdotto per controllare la quantità di rilevanza che si ottiene tramite gli hyperlinks.

Volendo formalizzare il tutto con la notazione matriciale otteniamo

\[\pi = \big(1-\delta, 1-\delta, \ldots, 1-\delta\big) + \delta \cdot \pi \cdot A\]

dove \(A\) rappresenta la matrice stocastica associata al grafo, ed è definita come segue

\[A = (a_{i, j})_{i, j}, \,\,\,\, a_{i, j} := \begin{cases} 1 \,&,\,\,\, \text{ esiste un link dal documento } i \text{ al documento } j \\ 0 \,&,\,\,\, \text{ altrimenti} \\ \end{cases}\]

TODO: continue this..

L'idea del metodo hubs and authorities è assegnare ad ogni pagina \(d\) web due valori: un valore di authority, denotato con \(a(d)\), e un valore di hub denotato con \(h(d)\). Questi valori sono relazionati come segue:

• Una pagina ha un buon valore di hub per un particolare topic quando punta a pagine con un buon valore di authority rispetto a quel particolare topic.

• Una pagina ha un buon valore di authority per un particolare topic quando è puntata da pagine con un buon valore di hub rispetto a quel particolare topic.

Per computare i valori di hubs e authorities l'idea è quella di procedere in modo iterativo. Si inizia definendo i valori di hubs e di authority ad \(1\) per ogni documento, e poi si utilizzano le seguenti formule in modo sequenziale per aggiornare i valori

• Update valori hub: \[h(d) = \sum\limits_{d \to y} a(y)\]

• Update valori authority: \[a(d) = \sum\limits_{y \to d} h(y)\]

Dopo un po' di iterazione, i valori di hubs e authority convergono ad un valore limite.

Nuovamente possiamo utilizzare la notazione matriciale per esprimere l'algoritmo HITS (Hubs and Authorities) nel seguente modo: prima definiamo i vettori che contengono i valori di hubs e authorities

• \(\overrightarrow{h} = (h_1, h_2, \ldots, h_N )\)

• \(\overrightarrow{a} = (a_1, a_2, \ldots, a_N )\)

e poi descriviamo come aggiornarli

• \(\overrightarrow{h} = A \cdot \overrightarrow{a}\)

• \(\overrightarrow{a} = A^T \cdot \overrightarrow{h}\)

Osservazione 1: Anche HITS formalizza il problema della link analysis come un problema di autovettori della matrice di adiacenza del grafo \(A\).

Osservazione 2: Un'altra trattazione (più approfondita) di questo algoritmo è disponibile nel seguente link: AR - 07 - Reti di Informazioni I.