\documentclass[11pt]{article}
\usepackage{linalg}
\usepackage{amsmath}
\usepackage{graphicx}
\date{}
\newcommand{\color}[2][]{}
\title{Math 2270-2 Spring 2012\\ Computer Lab 5: Web Search}
\pagestyle{empty}
\begin{document}
\thispagestyle{empty}
\maketitle

This lab was written by Professor Chris Cashen in his Postdoc years at
Utah. Major edits were made in April 2012, to clarify the ideas, using
figures and longer explanations. The original Sample Network is used for
the calculation and the answer set for the lab remains the same as
written by Chris Cashen.

 {\bf Submit your project} on the due date in class as a worksheet print. {\bf Submit study group} efforts as one worksheet print with multiple names.

\bigskip
See Section 6.7 of the text for problem background.

\section{Introduction}
Suppose $B$ is an $n\times n$ matrix with real eigenvalues
$\lambda_1>\lambda_2>\dots >\lambda_n$. Denote the $n$ eigenpairs by
$(\lambda_1,\vec{v}_1),(]lambda_2,\vec{v}_2),\dots,(\lambda_n,\vec{v}_n)$.

The $n$ vectors $\vec{v}_1,\ldots,\vec{v}_n$ are independent and span
$\Rr^n$, therefore for any $\vec{w}\in\Rr^n$ we may write
$$\vec{w}=c_1\vec{v}_1+\dots+c_n\vec{v}_n.$$
We verify that $B\vec{v}_1 = \lambda_1 \vec{v}_1$ implies
$$B^2\vec{v}_1 = \lambda_1B\vec{v}_1 =\lambda_1\lambda_1\vec{v}_1=\lambda_1^2\vec{v}_1.$$
Similarly, $B^3\vec{v}_1 = \lambda_1^3\vec{v}_1$, and in general
$B^k\vec{v}_1 = \lambda_1^k\vec{v}_1$. The same holds for any other
eigenpair. Then
$$\begin{array}{lcl}
B^k\vec{w}  &=&
c_1\lambda_1 B^k\vec{v}_1+\cdots+c_n\lambda_n B^k\vec{v}_n \\
&=& c_1\lambda_1^k\vec{v}_1+\cdots+c_n\lambda_n^k\vec{v}_n \\
&=& \lambda_1^k\left(c_1\left(
\frac{\lambda_2}{\lambda_1}\right)^k\vec{v}_1+\cdots+
c_n\left(\frac{\lambda_n}{\lambda_1}\right)^k\vec{v}_n \right) \\
 &\approx & \lambda_1^k c_1 \vec{v}_1 \quad\mbox{as $k\to\infty$}.
\end{array}
$$
In other words, the orbit of $\vec{w}$, which is the sequence
$\vec{w}, B\vec{w}, B^2\vec{w}, B^3\vec{w},\dots$ approaches multiples
of the leading eigenvector $\vec{v}_1$. Conversely, we can find
$\vec{v}_1$ by following an orbit $\vec{w}, B\vec{w}, B^2\vec{w},
B^3\vec{w},\dots$. Let $\vec{v}_1$ be a vector pointing in the
direction that the orbit is tending. If $n$ is large this approach is easier
than trying to compute roots of the characteristic polynomial of $B$.

In Section 6.7 of the text this approach is used to model an internet
search engine. Let $s_1,\dots, s_n$ be a list of web sites. Let
$L=(l_{i\, j})$ be the incidence matrix that records links between the
web sites:
$l_{i\,j}=1$ if site $s_i$ links to site $s_j$, and $l_{i\,j}=0$
otherwise.
By swapping rows and columns,  the $i\,j$ entry of the transpose $L^T$
is 1 if $s_j$ links to $s_i$.

There are two ways that a web site can be important, and therefore
worthy of a top listing in the search engine.
\begin{description}
\item[{\bf authority}]
A site $s$ is an
\emph{authority} if many other sites link to $s$.
\item[{\bf hub site}]
A site $s$ is a \emph{hub} if $s$ links to many other sites.
\end{description}

\subsection*{Ranking a Web Site}

Initially, the ranking of a web site $s$ is a simple count, defined as
follows.
\begin{center}
\begin{tabular}{lcl}
$a_i^0$ &=& the count of the number of sites $s$ that link to site $s_i$\\
     &=& sum of row $i$ elements in incidence matrix $L^T$, \\
