Understanding Google PageRank from Scratch Using Python

The PageRank score represents the relative importance of a webpage within a network.

The score of a webpage is based on:

• the number of webpages that link to it;
• the importance of the webpages that link to it;
• the number of outgoing links from those webpages.

Suppose there are three webpages: A, B, and C.

• Page A links to pages B and C.
• Page B links to page C.
• Page C links to page A.

A → B
A → C
B → C
C → A

These links can be represented using a Python dictionary:

links = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": ["A"]
}

The link matrix stores the probability of moving from one webpage to another.

If page A has two outgoing links, each link receives probability:

$$\frac{1}{2}$$

For this example, the link matrix is:

$$H=\left[\begin{array}{ccc}0& 0& 1\\ \frac{1}{2}& 0& 0\\ \frac{1}{2}& 1& 0\end{array}\right]$$

Each column represents the webpage we are leaving. Each row represents the webpage we are moving to.

for curr_page, linked_pages in links.items():
    total_links = len(linked_pages)
    source_index = page_index[curr_page]

    for linked_page in linked_pages:
        linked_index = page_index[linked_page]
        link_matrix[linked_index, source_index] = 1 / total_links

A user usually follows a link on the current webpage, but sometimes jumps to a random webpage.

This random jump prevents the user from becoming trapped within a small group of webpages.

The Google matrix combines these two behaviours:

$$G=dH+(1-d)J$$

where:

• $H$ is the link matrix;
• $J$ gives every webpage an equal probability;
• $d$ is the damping factor.

We use:

$$d=0.85$$

This means the user follows a link with probability 0.85 and randomly jumps with probability 0.15.

random_jump = np.ones(
    (total_pages, total_pages)
) / total_pages

google_matrix = (
    damping_factor * link_matrix
    + (1 - damping_factor) * random_jump
)

We begin by giving every webpage the same initial rank:

curr_rank = np.ones(total_pages) / total_pages

We repeatedly update the rank vector using:

$$r_{k+1}=G{r}_k$$

new_rank = google_matrix @ curr_rank

We stop when the difference between two consecutive rank vectors becomes very small:

error = np.sum(np.abs(new_rank - curr_rank))

if error < epsilon:
    break

Page C has the highest score following with A and B.

PageRank can be summarised as:

Web links → Link matrix → Google matrix → PageRank scores