Topic-Sensitive PageRank

In 1998 Larry Page and Sergey Brin described the PageRank algorithm: model a random surfer who follows links at random and occasionally teleports to any page on the web. The fraction of time the surfer spends on a page is its rank — popular pages that are linked from other popular pages naturally collect more visits.

The idea is elegant, but it treats every surfer as identical. A page about competitive chess strategy ranks the same whether the person searching is a grandmaster or a ten-year-old looking for the rules. The algorithm knows nothing about intent.

In 2002 Taher Haveliwala published Topic-Sensitive PageRank at the ACM World Wide Web conference. His insight was small but powerful: instead of teleporting uniformly to any page, bias the random walk so the surfer preferentially returns to pages inside a topic set — a curated collection of pages on a specific subject. The same link graph now yields a different vector of scores for each topic, and any query can be ranked by a weighted blend of those vectors based on the query's topic distribution.

The result is a family of rankings — one per topic — that can be combined at query time to personalize results without recomputing PageRank for every user.

The graph below has eight pages connected by links. Every page also belongs to one or two topics (Science, Tech, Sports). Choose a topic using the buttons, and the algorithm runs power iteration with the teleport distribution biased toward that topic's seed pages. Bar heights show the resulting rank scores.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="topic-btns" id="topicBtns">
  <button data-topic="science" class="topic-btn active">{{btn_science}}</button>
  <button data-topic="tech" class="topic-btn">{{btn_tech}}</button>
  <button data-topic="sports" class="topic-btn">{{btn_sports}}</button>
  <button data-topic="global" class="topic-btn ghost">{{btn_global}}</button>
</div>
<div id="graphArea" class="graph-area"></div>
<div class="status" id="status"></div>
<div class="legend">
  <span class="dot science"></span>{{legend_science}}
  <span class="dot tech"></span>{{legend_tech}}
  <span class="dot sports"></span>{{legend_sports}}
</div>

/* {{c_style}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.topic-btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .7rem; }
.topic-btn { font: 600 13px system-ui; padding: .35rem .75rem; border: 1.5px solid #1d3557;
             background: #1d3557; color: #fff; border-radius: 20px; cursor: pointer; transition: all .15s; }
.topic-btn.ghost { background: #fff; color: #1d3557; }
.topic-btn.active { background: #e63946; border-color: #e63946; color: #fff; }
.graph-area { width: 100%; max-width: 560px; position: relative; height: 320px; margin: .3rem 0; }
svg.graph { width: 100%; height: 100%; overflow: visible; }
.node-circle { stroke-width: 2; cursor: default; }
.node-label { font: 600 11px system-ui; fill: #fff; pointer-events: none; text-anchor: middle; dominant-baseline: central; }
.bar-wrap { position: absolute; bottom: 0; left: 0; right: 0; display: flex; align-items: flex-end;
            justify-content: space-around; height: 80px; padding: 0 4px; }
.bar { flex: 1; margin: 0 2px; border-radius: 4px 4px 0 0; transition: height .4s ease; min-height: 2px; }
.bar-lbl { position: absolute; bottom: -18px; width: 100%; text-align: center; font: 600 9px system-ui; color: #555; }
.status { font-size: .85rem; font-weight: 600; min-height: 1.3em; margin: .3rem 0 .1rem; color: #0a7d33; }
.legend { font-size: .8rem; color: #555; display: flex; gap: .8rem; align-items: center; margin-top: 2px; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; margin-right: 3px; }
.dot.science { background: #2a7de1; }
.dot.tech    { background: #6a3d9a; }
.dot.sports  { background: #e69500; }
.edge { stroke: #bbb; stroke-width: 1.4; fill: none; marker-end: url(#arrow); }

// Code not found

Notice that the same links produce very different authority distributions. A page that is deeply embedded in the Science cluster rises when you bias toward Science, even if it has fewer in-links overall. This is the core insight of Haveliwala (2002): a biased teleport turns a global rank into a topic-aware rank.

Classic PageRank solves the eigenvector equation $\mathbf{r} = d \cdot M \mathbf{r} + (1-d) \cdot \mathbf{u}$, where $M$ is the column-stochastic link matrix, $d \approx 0.85$ is the damping factor, and $\mathbf{u}$ is the uniform teleport vector — every page equally likely.

Topic-Sensitive PageRank replaces $\mathbf{u}$ with a biased teleport vector $\mathbf{u}_t$ that concentrates probability on the seed pages of topic $t$:

$$\mathbf{r}_t = d \cdot M \mathbf{r}_t + (1-d) \cdot \mathbf{u}_t$$

Each topic $t$ has its own seed set $S_t$ (pages strongly associated with that topic), so $\mathbf{u}_t[i] = 1/|S_t|$ if page $i \in S_t$ and $0$ otherwise.

Precomputation. Haveliwala used the 16 top-level categories of the Open Directory Project (ODP) as topics. Offline, power iteration runs 16 times — once per topic — until the rank vector converges (typically 50–100 iterations). Each iteration costs $O(|E|)$ where $|E|$ is the number of links. The result is 16 vectors of $n$ scores, stored on disk.

Query time. Given a query $q$, estimate how much $q$ belongs to each topic — call it $\lambda_t(q)$. The personalized score for page $i$ is simply $\sum_t \lambda_t(q) \cdot r_t[i]$, computed in $O(k)$ per page, where $k = 16$.

Why it scales. The expensive eigenvector computation happens entirely offline. Serving a ranked list at query time is a cheap dot product. Adding more topics costs one extra offline pass each — nothing touches the online path.

Compared to vanilla PageRank, the added cost is exactly $k-1$ extra power-iteration runs — a fixed multiplier, not a function of the number of users or queries.

Biasing the random walk with a topic vector is a general technique that appears far beyond web search:

• Personalized web search: Google's early personalization research built directly on Haveliwala's work, computing per-user teleport distributions from browsing history.
• Academic citation ranking: tools like Semantic Scholar weight citation authority toward a researcher's own field, so a chemistry paper is compared against chemistry norms, not physics or law.
• Social network influence: given a seed set of domain experts, a biased random walk on the follower graph identifies the most authoritative accounts in that domain — the same math, a different graph.
• Recommendation systems: biased PageRank on a user–item graph (users linked to items they liked) surfaces items popular among similar users, without explicit user clustering.
• Anti-spam detection: spam farms typically lack strong topical coherence. Comparing a page's topic-sensitive rank to its global rank reveals anomalies a uniform score misses.

The deeper principle — that authority is context-dependent and a biased random walk captures that context — connects topic-sensitive PageRank to spectral graph theory and to the random walk literature at large.

Topic-Sensitive PageRank shows how a tiny algorithmic change — swapping the uniform teleport for a topic-concentrated one — unlocks a qualitatively richer notion of authority. The same web, the same links, but now the score of a page depends on what the asker cares about.

Haveliwala's 2002 paper precomputed 16 rank vectors offline and blended them at query time with no extra crawl or matrix factorization. That architecture — expensive eigenvector work done once, cheap personalization done per query — became a blueprint for scalable personalization across search, recommendation, and social ranking systems.

The random surfer, it turns out, becomes far more useful once it knows where it would rather spend its time.