\documentclass{article}% \usepackage{amsmath}% \setcounter{MaxMatrixCols}{30}% \usepackage{amsfonts}% \usepackage{amssymb}% \usepackage{graphicx} %TCIDATA{OutputFilter=latex2.dll} %TCIDATA{Version=5.00.0.2552} %TCIDATA{CSTFile=40 LaTeX article.cst} %TCIDATA{Created=Monday, October 27, 2014 11:34:53} %TCIDATA{LastRevised=Monday, October 27, 2014 11:43:15} %TCIDATA{} %TCIDATA{} %TCIDATA{} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \begin{document} \title{Introduction to PageRank} \maketitle Consider the following web.% %TCIMACRO{\FRAME{dtbpF}{2.9921in}{2.2474in}{0pt}{}{}{web1.wmf}% %{\special{ language "Scientific Word"; type "GRAPHIC"; %maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F"; %width 2.9921in; height 2.2474in; depth 0pt; original-width 9.5998in; %original-height 7.1996in; cropleft "0"; croptop "1"; cropright "1"; %cropbottom "0"; filename 'pics/web1.wmf';file-properties "XNPEU";}} }% %BeginExpansion \begin{center} \includegraphics[ natheight=7.199600in, natwidth=9.599800in, height=2.2474in, width=2.9921in ]% {pics/web1.wmf}% \end{center} %EndExpansion 1) Give a ranking of the pages in the web where $x_{k}$ equal the number of backlinks for page $k,$ i.e., the number of links into page $k.$ 2) Explain why the rankings of pages $1$ and $4$ should not be the same since page $1$ has a ranking from a more important page than page $4$ does. 3) Now let $x_{k}$ be the ranking of page $k$ given so that the ranking of any page is equal to the sum of the rankings from each page linking into it. Show that this gives a systems of equations \begin{align*} x_{1} & =x_{3}+x_{4}\\ x_{2} & =x_{1}\\ x_{3} & =x_{1}+x_{2}+x_{4}\\ x_{4} & =x_{1}+x_{2}. \end{align*} Now show that this system has no solutions! Hint: solve the last 3 equations and then show it is not consistent with the first equation. 4) Now let's change the ranking so that each page gets a single vote that is divided equally among its outlinks, and the ranking $x_{k}$ is equal to the sum of the votes times the rankings of all backlinks. The system is now \begin{align*} x_{1} & =x_{3}+\frac{1}{2}x_{4}\\ x_{2} & =\frac{1}{3}x_{1}\\ x_{3} & =\frac{1}{3}x_{1}+\frac{1}{2}x_{2}+\frac{1}{2}x_{4}\\ x_{4} & =\frac{1}{3}x_{1}+\frac{1}{2}x_{2}. \end{align*} Show that this system can be solved to get $x_{1}=1,$ $x_{2}=\frac{1}{3},$ $x_{3}=\frac{3}{4},$ $x_{4}=\frac{1}{2}.$ Notice that $x_{1}$ has the highest ranking! This is because $x_{3}$ threw its whole vote to $x_{1}$ and so that even though $x_{3}$ got votes from three different sites, they still do not total as much as what $x_{1}$ gets. Note, usually we will rescale so that the sum is equal to $1,$ and so we get $x_{1}=\frac{12}{31},\;\;x_{2}=\frac{4}{31},\;\;x_{3}=\frac{9}{31}% ,\;\;x_{4}=\frac{6}{31}.$ \end{document}