**Personalized PageRank (PPR)** replaces the uniform teleport vector in PageRank with a **preference vector** $$\mathbf{v}$$ concentrated on a chosen seed set, so the stationary mass measures proximity to those seeds rather than global importance:

$$\mathbf{r} = d\, P^{\top} \mathbf{r} + (1-d)\, \mathbf{v}.$$

Jeh and Widom (2003) showed that PPR is linear in $$\mathbf{v}$$ and can be decomposed and scaled efficiently; Haveliwala (2002) used topic-biased $$\mathbf{v}$$ vectors for topic-sensitive search. **Local PageRank** (Andersen, Chung, and Lang, 2006) computes an $$\varepsilon$$-approximate personalized PageRank vector with an **approximate push** algorithm whose runtime depends on the support of the output rather than on the total graph size, making PPR practical on large graphs. All three variants share a defining property: scores are **stationary distributions of damped random walks**, so a node's value reflects the **summed mass across all reaching paths**, with longer paths damped multiplicatively by $$d$$.

Personalized / Local PageRank Propagation

**Topic-Sensitive PageRank**, introduced by Haveliwala (WWW 2002; extended in IEEE TKDE 2003), is a *seeded* variant of PageRank in which the uniform teleport distribution $$v$$ is replaced by a *topic-biased* distribution $$v_T$$ that puts mass only on a chosen seed set of pages representative of a topic $$T$$. For each topic in a fixed set of representative topics (e.g., ODP top-level categories), a biased PageRank vector

$$r_T = (1 - \alpha)\, M\, r_T + \alpha\, v_T$$

is precomputed. At query time, the query's topic distribution is estimated, and the corresponding biased PageRank vectors are mixed to produce a *query-sensitive* importance score. The method is the canonical seeded/personalized PageRank construction: graph diffusion from a *seed set* through the link structure, with the seed encoded in the teleport vector. It is the propagation primitive that dense-seeded local diffusion retrieval methods generalize, replacing stationary random-walk scores with alternative aggregation rules over reaching paths.

Topic-Sensitive PageRank (Haveliwala, 2002)

**Local Graph Partitioning using PageRank Vectors** (Andersen, Chung, and Lang, FOCS 2006) is a local clustering algorithm based on **approximate personalized PageRank (APPR)**. Starting from a single seed vertex $$v$$, the method computes a sparse approximation of the personalized PageRank vector with teleport distribution concentrated on $$v$$ using an incremental **push** operation, and then performs a **sweep** over vertices ordered by approximate PageRank score divided by degree to extract a low-conductance cut. Two key properties make the procedure *local*. First, the push computation touches only vertices in (or near) the eventual cluster, so its running time is bounded essentially in terms of the cluster size rather than the size of the whole graph. Second, the algorithm offers a Cheeger-style conductance guarantee: if a set $$S$$ of low conductance contains the seed, a sweep over the APPR vector recovers a set with conductance $$O(\sqrt{\phi(S) \log |S|})$$. The construction is the canonical **seeded** PageRank-style diffusion used to identify local cluster structure without globally analyzing the graph.

Local Graph Partitioning using PageRank Vectors (Andersen, Chung, Lang, 2006)

**PageRank-style propagation** is a family of graph scoring rules in which node importance is defined as the **stationary distribution of a random walk** on the graph that, at each step, either follows an outgoing edge with probability $$1-\alpha$$ or **teleports** to a seed distribution with probability $$\alpha$$ (the damping/restart term). The original PageRank (Brin & Page, 1998) uses a uniform teleport over all nodes, while **personalized PageRank** (Jeh & Widom, 2003) and **topic-sensitive PageRank** (Haveliwala, 2002) replace the teleport with a seed-specific distribution, so the stationary score concentrates near the seeds. **Local/approximate personalized PageRank** (Andersen, Chung & Lang, 2006) computes the same seed-localized stationary scores efficiently via push-style updates without touching the whole graph. The common structural feature across all variants is that a node's score is an **aggregate over infinitely many walks** weighted by damping, rather than a function of any single shortest or best path.

PageRank-Style Propagation on Graphs

**PageRank** is a link-analysis algorithm for assigning a global authority score to each node in a directed graph. It models a random surfer who follows an outgoing link with probability $$ 1 - \alpha $$ and teleports according to a distribution $$ v $$ with probability $$ \alpha $$. The PageRank vector $$ r $$ is the stationary distribution of that walk and satisfies $$ r = (1 - \alpha) M r + \alpha v $$, where $$ M $$ is the graph transition matrix. Higher PageRank means more stationary random-walk mass reaches the node, making the score useful for search ranking before query-specific personalization is added.

Claude

Google

In information retrieval, search ranking is a task that involves imposing a rank on a set of items. Instead of simply determining if an item is relevant to a user's query, the objective is to assign a score to each relevant candidate and display the top-rated elements most prominently, utilizing machine learning and behavioral models to obtain query-dependent relevance scores.

Search Ranking

Dive into Deep Learning

Root URL: https://doi.org/
Source URL: https://doi.org/10.1016/S0169-7552(98)00110-X
Publication title: The Anatomy of a Large-Scale Hypertextual Web Search Engine
Authors: Sergey Brin, Lawrence Page
Year: 1998
DOI: 10.1016/S0169-7552(98)00110-X
Publisher: Computer Networks and ISDN Systems (Elsevier) / WWW7
Researcher-agent use: Supports missing prerequisite "Personalized / Local PageRank Propagation" for the Researcher agent.

This Reference node represents a publication or authoritative source used by the Researcher agent to create prerequisite knowledge before citing paper-derived nodes.

Learn Before

Related

Learn After