$h_i^0$ &=& the count of the number of sites $s$ to which $s_i$ links \\
     &=& sum of row $i$ elements in incidence matrix $L$.
\end{tabular}
\end{center}
Then $a_i^0$ is the authority ranking of site $s_i$ and $h_i^0$ is the
hub ranking of site $s_i$.

\begin{center}
\input{authority.t}
\end{center}


\begin{center}
\input{hub.t}
\end{center}



Define vectors
$$\vec{a}^0 = \colvector{a_1^0 \\ a_2^0 \\ a_3^0 \\ \vdots},
\quad
\vec{h}^0 = \colvector{h_1^0 \\ h_2^0 \\ h_3^0 \\ \vdots}.$$

The number of links and also the quality of the links determines the
importance of a site. We use an iterative method to determine the site
rankings, denoted
$$\begin{array}{rl}
\mbox{\bf Authority:~} & \vec{a}^0, \vec{a}^1, \vec{a}^2, \ldots, \\
\mbox{\bf hub:~} & \vec{h}^0, \vec{h}^1, \vec{h}^2, \ldots.
 \end{array}$$

We can compute the initial authority rankings and the initial hub
rankings with the incidence matrix $L$.
$$
\begin{array}{lcl}
\vec{a}^0 &=& L^T \vec{1} \\
\vec{h}^0 &=& L \vec{1} \\
\vec{1} &=& \colvector{1 \\ 1 \\ \vdots \\ 1}.
\end{array}
$$
This works because $\row(L,i)\vec{1} = $ sum of the elements in row $i$
of $L$. This counts outgoing links from a hub, while
$\row(L^T,i)\vec{1} = $ sum of elements in row $i$ of $L^T$ is the count
of the number of incoming links to an authority.

The initial authority ranking of a the site $s_i$ is given by the
$i$--th component of $\vec{a}^0$. However, this ranking only counts
links, but does not consider link quality. A site is a better
authority if the incoming links are from important hubs, rather than
from random sites. We improve the authority rankings by taking into
account the hub ranking $\vec{h}^0$. Instead of adding up all the
incoming links to $s_i$ we weight them by them by $\vec{h}^0$. We
define the next iteration to rank an authority by the equation
$\vec{a}^1=L^T\vec{h}^0$.

Similarly, hubs are more important if they have many links to good
authorities, so we define the next iteration to rank a hub by the
equation $\vec{h}^1=L\vec{a}^0$.

We continue in this way to improve the rankings based on the rankings
of the previous step and define by iteration the hub and authority
rankings by the equations
$$\begin{array}{lcl}
  \vec{h}^{i+1} &=& L\vec{a}^i\\
   \vec{a}^{i+1} &=& L^T\vec{h}^i
\end{array}$$

Compute new equations for the iterates as follows.
$$ \begin{array}{lcl}
  \vec{h}^{4}
&=& L\vec{a}^3\\
 &=& (LL^T)\vec{h}^2 \\
 &=& (LL^T)L\vec{a}^1\\
 &=& (LL^T)^2\vec{h}^0, \\
 & & \mbox{and in general} \\
 \vec{h}^{2k} &=&(LL^T)^k\vec{h}^0.
\end{array}
$$
Similarly
$$ \begin{array}{lcl}
  \vec{a}^{4}
&=& L^T\vec{h}^3\\
 &=& (L^TL)\vec{a}^2 \\
 &=& (L^TL)L^T\vec{h}^1\\
 &=& (L^TL)^2\vec{a}^0, \\
 & & \mbox{and in general} \\
 \vec{a}^{2k} &=&(L^TL)^k\vec{a}^0.
\end{array}
$$
The rankings we want are:
\begin{quote}
 $\vec{h}$ equals the leading eigenvector of $LL^T$ and

 $\vec{a}$ equals the leading eigenvector of $L^TL$.
\end{quote}

\begin{center}
\includegraphics[scale=0.8]{internet}
\end{center}
\section{A Sample Network}

Above is a model of a network representing several web sites.

{\bf Problem 1}. Compute the incidence matrix $L$ from the diagram.

