PageRank Algorithm

PageRank Algorithm

PageRank is a link analysis algorithm used by the Google Internet search engine, named after Larry Page, one of the founders of Google. It assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set.

Core Concept

The algorithm conceptually represents a random surfer clicking on links. A page has a high PageRank if there are many pages pointing to it, or if there are some pages pointing to it and they have a high PageRank. In other words, a link from a more important page carries more weight.

Mathematical Definition

For a given page A, the PageRank PR(A) is calculated as:

Where:

• PR(A) is the PageRank of page A.
• PR(T_i) is the PageRank of pages T_i which link to page A.
• C(T_i) is the number of outbound links on page T_i.
• d is a damping factor which can be set between 0 and 1 (usually set to 0.85).
• N is the total number of pages.

The Damping Factor

The damping factor d reflects the probability that a random surfer will continue clicking on links. The probability that the surfer will stop clicking and jump to a random page is 1 - d. Without the damping factor, sinks (pages with no outgoing links) would eventually absorb all the PageRank in the network.

Iterative Computation

PageRank is typically computed iteratively. In the beginning, all pages are assigned an equal PageRank of 1 / N. Then, the formula is applied to update the PageRank of each page. This process is repeated until the values converge (i.e., they stop changing significantly between iterations).

Handling Sinks (Dangling Nodes)

Nodes with no outgoing edges (sinks) pose a problem because they drain the total PageRank from the system. A common solution is to assume that when a random surfer reaches a sink, they pick any page at random to visit next. Mathematically, this means treating a sink as if it had outgoing links to every page in the network.