\documentclass{article}
\usepackage{amsmath, amsfonts}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{hyperref}
\title{Math 2270-003\\ Computer Lab 5\\ Web Search}
\date{}
\voffset=-1in
\textheight=9in
\oddsidemargin=0in
\textwidth=6.5in
\begin{document}
\maketitle

Solve the following problems using Maple. Email the Maple worksheet as an attachment to:

 cashen@math.utah.edu

Labs are due on the last day of class.

Begin your Maple worksheet with the following lines:

\# Your Name

 \# Lab 5

\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$ and corresponding eigenvectors
$\bar{v}_1,\bar{v}_2,\dots,\bar{v}_n$. For any
$\bar{w}\in\mathbb{R}^n$ we may write
$\bar{w}=c_1\bar{v}_1+\dots+c_n\bar{v}_n$.
Then $B^k\bar{w}=c_1\lambda_1^k\bar{v}_1+\dots+c_n\lambda_n^k\bar{v}_n$.
As $k$ gets large, $\lambda_1^k$ becomes much larger than the other
$\lambda_i^k$, so, assuming $c_1\neq 0$, $B^k\bar{w}\approx
c_1\lambda_i^k\bar{v}_1$.
In other words, the orbit of $\bar{w}$, which is the sequence
$\bar{w}, B\bar{w}, B^2\bar{w}, B^3\bar{w},\dots$ approaches multiples
of the leading eigenvector $\bar{v}_1$. Conversely, we can find
$\bar{v}_1$ by following an orbit $\bar{w}, B\bar{w}, B^2\bar{w},
B^3\bar{w},\dots$. Let $\bar{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 websites. Let
$L=(l_{i\, j})$ be the matrix that records links between the websites:
$l_{i\,j}=1$ if site $s_i$ links to site $s_j$, and $l_{i\,j}=0$
otherwise.
(Note that the $i\,j$ entry of $L^T$ is 1 if $s_j$ links to $s_i$.)

There are two ways that a website can be important, and therefore
worthy of a top listing in our search engine. A site can be an
\emph{authority}, a site to which many other sites link, or it can be
a \emph{hub}, a site that has links to many other sites. However, in
each case it is not just the number, but also the quality of the links
that determine how important a site is. We use an iterative method to
determine the site rankings.

Let $a_i$ be the ranking of site $s_i$ as an authority, and let $h_i$
be the ranking of site $s_i$ as a hub. We collect these into
$n$--dimensional vectors $\bar{a}=(a_i)$ and $\bar{h}=(h_i)$.
Approximate these rankings
as follows. For a first approximation, let $a_i^0$ be the number of
sites that link to $s_i$, and let $h_i^0$ be the number of sites to
which $s_i$ links. We can compute these with the matrix $L$. The
number of sites to which $s_i$ links is the sum of row $i$ of $L$,
which can be found by taking the dot product of row $i$ with the
vector $\bar{1}$ consisting of all 1's. Thus, $\bar{h}^0=L\bar{1}$.
Similarly, $\bar{a}^0=L^T\bar{1}$, which counts incoming links.

The initial authority ranking of a the site $s_i$ is given by the
$i$--th component of $\bar{a}^0$. However, this ranking only counts
links, but not not consider their quality. A site is more of an
authority of the incoming links are from important hubs, rather than
from random sites. We improve the authority rankings by taking into
account the hub ranking $\bar{h}^0$. Instead of adding up all the
incoming links to $s_i$ we weight them by them by $\bar{h}^0$. Let $\bar{a}^1=L^T\bar{h}^0$.
Similarly, hubs are more important if they have many links to good
authorities, so let $\bar{h}^1=L\bar{a}^0$.

We continue in this way to improve the rankings based on the rankings
of the previous step:
\begin{gather*}
  \bar{h}^{i+1}=L\bar{a}^i\\
\bar{a}^{i+1}=L^T\bar{h}^i
\end{gather*}

Notice:
\[
  \bar{h}^{4}=L\bar{a}^3=(LL^T)\bar{h}^2=(LL^T)L\bar{a}^1=(LL^T)^2\bar{h}^0
\]
Similarly, $\bar{h}^{2k}=(LL^T)^k\bar{h}^0$ and
$\bar{a}^{2k}=(L^TL)^k\bar{a}^0$.
The rankings we want are $\bar{h}$ equals the leading eigenvector of
$LL^T$ and $\bar{a}$ equals the leading eigenvector of $L^TL$.

\section{A Sample Network}
\begin{flalign*}
&interface(displayprecision=2):with(LinearAlgebra): \end{flalign*}
Below is a model of a network. Compute the link matrix $L$.
Compute the rankings as follows:
\begin{flalign*}
&  h[0]:=L.Vector(7,1):\, Normalize(h[0],inplace):
  \,h[1]:=L.L^+.Vector(7,1):\,Normalize(h[1],inplace):\\
&H:=<h[0]\,|\,h[1]>:\\
&a[0]:=L^+.Vector(7,1):\, Normalize(a[0],inplace):
 \,a[1]:=L^+.L.Vector(7,1):\,Normalize(a[1],inplace):\\
&A:=<a[0]|a[1]>:\\
&\textbf{for}\, i\, \textbf{from}\, 2\, \textbf{to}\, 6\, \textbf{do}\,
h[i]:=L.L^+.h[i-2]:\,Normalize(h[i], inplace):\,H:=<H | h[i]>:\, 
a[i]:=L^+.L.a[i-2]:\\
&Normalize(a[i], inplace):\,A:=<A | a[i]>\, \textbf{end do}:\\
\end{flalign*}

(The command $Normalize(v,\,inplace)$ takes a vector $v$ and replaces it
by a vector in the same direction whose largest component is 1. You
could use $Normalize(v,\,inplace,\,Euclidean)$ to replace $v$ by
a unit vector.)

Observe how the rankings change at each step by considering the
matrices $H$ and $A$. These matrices will contain fractions, and will
be easier to interpret by evaluating these as decimals using $evalf$:
\begin{flalign*}
  & map(evalf,H);\, map(evalf,A);
\end{flalign*}

Estimate the eigenvectors $\bar{h}$ and $\bar{a}$ from these approximations.
Is the site with the most incoming links the best authority? Is the
site with the most outgoing links the best hub?

Verify that $\bar{h}$ is approximately an eigenvector for
$LL^T$ by computing $LL^T\bar{h}$ and normalizing. Compare the length
of $\bar{h}$ to the length of $LL^T\bar{h}$ to estimate the leading
eigenvalue. Do the same for $\bar{a}$.

\vfill

\centering
\includegraphics{internet}

\end{document}