Please verify this matrix. For example, \verb|2 --> 1|, \verb|6 --> 1|, \verb|7 --> 1|,
which implies \verb|col(L,1)=Vector([0,1,0,0,0,1,1])|.
\begin{verbatim}
L := <
<0, 1, 0, 0, 0, 1, 1>|
<1, 0, 1, 1, 0, 1, 0>|
<0, 0, 0, 1, 0, 0, 1>|
<0, 0, 0, 0, 0, 0, 1>|
<0, 0, 0, 1, 0, 1, 1>|
<0, 0, 0, 0, 0, 0, 1>|
<1, 0, 0, 0, 1, 0, 0>>;
\end{verbatim}

{\bf Problem 2}. Compute the rankings as follows:
\begin{verbatim}
# Compute the iterates a[0] to a[19] and h[0] to h[19].
fix:=x->Normalize(x,inplace):
Ones:=Vector(7,1):
h[0] := L.Ones; fix(h[0]);
a[0] := Transpose(L).Ones; fix(a[0]);
h[1] := L.a[0]; fix(h[1]);
a[1] := Transpose(L).h[0]; fix(a[1]);
for i from 2 to 19 do  h[i] := L.Transpose(L).h[i-2]; fix(h[i]); end do:
for i from 2 to 19 do  a[i] := Transpose(L).L.a[i-2]; fix(a[i]); end do:
# Do 10 iterations to find approximate eigenvectors for L^TL and LL^T.
H := <h[0] | h[1]>: for i from 2 to 9 do H := <H | h[i]>; end do:
A := <a[0] | a[1]>: for i from 2 to 9 do A := <A | a[i]>; end do:
A10:=map(evalf, A);
H10:=map(evalf, H);
\end{verbatim}

The command {\tt Normalize(v,inplace)} takes a vector $v$ and replaces it
by a vector in the same direction whose largest component is 1.

Observe how the rankings change at each step by considering the
matrices $H$ and $A$. These matrices will contain fractions. It is
easier to interpret $H$ and $A$ by using decimals instead of fractions:
\begin{verbatim}
A10:=map(evalf, A);
H10:=map(evalf, H);
\end{verbatim}

The last column of each matrix is an eigenvector approximation.

{\bf Problem 3}. Compute approximate eigenvectors $\vec{h}$ and $\vec{a}$ from
these matrices, using $\vec{h}=\col(A10,10)$ and $\vec{a}=\col(A10,10)$.

\begin{verbatim}
# Approximate eigenvectors are the last columns of the two matrices A,H.
v1:=map(evalf,Column (A10,10)); v2:=map(evalf,Column (H10,10));
\end{verbatim}

{\bf Problem 4}. Calculate the length of $LL^T\vec{h}$ and the length of
$\vec{h}$, then divide to estimate the leading eigenvalue $\lambda_2$ of $LL^T$. 
{\bf Repeat} for $L^TL\vec{a}$ and $\vec{a}$ to estimate the leading eigenvalue $\lambda_1$ of $L^TL$.
This idea comes from the eigenpair relation
$$ A\vec{v} =\lambda \vec{v}$$
which implies for $\lambda>0$ the equation
$$ \lambda = \frac{\| A\vec{v} \|}{\| \vec{v} \|}.$$


\begin{verbatim}
# Verify eigenpair (lambda2,v2)
ans2:=L.Transpose(L).v2;
lambda2:=Norm(ans2)/Norm(v2);
ans2-lambda2*v2; # should be zero
\end{verbatim}

{\bf Problem 5}. Verify that $\vec{h}$ is approximately an eigenvector
for $LL^T$ by computing $LL^T\vec{h}-\lambda_2\vec{h}$. It should be nearly the zero vector.
Repeat for $\vec{a}$ an eigenvector of $L^TL$, by computing $L^TL\vec{a} - \lambda_1\vec{a}$, which again should be nearly the zero vector.


\begin{verbatim}
# Verify eigenpair (lambda2,v2)
ans2:=L.Transpose(L).v2;
lambda2:=Norm(ans2)/Norm(v2);
ans2-lambda2*v2; # should be zero
\end{verbatim}
{\bf Problem 6}. Is the site with the most incoming links the best authority? Is the
site with the most outgoing links the best hub?

\end{document}
