## A Simple Gotha on PageRank

Below is given the graph of the Internet one milisecond after the Big Bang. Construct the corresponding Google matrix with α = 7/8.

$Figure\ 1:\ The\ Internet\ 1ms\ after\ the\ Big\ Bang$

## $Solution:$

With equation

$g(i,j) = \left\{ \frac{1}{\#(P_i)} \space if \space P_i \rightarrow P_j \atop 0 \space \text{otherwise} \right.$

we can obtain the topology matrix $G_1$:

$G_1 = \begin{matrix} 0 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 1/4 \\ 1/4 & 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 \\ 0 & 1/3 & 0 & 1/3 & 0 & 0 & 1/3 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/3 & 0 & 1/3 & 0 & 0 & 0 & 1/3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/3 & 0 & 1/3 & 0 & 1/3 & 0 & 0 & 0 \end{matrix}$

we found that it has dangling node, so we need to eliminate it by make it connects to every node, thus $G_1 + \frac{1}{M}\mathbf{d}e^{T}$. In addition, a random walk with $\alpha = 7/8$ should also be taken into consideration, as a result, we would have the Google matrix equation:

$7/8\left( G_1 + \frac{1}{M}\mathbf{de^{T}} \right) + \frac{1 - 7/8}{M}\mathbf{ee^T}$

Finally, the Google matrix is calculated to be:

$G = \begin{matrix} 1/64 & 15/64 & 15/64 & 15/64 & 1/64 & 1/64 & 1/64 & 15/64 \\ 15/64 & 1/64 & 15/64 & 1/64 & 15/64 & 1/64 & 15/64 & 1/64 \\ 1/64 & 59/192 & 1/64 & 59/192 & 1/64 & 1/64 & 59/192 & 1/64 \\ 1/64 & 1/64 & 1/64 & 1/64 & 29/64 & 29/64 & 1/64 & 1/64 \\ 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 \\ 59/192 & 1/64 & 59/192 & 1/64 & 1/64 & 1/64 & 59/192 & 1/64 \\ 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 & 1/8 \\ 59/192 & 1/64 & 59/192 & 1/64 & 59/192 & 1/64 & 1/64 & 1/64 \end{matrix}$

In case there is any ambiguity, python style pseudo code is provided.

def constructGoogleMatrix(adjacency, alpha):
"""
:rtype  G: List[List[float]]
"""