$(3$ mark$)($Page Rank Algorithm$)$ PageRank is the basis of Google's ranking of web pages in search results. Given a directed graph where pages are nodes and the links between pages are edges, the algorithm calculates the likelihood, or rank, that a page will be visited. The rank of a page is determined recursively by the ranks of the pages that link to it$.$ In this definition, pages that have a lot of incoming links or links from highly ranked pages are likely to be highly ranked. This idea is quite simple and yet powerful enough to produce search results that correspond well to human expectations of which pages are important. In the next section, we will see a mathematical definition of the problem and an iterative method to solve it$,$ which you will implement in this assignment.

The PageRank algorithm assumes that a web surfer is visiting some node $($web page$),$ and will either follow one of the links on that page or move to a random page $($chosen from all pages on the web$).$ The following equation recursively defines the rank $P_r(i)$ for each page i:

$P_r(i)=\frac{1-d}{N}+d{\displaystyle \underset{\text{j}\text{i}\text{n}\text{N}(i)}{\overset{?}{}}}\frac{P_r(j)}{L(j)}$

where $N$ is the number of total pages, $N(i)$ denotes the set of pages with links to page $i,L(j)$ is the number of outgoing links in page $j,$ and $d$ is the damping factor. Because of its usefulness, many researchers have explored various ways to solve this equation. In this assignment, we will pick an iterative method that is simple to implement.

$($Iterative Method for Page Rank$)$ As the name suggests, the iterative method repeats some calculation up to convergence. Let $P_r(i$;$t)$ be the rank of page $i$ at iteration $t.$ At iteration $t=0,$ all ranks are uniformly initialized to

$P_r(i$;$0)=\frac{1}{N},i=1,2,$dots,$N$

Then, we iteratively update the page rank as

$P_r(i$;$t+1)=\frac{1-d}{N}+d{\displaystyle \underset{\text{j}\text{i}\text{n}\text{N}(i)}{\overset{?}{}}}\frac{P_r(j\text{;}t)}{L(j)}$

The method converges when the $l_2$ norm of the difference between the previous and current ranks is smaller than some error bound $lon>0$ :

$\sqrt[\phantom{2}]{{\displaystyle \underset{i=1}{\overset{N}{}}}(P_r(i\text{;}t+1)-P_R(i\text{;}t){)}^2}lon$

Write a python code to implement the above iterative algorithm for page rank computation. Test your method with the following directed graph with $d=0\mathrm{.}95$ and $lon={10}^{-4}$ :

$1$