# Simple PageRank example

PageRank is a algorithm used by Google to rank the 'importance' of a web page. The concept is that every web page has an importance score, and it 'endows' its importance evenly amongst the pages to which it links. The will lead to a problem where the ranking of all pages is an eigenvalue problem. We will demonstrate the process for the small web of four pages.

Consider a web of four pages, $p_{0}$, $p_{1}$, $p_{2}$ and $p_{3}$. Consider the scenario:

- $p_{0}$ links to: $p_{1}$, $p_{2}$ and $p_{3}$
- $p_{1}$ links to: $p_{2}$ and $p_{3}$
- $p_{2}$ links to: $p_{0}$
- $p_{3}$ links to: $p_{0}$ and $p_{2}$

We can build a directed graph to describe the connections, and for this we use the package `networkx`. To visualise the graph, the packages `pygraphviz` and `pydot` are required.


```
import networkx as nx

# Create a directed networkx graph
G = nx.DiGraph()

# Add web pages (graph nodes)
for i in range(4):
   G.add_node(i, label="p" + str(i))

# Add outgoing web links with weights (directed graph edges)
G.add_edge(0, 1, weight=1.0/3.0, label="1/3")
G.add_edge(0, 2, weight=1.0/3.0, label="1/3")
G.add_edge(0, 3, weight=1.0/3.0, label="1/3")

G.add_edge(1, 2, weight=1.0/2.0, label="1/2")
G.add_edge(1, 3, weight=1.0/2.0, label="1/2")

G.add_edge(2, 0, weight=1.0, label="1")

G.add_edge(3, 0, weight=1.0/2.0, label="1/2")
G.add_edge(3, 2, weight=1.0/2.0, label="1/2")

# To plot graph, convert to a PyGraphviz graph for drawing
Ag = nx.to_agraph(G)
Ag.layout(prog='dot')
Ag.draw('web.png')
from IPython.display import Image
Image('web.png')
```

Note that edges have been given a weight which is $1/n$, where $n$ is the number of outgoing link/edges from a page/node. The is the fraction of page's importance/rank that it can give to the pages to which it links. 

If we denote the rank/importance of page $i$ by $x_{i}$, we can express the importance of each page:

$$
\begin{align}
x_{0} =& x_{2} + \tfrac{1}{2}x_{2}
\\
x_{1} =& \tfrac{1}{3}x_{0} 
\\
x_{2} =& \tfrac{1}{3}x_{0} + \tfrac{1}{2}x_{1} + \tfrac{1}{2}x_{3}
\\
x_{3} =& \tfrac{1}{3}x_{0} + \tfrac{1}{2}x_{1}
\end{align}
$$

We can express this as a system of equation:

$$
\underbrace{
\begin{bmatrix}
0 & 0 & 1 & \tfrac{1}{2}
\\
\tfrac{1}{3} & 0 & 0 & 0
\\
\tfrac{1}{3} & \tfrac{1}{2} & 0 & \tfrac{1}{2}
\\
\tfrac{1}{3} & \tfrac{1}{2} & 0 & 0
\end{bmatrix}}_{\boldsymbol{A}}
\begin{bmatrix}
x_{0} \\ x_{1} \\ x_{2} \\ x_{3}
\end{bmatrix}
=
\begin{bmatrix}
x_{0} \\ x_{1} \\ x_{2} \\ x_{3}
\end{bmatrix}
$$

This is an eigenvalue problem with eigenvalue $\lambda = 1$. To solve the problem we need to find the corresponding eigenvector.

First, we can create the matrix $\boldsymbol{A}$ directly from the graph (note that we added weights to the graph edges when building the graph):


```
# Get the matrix containing the graph weights
A = (nx.adjacency_matrix(G).T).getA()
print A
```

    [[ 0.          0.          1.          0.5       ]
     [ 0.33333333  0.          0.          0.        ]
     [ 0.33333333  0.5         0.          0.5       ]
     [ 0.33333333  0.5         0.          0.        ]]


Note that the columns of $\boldsymbol{A}$ sum to one. Such a matrix is known as a *stochastic matrix*. In our context, what is important is that the largest eigenvalue (in absolute terms) for such a matrix is one. Therefore, we are looking for the eigenvector associated with the largest eigenvalue.


## Direct computation of the PageRank vector

To find the solution, we can compute the eigenvectors of $\boldsymbol{A}$, and pick the eigenvectors that corresponds to $\lambda = 1$:


```
# Compute the eigenvalues and eigenvectors
import numpy as np
evalues, evectors = np.linalg.eig(A)

# Print largest eigenvalue and corresponding eigenvector
print("The maxiumum eigenvalue is: {}".format(np.max(evalues)))
evector = evectors[:, np.argmax(evalues)]
evector /= np.linalg.norm(evector, 1)
print("The PageRank vector (eigenvector) is: \n {}".format(evector))
```

    The maxiumum eigenvalue is: (1+0j)
    The PageRank vector (eigenvector) is: 
     [ 0.38709677+0.j  0.12903226+0.j  0.29032258+0.j  0.19354839+0.j]


The PageRank vector has been normalised using the $l_{1}$ norm such the the entries sum to one.


## Approximation of the PageRank vector via matrix multiplication

The direct computation of all eigenvalues and eigenvectors is an expensive operation, and can only be reasonably performed for small matrices. However, we are interested only in the eigenvector corresponding to the largest eigenvalue. Recall that, in almost all cases, the repeated multiplication of a vector by a matrix $\boldsymbol{A}$ will yield a vector that tends to the direction of the eigenvector corresponding to the largest eigenvalue. We can use this to approximate the PageRank vector using only matrix-vector multiplication:


```
# Create random starting vector
x0 = np.random.rand(A.shape[0])

# Perform 5 iterations
for i in range(5):
    x0 = A.dot(x0)
x0 = x0/np.linalg.norm(x0 ,1)
print("Estimated PageRank after 5 iterations: {}".format(x0))

# Perform another 5 iterations
for i in range(5):
    x0 = A.dot(x0)
x0 = x0/np.linalg.norm(x0 ,1)
print("Estimated PageRank after 10 iterations: {}".format(x0))

```

    Estimated PageRank after 5 iterations: [ 0.41444044  0.12356961  0.2825718   0.17941816]
    Estimated PageRank after 10 iterations: [ 0.38821763  0.12815233  0.29052499  0.19310505]


It is clear that the approximate solution is very close to the exact solution with relatively few iterations. The major advantage of this method is that it is computationally inexpensive, which makes it tractable for very large matrices.

d068dc6b66ae9a05ac18ff396426a495a5608ffd
ipynb
Jupyter Notebook
notebooks/pagerank-simple.ipynb
quang-ha/IA-maths-Ipython
8ff8533d64a3d8db8e4813a7b6dfee39339fd846
BSD-3-Clause
notebooks/pagerank-simple.ipynb
quang-ha/IA-maths-Ipython
8ff8533d64a3d8db8e4813a7b6dfee39339fd846
BSD-3-Clause
notebooks/pagerank-simple.ipynb
quang-ha/IA-maths-Ipython
8ff8533d64a3d8db8e4813a7b6dfee39339fd846
BSD-3-Clause
Qwen/Qwen-72B
1. YES
2. YES