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):
    """
    :type   adjacency: Dict{node,Set{node}}
    :rtype  G: List[List[float]]
    """

    G = [[0]*len(adjacency) for i in range(len(adjacency))]

    for node in adjacency:
        if len(adjacency[node]) > 0:
            weight = 1 / len(adjacency[node])
            for neighbour in adjacency[node]:
                G[node.num][neighbour.num] = weight*alpha + (1-alpha)/len(adjacency)
        else: # dangling node
            G[node.num][0:] = [(1/len(adjacency))*alpha + (1-alpha)/len(adjacency)] * len(G[node.num])
    return G
This entry was posted in TechNotes and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s