PageRank

PageRank is fundamentally a probabilistic model simulating a random surfer who clicks links indefinitely. The PageRank score represents the stationary probability that the surfer is on a specific page at any given time.

• The surfer starts on a random page and clicks a random outgoing link.
• This process repeats infinitely, creating a Markov chain.
• Pages with high PageRank are those the surfer visits most frequently.
• The model transforms the web's directed graph into a stochastic matrix.

A critical parameter, typically denoted as d and set to 0.85, that prevents the random surfer from getting trapped in spider traps (pages with no outgoing links or cycles).

• With probability d, the surfer follows a link on the current page.
• With probability (1-d), the surfer teleports to a completely random page.
• This teleportation vector ensures the Markov chain is irreducible and aperiodic, guaranteeing convergence.
• Without it, PageRank scores could become concentrated in sink nodes.

Not all links are equal. A link from a high-PageRank page is a more significant vote of confidence than a link from a low-PageRank page.

• The PageRank of a page is divided equally among its outgoing links.
• A link from a page with PR=10 and 5 outlinks passes a value of 2.
• A link from a page with PR=1 and 2 outlinks passes a value of 0.5.
• This recursive definition means authority begets authority in a virtuous cycle.

PageRank is computed using the power iteration method, an iterative algorithm that repeatedly refines the score vector until it converges to a stable distribution.

• Initialize all pages with an equal PageRank score (e.g., 1/N).
• In each iteration, update every page's score based on the sum of incoming link contributions.
• Continue until the change between iterations falls below a small epsilon threshold.
• For the web-scale graph, this requires distributed computing frameworks like MapReduce.

An evolution of the original algorithm that computes multiple, biased PageRank vectors to provide contextual authority rather than a single global score.

• Instead of teleporting uniformly, the surfer teleports to a predefined set of topically relevant pages.
• A separate PageRank vector is pre-computed for each topic category (e.g., sports, science).
• At query time, the user's query is classified, and the corresponding topic-specific score is used.
• This mitigates the problem where a globally authoritative page on 'cars' ranks for a query about 'car seats'.

A further refinement where the teleportation vector is biased toward a specific user's preferences or a seed set of trusted pages, creating a personalized authority measure.

• The teleportation set can be a user's bookmarks or browsing history.
• TrustRank is a variant where the seed set consists of manually vetted, high-quality pages to combat web spam.
• Personalized PageRank is computationally expensive at scale and often approximated using hub-based decomposition.
• It forms the conceptual basis for modern graph neural network propagation schemes.

A graph-based ranking algorithm that adapts PageRank for natural language processing. Instead of web pages, TextRank builds a graph where vertices represent sentences or keywords, and edges represent lexical co-occurrence or semantic similarity. The algorithm iteratively scores each vertex based on the number and weight of its connections, converging on the most salient textual units. It is widely used for extractive summarization and keyphrase extraction without requiring labeled training data.

A link analysis algorithm developed by Jon Kleinberg that runs concurrently with PageRank's early development. HITS assigns two scores to each page: authority (a measure of content quality based on inbound links) and hub (a measure of outbound link curation quality). The algorithm operates on a focused subgraph generated from search query results, making it query-dependent, unlike PageRank's global, query-independent prestige score.

The probabilistic interpretation of PageRank where a hypothetical user either clicks a random link on the current page (with probability d, the damping factor) or teleports to a random page (with probability 1-d). This model solves the rank sink problem—where pages in a loop trap all the rank—and ensures the Markov chain is irreducible and aperiodic, guaranteeing convergence to a unique stationary distribution. The typical damping factor is 0.85.

A variant that biases the random surfer's teleportation vector toward a user-specific set of preferred pages rather than a uniform distribution. This computes importance relative to a particular perspective, enabling applications like recommendation systems (e.g., recommending items similar to a user's purchase history) and local graph clustering. The algorithm is foundational to Google's original personalized search efforts.

A measure of node influence in a network where a node's score is proportional to the sum of its neighbors' scores. PageRank is a variant of eigenvector centrality applied to directed graphs with the addition of the damping factor for convergence guarantees. In an undirected, connected graph without teleportation, PageRank reduces to standard eigenvector centrality. Both compute the principal eigenvector of the adjacency matrix.

A semi-automatic technique for combating web spam that uses PageRank propagation from a manually curated set of seed pages known to be trustworthy. Trust is attenuated as it flows outward through the link graph, with spam pages typically receiving little to no trust because they are rarely linked from reputable sources. This method helps search engines penalize link farms and other manipulative structures.