Web Database

HITS

Hubs and Authorities

More good hubs pointing to a web page $\to$ higher authority weight

$$\begin{array}{rl}& a(v)=\sum _{u\to v}h(u)\\ & h(v)=\sum _{v\to u}a(u)\end{array}$$

Sampling

Root Set

Web pages that contain the query terms (split by spaces)

Link Pages

Web pages that are linked to the root set (either way)

Base Set

Merge the root set and the link pages

Iteration

1. Construct the adjacency matrix (row-wise matrix, 1 or 0)
2. Iterate over the authority vector and hub vector until at least 2 output is the same
3. Ranking can be done based on the 2 resulting vector

$$\begin{array}{rl}& \{\begin{array}{l}h=Ma\\ a=M^{T}h\end{array}\\ & \\ & h=M{M}^{T}h\\ & a=M^{T}Ma\end{array}$$

The sum of the elements in the authority vector is always the number of web pages

Normalization can be done to the authority/hub vector, i.e. $\frac{Element}{\text{Sum of Elements}}\cdot \text{Sum of Initial Vector}$

PageRank

Iteration

1. Construct the stochastic matrix (column-wise matrix, probability)
2. Iterate over the PageRank vector until at least 2 output is the same

$$r=Mr$$

Spider Trap

A set of web pages with no outgoing links, which would take over the importance

It can be mitigated with the following equation, where $c_1$ and $c_2$ are constants that sum up to 1

$$\begin{array}{rl}& r=c_{1}Mr+c_2\\ & c_1=0.8c_2=\left(\begin{array}{c}0.2\\ 0.2\\ 0.2\end{array}\right)\end{array}$$

The sum of the elements in the PageRank vector is always same as the sum in the initial vector